Permutation matrix and LU decomposition

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?

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$.
• 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}$. – user1131274 Dec 26 '16 at 15:13
• $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. – Little Rookie Dec 26 '16 at 15:29
• 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$ – user1131274 Dec 26 '16 at 15:41