Solving Systems of Linear Equations; Row Reduction
$\def\Height{\vphantom{\begin{array}{c}a\cr a\cr a\cr\end{array}}}
\def\{\!\!\smash{\left\Height\right.}\!\!}
\def\Matrix#1{\left[\;\;\Height\begin{array}{rrrcr}#1\end{array}\;\;\right]} $
Systems of linear equations arise in all sorts of applications in many
different fields of study. The method reviewed here can be
implemented to solve a linear system
$\begin{array}{ccccccccc}
a_{11}x_{1} & + & a_{12}x_{2} & + & \ldots & + & a_{1n}x_{n} & = & b_{1} \\
a_{21}x_{1} & + & a_{22}x_{2} & + & \ldots & + & a_{2n}x_{n} & = & b_{2} \\
\vdots & & \vdots & & \ddots & & \vdots & & \vdots \\
a_{m1}z_{1} & + & a_{m2}x_{2} & + & \ldots & + & a_{mn}x_{n} & = & b_{m} \\
\end{array}$
of any size. We write this system in matrix form as
$$
\left[\begin{array}{cccc}
a_{11} & a_{12} & \cdots & a_{1n}\\
a_{21} & a_{22} & \cdots & a_{2n}\\
\vdots & \vdots & \ddots & \ddots\\
a_{m1} & a_{m2} & \cdots & a_{mn}
\end{array}
\right]
\left[
\begin{array}{c}
x_1\\
x_2\\
\vdots\\
x_n
\end{array}
\right] =
\left[
\begin{array}{c}
b_1\\
b_2\\
\vdots\\
b_m
\end{array}
\right]
$$

That is, $ A{\bf x} = {\bf b}. $


We can capture all the information contained in the sytem in the
single augmented matrix
$$
\Matrix{
a_{11} & a_{12} & \cdots & a_{1n} & & b_{1}\\
a_{21} & a_{22} & \cdots & a_{2n} &\& b_{2}\\
\vdots & \vdots & \ddots & \vdots &\& \vdots\\
a_{m1} & a_{m2} & \cdots & a_{mn} & & b_{m}\\
}
$$
We will solve the original system of linear equations by performing a
sequence of the following elementary row operations on the augmented
matrix:
Elementary Row Operations
 Interchange two rows.
 Multiply one row by a nonzero number.
 Add a multiple of one row to a different row.

Do you see how we are manipulating the system of
linear equations by applying each of these operations?


When a sequence of elementary row operations is performed on an
augmented matrix, the linear system that corresponds to the resulting
augmented matrix is equivalent to the original system. That is, the
resulting system has the same solution set as the original system.
Our strategy in solving linear systems, therefore, is to take an
augmented matrix for a system and carry it by means of elementary row
operations to an equivalent augmented matrix from which the solutions
of the system are easily obtained. In particular, we bring the
augmented matrix to RowEchelon Form:
RowEchelon Form
A matrix is said to be in rowechelon form if
 All rows consisting entirely of zeros are at the bottom.
 In each row, the first nonzero entry form the left is a 1,
called the leading 1.
 The leading 1 in each row is to the right of all leading 1's in
the rows above it.
If, in addition, each leading 1 is the only nonzero entry in its
column, then the matrix is in reduced rowechelon form.
It can be proven that every matrix can be brought to rowechelon form
(and even to reduced rowechelon form) by the use of elementary row
operations. At that point, the solutions of the system are easily
obtained.
In the following example, suppose that each of the matrices was the
result of carrying an augmented matrix to reduced rowechelon form by
means of a sequence of row operations.
Example
The augmented matrix
$$
A_{1} = \Matrix{
1 & 0 & 0 & & 2\\
0 & 1 & 0 &\& 3\\
0 & 0 & 1 & & 4 }
$$
in reduced rowechelon form, corresponds to the system
$\begin{array}{ccccr}
x_1 & & & = & 2\\
& x_2 & & = & 3\\
& & x_3 & = &4
\end{array}$
which is already fully solved!
The augmented matrix
$$
A_{2} = \Matrix{
1 & 0 & 3 & & 5\\
0 & 1 & 2 &\& 4\\
0 & 0 & 0 & & 0 }
$$
also in reduced rowechelon form, corresponds to the system
$\begin{array}{ccrcr}
x_1 & & 3x_3 & = & 5\\
& x_2 & +2x_3 & = & 4\\
& & 0 & = & 0
\end{array}$
Letting $x_3=t$, we find that $x_2 = 2t+4$ and $x_1=3t5$. Thus, the
system has infinitely many solutions, parametrized for all $t$ as
$$
\left[\begin{array}{c}
x_1\\
x_2\\
x_3
\end{array}\right] = \left[\begin{array}{c}
3t5\\
2t+4\\
t
\end{array}\right]
$$
Finally, the augmented matrix
$$
A_{3} = \Matrix{
1 & 0 & 0 & & 3\\
0 & 1 & 0 &\& 2\\
0 & 0 & 0 & & 1 }
$$
again in reduced rowechelon form, corresponds to the system
$\begin{array}{ccccr}
x_1 & & & = & 3\\
& x_2 & & = & 2\\
& & 0 & = & 1
\end{array}$
which clearly has no solution. The system is inconsistent.
Notes
 If a matrix is carried to rowechelon form by means of
elementary row operations, the number of leading 1's in the resulting
matrix is called the rank $r$ of the original matrix.
 Suppose that a system of linear equations in $n$ variables has a
solution. Then the set of solutions has $nr$ parameters, where $r$
is the rank of the augmented matrix.
 Suppose that $A$ is an $n \times n$ invertible matrix.
Then the system $A{\bf x}= {\bf b}$ has a unique solution given by
${\bf x} = A^{1}{\bf b}$. That is, the reduced rowechelon augmented
matrix will be of the form
$$
\left[ I \left A^{1}{\bf b}\right.\right].
$$
Gaussian Elimination
 If the matrix is already in rowechelon form, then stop.
 Otherwise, find the first column from the left with a nonzero
entry $a$ and move the row containing that entry to the top of the
rows being worked on.
 Multiply that row by $1/a$ to create a leading 1.
 Subtract multiples of that row from the rows below it to make
each entry below the leading 1 zero. We are now done working on that
row.
 Repeat steps 1$$4 on the rows still being worked on.
Notes
 In practice, you have some flexibility in th eapplication of the
algorithm. For instance, in Step 2 you often have a choice of rows to
move to the top.
 A more computationallyintensive algorithm that takes a matrix
to reduced rowechelon form is given by the GaussJordon Reduction.
Example
We will use Gaussian Elimination to solve the linear system
$\begin{array}{rcrcrcr}
x_1 & + & 2x_2 & + & 3x_3 & = & 9 \\
2x_1 &  & x_2 & + & x_3 & = & 8 \\
3x_1 & & &  & x_3 & = & 3
\end{array}$.
The augmented matrix is
$$
\Matrix{
1 & 2 & 3 & & 9\\
2 & 1 & 1 &\& 8\\
3 & 0 & 1 & & 3 }
$$
The Gaussian Elimination algorithm proceeds as follows:
$\Matrix{
1 & 2 & 3 & & 9\\
2 & 1 & 1 &\& 8\\
3 & 0 & 1 & & 3 }
$

 $$ \quad\longrightarrow\quad $$
 $\Matrix{
1 & 2 & 3 & & 9\\
0 & 5 & 5 &\& 10\\
0 & 6 & 10 & & 24 }
$

(Row 1) 
(Row 2$2\cdot$Row 1) 
(Row 3$3\cdot$Row 1) 


 $$ \quad\longrightarrow\quad $$
 $\Matrix{
1 & 2 & 3 & & 9\\
0 & 1 & 1 &\ & 2\\
0 & 6 & 10 && 24 }
$

(Row 1) 
($1/5\cdot$Row 2) 
(Row 3) 


 $$ \quad\longrightarrow\quad $$
 $\Matrix{
1 & 2 & 3 & & 9\\
0 & 1 & 1 &\& 2\\
0 & 0 & 4 & & 12 }
$

(Row 1) 
(Row 2) 
(Row 3$+6\cdot$Row 2) 


 $$ \quad\longrightarrow\quad $$
 $\Matrix{
1 & 2 & 3 & & 9\\
0 & 1 & 1 &\& 2\\
0 & 0 & 1 & & 3 }
$

(Row 1) 
(Row 2) 
($1/4\cdot$Row 3) 

We have brought the matrix to rowechelon form. The corresponding
system
$$\begin{array}{rrrrrcr}
x_1 & + & 2x_2 & + & 3x_3 & = & 9\\
& & x_2 & + & x_3 & = & 2\\
& & & & x_3 & = & 3
\end{array}$$
is easily solved from the bottom up:
\begin{eqnarray*}
& & x_3 = 3 \\
& & x_2+3=2 \longrightarrow x_2 =1\\
& & x_1 +2(1)+3(3)=9 \longrightarrow x_1 =2.\\
\end{eqnarray*}
Thus, the solution of the original system is $x_1=2, \quad x_2=1,
\quad x_3=3.$
In the Exploration, use the Row Reduction Calculator to practice
solving systems of linear equations by reducing the augmented matrices
to rowechelon form.
Exploration
Key Concepts
To solve a system of linear equations, reduce the corresponding
augmented matrix to rowechelon form using the Elementary Row
Operations:
 Interchange two rows.
 Multiply one row by a nonzero number.
 Add a multiple of one row to a different row.
Gaussian Elimination is one algorithm that reduces matrices to
rowechelon form.
