ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 03 Jun 2021 21:04:36 +0200Finding a permutation matrix associated to a non-singular matrixhttps://ask.sagemath.org/question/57433/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.1007%2F978-3-319-70953-6_1 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)?Thu, 03 Jun 2021 18:42:03 +0200https://ask.sagemath.org/question/57433/finding-a-permutation-matrix-associated-to-a-non-singular-matrix/Answer by tmonteil for <p>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 <a href="https://link.springer.com/chapter/10.1007/978-3-319-70953-6_1">https://link.springer.com/chapter/10....</a> theorem 1.1.10)</p>
<blockquote>
<p>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)?</p>
</blockquote>
https://ask.sagemath.org/question/57433/finding-a-permutation-matrix-associated-to-a-non-singular-matrix/?answer=57434#post-id-57434The 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?Thu, 03 Jun 2021 19:41:13 +0200https://ask.sagemath.org/question/57433/finding-a-permutation-matrix-associated-to-a-non-singular-matrix/?answer=57434#post-id-57434Comment by klaaa for <p>The LU method does that:</p>
<pre><code>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
</code></pre>
<p>For the doc, see</p>
<pre><code>sage: A.LU?
</code></pre>
https://ask.sagemath.org/question/57433/finding-a-permutation-matrix-associated-to-a-non-singular-matrix/?comment=57436#post-id-57436Thank you for the answer. But in my question we need A=LPU instead of A=PLU.Thu, 03 Jun 2021 21:04:36 +0200https://ask.sagemath.org/question/57433/finding-a-permutation-matrix-associated-to-a-non-singular-matrix/?comment=57436#post-id-57436