Gaussian Elimination and Row Operations, linear algebra I lesson

Elimination solves a system by rewriting it, one step at a time, as a system that is easier to read. Each rewrite is only safe if the new system has exactly the same solutions as the old one, with nothing lost and nothing gained. Which changes have that property, and how should they be organized so that the answer can be read off at the end? This lesson answers both questions and ends every solution with a check against the original equations. Throughout, a tuple such as $(2, 1)$ stands for a column vector.

Key terms

Elementary row operations

Definition The elementary row operations on a matrix are the following three.

Interchange. Swap two rows, written $R_i \leftrightarrow R_j$ .
Scaling. Multiply one row by a nonzero number $c$ , written $R_i \to cR_i$ with $c \ne 0$ .
Row replacement. Add a multiple of one row to a different row, written $R_i \to R_i + cR_j$ with $i \ne j$ and $c$ any real number.

In a row replacement only row $i$ changes, and the source row $R_j$ stays as it was. On an augmented matrix each operation acts on entire rows, constants included. Each operation is undone by an operation of the same type. A swap is undone by the same swap, the scaling $R_i \to cR_i$ by $R_i \to \frac{1}{c}R_i$ , and the replacement $R_i \to R_i + cR_j$ by $R_i \to R_i - cR_j$ .

In plain words You may reorder the equations, multiply one equation by a nonzero number, or add a multiple of one equation to a different equation, leaving the equation whose multiple you added unchanged. These are moves that can always be taken back.

Example For the system $x + y = 3$ , $x - y = 1$ , the replacement $R_2 \to R_2 - R_1$ acts on the whole second row,

\left[\begin{array}{cc|c} 1 & 1 & 3 \\ 1 & -1 & 1 \end{array}\right] \to \left[\begin{array}{cc|c} 1 & 1 & 3 \\ 0 & -2 & -2 \end{array}\right].

The new second equation $-2y = -2$ describes a different line, but that line still passes through the solution $(2, 1)$ . Applying $R_2 \to R_2 + R_1$ to the result brings back the original second row. The scaling $R_2 \to -\frac{1}{2}R_2$ would instead turn the new row into the equation $y = 1$ .

Equivalent systems

Definition Two linear systems in the same unknowns are equivalent if they have the same solution set. Two matrices are row equivalent if one can be obtained from the other by a finite sequence of elementary row operations. If the augmented matrices of two systems are row equivalent, the two systems are equivalent. The reason is that each operation turns true equations into true equations, so every solution of the old system solves the new one, and the reverse operation shows that every solution of the new system solves the old one.

In plain words Row operations may change the individual equations and the lines or planes they describe, but never the set of points that satisfy all of the equations together.

Example The pair $x + y = 3$ , $x - y = 1$ and the pair $x + y = 3$ , $2x = 4$ are equivalent, since the second pair comes from the first by $R_2 \to R_2 + R_1$ . Both have the single solution $(2, 1)$ . Keeping only the sum $2x = 4$ is not a row operation, because it discards an equation, and indeed the point $(2, 0)$ satisfies $2x = 4$ but fails both $x + y = 3$ and $x - y = 1$ . Multiplying the second row by $0$ is not allowed either. It turns $x - y = 1$ into $0 = 0$ . After that, every row that further row operations produce is a multiple of the row of $x + y = 3$ , so the lost equation never comes back.

Elementary matrix

Definition An elementary matrix is a matrix obtained from an identity matrix $I_m$ by a single elementary row operation. If $E$ is obtained from $I_m$ by an operation and $A$ is any $m \times n$ matrix, then $EA$ is the result of applying the same operation to $A$ . For a system $A\mathbf{x} = \mathbf{b}$ the operation produces $EA\mathbf{x} = E\mathbf{b}$ , which amounts to $E[\,A \mid \mathbf{b}\,] = [\,EA \mid E\mathbf{b}\,]$ . Every elementary matrix is invertible, and its inverse is the elementary matrix of the reverse operation. If operations with elementary matrices $E_1, E_2, \dots, E_k$ are applied in that order, the result is $E_k \cdots E_2 E_1 A$ , with the first operation on the right.

In plain words A row operation is a multiplication on the left. Perform the operation once on the identity matrix, and the matrix you get performs it on any matrix with the same number of rows. Multiplying on the right would combine columns instead.

Example Applying $R_2 \to R_2 - 2R_1$ to $I_3$ gives $E$ , and the reverse operation $R_2 \to R_2 + 2R_1$ gives $E^{-1}$ ,

\begin{gathered} E = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \\[0.4em] E^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}. \end{gathered}

Multiplying them in either order gives $I_3$ . For a coefficient matrix $A$ ,

\begin{aligned} EA &= \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} 1 & 1 & 1 \\ 2 & 3 & 1 \\ 1 & 2 & 3 \end{bmatrix} \\[0.4em] &= \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & -1 \\ 1 & 2 & 3 \end{bmatrix}, \end{aligned}

which is $A$ with its second row replaced by row 2 minus twice row 1. The same $E$ sends the right-hand side $\mathbf{b} = (6, 11, 14)$ to $E\mathbf{b} = (6, -1, 14)$ .

Row echelon form

Definition The leading entry of a nonzero row is its leftmost nonzero entry. A matrix is in row echelon form if

every row of zeros lies below every nonzero row,
the leading entry of each nonzero row lies in a column strictly to the right of the leading entry of the row above it, and
every entry below a leading entry is zero.

The leading entries of a matrix in row echelon form are its pivots. They need not equal $1$ , and the entries above them need not be zero. A system is in echelon form when its augmented matrix is in row echelon form.

In plain words The nonzero entries form a staircase that steps down and to the right, with only zeros beneath it.

Example The augmented matrix

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

is in row echelon form, with pivots $1$ , $1$ and $3$ in the first three columns. By contrast, the matrix

\begin{bmatrix} 0 & 2 & 1 \\ 1 & 0 & 4 \end{bmatrix}

is not, because the leading entry of its second row lies to the left of the leading entry of the first. Swapping the two rows repairs this.

Gaussian elimination

Definition Gaussian elimination solves a linear system in two stages. The forward stage reduces the augmented matrix to row echelon form, one column at a time.

Find the leftmost column that has a nonzero entry in the rows not yet used.
If the top unused row has a zero in that column, swap it with a lower row that has a nonzero entry there. The entry of the top unused row in that column is now nonzero, and it is the pivot.
Use row replacements to make every entry below the pivot zero.
Leave the pivot row as it is and repeat steps 1 to 3 on the rows below it, until no rows remain or the remaining rows are all zero.

The backward stage solves the echelon system by back-substitution. If the echelon form has a row that stands for an equation $0 = c$ with $c \ne 0$ , the system has no solution and there is nothing to substitute. Every matrix can be reduced to row echelon form this way, and since only elementary row operations are used, the echelon system is equivalent to the original one.

In plain words Use the first equation to remove the first unknown from every equation below it, then use the next equation to remove the next unknown, and so on down the staircase. A zero where a pivot should go is no reason to give up. Swap in a lower row that has a nonzero entry in that column, and if no lower row has one, move on to the next column.

Example Solve $x + y + z = 6$ , $2x + 3y + z = 11$ , $x + 2y + 3z = 14$ . The replacements $R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 - R_1$ clear the first column, and $R_3 \to R_3 - R_2$ clears the entry below the second pivot,

\begin{aligned} &\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 2 & 3 & 1 & 11 \\ 1 & 2 & 3 & 14 \end{array}\right] \\[0.4em] \to\ &\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & -1 \\ 0 & 1 & 2 & 8 \end{array}\right] \\[0.4em] \to\ &\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & 3 & 9 \end{array}\right]. \end{aligned}

In the last step the new constant is $8 - (-1) = 9$ , a place where a sign error is easy to make. In matrix language the three steps multiply $[\,A \mid \mathbf{b}\,]$ on the left by $E_3 E_2 E_1$ , where $E_1$ , $E_2$ and $E_3$ are the elementary matrices of the three steps in the order they were applied.

Back-substitution

Definition Back-substitution solves a consistent system in echelon form from the bottom up. Solve the last nonzero equation for its pivot variable, substitute the result into the equation above, solve that equation for its pivot variable, and continue upward, each time substituting every value already found. When the system has $n$ equations in $n$ unknowns and its pivots $u_{11}, \dots, u_{nn}$ lie on the diagonal, the equation in row $i$ reads $u_{ii}x_i + u_{i,i+1}x_{i+1} + \cdots + u_{in}x_n = c_i$ , and

x_i = \frac{1}{u_{ii}}\Big(c_i - \sum_{j=i+1}^{n} u_{ij}x_j\Big)

for $i = n, n - 1, \dots, 1$ . Every pivot is nonzero, so each division is allowed and the solution is unique. If some unknowns have no pivot, the same upward pass expresses the pivot variables in terms of them.

In plain words The lowest nonzero equation starts farthest to the right, so it involves only the last unknowns. Start there and carry every value you find into each equation above it. The last column of the echelon matrix holds the constants of the echelon system, and in general these are not the values of the unknowns.

Example In the echelon system above, the last equation $3z = 9$ gives $z = 3$ . The second equation $y - z = -1$ then gives $y = 2$ , and the first equation $x + y + z = 6$ gives $x = 1$ . The solution is $(1, 2, 3)$ in the order $x, y, z$ . Check it in the original equations, not only in the echelon ones. Indeed $1 + 2 + 3 = 6$ , then $2 + 6 + 3 = 11$ , and $1 + 4 + 9 = 14$ .

Check yourself

Write the $3 \times 3$ elementary matrix for $R_3 \to R_3 + 4R_1$ and its inverse. Then do the same for the swap $R_1 \leftrightarrow R_2$ .

Show the answer

Apply each operation to $I_3$ . The replacement and its reverse $R_3 \to R_3 - 4R_1$ give

\begin{gathered} E = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 4 & 0 & 1 \end{bmatrix}, \\[0.4em] E^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -4 & 0 & 1 \end{bmatrix}. \end{gathered}

The swap gives the matrix below, and it is its own inverse, because swapping the same two rows twice restores every matrix,

P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} = P^{-1}.

To solve $x + y = 3$ , $2x + 3y = 8$ , a student applies $R_2 \to R_2 - 2R_1$ to the coefficients only and writes the new second equation as $y = 8$ . What goes wrong, and what is the correct solution?

Show the answer

A row replacement acts on the whole row, so the constant must change too, from $8$ to $8 - 2 \cdot 3 = 2$ . The correct new equation is $y = 2$ , and then $x + 2 = 3$ gives $x = 1$ . Check that $1 + 2 = 3$ and $2 + 6 = 8$ .

The student’s value $y = 8$ leads to $x = -5$ , and then $2(-5) + 3(8) = 14$ , not $8$ . Leaving the constant behind replaced the system by one that is not equivalent to it.

Solve the system $y - z = -3$ , $x + 2y + z = 3$ , $2x + 3y + 4z = 11$ by Gaussian elimination and back-substitution, and check your answer.

Show the answer

The first equation has no $x$ term, so the top entry of the first column is zero. Swap $R_1 \leftrightarrow R_2$ , then apply $R_3 \to R_3 - 2R_1$ and $R_3 \to R_3 + R_2$ ,

\begin{aligned} &\left[\begin{array}{ccc|c} 0 & 1 & -1 & -3 \\ 1 & 2 & 1 & 3 \\ 2 & 3 & 4 & 11 \end{array}\right] \\[0.4em] \to\ &\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 1 & -1 & -3 \\ 2 & 3 & 4 & 11 \end{array}\right] \\[0.4em] \to\ &\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 1 & -1 & -3 \\ 0 & -1 & 2 & 5 \end{array}\right] \\[0.4em] \to\ &\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 1 & -1 & -3 \\ 0 & 0 & 1 & 2 \end{array}\right]. \end{aligned}

Back-substitution gives $z = 2$ , then $y - 2 = -3$ so $y = -1$ , then $x - 2 + 2 = 3$ so $x = 3$ . The solution is $(3, -1, 2)$ . The swap reordered the equations, not the unknowns, so the entries stay in the order $x, y, z$ . In the original equations, $-1 - 2 = -3$ , then $3 - 2 + 2 = 3$ , and $6 - 3 + 8 = 11$ .

Gaussian Elimination and Row Operations

Key terms

Elementary row operations

Equivalent systems

Elementary matrix

Row echelon form

Gaussian elimination

Back-substitution

Check yourself

How this lesson connects

Builds on

Used later in