11.3: Gaussian Elimination
- Page ID
- 44312
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The work we did in the previous section will always find the solution to the system. In this section, we will explore a less cumbersome way to find the solutions. First, we will represent a linear system with an augmented matrix. A matrix is simply a rectangular array of numbers. The size or dimension of a matrix is defined as \(m\times n\) where \(m\) is the number of rows and \(n\) is the number of columns. In order to construct an augmented matrix from a linear system, we create a coefficient matrix from the coefficients of the variables in the system, as well as a constant matrix from the constants. The coefficients from one equation of the system create one row of the augmented matrix.
For example, consider the linear system \[\begin{array}{c} x+3y+6z=25 \\ 2x+7y+14z=58 \\ 2y+5z=19 \end{array}\] This system can be written as an augmented matrix, as follows \[\left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 2 & 7 & 14 & 58 \\ 0 & 2 & 5 & 19 \end{array} \right] \]
Notice that it has exactly the same information as the original system. Here it is understood that the first column contains the coefficients from \(x\) in each equation, in order, \(\left[ \begin{array}{r} 1 \\ 2 \\ 0 \end{array} \right] .\) Similarly, we create a column from the coefficients on \(y\) in each equation, \(\left[ \begin{array}{r} 3 \\ 7 \\ 2 \end{array} \right]\) and a column from the coefficients on \(z\) in each equation, \(\left[ \begin{array}{r} 6 \\ 14 \\ 5 \end{array} \right] .\) For a system of more than three variables, we would continue in this way constructing a column for each variable. Similarly, for a system of less than three variables, we simply construct a column for each variable.
Finally, we construct a column from the constants of the equations, \(\left[ \begin{array}{r} 25\\ 58\\ 19 \end{array} \right] .\)
The rows of the augmented matrix correspond to the equations in the system. For example, the top row in the augmented matrix, \(\left[ \begin{array}{rrrrr} 1 & 3 & 6 & | & 25 \end{array} \right]\) corresponds to the equation \[x+3y+6z=25.\]
Consider the following definition.
Definition \(\PageIndex{1}\): Augmented Matrix of a Linear System
For a linear system of the form \[\begin{array}{c} a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1} \\ \vdots \\ a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m} \end{array}\] where the \(x_{i}\) are variables and the \(a_{ij}\) and \(b_{i}\) are constants, the augmented matrix of this system is given by \[\left[ \begin{array}{rrr|r} a_{11} & \cdots & a_{1n} & b_{1} \\ \vdots & & \vdots & \vdots \\ a_{m1} & \cdots & a_{mn} & b_{m} \end{array} \right]\]
Now, consider elementary operations in the context of the augmented matrix. The elementary operations in Definition\(\PageIndex{1}\) can be used on the rows just as we used them on equations previously. Changes to a system of equations in as a result of an elementary operation are equivalent to changes in the augmented matrix resulting from the corresponding row operation. Note that Theorem 11.2.1 implies that any elementary row operations used on an augmented matrix will not change the solution to the corresponding system of equations. We now formally define elementary row operations. These are the key tool we will use to find solutions to systems of equations.
Definition \(\PageIndex{2}\): Elementary Row Operations
The elementary row operations (also known as row operations) consist of the following
- Switch two rows.
- Multiply a row by a nonzero number.
- Replace a row by any multiple of another row added to it.
Recall how we solved Example 11.2.3. We can do the exact same steps as above, except now in the context of an augmented matrix and using row operations. The augmented matrix of this system is \[ \nonumber \left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 2 & 7 & 14 & 58 \\ 0 & 2 & 5 & 19 \end{array} \right]\] Thus the first step in solving this system would be to take \(\left( -2\right)\) times the first row of the augmented matrix and add it to the second row, \[\nonumber\left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 0 & 1 & 2 & 8 \\ 0 & 2 & 5 & 19 \end{array} \right]\] Note how this corresponds to this step in Example 11.2.3. Next take \(\left( -2\right)\) times the second row and add to the third, \[\nonumber\left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 0 & 1 & 2 & 8 \\ 0 & 0 & 1 & 3 \end{array} \right]\] This augmented matrix corresponds to the system \[\nonumber\begin{array}{c} x+3y+6z=25 \\ y+2z=8 \\ z=3 \end{array}\] which is the same as this step in Example 11.2.3. By back substitution you obtain the solution \(x=1,y=2,\) and \(z=3.\)
Through a systematic procedure of row operations, we can simplify an augmented matrix and carry it to row-echelon form or reduced row-echelon form, which we define next. These forms are used to find the solutions of the system of equations corresponding to the augmented matrix.
In the following definitions, the term leading entry refers to the first nonzero entry of a row when scanning the row from left to right.
Definition \(\PageIndex{3}\): Row-Echelon Form
An augmented matrix is in row-echelon form if
- All nonzero rows are above any rows of zeros.
- Each leading entry of a row is in a column to the right of the leading entries of any row above it.
- Each leading entry of a row is equal to \(1\).
We also consider another reduced form of the augmented matrix which has one further condition.
Definition \(\PageIndex{4}\): Reduced Row-Echelon Form
An augmented matrix is in reduced row-echelon form if
- All nonzero rows are above any rows of zeros.
- Each leading entry of a row is in a column to the right of the leading entries of any rows above it.
- Each leading entry of a row is equal to \(1\).
- All entries in a column above and below a leading entry are zero.
Notice that the first three conditions on a reduced row-echelon form matrix are the same as those for row-echelon form.
Hence, every reduced row-echelon form matrix is also in row-echelon form. The converse is not necessarily true; we cannot assume that every matrix in row-echelon form is also in reduced row-echelon form. However, it often happens that the row-echelon form is sufficient to provide information about the solution of a system.
The following examples describe matrices in these various forms. As an exercise, take the time to carefully verify that they are in the specified form.
Example \(\PageIndex{5}\): Not in Row-Echelon Form
The following augmented matrices are not in row-echelon form (and therefore also not in reduced row-echelon form).
\[\nonumber\left[ \begin{array}{rrr|r} 0 & 0 & 0 & 0 \\ 1 & 2 & 3 & 3 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array} \right] ,\left[ \begin{array}{rr|r} 1 & 2 & 3 \\ 2 & 4 & -6 \\ 4 & 0 & 7 \end{array} \right] ,\left[ \begin{array}{rrr|r} 0 & 2 & 3 & 3 \\ 1 & 5 & 0 & 2 \\ 7 & 5 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right]\]
Example \(\PageIndex{6}\): Matrices in Row-Echelon Form
The following augmented matrices are in row-echelon form, but not in reduced row-echelon form. \[\nonumber\left[ \begin{array}{rrrrr|r} 1 & 0 & 6 & 5 & 8 & 2 \\ 0 & 0 & 1 & 2 & 7 & 3 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] ,\left[ \begin{array}{rrr|r} 1 & 3 & 5 & 4 \\ 0 & 1 & 0 & 7 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array} \right], \left[ \begin{array}{rrr|r} 1 & 0 & 6 & 0 \\ 0 & 1 & 4 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\]
Notice that we could apply further row operations to these matrices to carry them to reduced row-echelon form. Take the time to try that on your own. Consider the following matrices, which are in reduced row-echelon form.
Example \(\PageIndex{7}\): Matrices in Reduced Row-Echelon Form
The following augmented matrices are in reduced row-echelon form. \[\nonumber\left[ \begin{array}{rrrrr|r} 1 & 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 1 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] ,\left[ \begin{array}{rrr|r} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array} \right] , \left[ \begin{array}{rrr|r} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 2 \end{array} \right]\]
One way in which the row-echelon form of a matrix is useful is in identifying the pivot positions and pivot columns of the matrix.
Definition \(\PageIndex{8}\): Pivot Position and Pivot Column
A pivot position in a matrix is the location of a leading entry in the row-echelon form of a matrix.
A pivot column is a column that contains a pivot position.
For example consider the following.
Example \(\PageIndex{9}\): Pivot Position
Let \[A=\left[ \begin{array}{rrr|r} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 6 \\ 4 & 4 & 4 & 10 \end{array} \right]\] Where are the pivot positions and pivot columns of the augmented matrix \(A\)?
Solution
The row-echelon form of this matrix is \[\left[ \begin{array}{rrr|r} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & \frac{3}{2} \\ 0 & 0 & 0 & 0 \end{array} \right]\]
This is all we need in this example, but note that this matrix is not in reduced row-echelon form.
In order to identify the pivot positions in the original matrix, we look for the leading entries in the row-echelon form of the matrix. Here, the entry in the first row and first column, as well as the entry in the second row and second column are the leading entries. Hence, these locations are the pivot positions. We identify the pivot positions in the original matrix, as in the following: \[\nonumber\left[ \begin{array}{rrr|r} \fbox{1} & 2 & 3 & 4 \\ 3 & \fbox{2} & 1 & 6 \\ 4 & 4 & 4 & 10 \end{array} \right]\] Thus the pivot columns in the matrix are the first two columns.
The following is an algorithm for carrying a matrix to row-echelon form and reduced row-echelon form. You may wish to use this algorithm to carry the above matrix to row-echelon form or reduced row-echelon form yourself for practice.
Algorithm \(\PageIndex{10}\): Reduced Row-Echelon Form Algorithm
This algorithm provides a method for using row operations to take a matrix to its reduced row-echelon form. We begin with the matrix in its original form.
- Starting from the left, find the first nonzero column. This is the first pivot column, and the position at the top of this column is the first pivot position. Switch rows if necessary to place a nonzero number in the first pivot position.
- Use row operations to make the entries below the first pivot position (in the first pivot column) equal to zero.
- Ignoring the row containing the first pivot position, repeat steps 1 and 2 with the remaining rows. Repeat the process until there are no more rows to modify.
- Divide each nonzero row by the value of the leading entry, so that the leading entry becomes \(1\). The matrix will then be in row-echelon form.
The following step will carry the matrix from row-echelon form to reduced row-echelon form.
- Moving from right to left, use row operations to create zeros in the entries of the pivot columns which are above the pivot positions. The result will be a matrix in reduced row-echelon form.
Most often we will apply this algorithm to an augmented matrix in order to find the solution to a system of linear equations. However, we can use this algorithm to compute the reduced row-echelon form of any matrix which could be useful in other applications.
Consider the following example of the Reduced Row-Echelon Form Algorithm.