MHB LR decomposition with column pivoting

AI Thread Summary
The discussion focuses on performing LR decomposition with column pivoting on the matrix A. The initial steps involve permuting rows and applying the Gauss algorithm to derive matrices L and R. Participants clarify the definition and calculation of permutation matrices P_0 and P_1, which are essential for ensuring the equality LR = PA holds true. A mistake in calculating L is identified, leading to a corrected formulation that satisfies the equation. The final matrices L and R are confirmed to be accurate, concluding the discussion positively.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Mathematics news on Phys.org
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)
 
Klaas van Aarsen said:
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)
 
Last edited by a moderator:
mathmari said:
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)
 
Klaas van Aarsen said:
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)
 
mathmari said:
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)
 
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
 
mathmari said:
Ah so we exchange at the identity matrix the rows that we want to permutate at the matrix $A$, right?

Yes. (Nod)

mathmari said:
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)
 
Klaas van Aarsen said:
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)
 
  • #10
Yep. All correct now. (Happy)
 
  • #11
Klaas van Aarsen said:
Yep. All correct now. (Happy)

Great! Thank you! (Mmm)
 

Similar threads

Replies
5
Views
2K
Replies
2
Views
2K
Replies
4
Views
1K
Replies
21
Views
4K
Replies
16
Views
4K
Replies
9
Views
3K
Back
Top