# Prove that elementary matrices perform row operations

How to prove that elementary matrices actually perform their intended row operations: multiplying by a constant, adding a multiple of one row to another, and switching two rows?

I've seen examples of their use, but I haven't seen a proof for an $n$ by $n$ matrix.

• Proof of what? – Michael Joyce Feb 7 '16 at 15:39
• Do you want to prove that every invertible matrix is a product of elementary matrices? – Akiva Weinberger Feb 7 '16 at 15:43
• Or that the kernel of the map given by left multiplication by a given matrix is invariant under these operations? – Travis Feb 7 '16 at 15:50
• Or that any row operation is multiplication by some elementary matrix? – Omnomnomnom Feb 7 '16 at 15:58
• Maybe you want to have a look at the Gauss algorithm? – noctusraid Feb 7 '16 at 16:02

The key is to understand what matrix matrix multiplication really does. Consider the problem of computing the product $C = AB$, where all matrices are square of dimension $n$ for the sake of simplicity. By definition we have \begin{equation} c_{i,j} = \sum_{k=1}^n a_{ik}b_{k,j} \end{equation} for each component $c_{i,j}$. If we zoom out and consider the $i$ row of $C$ using notation adapted from MATLAB we have \begin{equation} c_{i,1:n} = \sum_{k=1}^n a_{ik}b_{k,1:n}. \end{equation} This shows that the $i$th row of $C$ is obtained by forming linear combinations of all $n$ rows of $B$ using the coefficient along the $i$th row of $A$ as weights. In particular, if $a_{ik} = 0$, then the $k$ row of $B$ is not involved in the computation of the $i$th row of $C$.
In particular, let $E$ be the elementary matrix that adds $\beta$ times the first row of an $n \times k$ matrix to the second row. We will know that $E$ does what it's supposed to do if, for an $n \times k$ matrix $A$, we have $$(EA)[i,j] = \begin{cases} a_{ij} & i \neq 2\\ \beta a_{1j} + a_{2j} & i =2 \end{cases} \tag{*}$$ So, now I'm going to say what my matrix $E$ is, then show that $E$ does what it's supposed to, which is to say that it satisfies $(*)$.
My $E$ will be given by $$e_{ij} = \begin{cases} 1 & i=j\\ \beta & i=2, \quad j=1\\ 0 & \text{otherwise} \end{cases}$$ Pro-tip: to find $E$ for a given row operation, just apply the row-operation to the identity matrix and use the matrix that you get.
Now, let's see what $(EA)[i,j]$ is, using the definition of matrix multiplication: first, the case that $i \neq 2$. Note that $e_{ik} \neq 0$ only if $i = k$. So, we have $$(EA)[i,j] = \sum_{k=1}^n e_{ik}a_{kj} = e_{ii}a_{ij} = a_{ij}$$ Now, if $i = 2$, we have $e_{ik} \neq 0$ except at $i = 1$ and at $i=2$. So, we find $$(EA)[2,j] = \sum_{k=1}^n e_{ik}a_{kj} = e_{21}a_{1j} + e_{22}a_{2j} = \beta a_{aj} + a_{2j}$$ So, we see that the matrix $E$ indeed does exactly what it was supposed to do.