Skip to main content

Elementary Linear Algebra: An Active Learning Approach

Section 3.7 Row Operations via Matrix Multiplication

Row operations form an important class of operations with hidden structure. That structure is revealed by observing that certain row operations act as fundamental building blocks. Any general row operation can be expressed in terms of these fundamental building blocks called elementary row operations, all of which can be executed by matrix multiplication.

Definition 3.7.1. Elementary row operations. 

The elementary row operations on a linear system are the basic building blocks of the general row operation of linear combination row replacement. The elementary row operations are: 
    

  1. Row swap: \(R_i\longleftrightarrow R_j,\) for \(i\ne j,\) by which the row \(R_i\) is swapped with the row \(R_j.\)

    2. 

  2. Scalar multiple replacement: \(aR_i \rightarrow R_i,\) for \(a\ne0,\) which replaces the target row \(R_i\) by a scalar multiple of itself.
    3. 

  3. Scalar multiple addition replacement: \(aR_i+R_j\rightarrow R_j,\) for \(a\ne0,\) by which a scalar multiple of the row \(R_i\) is added to the target row \(R_j.\)

    4. 

Recall (2.7.3) in Remark 2.7.12 from which we learned that left-multiplication of \(\A\) by a matrix \(\C\) creates the product \(\C\A\) whose rows are linear combinations of the rows of \(\A.\) This fact allows us to accomplish row operations by matrix multiplication as follows.



Definition 3.7.2. Elementary matrices.

 An elementary matrix \(\E\in\R^{m\times m}\) executes an elementary row operation on \(\A\in\R^{m\times n}\) by left-multiplication of \(\A\) by \(\E.\)

Definition 3.7.3. Three types of elementary matrices.



Let \(\A\in\R^{m\times n}\) and \(\E\in\R^{m\times m}.\) 


For any \(\E\in\R^{m\times m},\) left-multiplication of \(\A\) by \(\E\) yields the following linear combinations of the rows of \(\A:\)




\begin{align}
(\E\A)_{1\ast}\amp=\,E_{11}\A_{1\ast}+ E_{12}\A_{2\ast}\,+\,\cdots\,+\,E_{1m}\A_{m\ast}\amp\notag\\
(\E\A)_{2\ast}\amp=\,E_{21}\A_{1\ast}+ E_{22}\A_{2\ast}\,+\,\cdots\,+\,E_{2m}\A_{m\ast}\amp\notag\\
\amp\qquad\qquad\qquad\,\,\vdots\amp\notag\\
(\E\A)_{i\ast}\,\amp =\,E_{i1}\A_{1\ast}+\,E_{i2}\A_{2\ast}\,+\,\cdots\,+\,\,E_{im}\A_{m\ast}\amp\tag{3.7.1}\\
\amp\qquad\qquad\qquad\vdots\amp\notag\\
(\E\A)_{m\ast}\amp=\,E_{m1}\A_{1\ast}\!+E_{m2}\A_{2\ast}+\,\cdots\,+E_{mm}\A_{m\ast}.\amp\notag
\end{align}



We will use this set of equations as an intuitive guide for determining the elementary matrix associated with each elementary row operation.


 
    

  1. 

    
Row swap: To swap row \(R_i\) with \(R_j\) we want \((\E\A)_{j\ast}=\A_{i\ast},\) \(\,(\E\A)_{i\ast}=\A_{j\ast}\) and otherwise \((\E\A)_{k\ast}=\A_{k\ast}.\) By (3.7.1) this requires \(E_{ji}=E_{ij}=1\) and that all other entries in the \(i^{\text{th}}\) and \(j^{\text{th}}\) rows of \(\E\) be \(0.\)

    

    Such a matrix is, not coincidentally, the result of swapping the \(i^{\text{th}}\) and \(j^{\text{th}}\) rows of the identity matrix \(\I.\) We will denote such a row swap matrix by \(\E_{(ij)}\) where the subscripts in parentheses indicate the rows to be swapped.
    

    

    For example, to swap rows \(1\) and \(2\) in the matrix \(\A=\lmatrix{ccc}A_{11}\amp A_{12}\amp A_{13}\\A_{21}\amp A_{22}\amp A_{23}\\A_{31}\amp A_{32}\amp A_{33}\rmatrix\) we multiply on the left by \(\E_{(12)}\in\R^{3\times3},\) which corresponds a swap of rows \(1\) and \(2\) in the identity matrix.
    

    
\begin{equation*}
\lmatrix{ccc} 0 \amp {\bf 1}\amp 0 \\ {\bf 1} \amp 0 \amp 0  \\ 0\amp 0 \amp 1 \rmatrix \lmatrix{ccc} A_{11} \amp A_{12} \amp A_{13}\\A_{21} \amp A_{22} \amp A_{23}\\A_{31} \amp A_{32} \amp A_{33}\rmatrix=\lmatrix{ccc} A_{21} \amp A_{22} \amp A_{23}\\A_{11} \amp A_{12} \amp A_{13}\\A_{31} \amp A_{32} \amp A_{33}\rmatrix.
\end{equation*}

    

    

    2. 

  2. 

    
Scalar multiple: To replace row \(R_i\) by a scalar multiple \(aR_i,\) we use the matrix resulting from multiplying the \(i^{\text{th}}\) row \(\I_{i\ast}\) of \(\I_m\) by \(a.\) We denote such an elementary matrix by \(\E_{(a)ii}.\)

    

    

    For example, we can multiply row \(R_3\) in \(\A\) by \(5\) by left-multiplying \(\A\) by \(\E_{(5)33}\text{:}\)

    

    
\begin{equation*}
\lmatrix{ccc} 1\amp  0\amp  0 \\ 0\amp 1 \amp  0 \\ 0\amp  0\amp {\bf 5} \rmatrix \lmatrix{ccc} A_{11} \amp  A_{12}\amp  A_{13} \\A_{21} \amp  A_{22}\amp  A_{23} \\A_{31} \amp  A_{32}\amp  A_{33}\rmatrix=\lmatrix{ccc} A_{11} \amp  A_{12}\amp  A_{13} \\A_{21} \amp A_{22}\amp A_{23} \\ \boldsymbol{5A_{31}} \amp \boldsymbol{5A_{32}}\amp  \boldsymbol{5A_{33}}\rmatrix
\end{equation*}

    

    

    3. 

  3. 

    
Scalar multiple with addition: To perform an operation such as \(aR_i+R_j \rightarrow R_j\) we need \(E_{ji}=a\) in a matrix whose other entries are the corresponding entries of the identity \(\I.\)  Such an elementary matrix is denoted by \(\E_{(a)ji}\) and is the result of performing \(aR_i+R_j\rightarrow R_j\) on \(\I_m.\)

    

    

    For example, to perform the operation \(7R_2+R_3\rightarrow R_3\) on \(\A\) we left-multiply \(\A\) by \(\E_{(7)32}\in\R^{3\times3}:\)

    

    
\begin{equation*}
\!\!\lmatrix{ccc} \!1\!\amp \!0\!\amp \!0\! \\ \!0\!\amp \!1\!\amp \!0\! \\ \!0\!\amp\!{\bf 7}\!\amp \!1\! \rmatrix \!\!\!\lmatrix{ccc} \!A_{11}\! \amp \!\!A_{12}\!\amp \!\!A_{13}\! \\\!A_{21}\! \amp \!\!A_{22}\!\amp \!\!A_{23}\! \\\!A_{31}\! \amp \!\!A_{32}\!\amp \!\!A_{33}\!\rmatrix\!\!=\!\!
\lmatrix{ccc} A_{11} \amp A_{12}\amp A_{13} \\A_{21} \amp A_{22}\amp A_{23} \\\!\boldsymbol{7\!A_{21}\!\!+\!\!A_{31}}\!\! \amp \!\!\boldsymbol{7\!A_{22}\!\!+\!\!A_{32}}\!\!\amp \!\!\boldsymbol{7\!A_{23}\!\!+\!\!A_{33}}\!\rmatrix\!.
\end{equation*}

    

    

    4. 


Example 3.7.4. Which \(\E\) performs this row operation?

Which matrix \(\E\) can be used to implement \(4R_2+R_1\rightarrow R_1\) by left-multiplying a \(3\times 3\) matrix \(\A\) by \(\E\text{?}\)

 



Solution: We need \(E_{12}=4\) so \(\E=\left(\begin{array}{rrr}1\amp  4\amp  0\\0\amp  1\amp  0\\0\amp  0\amp  1\end{array}\right).\) We can check by multiplying by an arbitrary matrix



\begin{equation*}
\lmatrix{rrr}1\amp 4\amp 0\\0\amp 1\amp 0\\0\amp 0\amp 1\rmatrix \lmatrix{ccc} a\amp  b\amp  c\\d\amp  e\amp  f\\g\amp  h\amp  i \rmatrix = \lmatrix{ccc} 4d+a\amp 4e+b\amp 4f+c\\d\amp  e\amp  f\\g \amp h \amp i \rmatrix.
\end{equation*}




Example 3.7.5. Which \(\E\) performs this row operation?

Find a matrix \(\E\) for which multiplying a \(3\times 3\) matrix \(\A\) on the left by \(\E\) has the effect of \(4R_2+(-2)R_3\rightarrow R_3.\) 

Solution: \(\E=\left(\begin{array}{rrr}1\amp 0\amp 0\\0\amp 1\amp 0\\0\amp 4\amp -2 \end{array} \right).\)


Example 3.7.6. Which row operation is performed by this \(\E?\)



Which row operation does the matrix multiplication



\begin{equation*}
\left(\begin{array}{rrr} 1\amp 0\amp 0\\-2\amp 3\amp 0\\0\amp 0\amp 1 \end{array} \right)\left(\begin{array}{rrr} 3\amp 2\amp -1\\2\amp -1\amp 7\\5\amp 0\amp 1 \end{array} \right)
\end{equation*}



perform on \(\left(\begin{array}{rrr} 3\amp 2\amp -1\\2\amp -1\amp 7\\5\amp 0\amp 1 \end{array} \right)\text{?}\)



 

Solution: \((-2)R_1+3R_2\rightarrow R_2.\)


Remark 3.7.8. The matrix for general linear combination replacement.



For given \(\a_1,\a_2\in\R,\) the linear combination replacement \(\a_1R_1+\a_2R_2\rightarrow R_2\) may be interpreted as the composition of two elementary row operations: 
    

  1. Replacing \(R_2\) by a scalar multiple \(\a_2R_2\rightarrow R_2,\) then
    2. 

  2. Using the scalar multiple addition \(\a_1R_1+R_2\rightarrow R_2.\)

    3. 

 
Performing \(\a_1R_i+\a_2R_j \rightarrow R_j\) via matrix multiplication can be accomplished by first applying \(\E_{(\a_2)jj}\) followed by \(\E_{(\a_1)ji}.\) The corresponding matrix is then the product \(\E_{(\a_1)ji}\E_{(\a_2)jj}.\) We note that such a product is not an elementary matrix since it does not arise from a single elementary row operation.

Remark 3.7.9. Elimination below and above the diagonal.



Let \(\A\in\R^{n\times n}.\) Elimination below the diagonal of \(\A\) is accomplished by \(\E_{(a)ij}\) in which \(i>j,\) and elimination above the diagonal of \(\A\) is accomplished by \(\E_{(a)ij}\) in which \(i\lt j.\)
The matrices \(\E_{ij}\) that effect row swaps are a special case of what are called permutation matrices.



Definition 3.7.11. Permutation matrix.



A permutation matrix \(\P\in\R^{n\times n},\) is any matrix that can be obtained from the identity matrix \(\I\) by some number of row swaps.
Proof.
The proof is a worksheet exercise.

Example 3.7.13. A permutation matrix.

The matrix \(\P_{231}:=\lmatrix{ccc} 0\amp  1\amp 0 \\ 0\amp  0\amp 1 \\ 1\amp  0\amp 0 \rmatrix\) can be obtained by, for example, starting with \(\I\) and 1) swapping rows \(1\) and \(3,\) and 2) then swapping rows \(1\) and \(2.\) The net effect is that \(\P_{231}\) contains the rows of \(\I\) but in the order specified by the subscript:

\begin{equation*}
\P_{231}=\left(\begin{array}{ccc}-\amp \I_{2\ast}\amp-\\-\amp \I_{3\ast}\amp-\\-\amp \I_{1\ast}\amp-\end{array}\right)
\end{equation*}




PrevTopNext