Is the permutation matrix P of PLU decomposition unique?

Question

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?

Answer 1

For each nonsingular matrix A, there exists a permutation matrix P 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.

Answer 2

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.