Let $A$ be a square matrix. Then there exists a permutation matrix $P$ such that $A=PLU$, where $L$ is a lower triangular matrix and $U$ is an upper triangular matrix. To further ensure the uniqueness, we assume that the main diagonal of $L$ (or $U$) to be 1. So, the question is, is the permutation matrix unique, i.e., can we find another $P'\ne P$ such that $A=PLU=P'L'U'$ where $L', U'$ are still triangular matrix? If yes, what is the condition for the uniqueness?
$\endgroup$ 22 Answers
$\begingroup$For each nonsingular matrix A, there exists a permutation matrixP such that PA possesses an LU factorization PA = LU.
Therefore, since the LU decomposition is unique -assuming the diagonal of L must be one- P will also be unique.
$\endgroup$ $\begingroup$No, the permutaion is not unqiue. Here is an example:$$ \begin{pmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix} =\underbrace{\begin{pmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix}}_{L}\underbrace{\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix}}_{U}\\ \underbrace{\begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}}_{P}\begin{pmatrix} 1 & 0 & 0\\ 1 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix} =\begin{pmatrix} 1 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix} =\underbrace{\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix}}_{L}\underbrace{\begin{pmatrix} 1 & 1 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix}}_{U} $$where $\displaystyle P$ is the permutation matrix that switches first and second row. It follows that we can find a different permutation matrix but has a different LU-decomposition.
$\endgroup$
