MHB LU decomposition: Total pivoting

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Decomposition
AI Thread Summary
The discussion focuses on determining the LU decomposition of a matrix with total pivoting, specifically for the matrix A. The participants detail the steps taken to perform row and column exchanges to achieve the upper triangular matrix U and discuss the definitions of permutation matrices P and P_i. There is confusion regarding the correct formulation of the matrix L and its relationship with the permutation matrices and inverses of the Gaussian elimination steps. Ultimately, it is clarified that the relationship should be expressed as LU = PAQ, where P and Q account for the row and column permutations, respectively. The final consensus is that the calculations for L are correct, and the relationship between the matrices is properly established.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

I want to determine the LU decomposition of
$A=\begin{pmatrix}0 & 2 & 1\\1 & 10 & 1 \\1 & 1 & 1\end{pmatrix}$ with total pivoting. I have done the following:

The biggest element of the whole matrix is $10$, so we exchange the first two rows and the first two columns and then we get $\begin{pmatrix}10 & 1 & 1 \\2 & 0 & 1\\1 & 1 & 1\end{pmatrix}$.
Applying now the Gauss algorithm we get $\begin{pmatrix}10 & 1 & 1 \\0 & -\frac{1}{5} & \frac{4}{5}\\0 & \frac{9}{10} & \frac{9}{10}\end{pmatrix}$.
The biggest element of the submatrix is $\frac{9}{10}$ and so we exchange the last two rows and get: $\begin{pmatrix}10 & 1 & 1 \\ 0 & \frac{9}{10} & \frac{9}{10} \\ 0 & -\frac{1}{5} & \frac{4}{5} \end{pmatrix}$. Now we apply the Gauss algorithm and get: $\begin{pmatrix}10 & 1 & 1 \\ 0 & \frac{9}{10} & \frac{9}{10} \\ 0 & 0 & 1 \end{pmatrix}$.

The matrix $U$ is the resulting matrix, $U=\begin{pmatrix}10 & 1 & 1 \\ 0 & \frac{9}{10} & \frac{9}{10} \\ 0 & 0 & 1 \end{pmatrix}$.

The matrix $L$ is $L=P\cdot P_0\cdot G_1^{-1}\cdot P_1\cdot G_2^{-1}$, or not? (Wondering)

The matrices $G_i^{-1}$ are defined as:
$$G_1^{-1}=\begin{pmatrix}1 & 0 & 0 \\\frac{2}{10} & 1 & 0\\\frac{1}{10} & 0 & 1\end{pmatrix} \ \text{ and } \ G_2^{-1}=\begin{pmatrix}1 & 0 & 0 \\0 & 1 & 0\\0 & -\frac{2}{9} & 1\end{pmatrix}$$ or not? (Wondering)


Are the matrices $P_i$ defined as follows?
$$P_0=\begin{pmatrix}1 & 0 & 0 \\0 & 1 & 0\\0 & 0 & 1\end{pmatrix}$$ since this describes the step at which we exchanged the first two rows and the first two columns. (Wondering)
$$P_1=\begin{pmatrix}1 & 0 & 0 \\0 & 0 & 1\\0 & 1 & 0\end{pmatrix}$$ since this describes the step at which we exchanged the two last rows. (Wondering) If these are correct, it doesn't hold that $LU=PA$, does it? (Wondering)
 
Last edited by a moderator:
Mathematics news on Phys.org
mathmari said:
Are the matrices $P_i$ defined as follows?
$$P_0=\begin{pmatrix}1 & 0 & 0 \\0 & 1 & 0\\0 & 0 & 1\end{pmatrix}$$ since this describes the step at which we exchanged the first two rows and the first two columns. (Wondering)
$$P_1=\begin{pmatrix}1 & 0 & 0 \\0 & 0 & 1\\0 & 1 & 0\end{pmatrix}$$ since this describes the step at which we exchanged the two last rows.

Hey mathmari!

It should be clear that
$$P_0=\begin{pmatrix}1 & 0 & 0 \\0 & 1 & 0\\0 & 0 & 1\end{pmatrix}$$
cannot be correct. It is the identity matrix, isn't it? (Worried)

Let's define instead:
$$P_0=\begin{pmatrix}0 & 1 & 0 \\1 & 0 & 0\\0 & 0 & 1\end{pmatrix}$$
This is the matrix that swaps either 2 rows or 2 columns, isn't it?
And it's its own inverse. That is, $P_0^{-1}=P_0$.

Swapping 2 rows is a permutation on the left.
However, swapping 2 columns is a permutation on the right.
So after those 2 permutations we have $P_0 A P_0$. (Thinking)

mathmari said:
If these are correct, it doesn't hold that $LU=PA$, does it?

Shouldn't it be $LU=PAQ$, where $P$ reorders the rows of $A$ and $Q$ reorders the columns of $A$? (Wondering)

mathmari said:
The matrix $L$ is $L=P\cdot P_0\cdot G_1^{-1}\cdot P_1\cdot G_2^{-1}$, or not?

I don't think so. We have:
$$R = G_2 \cdot P_1 \cdot G_1 \cdot P_0 \cdot A \cdot P_0$$
From this we have to deduce $L$ such that:
$$LR = PAQ$$
Don't we? (Wondering)
 
We have $R=\begin{pmatrix}10 & 1 & 1 \\ 0 & \frac{9}{10} & \frac{9}{10} \\ 0 & 0 & 1 \end{pmatrix}$.

Since $R = G_2 \cdot P_1 \cdot G_1 \cdot P_0 \cdot A \cdot P_0$ we get that $$L\cdot G_2 \cdot P_1 \cdot G_1 \cdot P_0 \cdot A \cdot P_0=P\cdot A\cdot P_0 \Rightarrow L =P\cdot P_0^{-1}\cdot G_1^{-1}\cdot P_1^{-1}\cdot G_2^{-1} \Rightarrow L=P_1\cdot G_1^{-1}\cdot P_1\cdot G_2^{-1}$$

We have the matrices $$G_1^{-1}=\begin{pmatrix}1 & 0 & 0 \\\frac{2}{10} & 1 & 0\\\frac{1}{10} & 0 & 1\end{pmatrix} \ \text{ and } \ G_2^{-1}=\begin{pmatrix}1 & 0 & 0 \\0 & 1 & 0\\0 & -\frac{2}{9} & 1\end{pmatrix}$$ We also have the matrices $$P_0=\begin{pmatrix}0 & 1 & 0 \\1 & 0 & 0\\0 & 0 & 1\end{pmatrix} \ \text{ and } \ P_1=\begin{pmatrix}1 & 0 & 0 \\0 & 0 & 1\\0 & 1 & 0\end{pmatrix}$$

So we get $$L=\begin{pmatrix}1 & 0 & 0 \\0 & 0 & 1\\0 & 1 & 0\end{pmatrix}\begin{pmatrix}1 & 0 & 0 \\\frac{2}{10} & 1 & 0\\\frac{1}{10} & 0 & 1\end{pmatrix}\begin{pmatrix}1 & 0 & 0 \\0 & 0 & 1\\0 & 1 & 0\end{pmatrix}\begin{pmatrix}1 & 0 & 0 \\0 & 1 & 0\\0 & -\frac{2}{9} & 1\end{pmatrix}=\begin{pmatrix}1 & 0 & 0 \\ \frac{1}{10} & 1 & 0 \\ \frac{1}{5} & -\frac{2}{9} & 1\end{pmatrix}$$

Is this correct? (Wondering)
 
mathmari said:
Since $R = G_2 \cdot P_1 \cdot G_1 \cdot P_0 \cdot A \cdot P_0$ we get that $$L\cdot G_2 \cdot P_1 \cdot G_1 \cdot P_0 \cdot A \cdot P_0=P\cdot A\cdot P_0 \Rightarrow L =P\cdot P_0^{-1}\cdot G_1^{-1}\cdot P_1^{-1}\cdot G_2^{-1} \Rightarrow L=P_1\cdot G_1^{-1}\cdot P_1\cdot G_2^{-1}$$

How did you get $P\cdot P_0^{-1}=P_1$ ?
I think that the $P$ we will get, will be incorrect. (Worried)

mathmari said:
So we get $$L=\begin{pmatrix}1 & 0 & 0 \\0 & 0 & 1\\0 & 1 & 0\end{pmatrix}\begin{pmatrix}1 & 0 & 0 \\\frac{2}{10} & 1 & 0\\\frac{1}{10} & 0 & 1\end{pmatrix}\begin{pmatrix}1 & 0 & 0 \\0 & 0 & 1\\0 & 1 & 0\end{pmatrix}\begin{pmatrix}1 & 0 & 0 \\0 & 1 & 0\\0 & -\frac{2}{9} & 1\end{pmatrix}=\begin{pmatrix}1 & 0 & 0 \\ \frac{1}{10} & 1 & 0 \\ \frac{1}{5} & -\frac{2}{9} & 1\end{pmatrix}$$

Is this correct?

Yes. (Nod)
 
Klaas van Aarsen said:
How did you get $P\cdot P_0^{-1}=P_1$ ?
I think that the $P$ we will get, will be incorrect. (Worried)

Do we not have $P=P_1P_0 \Rightarrow PP_0^{-1}=P_1$ ? (Wondering)
 
mathmari said:
Do we not have $P=P_1P_0 \Rightarrow PP_0^{-1}=P_1$ ?

Ah yes, $P$ has to be whatever row permutation it takes to ensure that $L$ is a lower triangular matrix.

We have:
$$L =P\cdot P_0^{-1}\cdot G_1^{-1}\cdot P_1^{-1}\cdot G_2^{-1}$$
And $G_1^{-1}$ and $G_2^{-1}$ are lower triangular.
Since $P_1\cdot G_1^{-1}\cdot P_1^{-1}$ is a conjugation, it is lower triangular as well.
That is, we swap 2 rows and we also swap the corresponding 2 columns, so that the triangular form is retained. (Nerd)

So we can indeed pick $\smash{P\cdot P_0^{-1}=P_1}$.
I must have made a calculation mistake earlier. (Blush)
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...

Similar threads

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