0
$\begingroup$

Let $A$ be a square matrix. Then there exist a permutation matrix $P$ such that $PA$ = $LU$ , where $L$ is a lower triangular matrix and $U$ is a upper triangular matrix.

Here, the permutation matrix $P$ is the row swappings applied to $A$ during Gaussian Elimination.

Can someone explain why is this true?

$\endgroup$
0
$\begingroup$

In LU decomposition you convert A into an upper triangular matrix and the operations you do can be expressed by lower triangular matrices. Lets say for argument sake there are no swap required so $L_kL_{k-1}...L_1A=U$. Now product of bunch of lower triangular matirces is lower triangular and inverse of lower triangular matrix is also lower triangular so $A=LU$. Now if swaps were required in the decomposition and you knew them beforehand and then you can apply them first and do your decomposition(without any swaps required now) so if P encodes all the swaps then you have $PA=LU$.

$\endgroup$
  • $\begingroup$ Yes, i understand what you have said. But i don't understand why doing the known required row swappings beforehand is the same as that doing them later during Gaussian Elimination. $\endgroup$ – Little Rookie Dec 26 '16 at 14:59
  • $\begingroup$ This is because of the way we perform LU. For example let say I have $A\in R^{4*4}$ and I reduced row 1 and row 2 with let say $L_{12}$ and realized that I now have to swap row 3 and 4 with lets say $P_{34}$. Now note that $P_{34}L_{12}=L_{12}P_{34}$. Because the only non zero entries in $L_{12}$ exist in $a_{11},a_{21}$ and $a_{22}$. $\endgroup$ – user1131274 Dec 26 '16 at 15:13
  • $\begingroup$ $a_{33}$ and $a_{44}$ are also non-zero entries. I noticed that $P_{34}L_{12} = L_{12}P_{34}$. But, i still can't think why is it true in general. $\endgroup$ – Little Rookie Dec 26 '16 at 15:29
  • $\begingroup$ yeah you are right $a_{33}=a_{44}=1$. But as you can see they commute so you can bring all permutation matrices in front and use the fact that product of permutation matrices is a permutation matrix. Use induction. For example : $L_3P_2L_2P_1L_1=L_3L_2L_1P_2P_1=LP$. So $LPA=U \rightarrow PA=L'U$ $\endgroup$ – user1131274 Dec 26 '16 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.