Adar Kahiri

Matrix Multplication

December 2020

Theorem. Let \(e\) be an elementary row operation and let \(E\) be the \( m \times m\) elementary matrix \(E = e(I)\). Then, for every \(m \times n\) matrix \(A\),

\[e(A) = EA\]

Proof. We prove this for each of the three elementary row operations separately.

Swap: If \(e\) 'swaps' rows \(s\) and \(r\) of \(A\), then

\[e(A)_{ij} = \begin{cases} A_{ij} \quad \text{if } s \neq i \neq r \\ A_{sj} \quad \text{if } i = r \\ A_{rj} \quad \text{if } i = s \end{cases}\]

and

\[ EA_{ij} = e(I)A_{ij} = \sum\limits_{k=1}^{m} e(I)_{ik}A_{kj}.\]

Noting that the same row operation as before is being applied to \(I\), we can equivalently define this matrix as follows:

\[ e(I)A_{ij} = \begin{cases} \sum\limits_{k=1}^{m} I_{ik}A_{kj} \quad \text{if } s \neq i \neq r \\ \sum\limits_{k=1}^{m} I_{sk}A_{kj} \quad \text{if } i = r \\ \sum\limits_{k=1}^{m} I_{rk}A_{kj} \quad \text{if } i = s \end{cases}\]

We can now simplify each of these cases. For the first case, since \(I_{ik} = 0\) for all but the \(i\)-th column, the only non-zero term in the sum will be \(I_{ii}A_{ij} = A_{ij}\). For the second case, the only non-zero term in the sum will be \(I_{ss}A_{sj} = A_{sj}\) and for the third case the only non-zero term in the same will be \(I_{rr}A_{rj} = A_{rj}\).


Scale: If \(e\) scales some row \(r\) by some scalar \(c\), then

\[e(A)_{ij} = \begin{cases} A_{ij} \quad \text{if } i \neq r \\ cA_{rj} \quad \text{if } i = r \end{cases}\]

and

\[ EA_{ij} = e(I)A_{ij} = \sum\limits_{k=1}^{m} e(I)_{ik}A_{kj}.\]

Noting that the same row operation as before is being applied to \(I\), we can equivalently define this matrix as follows:

\[ e(I)A_{ij} = \begin{cases} \sum\limits_{k=1}^{m} I_{ik}A_{kj} \quad \text{if } s \neq i \neq r \\ \sum\limits_{k=1}^{m} c I_{rk}A_{kj} \quad \text{if } i = r \end{cases}\]

We've already seen why the first case simplifies to \(A_{ij}\), and for identical reasons the second case simplifies to \(c A_{rj}\).


Add a scaled row to another row: If \(e\) scales adds row \(s\) of the matrix, scaled by a scalar \(c\), to another row \(r\) (where \(r \neq s\)), then

\[e(A)_{ij} = \begin{cases} A_{ij} \quad \text{if } i \neq r \\ A_{rj} + cA_{sj} \quad \text{if } i = r \end{cases}\]

and

\[ EA_{ij} = e(I)A_{ij} = \sum\limits_{k=1}^{m} e(I)_{ik}A_{kj}.\]

If \(i \neq r\), then \(e(I)A_{ij} = A_{ij}\), as we have shown before. If \( i = r \), then the only non-zero terms of the sum above are \(e(I)_{rr}A_{rj}\) and \(e(I)_{rs}A_{sj}\). Since \(I_{ss} = 1\) and \(e(I)_{rs} = cI_{ss}\), \(e(I)_{rs} = c\). Then the value of the sum above if \(i=r\) is \(A_{rj} + cA_{sj}\).