Gaussian Elimination by David Parra

To solve a linear system of equations of n variables, we use the Gaussian Elimination algorithm.
In this example we will use the next system of equations:
x + 4y + z = 7
x + 6y - z = 13
2x -y + 2z = 5

We write our system as a matrix:

(1)
\begin{align} \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 1 & 6 & -1 & 13 \\ 2 & -1 & 2 & 5 \end{array}\right] \end{align}

//on matlab: a1=[1,4,1,7;1,6,-1,13;2,-1,-2,5]

We already have a pivot on the first row, now we need all the numbers below the pivot to be 0s. We do that by subtracting the first row from the second row once, and 2 times from the third row:
R2 - R1

(2)
\begin{align} \left[\begin{array}{cc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 1 & 6 & -1 & 13 \\ 2 & -1 & 2 & 5 \end{array}\right] = \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 2 & -2 & 6 \\ 2 & -1 & 2 & 5 \end{array}\right] \end{align}

on matlab; b1=[1,0,0;-1,1,0;0,0,1] then a2=b1*a1

R3 - 2R1

(3)
\begin{align} \left[\begin{array}{cc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{array}\right] \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 2 & -2 & 6 \\ 2 & -1 & 2 & 5 \end{array}\right] = \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 2 & -2 & 6 \\ 0 & -9 & 0 & -9 \end{array}\right] \end{align}

//on matlab: b2=[1,0,0;0,1,0;-2,0,1] then a3=b2*a2

Now we need a pivot on the second row, we get that by dividing the second row by 2:

1/2R2

(4)
\begin{align} \left[\begin{array}{cc} 1 & 0 & 0 \\ 0 & 1/2 & 0 \\ 0 & 0 & 1 \end{array}\right] \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 2 & -2 & 6 \\ 0 & -9 & 0 & -9 \end{array}\right] = \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & -1 & 3 \\ 0 & -9 & 0 & -9 \end{array}\right] \end{align}

//on matlab: b3=[1,0,0;0,1/2,0;0,0,1] then a4=b3*a3

The next thing to do is to get a 0 below the second pivot by adding the second row to the third row 9 times:

R3+9R2

(5)
\begin{align} \left[\begin{array}{cc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 9 & 1 \end{array}\right] \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & -1 & 3 \\ 0 & -9 & 0 & -9 \end{array}\right] = \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & -1 & 3 \\ 0 & 0 & -9 & 18 \end{array}\right] \end{align}

//on matlab: b4=[1,0,0;0,1,0;0,9,1] then a5=b4*a4

Now we need a pivot on the third row by dividing the third row by -9:

-1/9R3

(6)
\begin{align} \left[\begin{array}{cc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1/9 \end{array}\right] \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & -1 & 3 \\ 0 & 0 & -9 & 18 \end{array}\right] = \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & -1 & 3 \\ 0 & 0 & 1 & -2 \end{array}\right] \end{align}

//on matlab: b5=[1,0,0;0,1,0;0,0,-1/9] then a6=b5*a5

That is the Row Echelon Form. To get the Reduced Row Echelon we need 0s above the pivots. To do that now we add the third row to the second row:

R2 + R3

(7)
\begin{align} \left[\begin{array}{cc} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array}\right] \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & -1 & 3 \\ 0 & 0 & 1 & -2 \end{array}\right] = \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -2 \end{array}\right] \end{align}

//on matlab: b6=[1,0,0;0,1,1;0,0,1] then a7=b6*a6

And to finish we substract the third row from first row once, and the second row from the first row 4 times:

R1 - 4R2 - R3

(8)
\begin{align} \left[\begin{array}{cc} 1 & -4 & -1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] \left[\begin{array}{cc} 1 & 4 & 1 & 7 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -2 \end{array}\right] = \left[\begin{array}{cc} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & -2 \end{array}\right] \end{align}

//on matlab: b7[1,-4,-1;0,1,0;0,0,1] then a8=b7*a7

That is the Reduced Echelon Form. The final matrix expresses that:

x=5
y=1
z=-2

To verify this you can use the rref function in matlab: rref(a1).

Credit to Justin K for the matrix code.

page revision: 0, last edited: 18 Sep 2011 05:01