# How to find the correct order to multiply elimination matrices?

Let's say I have the following matrix $A \in \mathbb{R}^{4\times4}$

$$A = \begin{bmatrix} a & a & a & a \\ a & b & b & b \\ a & b & c & c \\ a & b & c & d \end{bmatrix}$$

And I perform the following Row Operations (which are really just matrix multiplications) to reduce $A$ into an upper triangular matrix $U$

1. $R_2 - (l_{21} = 1)R_1$ ($\text{corresponds to }E_{21})$
2. $R_3 - (l_{31} = 1)R_2$ ($\text{corresponds to }E_{31})$
3. $R_4 - (l_{41} = 1)R_3$ ($\text{corresponds to }E_{41})$
4. $R_3 - (l_{32} = 1)R_2$ ($\text{corresponds to }E_{32})$
5. $R_4 - (l_{42} = 1)R_3$ ($\text{corresponds to }E_{42})$
6. $R_4 - (l_{43} = \frac{c-a}{c-b})R_3$ ($\text{corresponds to }E_{43})$

After performing all these row operations we arrive at $$U = \begin{bmatrix} a & a & a & a \\ 0 & b-a & b-a & b-a \\ 0 & 0 & c-b & c-b \\ 0 & 0 & 0 & d-c \end{bmatrix}$$

But now if I want to find the elimination matrix $E$, that does all of these row operation in one step? How do I go about finding it? To re-iterate, I'm trying to find a $E$ such that $EA = U$.

I understand $E$ would be the product of the elimination matrices used in the row operations, but in what order would the matrices be multiplied? The order being of importance as matrix multiplication isn't commutative.

As it turns out, $E \neq E_{21}E_{31}E_{41}E_{32}E_{42}E_{43}$

Is there a theorem/general rule that can be used to find the correct order to multiply the matrices used in the row operations, so that a single elimination matrix can be found without trying every possible permutation?

A Second Example, $B \in \mathbb{R}^{3\times3}$

$$B = \begin{bmatrix} 1 & 4 & 0 \\ 4 & 12 & 4 \\ 0 & 4 & 0 \\ \end{bmatrix}$$

The following row operations are performed to transform $B$ into an upper triangular $U$

1. $R_2 - (l_{21} = 4)R_1$ $\text{(corresponds to } E_{21})$
2. $R_3 - (l_{32} = -1)R_2$ $\text{(corresponds to } E_{32})$

We arrive at

$$U = \begin{bmatrix} 1 & 4 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \\ \end{bmatrix}$$

In this case, $E_{32}E_{21}B \neq U$, however $E_{21}E_{32}B = U$, going against the convention in example 1

• You don't need to write $\mathbb{R^{4\ x\ 4}}$; you can write $\mathbb R^{4\times 4}$. The superscript is set as $4\times 4$. The superscript should not be within \mathbb{}; only the R should be; thus $\mathbb R^n$ rather than $\mathbb{R^n}$. $\qquad$ – Michael Hardy Aug 5 '16 at 18:31

Perhaps I am misunderstanding something, but here is the answer I think you're looking for. Suppose that we first conduct the row operation ${\bf R}_1$ on the matrix ${\bf A}$, then the resulting matrix is ${\bf A}_1 = {\bf R}_1 {\bf A}$. The next row operation ${\bf R}_2$ is then applied to ${\bf A}_1$, resulting in ${\bf A}_2 = {\bf R}_2 {\bf A}_1 = {\bf R}_2 {\bf R}_1 {\bf A}$. Continuing this way, you can see that if you apply $n$ row operations ${\bf R}_1, \ldots ,{\bf R}_n$, the result will be ${\bf A}_n = {\bf R}_n {\bf R}_{n-1} \cdots {\bf R}_1 {\bf A}$, showing you the order in which to multiply the operations ${\bf R}_i$.
• please see my second example which I have included in the OP specifically for your answer. In the second example I performed row operation (1), before row operation (2), however multiplying the elimination matrices the way you indicated $A_n = R_nR_{n-1}....R_1A$, would've corresponded to the following $U = E_{32}E_{21}A$, which is incorrect as $U = E_{21}E_{32}A$ – Perturbative Aug 5 '16 at 18:38
• @Perturbative you've made a mistake in your second example. A correct computation yields $E_{32}E_{12}B = U$. – Omnomnomnom Aug 5 '16 at 19:29
• @Tom, is there a reason in your $A_n = R_nR_{n-1}...R_1A$ example, why only left multiplication is used/preferred instead of right multiplication? – Perturbative Aug 6 '16 at 14:54
• @Perturbative Let ${\bf A} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ and write out a few explicit examples yourself of doing row operations on ${\bf A}$ as matrices; can you produce these by multiplying on either side? For example, suppose you wanted $(2 \times \text{row 1}) + (\text{row 2})$ put in place of row 2; as a matrix multiplied on the left of ${\bf A}$, this would be ${\bf R} = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix}$; can you produce a matrix that would do this by multiplication on the right of ${\bf A}$? – Tom Aug 8 '16 at 13:28