LR decomposition with column pivoting

In summary: L$ is the permutation matrix that switches the first two rows and the last $L$ is the permutation matrix that switches the last two rows, right?Yes, that's correct.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! :eek:

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
  • #2
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)
 
  • #3
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:
  • #4
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)
 
  • #5
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)
 
  • #6
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)
 
  • #7
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)
 
  • #8
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)
 
  • #9
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)
 

FAQ: LR decomposition with column pivoting

1. What is LR decomposition with column pivoting?

LR decomposition with column pivoting is a matrix factorization technique used to decompose a square matrix A into a lower triangular matrix L, an upper triangular matrix R, and a permutation matrix P. This technique is often used in numerical linear algebra to solve systems of linear equations and to find the inverse of a matrix.

2. Why is column pivoting necessary in LR decomposition?

Column pivoting is necessary in LR decomposition because it helps to reduce the numerical errors that can occur during the decomposition process. It also helps to improve the stability and accuracy of the solutions obtained from the decomposition.

3. How does LR decomposition with column pivoting differ from regular LR decomposition?

The main difference between LR decomposition with column pivoting and regular LR decomposition is that in column pivoting, the columns of the matrix A are permuted before the decomposition process begins. This helps to improve the numerical stability and accuracy of the decomposition, whereas regular LR decomposition does not involve any column pivoting.

4. What are the advantages of using LR decomposition with column pivoting?

Some advantages of using LR decomposition with column pivoting include improved numerical stability and accuracy, reduced computational complexity, and better conditioning of the matrices involved. It also helps to avoid the occurrence of zero pivots, which can lead to division by zero errors.

5. In what applications is LR decomposition with column pivoting commonly used?

LR decomposition with column pivoting is commonly used in various applications such as solving systems of linear equations, finding the inverse of a matrix, and solving least squares problems. It is also used in numerical methods for solving differential equations, image processing, and data analysis.

Similar threads

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