Monday, November 25, 2019

linear algebra - 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


Answer



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$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...