# Simultaneous LU and UL decomposition

It is known that a square, invertible matrix $\mathbf{A}$ always has a LU decomposition, after possibly a column permutation, i.e., $$\mathbf{A} \mathbf{P}_C = \mathbf{L}_1 \mathbf{U}_1$$ where $\mathbf{P}_C$ is a permutation matrix, $\mathbf{L}_1$ is a lower triangular matrix with nonzero diagonal elements and $\mathbf{U}_1$ is an upper triangular matrix with nonzero diagonal elements.

Analogously, $\mathbf{A}$ always has a UL decomposition, after possibly a row permutation, i.e., $$\mathbf{P}_R \mathbf{A} = \mathbf{U}_2 \mathbf{L}_2$$ where $\mathbf{P}_R$ is a permutation matrix, $\mathbf{U}_2$ is an upper triangular matrix with nonzero diagonal elements and $\mathbf{L}_2$ is a lower triangular matrix with nonzero diagonal elements.

Now, I can neither prove nor disprove the following conjecture.

Conjecture: For every square, invertible matrix $\mathbf{A}$, there exist a row and a column permutation such that a LU and a UL decomposition are simultaneously possible, i.e.: $$\mathbf{P}_R \mathbf{A} \mathbf{P}_C = \mathbf{L}_1 \mathbf{U}_1 = \mathbf{U}_2 \mathbf{L}_2.$$

Can somebody help me?