# 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? Commented Feb 7, 2016 at 15:39
• Do you want to prove that every invertible matrix is a product of elementary matrices? Commented Feb 7, 2016 at 15:43
• Or that the kernel of the map given by left multiplication by a given matrix is invariant under these operations? Commented Feb 7, 2016 at 15:50
• Or that any row operation is multiplication by some elementary matrix? Commented Feb 7, 2016 at 15:58
• Maybe you want to have a look at the Gauss algorithm? Commented Feb 7, 2016 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 $$c_{i,j} = \sum_{k=1}^n a_{ik}b_{k,j}$$ for each component $c_{i,j}$. If we zoom out and consider the $i$ row of $C$ using notation adapted from MATLAB we have $$c_{i,1:n} = \sum_{k=1}^n a_{ik}b_{k,1:n}.$$ 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$.

The case of the elementary matrices is now easy to understand as the vast majority of the entries are either zeros or ones.

Let's go through an example of proving that one kind of elementary matrix does what it's supposed to.

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.