LR decomposition with column pivoting

[mathmari]

Hey!

We have the matrix $$A=\begin{pmatrix}1 & -2 & 1 \\ 3 & -1 & 2 \\ -2 & -2 & 1\end{pmatrix}$$ I want to apply the LR decomposition with column pivoting. First we permutate the first two rows and we get $$A=\begin{pmatrix}3 & -1 & 2 \\ 1 & -2 & 1 \\ -2 & -2 & 1\end{pmatrix}$$ Then we apply the Gauss algorithm and we get $$A=\begin{pmatrix}3 & -1 & 2 \\ 0 & -5/3 & 1/3 \\ 0 & -8/3 & 7/3\end{pmatrix}$$ Then the largest value of the submatrix in absolute value is $8/3$ so we permutate the second and third row and we get $$A=\begin{pmatrix}3 & -1 & 2 \\ 0 & -8/3 & 7/3 \\ 0 & -5/3 & 1/3 \end{pmatrix}$$ Then we apply again the Gauss algorithm and we get $$A=\begin{pmatrix}3 & -1 & 2 \\ 0 & -8/3 & 7/3 \\ 0 & 0 & -9/8 \end{pmatrix}$$ From the above we get the matrices $$R=\begin{pmatrix}3 & -1 & 2 \\ 0 & -8/3 & 7/3 \\ 0 & 0 & -9/8 \end{pmatrix} \ \text{ and } \ L=\begin{pmatrix}1 & 0 & 0 \\ 1/3 & 1 & 0 \\ -2/3 & 5/8 & 1 \end{pmatrix}$$ To check if the results are correct we have to check if $LR=PA$, where $P=P_1P_0$ where $P_0$ and $P_1$ are the permutation matrices, or not? (Wondering)

How are the permutation matrices $P_0$ and $P_1$ defined in this case? $P_0$ is the one that permutated the first two rows and $P_1$ is the one that permutated the second and third row, right? But how can we calculate the matric $P$ ? (Wondering)

 

[I like Serena]

Hey mathmari!

Indeed, we have to check $LR=PA$. (Nod)

The permutation matrix that switches the first two rows is:
$$P_0=\begin{pmatrix}&1\\1\\&&1\end{pmatrix}$$
Similarly we can find $P_1$. Consequently the permutation matrix is:
$$P=P_1 P_0=\begin{pmatrix}1\\&&1\\&1\end{pmatrix}\begin{pmatrix}&1\\1\\&&1\end{pmatrix}
= \begin{pmatrix}&1\\&&1\\1\end{pmatrix}$$

I don't think your $L$ is correct though. (Worried)

 

[mathmari]

The permutation matrix that switches the first two rows is:
$$P_0=\begin{pmatrix}&1\\1\\&&1\end{pmatrix}$$
Similarly we can find $P_1$. Consequently the permutation matrix is:
$$P=P_1 P_0=\begin{pmatrix}1\\&&1\\&1\end{pmatrix}\begin{pmatrix}&1\\1\\&&1\end{pmatrix}
= \begin{pmatrix}&1\\&&1\\1\end{pmatrix}$$

Ah it is $\tilde{A}=P_0A \Rightarrow \tilde{A}A^{-1}=P_0$, isn't it ? (Wondering)

 

[I like Serena]

Why are the matrices $P_i$ defined like that? Is it maybe $\tilde{A}=P_0A \Rightarrow \tilde{A}A^{-1}=P_0$ ? (Wondering)

If we calculate $P_0 A$ with the $P_0$ I gave we get:
$$P_0 A=\begin{pmatrix}&1\\1\\&&1\end{pmatrix}\begin{pmatrix}1 & -2 & 1 \\ 3 & -1 & 2 \\ -2 & -2 & 1\end{pmatrix}
= \begin{pmatrix}3 & -1 & 2 \\ 1 & -2 & 1 \\ -2 & -2 & 1\end{pmatrix}$$
That's the matrix $A$ with the first two rows permutated isn't it? (Thinking)

Generally we can construct a matrix by looking at what the images of the unit vectors should be.
To switch the first two rows we want that $\begin{pmatrix}1\\0\\0\end{pmatrix}$ maps to $\begin{pmatrix}0\\1\\0\end{pmatrix}$, so that is what the first column of $P_0$ must be. We can find the other 2 columns in the same fashion. (Nerd)

 

[mathmari]

If we calculate $P_0 A$ with the $P_0$ I gave we get:
$$P_0 A=\begin{pmatrix}&1\\1\\&&1\end{pmatrix}\begin{pmatrix}1 & -2 & 1 \\ 3 & -1 & 2 \\ -2 & -2 & 1\end{pmatrix}
= \begin{pmatrix}3 & -1 & 2 \\ 1 & -2 & 1 \\ -2 & -2 & 1\end{pmatrix}$$
That's the matrix $A$ with the first two rows permutated isn't it? (Thinking)

Generally we can construct a matrix by looking at what the images of the unit vectors should be.
To switch the first two rows we want that $\begin{pmatrix}1\\0\\0\end{pmatrix}$ maps to $\begin{pmatrix}0\\1\\0\end{pmatrix}$, so that is what the first column of $P_0$ must be. We can find the other 2 columns in the same fashion. (Nerd)

So the permutation matrix is the identity matrix where we exchange two columns that corresponds to the two rows of the matrix $A$ that we want to permute? (Wondering)

 

[I like Serena]

So the permutation matrix is the identity matrix where we exchange two columns that corresponds to the two rows of the matrix $A$ that we want to permute? (Wondering)

It's actually the identity matrix with the first 2 rows exchanged, which is the same thing in this case. (Nerd)

 

[mathmari]

It's actually the identity matrix with the first 2 rows exchanged, which is the same thing in this case. (Nerd)

Ah so we exchange at the identity matrix the rows that we want to permutate at the matrix $A$, right? (Wondering)

I don't think your $L$ is correct though. (Worried)

Yes, the equality $LR=PA$ is not satisfied. (Worried)

I tried that again and I found the same $L$. I don't see where I have done a mistake. Have you maybe seen the mistake? (Wondering)

 

[I like Serena]

Ah so we exchange at the identity matrix the rows that we want to permutate at the matrix $A$, right?

Yes. (Nod)

Yes, the equality $LR=PA$ is not satisfied. (Worried)

I tried that again and I found the same $L$. I don't see where I have done a mistake. Have you maybe seen the mistake?

I think so yes.

Effectively we have calculated:
$$L_1P_1L_0P_0 A=R$$
We want to rearrange this to:
$$PA=LR$$
If I'm not mistaken you have effectively calculated $L=L_0^{-1}L_1^{-1}$. Is that the case? (Wondering)
However, that doesn't quite work because the permutation matrices are mixed with the lower triangular pivoting matrices. We have to disentangle them.Suppose we calculate $PA$ first and pivot afterwards?
That is, suppose we start with:
$$PA=\begin{pmatrix}3&-1&2\\-2&-2&1\\1&-2&1\end{pmatrix}$$
If we do the exact same pivoting, we will find the same $R$. But which $L$ do we find then? (Wondering)Alternatively, we can calculate $L$ directly since we must have:
$$LR=\begin{pmatrix}1&0&0\\?&1&0\\?&?&1\end{pmatrix}
\begin{pmatrix}3&-1&2\\&-\frac 83&\frac 73\\&&-\frac 98\end{pmatrix}
=\begin{pmatrix}3&-1&2\\-2&-2&1\\1&-2&1\end{pmatrix}=PA$$
Can we find the question marks? (Wondering)

 

[mathmari]

Effectively we have calculated:
$$L_1P_1L_0P_0 A=R$$
We want to rearrange this to:
$$PA=LR$$
If I'm not mistaken you have effectively calculated $L=L_0^{-1}L_1^{-1}$. Is that the case? (Wondering)

Ah yes the mistake is that I calculated $L=L_0^{-1}L_1^{-1}$. (Malthe)

We have the following: $$LR=PA \Rightarrow LL_1P_1L_0P_0 A=PA \Rightarrow LL_1P_1L_0P_0 =P \Rightarrow L=PP_0^{-1}L_0^{-1}P_1^{-1}L_1^{-1} \Rightarrow L=P_1L_0^{-1}P_1L_1^{-1}$$

From that we get $$L=\begin{pmatrix}1 & 0 & 0 \\ -2/3 & 1 & 0 \\ 1/3 & 5/8 & 1\end{pmatrix}$$ Using this $L$ and the matrix $R$ of post #1 we get $LR=PA$. So now it is correct, isn't it? (Wondering)

 

[I like Serena]

Yep. All correct now. (Happy)

 

[mathmari]

Yep. All correct now. (Happy)

Great! Thank you! (Mmm)