$$\newcommand{\mat}[1]{\begin{bmatrix}#1\end{bmatrix}} \newcommand{\vxy}[2]{\begin{bmatrix}#1 \\ #2\end{bmatrix}} \newcommand{\vxyz}[3]{\begin{bmatrix}#1 \\ #2 \\ #3\end{bmatrix}} \newcommand{\rxy}[2]{\begin{bmatrix}#1 & #2\end{bmatrix}} \newcommand{\rxyz}[3]{\begin{bmatrix}#1 & #2 & #3\end{bmatrix}} \newcommand{\uu}[0]{\mathbf{u}} \newcommand{\uuu}[0]{\mathbf{\hat{u}}} \newcommand{\vv}[0]{\mathbf{v}} \newcommand{\vvv}[0]{\mathbf{\hat{v}}} \newcommand{\AA}[0]{\mathbf{A}} \newcommand{\BB}[0]{\mathbf{B}} \newcommand{\EE}[0]{\mathbf{E}} \newcommand{\MM}[0]{\mathbf{M}} \newcommand{\PP}[0]{\mathbf{P}} \newcommand{\ww}[0]{\mathbf{w}} \newcommand{\sm}[1]{\bigl[\begin{smallmatrix}#1\end{smallmatrix}\bigr]} \newcommand{\dotp}[2]{#1~{\cdot}~#2}$$

# Linear Algebra, Part 5: Elimination Using Matrices

posted August 3, 2013

In Part 4 of this series we looked at elimination as a process of determining when to do row exchanges and how to use row multiplication and addition to eliminate unknowns in a system of equations. Now we'll look at how we can use matrices to do this.

We've already looked at matrices multiplying vectors. The process is just shorthand for the system-of-equations form with all of the coefficients multiplying the unknowns explicitly. We've also looked at how a matrix multiplying a vector is a linear combination of the columns of the matrix. But what about when we multiply two matrices?

Matrix multiplication just repeats the process for each column in the right-hand side matrix. For columns $$\BB_i$$:

$\AA\BB = \mat{\AA\BB_1 & \AA\BB_2 & \cdots & \AA\BB_n}.$

Another way to look at this operation is that the rows of $$\AA$$ determine a linear combination of the rows of $$\BB$$. For rows $$\AA_i$$:

$\AA\BB = \mat{\AA_1\BB \\ \AA_2\BB \\ \vdots \\ \AA_n\BB}.$

Because of this, the matrices $$\AA$$ and $$\BB$$ must have compatible sizes to permit multiplication:

An $$m \times n$$ matrix $$\AA$$ can multiply a matrix $$\BB$$ if and only if $$\BB$$ has size $$n \times k$$. The resulting matrix will have size $$m \times k$$.

In this example, we double the first row and the third row becomes the first row added to three times the third:

$\mat{2 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 3}\mat{1 & 2 & 3 \\ 0 & 0 & 1 \\ 1 & 1 & 2} = \mat{2 & 4 & 6 \\ 0 & 0 & 1 \\ 4 & 5 & 9}.$

If we wanted to construct a matrix $$\AA$$ which added the first row of a matrix $$\BB$$ to its second row but left its other rows unchanged, we could write

$\AA = \mat{1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1}.$

Using $$\AA$$ as written above, the second row of $$\AA\BB$$ will be determined by the second row of $$\AA$$: it will be $$1$$ times row $$1$$ of $$\BB$$ plus $$1$$ times row $$2$$ of $$\BB$$ plus $$0$$ times row $$3$$ of $$\BB$$.

Given the following system of equations,

\begin{align*} x + 2y + 3z &= 2 \\ 4x + 5y + 6z &= 3 \\ 7x + 8y + 10z &= 11 \end{align*} \hskip{0.5in} \mat{1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10}\vxyz{x}{y}{z} = \vxyz{2}{3}{11}

elimination reduces it to

\begin{align*} x + 2y + 3z &= 2 \\ 3y - 6z &= -5 \\ z &= 7 \end{align*} \hskip{0.5in} \mat{1 & 2 & 3 \\ 0 & -3 & -6 \\ 0 & 0 & 1}\vxyz{x}{y}{z} = \vxyz{2}{-5}{7}.

Along the way we perform these operations in the order listed:

• subtract $$4$$ times row $$1$$ from row $$2$$;
• subtract $$7$$ times row $$1$$ from row $$3$$;
• subtract $$2$$ times the new row $$2$$ from the new row $$3$$.

Each step yields a new (intermediate) system and a multiplier $$\ell_{ij}$$. The multiplier $$\ell_{ij}$$ is the multiple of row $$j$$ which we want to subtract from row $$i$$. So the multipliers for the above steps would be $$\ell_{21} = 4$$, $$\ell_{31} = 7$$, and $$\ell_{32} = 2$$.

From the first part of this post we know that we can construct matrices to perform these manipulations. Given some $$\ell_{ij}$$, we can construct an elementary matrix $$\EE_{ij}$$ with $$-\ell_{ij}$$ in row $$i$$, column $$j$$. Then we can multiply this matrix times another to perform the row manipulation we desire. Given $$\ell_{21} = 4$$:

$\EE_{21} = \mat{1 & 0 & 0 \\ -4 & 1 & 0 \\ 0 & 0 & 1}; \hskip{1em} \AA = \mat{1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9}; \\ \EE_{21}\AA = \mat{1 & 2 & 3 \\ 0 & -3 & -6 \\ 7 & 8 & 9}.$

Next, we can construct a matrix $$\EE_{31}$$ with $$\ell_{31} = 7$$ placed accordingly. We then add it to the multiplication sequence: $$\EE_{31}\EE_{21}\AA$$. Lastly, we construct $$\EE_{32}$$ similarly and multiply:

$\EE_{21} = \mat{1 & 0 & 0 \\ -4 & 1 & 0 \\ 0 & 0 & 1}; \hskip{1em} \EE_{31} = \mat{1 & 0 & 0 \\ 0 & 1 & 0 \\ -7 & 0 & 1}; \hskip{1em} \EE_{32} = \mat{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1}; \\ \EE_{32}\EE_{31}\EE_{21}\AA = \mat{1 & 2 & 3 \\ 0 & -3 & -6 \\ 0 & 0 & 1}.$

Because matrix multiplication is associative we can view the $$\EE_{32}\EE_{31}\EE_{21}$$ matrix product as a single matrix, say $$\MM$$, which performs all of the elimination steps on $$\AA$$ simultaneously, written $$\MM\AA$$.

## Row Exchanges

We can also use matrices to perform row exchanges. We saw in Part 4 that row exchanges may be required to permit elimination to continue or to succeed. For example, the following system requires a row exchange to continue:

\begin{align*} 2y + 3z &= 2 \\ 4x + 5y + 6z &= 3 \\ 7x + 8y + 10z &= 11 \end{align*} \hskip{0.5in} \AA = \mat{0 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 10}\vxyz{x}{y}{z} = \vxyz{2}{3}{11}.

We can write a permutation matrix $$\PP_{ij}$$ to swap rows $$i$$ and $$j$$. In this case we want to swap row 1 with row 2:

$\PP_{12} = \mat{0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1}; \hskip{0.5in} \PP_{12}\AA = \mat{4 & 5 & 6 \\ 0 & 2 & 3 \\ 7 & 8 & 10}.$

(If we multiply by $$\PP_{12}$$ on the right instead of the left, the matrix permutes the columns of $$\AA$$ instead of its rows.)

## Afterword

With $$\EE_{ij}$$ and $$\PP_{ij}$$ we can encode the process of elimination as a series of matrix multiplications to perform the row operations that we need. Next time we'll look at matrix inverses and some ways of telling whether a matrix is invertible. After that we'll move on to Gauss-Jordan elimination, a modified elimination process that finds the inverse $$\AA^{-1}$$ of $$\AA$$ if it exists.