# Finding a permutation matrix associated to a non-singular matrix

Let $A$ be a non-singular complex matrix. Then there exist a decomposition A=LPU where L is lower triangular, U is upper triangular and P is a uniquely determined permutation matrix just depending on A. Similarly, there exists a decomposition A=L' P' L' , where L' is a lower triangular matrix and P' is a uniquely determined permutation just depending on A. (see for example https://link.springer.com/chapter/10.... theorem 1.1.10)

Question: Is there a quick way to determine the permutation matrices P and P' for a given non-singular matrix A (we can assume that A has integer entries if that helps)?

edit retag close merge delete

Sort by ยป oldest newest most voted

The LU method does that:

sage: A = random_matrix(ZZ,4)
sage: A
[ 0  1 -1  1]
[ 0 -1  2  0]
[ 1 -9 -8 -1]
[ 2  0  0 -2]
sage: A.LU()
(
[0 0 0 1]  [     1      0      0      0]  [   2    0    0   -2]
[0 0 1 0]  [   1/2      1      0      0]  [   0   -9   -8    0]
[0 1 0 0]  [     0    1/9      1      0]  [   0    0 26/9    0]
[1 0 0 0], [     0   -1/9 -17/26      1], [   0    0    0    1]
)
sage: P,L,U = A.LU()
sage: P*L*U
[ 0  1 -1  1]
[ 0 -1  2  0]
[ 1 -9 -8 -1]
[ 2  0  0 -2]
sage: P*L*U == A
True


For the doc, see

sage: A.LU?

more

Thank you for the answer. But in my question we need A=LPU instead of A=PLU.

( 2021-06-03 21:04:36 +0200 )edit