<s>[INST] 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?
 [/INST] 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.
</s>