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:
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\).
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.)
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.