Gaussian elimination

Gaussian elimination is a systematic method for solving systems of linear equations by transforming them step by step into a simpler, equivalent system. In the context of linear algebra, it is usually performed on the augmented matrix of the system, using row operations.

In this chapter, we will focus on:

• What row operations are
• How to perform Gaussian elimination step by step
• How to recognize the different types of solutions from the row–reduced form
• How Gaussian elimination connects to concepts like rank and pivot variables (but without fully developing those separate topics)

Row operations

Gaussian elimination is based on three basic operations that transform a system into an equivalent one (i.e. with exactly the same solution set). When working with matrices, these are called elementary row operations:

1. Row swapping
   Interchange two rows:
   $$R_i \leftrightarrow R_j$$
2. Row scaling
   Multiply a row by a nonzero constant:
   $$R_i \leftarrow c R_i \quad (c \neq 0)$$
3. Row replacement (row addition)
   Add a multiple of one row to another:
   $$R_i \leftarrow R_i + c R_j$$

Here $R_i$ means “row $i$”. Only these transformations are allowed in Gaussian elimination.

Each of these operations corresponds to a legal change of the original system of equations that does not change its solution set.

The augmented matrix

Suppose you have a linear system written in standard form. For example, in three unknowns $x, y, z$:

$$
\begin{cases}
2x - y + 3z = 5 \\
4x + y - z = 1 \\
-2x + 3y + z = 4
\end{cases}
$$

We write the coefficient matrix and then append the right-hand side as one extra column to form the augmented matrix:

$$
\left[
\begin{array}{ccc|c}
2 & -1 & 3 & 5 \\
4 & 1 & -1 & 1 \\
-2 & 3 & 1 & 4
\end{array}
\right]
$$

Gaussian elimination is performed on this augmented matrix using the row operations above.

You should think of every row as representing one equation, and every column (before the vertical bar) as corresponding to a variable.

Goals of Gaussian elimination

The idea is to successively simplify the system until:

• The matrix looks “triangular” (zeros below the main diagonal): this is row echelon form.
• Then you can solve the system by back-substitution.

More advanced is reduced row echelon form (RREF), which is often obtained by a further process called Gauss–Jordan elimination. In this chapter, we focus on the original Gaussian elimination: getting to an echelon form and reading off solutions.

Row echelon form (REF)

A matrix is in row echelon form if:

1. All nonzero rows appear above any rows of all zeros.
2. In each nonzero row, the first nonzero entry (from the left) is called a leading entry or pivot. In rows below, the leading entry is to the right of the leading entry in the row above.
3. All entries below each leading entry are zero.

For example:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & -1 & 3 \\
0 & 1 & 4 & -2 \\
0 & 0 & 0 & 0
\end{array}
\right]
$$

is in row echelon form. There are leading 1’s in columns 1 and 2, and every entry below those leading entries is zero.

Gaussian elimination is exactly the process of using row operations to get to such a form.

Step-by-step Gaussian elimination (a worked example)

We illustrate the process on a system with three equations in three unknowns:

$$
\begin{cases}
x + 2y - z = 1 \\
2x + 3y + z = 4 \\
3x + 8y - 2z = 7
\end{cases}
$$

Write its augmented matrix:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & -1 & 1 \\
2 & 3 & 1 & 4 \\
3 & 8 & -2 & 7
\end{array}
\right]
$$

We eliminate variables below the pivot positions, moving from left to right.

Step 1: First pivot and eliminating below

The entry in the first row, first column (1) will be our first pivot. We want zeros below it in the first column.

• Make row 2: $R_2 \leftarrow R_2 - 2R_1$
• Make row 3: $R_3 \leftarrow R_3 - 3R_1$

Compute:

• Row 2: $[2, 3, 1 \mid 4] - 2[1, 2, -1 \mid 1] = [0, -1, 3 \mid 2]$
• Row 3: $[3, 8, -2 \mid 7] - 3[1, 2, -1 \mid 1] = [0, 2, 1 \mid 4]$

So we obtain:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & -1 & 1 \\
0 & -1 & 3 & 2 \\
0 & 2 & 1 & 4
\end{array}
\right]
$$

Now the first column below the pivot is all zeros.

Step 2: Second pivot and eliminating below

Move to the second column. We need a nonzero entry to serve as the pivot in row 2. Row 2 has $-1$ there, which is fine.

To make calculations easier, you can scale row 2 to make that pivot equal to 1:

• $R_2 \leftarrow -1 \cdot R_2$

Row 2 becomes $[0, 1, -3 \mid -2]$, giving:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & -1 & 1 \\
0 & 1 & -3 & -2 \\
0 & 2 & 1 & 4
\end{array}
\right]
$$

Now eliminate the entry below this pivot (the 2 in row 3, column 2):

• $R_3 \leftarrow R_3 - 2R_2$

Row 3: $[0, 2, 1 \mid 4] - 2[0, 1, -3 \mid -2] = [0, 0, 7 \mid 8]$.

So:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & -1 & 1 \\
0 & 1 & -3 & -2 \\
0 & 0 & 7 & 8
\end{array}
\right]
$$

Now the second column below the pivot is all zeros.

Step 3: Third pivot

Move to the third column. Row 3 has 7, which will be our pivot in that column. We usually scale it to 1 for convenience:

• $R_3 \leftarrow \frac{1}{7} R_3$

Row 3 becomes $[0, 0, 1 \mid 8/7]$:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & -1 & 1 \\
0 & 1 & -3 & -2 \\
0 & 0 & 1 & 8/7
\end{array}
\right]
$$

This matrix is in row echelon form: each pivot is to the right of the pivot above it, and entries below each pivot are zero.

Step 4: Back-substitution (reading off the solution)

Translating the last matrix back into equations:

• Third row: $z = \dfrac{8}{7}$.
• Second row: $y - 3z = -2$.
• First row: $x + 2y - z = 1$.

Substitute $z$ into the second row equation:

$$
y - 3\left(\frac{8}{7}\right) = -2
\quad\Rightarrow\quad
y - \frac{24}{7} = -2
$$

Since $-2 = -\dfrac{14}{7}$, we get

$$
y = -\frac{14}{7} + \frac{24}{7} = \frac{10}{7}.
$$

Now substitute $y$ and $z$ into the first equation:

$$
x + 2\left(\frac{10}{7}\right) - \frac{8}{7} = 1
\quad\Rightarrow\quad
x + \frac{20}{7} - \frac{8}{7} = 1
\quad\Rightarrow\quad
x + \frac{12}{7} = 1.
$$

Since $1 = \dfrac{7}{7}$,

$$
x = \frac{7}{7} - \frac{12}{7} = -\frac{5}{7}.
$$

So the unique solution is

$$
(x, y, z) = \left(-\frac{5}{7}, \frac{10}{7}, \frac{8}{7}\right).
$$

This entire solution process—forming the augmented matrix, using row operations to get an echelon form, and then back-substituting—is Gaussian elimination.

Gaussian elimination and types of solutions

Gaussian elimination can reveal whether:

• There is one unique solution.
• There are infinitely many solutions.
• There is no solution.

You detect these possibilities by the patterns appearing in the row echelon form of the augmented matrix.

Inconsistent system (no solution)

During elimination, you might obtain a row like

$$
[0\ \ 0\ \ 0 \mid c],
$$

where $c$ is nonzero. In equation form, this is

$$
0x + 0y + 0z = c,
$$

which simply says $0 = c$, an impossibility. This indicates no solution (the system is inconsistent).

Example of such an echelon form:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & -1 & 3 \\
0 & 1 & 4 & 5 \\
0 & 0 & 0 & 1
\end{array}
\right]
$$

The last row corresponds to $0 = 1$, so the system has no solution.

Infinitely many solutions (free variables)

You might end in a row echelon form where some columns (for variables) do not contain pivots, and no inconsistent row appears.

For example:

$$
\left[
\begin{array}{ccc|c}
1 & 2 & 0 & 3 \\
0 & 0 & 1 & -1 \\
0 & 0 & 0 & 0
\end{array}
\right]
$$

Suppose the variables are $x, y, z$. This matrix gives:

• First row: $x + 2y = 3$.
• Second row: $z = -1$.
• Third row: $0 = 0$ (always true, so it adds no restriction).

There is no equation directly solving for $y$, and the column of $y$ has no pivot. We then treat $y$ as a free variable. Choosing any value for $y$, we can compute $x$ and $z$:

• From first row: $x = 3 - 2y$.
• Second row: $z = -1$.

Thus there are infinitely many solutions, one for each value of $y$.

Gaussian elimination is how you systematically detect this structure.

General algorithm for Gaussian elimination

Here is a generic procedure for a system with $m$ equations and $n$ unknowns:

1. Form the augmented matrix of the system.
2. Forward elimination (creating echelon form):
• Start with column 1, then move to column 2, etc.
• In the current column:
• Find a row at or below the current row with a nonzero entry in this column.
• If necessary, swap it with the current row (row swapping).
• Optional but common: scale the row so that the pivot becomes 1.
• Use row replacement operations to make all entries below this pivot equal to 0.
• Move down to the next row and to the right to the next column, and repeat until:
• You run out of rows, or
• You run out of columns.
3. Check for inconsistency:
• If any row has all zeros in the coefficient part but a nonzero entry in the augmented column, the system has no solution.
4. Back-substitution (if the system is consistent):
• Starting from the last nonzero row, solve for the variable corresponding to its pivot.
• Move upward, substituting the already found values, until all pivot variables are found.
• Any variable that does not correspond to a pivot column becomes a free variable, which can take arbitrary values.

This is Gaussian elimination.

Reduced row echelon form vs. Gaussian elimination

Gaussian elimination stops at row echelon form and then relies on back-substitution.

If, after obtaining echelon form, you continue to use row operations to also make the entries above each pivot zero (and pivots equal to 1), you reach the reduced row echelon form (RREF). That extended procedure is often called Gauss–Jordan elimination and allows you to read solutions directly without back-substitution.

In this chapter we focus on the basic Gaussian version: zeros below the pivots and then back-substitution.

Gaussian elimination and matrix concepts

Although detailed study of these ideas is left to other chapters, it is useful to note briefly how Gaussian elimination connects to broader linear algebra concepts:

• The number of pivots you obtain tells you the rank of the coefficient matrix.
• If there is a pivot in every column corresponding to a variable, the system has at most one solution.
• If the number of pivots equals the number of variables and there is no inconsistency, the solution is unique.
• If there are fewer pivots than variables and no inconsistency, there are infinitely many solutions (with some free variables).

Gaussian elimination is therefore not just a computational technique; it is also a key tool for understanding the structure of linear systems.

Practical tips and common pitfalls

• Choose good pivots when possible. In hand computations, you may swap rows to bring a nicer number (like 1 or -1) into the pivot position, reducing fractions and arithmetic mistakes.
• Avoid dividing too early if it complicates numbers. Sometimes it is easier to keep an integer pivot like 2 and only scale later, rather than introducing fractions early.
• Keep track of row operations carefully. Write them out (for example, $R_3 \leftarrow R_3 - 2R_1$) so you can check your steps.
• Recognize zero rows and inconsistent rows early. They tell you immediately about the type of solution.

Gaussian elimination is a foundational algorithm in linear algebra, forming the backbone of many procedures for matrices and systems of equations. Once you are comfortable carrying it out by hand on small systems, you will be well prepared to understand more advanced topics and computer implementations.