# Is the permutation matrix P of PLU decomposition unique?

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?

• In general, no. One must assume more about $A$ for the LU decomposition to be unique. One example is if there exists an LDU decomposition of $A$ with diagonal identically one. – Math1000 Jun 14 '20 at 9:42
• @Math100, hi thanks for the reply, the LU decomposition of A is unique because we assume the diagonal of L must be one. – qjgods Jun 14 '20 at 11:19

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.