Systems of linear equations: Gauss and Gauss-Jordan elimination

The first week of the linear algebra course is the toolbox for the rest of the semester. Inverse matrix, determinant, rank, null space, eigenvector: all of them end up at the step “solve a system with row operations”. The biggest block of points on the midterm comes from here too: solve a 3×3 system with Gauss, write the general solution of a system with Gauss-Jordan, solve a “for which $k$” question case by case.

Golden rules:

1. Write every row operation above the arrow ($R_2 \leftarrow R_2 - 2R_1$). It gives both partial credit and error checking.
2. A row operation is applied to the whole row, including the right-hand side column.
3. One column at a time: first clear below the pivot, then move right.
4. A row $[0\ 0\ 0 \mid c]$ with $c \neq 0$ means no solution. A row $[0\ 0\ 0 \mid 0]$ is harmless.
5. Substitute your solution back into the equations. It takes 20 seconds and saves points.

Linear equations and systems

A linear equation in the variables $x_1, \dots, x_n$ has the form:

$a_1x_1 + a_2x_2 + \dots + a_nx_n = b.$

The variables appear only to the first power, are not multiplied by each other, and do not appear inside roots, sines or exponentials. $3x - 2y + z = 5$ is linear; $xy = 2$, $x^2 + y = 1$, $\sqrt{x} + y = 3$ are not linear.

Several linear equations form a system of linear equations. A solution is a list of numbers that satisfies all the equations at the same time. For the solution set of a linear system there are only three possibilities:

There is no such thing as “exactly two solutions”. If there are two solutions, every point on the line between them is also a solution.

Augmented matrix and row operations

When writing a system, repeating the variable names in every row is unnecessary. We put the coefficients and the right-hand side into a table. The coefficients give the coefficient matrix $A$, and adding the right-hand side gives the augmented matrix $[A \mid \mathbf{b}]$:

$\begin{aligned} x + 2y - z &= 3 \\ 2x + 5y + z &= 14 \\ -x + y + 4z &= 9 \end{aligned} \quad\longrightarrow\quad \left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 14 \\ -1 & 1 & 4 & 9 \end{array}\right]$

If a variable is missing from an equation, write 0 in its place. Skipping this step shifts the columns and ruins the whole calculation.

The elementary row operations are the three operations that do not change the solution set:

Two matrices that can be turned into each other with these three operations are called row equivalent. The systems of row equivalent augmented matrices have the same solution set. The whole method rests on this.

REF and RREF

A matrix is in row echelon form (REF) if:

1. Rows that are entirely zero are at the bottom.
2. The first nonzero entry of every nonzero row (the leading entry, the pivot) is 1.
3. Each pivot is to the right of the pivot in the row above it (a staircase shape).

If, in addition, all entries in each pivot column other than the pivot are 0, the matrix is in reduced row echelon form (RREF).

$\underbrace{\begin{bmatrix} 1 & 3 & -2 & 4 \\ 0 & 1 & 5 & 1 \\ 0 & 0 & 1 & 2 \end{bmatrix}}_{\text{REF}} \qquad \underbrace{\begin{bmatrix} 1 & 0 & 0 & 35 \\ 0 & 1 & 0 & -9 \\ 0 & 0 & 1 & 2 \end{bmatrix}}_{\text{RREF}}$

The matrix on the right is the one on the left with the entries above the pivots also cleared by Gauss-Jordan. A matrix can have many REFs, but its RREF is unique. Some books do not require the pivot to be 1 in the definition of REF; in this course (in line with the problem book) we make the pivot 1.

TIP · pivot column and free variable. In the RREF, the variables of the columns that contain a pivot are the leading variables. The variables of the columns without a pivot are the free variables. You give the free variables a parameter ($t$, $s$) and write the leading variables in terms of them.

Gaussian elimination: a unique solution

Gaussian elimination: bring the augmented matrix to REF, then start from the bottom and do back-substitution. Let us solve the system above.

$\left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 14 \\ -1 & 1 & 4 & 9 \end{array}\right] \xrightarrow[R_3 \leftarrow R_3 + R_1]{R_2 \leftarrow R_2 - 2R_1} \left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 8 \\ 0 & 3 & 3 & 12 \end{array}\right]$

Column 1 is done. The pivot of row 2 is already 1. Clear below it:

$\xrightarrow{R_3 \leftarrow R_3 - 3R_2} \left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 8 \\ 0 & 0 & -6 & -12 \end{array}\right] \xrightarrow{R_3 \leftarrow -\frac16 R_3} \left[\begin{array}{ccc|c} 1 & 2 & -1 & 3 \\ 0 & 1 & 3 & 8 \\ 0 & 0 & 1 & 2 \end{array}\right]$

side work:  R2 - 2R1 = (2-2, 5-4, 1+2 | 14-6) = (0, 1, 3 | 8)
            R3 + R1  = (0, 3, 3 | 12)
            R3 - 3R2 = (0, 3-3, 3-9 | 12-24) = (0, 0, -6 | -12)
back-sub:   z = 2
            y + 3z = 8      → y = 2
            x + 2y - z = 3  → x = 3 - 4 + 2 = 1

The solution is $(x, y, z) = (1, 2, 2)$. Check (3rd equation): $-1 + 2 + 8 = 9$.

Gauss-Jordan: infinitely many solutions and parametric form

Gauss-Jordan elimination does not stop at REF: it also clears the entries above the pivots and reaches the RREF. The advantage: you read the solution directly, with no back-substitution. Look at this system with four variables:

$\begin{aligned} x_1 + 2x_2 - x_3 + x_4 &= 3 \\ 2x_1 + 4x_2 + x_3 + 5x_4 &= 12 \\ x_1 + 2x_2 + 2x_3 + 4x_4 &= 9 \end{aligned}$

$\left[\begin{array}{cccc|c} 1 & 2 & -1 & 1 & 3 \\ 2 & 4 & 1 & 5 & 12 \\ 1 & 2 & 2 & 4 & 9 \end{array}\right] \xrightarrow[R_3 \leftarrow R_3 - R_1]{R_2 \leftarrow R_2 - 2R_1} \left[\begin{array}{cccc|c} 1 & 2 & -1 & 1 & 3 \\ 0 & 0 & 3 & 3 & 6 \\ 0 & 0 & 3 & 3 & 6 \end{array}\right]$

In column 2 there is no nonzero entry in row 2 or below, so column 2 has no pivot. Move to column 3:

$\xrightarrow{R_2 \leftarrow \frac13 R_2} \left[\begin{array}{cccc|c} 1 & 2 & -1 & 1 & 3 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 3 & 3 & 6 \end{array}\right] \xrightarrow{R_3 \leftarrow R_3 - 3R_2} \left[\begin{array}{cccc|c} 1 & 2 & -1 & 1 & 3 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right] \xrightarrow{R_1 \leftarrow R_1 + R_2} \left[\begin{array}{cccc|c} 1 & 2 & 0 & 2 & 5 \\ 0 & 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right]$

The pivots are in columns 1 and 3. $x_2$ and $x_4$ are free: $x_2 = s$, $x_4 = t$.

$x_1 = 5 - 2s - 2t, \quad x_2 = s, \quad x_3 = 2 - t, \quad x_4 = t \qquad (s, t \in \mathbb{R}).$

In vector form: $\mathbf{x} = (5, 0, 2, 0) + s(-2, 1, 0, 0) + t(-2, 0, -1, 1)$. To check, take $s = 1$, $t = 2$: $(-1, 1, 0, 2)$. Equation 2: $-2 + 4 + 0 + 10 = 12$.

An inconsistent system

$\left[\begin{array}{ccc|c} 1 & 1 & -1 & 1 \\ 2 & 3 & 1 & 4 \\ 3 & 4 & 0 & 6 \end{array}\right] \xrightarrow[R_3 \leftarrow R_3 - 3R_1]{R_2 \leftarrow R_2 - 2R_1} \left[\begin{array}{ccc|c} 1 & 1 & -1 & 1 \\ 0 & 1 & 3 & 2 \\ 0 & 1 & 3 & 3 \end{array}\right] \xrightarrow{R_3 \leftarrow R_3 - R_2} \left[\begin{array}{ccc|c} 1 & 1 & -1 & 1 \\ 0 & 1 & 3 & 2 \\ 0 & 0 & 0 & 1 \end{array}\right]$

The last row says $0x + 0y + 0z = 1$. Impossible, the system is inconsistent. When you see this, stop; do not try to write a solution.

Decision table (after reducing to REF):

Systems with parameters: “for which $k$?”

Keep $k$ as a symbol and eliminate normally. The only forbidden thing is dividing by an expression containing $k$, because that expression can be zero.

$\begin{aligned} x + y - z &= 2 \\ 2x + 3y + z &= 5 \\ x + 2y + (k^2 + k)z &= k + 2 \end{aligned}$

$\left[\begin{array}{ccc|c} 1 & 1 & -1 & 2 \\ 2 & 3 & 1 & 5 \\ 1 & 2 & k^2+k & k+2 \end{array}\right] \xrightarrow[R_3 \leftarrow R_3 - R_1]{R_2 \leftarrow R_2 - 2R_1} \left[\begin{array}{ccc|c} 1 & 1 & -1 & 2 \\ 0 & 1 & 3 & 1 \\ 0 & 1 & k^2+k+1 & k \end{array}\right] \xrightarrow{R_3 \leftarrow R_3 - R_2} \left[\begin{array}{ccc|c} 1 & 1 & -1 & 2 \\ 0 & 1 & 3 & 1 \\ 0 & 0 & k^2+k-2 & k-1 \end{array}\right]$

The last row: $(k-1)(k+2)\,z = k - 1$. Factor and examine each root separately:

• $k = 1$: the last row is $[0\ 0\ 0 \mid 0]$. $z$ is free, infinitely many solutions: $z = t$, $y = 1 - 3t$, $x = 2 - y + z = 1 + 4t$.
• $k = -2$: the last row is $[0\ 0\ 0 \mid -3]$. No solution.
• $k \neq 1, -2$: unique solution. $z = \frac{1}{k+2}$, $y = 1 - 3z = \frac{k-1}{k+2}$, $x = 2 - y + z = \frac{k+6}{k+2}$.

PITFALL · simplifying and losing a root. In the equation $(k-1)(k+2)z = k-1$, if you immediately divide both sides by $k-1$ and write "$z = \frac{1}{k+2}$", you lose the case $k = 1$. First separate the roots, then divide.

Homogeneous systems

If the whole right-hand side is zero, the system is homogeneous: $A\mathbf{x} = \mathbf{0}$. A homogeneous system is always consistent, because $\mathbf{x} = \mathbf{0}$ (the trivial solution) always satisfies it. The question is whether there is any other (nontrivial) solution.

• If there is a free variable, there are infinitely many nontrivial solutions.
• If the number of unknowns is greater than the number of equations, there is necessarily a free variable.

In a homogeneous system the right-hand side column stays 0 through all the row operations; most people never write it and just reduce $A$.

PITFALL · “fewer equations, so infinitely many solutions”. This is true only for a consistent system. In the system $x + y + z = 0$, $x + y + z = 1$ there are 2 equations and 3 unknowns, yet there is no solution. For a homogeneous system, consistency comes for free, so the claim is true.

Common mistakes