1.2.1: Elimination and Augmented Matrices
- Page ID
- 186281
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \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{\longvect}{\overrightarrow}\)
\( \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}\)We will solve systems of linear equations algebraically using the elimination method. In other words, we will combine the equations in various ways to try to eliminate as many variables as possible from each equation. There are three valid operations we can perform on our system of equations:
- Scaling: we can multiply both sides of an equation by a nonzero number.
\[\left\{\begin{array}{rrrrrrr}x &+& 2y &+& 3z &=& 6\\ 2x &-& 3y &+& 2z &=& 14\\ 3x &+& y &-& z &=& -2\end{array}\right. \quad\xrightarrow{\text{multiply 1st by $-3$}}\quad \left\{\begin{array}{rrrrrrr} -3x &-& 6y &-& 9z &=& -18\\ 2x &-& 3y &+& 2z &=& 14\\ 3x &+& y &-& z &=& -2\end{array}\right. \nonumber \] - Replacement: we can add a multiple of one equation to another, replacing the second equation with the result.
\[\left\{\begin{array}{rrrrrrr}x &+& 2y &+& 3z &=& 6\\ 2x &-& 3y &+& 2z &=& 14\\ 3x &+& y &-& z &=& -2 \end{array}\right. \quad\xrightarrow{\text{2nd ${}={}$ 2nd$-2\times$1st}}\quad \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6\\ {}&{}& -7y &-& 4z &=& 2\\ 3x &+& y &-& z &=& -2\end{array}\right.\nonumber\] - Swap: we can swap two equations.
\[\left\{\begin{array}{rrrrrrr}x &+& 2y &+& 3z &=& 6\\ 2x &-& 3y &+& 2z &=& 14\\ 3x &+& y &-& z &=& -2 \end{array}\right. \quad\xrightarrow{\text{3rd $\longleftrightarrow$ 1st}}\quad \left\{\begin{array}{rrrrrrr} 3x &+& y &-& z &=& -2\\ 2x &-& 3y &+& 2z &=& 14\\ x &+& 2y &+& 3z &=& 6\end{array}\right.\nonumber\]
Use elimination to solve \[ \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6\\ 2x &-& 3y &+& 2z &=& 14\\ 3x &+& y &-& z &=& -2 \end{array}\right. \nonumber \]
Solution
\[\begin{aligned} \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6\\ 2x &-& 3y &+& 2z &=& 14\\ 3x &+& y &-& z &=& -2\end{array}\right. \quad\xrightarrow{\text{2nd ${}={}$ 2nd$-2\times$1st}}\quad & \left\{\begin{array}{rrrrrrr}x &+& 2y &+& 3z &=& 6\\ {}&{}& -7y &-& 4z &=& 2\\ 3x &+& y &-& z &=& -2 \end{array}\right. \\ {} \quad\xrightarrow{\text{3rd ${}={}$ 3rd$-3\times$1st}}\quad& \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6 \\ {}&{}& -7y &-& 4z &=& 2\\ {}&{}& -5y &-& 10z &=& -20 \end{array}\right. \\ {} \quad\xrightarrow{\text{2nd $\longleftrightarrow$ 3rd}}\quad & \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6\\ {}&{}& -5y &-& 10z &=& -20 \\ {}&{}& -7y &-& 4z &=& 2\end{array}\right. \\ {} \quad\xrightarrow{\text{divide 2nd by $-5$}}\quad & \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6 \\ {}&{}& y &+& 2z &=& 4\\ {}&{}& -7y &-& 4z &=& 2 \end{array}\right. \\ {} \quad\xrightarrow{\text{3rd ${}={}$ 3rd$+7\times$2nd}}\quad & \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6\\ {}&{}&y &+& 2z &=& 4 \\ {}&{}&{}&{}&10z &=& 30 \end{array}\right.\end{aligned}\]
At this point we’ve eliminated both \(x\) and \(y\) from the third equation, and we can solve \(10\cdot z=30\) to get \(z=3\). Substituting for \(z\) in the second equation gives \(y+2\cdot3=4\text{,}\) or \(y=-2\). Substituting for \(y\) and \(z\) in the first equation gives \(x + 2\cdot(-2) + 3\cdot3 = 6\text{,}\) or \(x=1\). Thus, the only solution is \((x,y,z)=(1,-2,3)\).
We can check that our solution is correct by substituting \((x,y,z)=(1,-2,3)\) into the original equation:
\[\left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6 \\ 2x &-& 3y &+& 2z &=& 14 \\ 3x &+& y &-& z &=& -2 \end{array}\right. \quad\xrightarrow{\text{substitute}}\quad \left\{\begin{array}{rrrrrrr} 1 &+&2\cdot(-2) &+& 3\cdot 3 &=& 6 \\ 2\cdot 1 &-& 3\cdot(-2) &+& 2\cdot 3 &=& 14 \\ 3\cdot 1 &+& (-2) &-& 3 &=& -2 \end{array}\right. \nonumber\]
Solving equations by elimination requires writing the variables \(x,y,z\) and the equals sign \(=\) over and over again, merely as placeholders: all that is changing in the equations is the coefficient numbers. We can make our life easier by extracting only the numbers and putting them in a box:
\[\left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6\\ 2x &-& 3y &+& 2z& =& 14\\ 3x &+& y &-& z &=& -2\end{array}\right. \quad\xrightarrow{\text{becomes}}\quad \left[\begin{array}{ccc|c} 1&2&3&6 \\ 2&-3&2&14 \\ 3&1&-1&-2 \end{array}\right]\nonumber\]
This is called an augmented matrix. The word “augmented” refers to the vertical line, which we draw to remind ourselves where the equals sign belongs; a matrix is a grid of numbers without the vertical line. In this notation, our three valid ways of manipulating our equations become row operations:
- Scaling: multiply all entries in a row by a nonzero number.
\[\left[\begin{array}{ccc|c} 1& 2& 3& 6&\\ 2& -3& 2& 14\\ 3& 1& -1& -2\end{array}\right] \quad\xrightarrow{R_1 = R_1 \times -3}\quad \left[\begin{array}{ccc|c} -3 &-6 &-9 &-18\\ 2& -3& 2& 14\\ 3& 1& -1& -2\end{array}\right]\nonumber\]
Here the notation \(R_1\) simply means “the first row”, and likewise for \(R_2,R_3,\) etc. - Replacement: add a multiple of one row to another, replacing the second row with the result.
\[\left[\begin{array}{ccc|c}1 &2& 3& 6\\ 2& -3& 2& 14\\ 3& 1& -1& -2\end{array}\right] \quad\xrightarrow{R_2 = R_2 -2\times R_1}\quad \left[\begin{array}{ccc|c} 1 &2 &3 &6 \\ 0& -7& -4& 2\\ 3& 1& -1& -2\end{array}\right]\nonumber\] - Swap: interchange two rows.
\[\left[\begin{array}{ccc|c} 1 &2 &3 &6 \\ 2& -3& 2& 14\\ 3& 1& -1& -2\end{array}\right] \quad\xrightarrow{R_1 \longleftrightarrow R_3}\quad \left[\begin{array}{ccc|c} 3 &1 &-1& -2\\ 2& -3& 2& 14\\ 1& 2& 3& 6\end{array}\right]\nonumber\]
When we wrote our row operations above, we used expressions like \(R_2 = R_2 - 2 \times R_1\). Of course this does not mean that the second row is equal to the second row minus twice the first row. Instead it means that we are replacing the second row with the second row minus twice the first row. This kind of syntax is used frequently in computer programming when we want to change the value of a variable.
Use row operations to solve \[ \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6\\ 2x &-& 3y &+& 2z &=& 14\\ 3x &+& y &-& z &=& -2 \end{array}\right. \nonumber \]
Solution
We start by forming an augmented matrix:
\[\left\{\begin{array}{rrrrrrr} x&+&2y&+&3z&=& 6\\ 2x&-&3y&+&2z&=&14 \\ 3x&+&y&-&z&=&-2 \end{array}\right. \quad\xrightarrow{\text{becomes}}\quad \left[\begin{array}{ccc|c}1&2&3&6\\2&-3&2&14\\3&1&-1&-2\end{array}\right]\nonumber \]
Eliminating a variable from an equation means producing a zero to the left of the line in an augmented matrix. First, we produce zeros in the first column (i.e. we eliminate \(x\)) by subtracting multiples of the first row.
\[\begin{aligned} \left[\begin{array}{ccc|c} 1 &2 &3& 6\\ 2& -3& 2& 14\\ 3& 1& -1& -2\end{array}\right] & \quad\xrightarrow{R_2=R_2-2R_1}\quad \left[\begin{array}{ccc|c} 1 &2 &3& 6\\ \color{red}{0}& -7& -4& 2\\ 3& 1& -1& -2\end{array}\right]\\ & \quad\xrightarrow{R_3=R_3-3R_1}\quad \left[\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& -7& -4& 2\\ \color{red}{0}& -5& -10& -20\end{array}\right] \end{aligned}\]
This was made much easier by the fact that the top-left entry is equal to \(1\text{,}\) so we can simply multiply the first row by the number below and subtract. In order to eliminate \(y\) in the same way, we would like to produce a \(1\) in the second column. We could divide the second row by \(-7\text{,}\) but this would produce fractions; instead, let’s divide the third by \(-5\).
\[\begin{aligned} \left[\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& -7& -4& 2\\ 0& -5& -10& -20 \end{array}\right] \quad\xrightarrow{R_3=R_3\cdot\left(-\frac{1}{5}\right)}\quad & \left[\begin{array}{ccc|c} 1 &2& 3& 6\\ 0 &-7& -4& 2\\ 0& \color{red}{1}& 2& 4\end{array}\right] \\ {}\quad\xrightarrow{R_2\longleftrightarrow R_3}\quad & \left[\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4 \\ 0& -7& -4& 2\end{array}\right] \\ {}\quad\xrightarrow{R_3 = R_3+7R_2}\quad & \left[\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4\\ 0& \color{red}{0} & 10& 30 \end{array}\right] \\ {}\quad\xrightarrow{R_3 = R_3\div 10}\quad & \left[\begin{array}{ccc|c}1 &2& 3& 6\\ 0& 1& 2& 4 \\ 0& 0& \color{red}{1}& 3\end{array}\right]\end{aligned}\]
We swapped the second and third rows just to keep things orderly. Now we translate this augmented matrix back into a system of equations:
\[\left[\begin{array}{ccc|c} 1 &2& 3& 6\\ 0& 1& 2& 4\\ 0& 0& 1& 3\end{array}\right] \quad\xrightarrow{\text{becomes}}\quad \left\{\begin{array}{rrrrrrr} x &+& 2y &+& 3z &=& 6 \\ {}&{}& y &+& 2z &=& 4 \\ {}&{}&{}&{}&z &=& 3\end{array}\right.\nonumber \]
Hence, \(z=3\); back-substituting gives \((x,y,z)=(1,-2,3)\).
The process of doing row operations to a matrix does not change the solution set of the corresponding linear equations!
Indeed, the whole point of doing these operations is to solve the equations using the elimination method.
Two matrices are called row equivalent if one can be obtained from the other by doing some number of row operations.
So the linear equations of row-equivalent matrices have the same solution set.
Solve the following system of equations using row operations:
\[\left\{\begin{array}{rrrrr} x &+& y& =& 2\\ 3x &+& 4y &=& 5\\ 4x &+ &5y &=& 9\end{array}\right. \nonumber\]
Solution
First, we put our system of equations into an augmented matrix.
\[\left\{\begin{array}{rrrrr} x &+& y &=& 2\\ 3x &+& 4y &=& 5\\ 4x &+& 5y &=& 9\end{array}\right. \quad\xrightarrow{\text{augmented matrix}}\quad \left[\begin{array}{cc|c} 1 &1& 2\\ 3 &4& 5\\ 4& 5& 9\end{array}\right]\nonumber\]
We clear the entries below the top-left using row replacement.
\[\begin{aligned}\left[\begin{array}{cc|c} 1 &1& 2\\ 3& 4& 5\\ 4& 5& 9\end{array}\right] \quad\xrightarrow{R_2=R_2-3R_1}\quad & \left[\begin{array}{cc|c} 1 &1& 2\\ \color{red}{0} & 1& -1\\ 4& 5& 9\end{array}\right]\\ {} \quad\xrightarrow{R_3=R_3-4R_1}\quad & \left[\begin{array}{cc|c} 1 &1& 2\\ 0& 1& -1\\ \color{red}{0}& 1& 1\end{array}\right]\end{aligned} \nonumber\]
Now we clear the second entry from the last row.
\[\left[\begin{array}{cc|c} 1 &1& 2\\ 0& 1& -1\\ 0 &1& 1\end{array}\right] \quad\xrightarrow{R_3=R_3-R_2}\quad \left[\begin{array}{cc|c} 1 &1& 2\\ 0& 1& -1\\ 0& \color{red}{0}& 2\end{array}\right] \nonumber \]
This translates back into the system of equations
\[\left\{\begin{array}{rrrrr} x &+& y &=& 2\\ {}&{}& y& =& -1 \\ {}&{}& 0& =& 2 \end{array}\right. \nonumber\]
Our original system has the same solution set as this system. But this system has no solutions: there are no values of \(x,y\) making the third equation true! We conclude that our original equation was inconsistent.