How to Reduce a Linear System to Row Echelon Form

To reduce a system of linear equations to row echelon form I apply the standard operations of Gaussian elimination.

I add a multiple of one equation to another, provided the scalar is nonzero
I multiply an equation by a nonzero scalar
I swap the positions of two equations in the system

A worked example

Consider the linear system

$$ \begin{cases} x+y+z = 1 \\ x+z=1 \\ x+y=2 \end{cases} $$

I begin by writing its augmented matrix A|B, which includes the coefficients and the constant terms, alongside the coefficient matrix A.

$$ A|B= \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 2 \end{pmatrix} $$

$$ A= \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} $$

The matrix A is clearly not in row echelon form.

To obtain such a form, I perform Gaussian elimination on the augmented matrix A|B.

The first task is to clear the entries below the leading 1 in the first column. Two entries, highlighted in red, must be eliminated.

$$ A|B= \begin{pmatrix} 1 & 1 & 1 & 1 \\ \color{red}1 & 0 & 1 & 1 \\ \color{red}1 & 1 & 0 & 2 \end{pmatrix} $$

I replace the second row R2 with R2 minus R1.

$$ R2 = R2 + R1 \cdot (-1) $$

$$ A|B= \begin{pmatrix} 1 & 1 & 1 & 1 \\ \color{red}1-1 & 0-1 & 1-1 & 1-1 \\ \color{red}1 & 1 & 0 & 2 \end{pmatrix} $$

$$ A|B= \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & -1 & 0 & 0 \\ \color{red}1 & 1 & 0 & 2 \end{pmatrix} $$

Next I eliminate the corresponding entry in the third row by replacing R3 with R3 minus R1.

$$ R3 = R3 + R1 \cdot (-1) $$

$$ A|B= \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & -1 & 0 & 0 \\ \color{red}1-1 & 1-1 & 0-1 & 2-1 \end{pmatrix} $$

$$ A|B= \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 1 \end{pmatrix} $$

At this stage the coefficient matrix is already in row echelon form:

$$ A= \begin{pmatrix} 1 & 1 & 1 \\ 0 & -1 & 0 \\ 0 & 0 & -1 \end{pmatrix} $$

Note. Once the augmented matrix A|B has been reduced, the coefficient matrix A is obtained simply by removing the last column, which contains the constant terms B.

To determine the rank of each matrix, I count the number of pivot positions.

Since both A|B and A contain three pivots, their rank is r=3.

$$ r(A) = r(A|B)= 3 $$

By the Rouché - Capelli theorem the system is consistent.

Because the system has n=3 variables, the dimension of its solution space is

$$ \infty^{n-r} = \infty^{3-3} = \infty^0 = 1 \ soluzione $$

The system therefore admits a unique solution.

I now rewrite the system in the form corresponding to the reduced augmented matrix A|B.

$$ A|B= \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 1 \end{pmatrix} $$

$$ \begin{cases} x+y+z=1 \\ -y=0 \\ -z=1 \end{cases} $$

$$ \begin{cases} x+y+z=1 \\ y=0 \\ z=-1 \end{cases} $$

Solving the system is immediate. Two variables are already determined, so I substitute y=0 and z=-1 into the first equation:

$$ \begin{cases} x+0-1=1 \\ y=0 \\ z=-1 \end{cases} $$

$$ \begin{cases} x=1+1 \\ y=0 \\ z=-1 \end{cases} $$

$$ \begin{cases} x=2 \\ y=0 \\ z=-1 \end{cases} $$

The unique solution is x=2, y=0 and z=-1.

Verification. The original system is $$ \begin{cases} x+y+z = 1 \\ x+z=1 \\ x+y=2 \end{cases} $$ Substituting x=2, y=0 and z=-1 yields $$ \begin{cases} 2+0+(-1) = 1 \\ 2+(-1)=1 \\ 2+0=2 \end{cases} $$ $$ \begin{cases} 1 = 1 \\ 1=1 \\ 2=2 \end{cases} $$ All three identities hold, confirming the correctness of the solution.

And the procedure continues in the same way for larger systems.