$UL$ factorization from $LU$ factorization with permutation matrix The answer at A = UL factorization shows that, if a matrix $A$ has an $LU$ factorization, then one can also get a $UL$ factorization. But it does so by starting with an $LU$ factorization not of $A$ but of the matrix $B = PAP$, where $P$ is the permutation matrix \begin{equation*}\begin{pmatrix}0 & \dots & 0 & 1 \\ 0 & \dots & 1 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \dots & 0 & 0\end{pmatrix}\end{equation*} My question is how do we know that an $LU$ factorization of $B$ actually exists? It does not seem to easily follow just from the fact that $A$ has an $LU$ factorization. Thanks in advance for assistance.
 A: UL factorization from LU factorization with permutation matrix
According to the preprint Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix, a both necessary and sufficient condition for the existence of an LU factorization of a square $n\times n$ matrix $A$ is given by:
$$(1)\,\text{$A$ has LU factorization} \iff \forall k\colon\, \operatorname{rk}(A[\colon k,\, \colon k]) \ge \operatorname{rk}(A[\colon k,\, \colon n]) + \operatorname{rk}(A[\colon n,\, \colon k]) -k$$
Where $A[\colon i, \colon j]$ is the matrix consisting of the first $i$ rows and $j$ columns of $A$. We shall see that:
$$(2)\,\text{$A$ has UL factorization} \iff \forall k\colon\, \operatorname{rk}(A[k\colon,\, k\colon]) \ge \operatorname{rk}(A[k\colon,\, n\colon]) + \operatorname{rk}(A[n\colon,\, k\colon]) -k$$
Where $A[i\colon, j\colon]$ is the matrix consisting of the last $i$ rows and $j$ columns of $A$.
Now, without further notice, given any $k\times l$ matrix  $X$ let $\overline X = P_k^T X P_l$, be the flip of $X$, where $(P_n)_{ij}=\delta_{i, n-i}$ is the exchange matrix of size $n$. We will show:
$$(3)\qquad \text{$A$ has UL factorization} \iff \text{$\overline A$ has LU factorization}$$
So the existence of an LU factorization of $B=\overline A$ is in fact equivalent to $A$ having a UL factorization.

Proof of (2): Note that the way the preprint proves (1) is by splitting $A$ into a block matrix at index $k$ for every $k=1 \ldots n$
$$
A =\left[\begin{array}{cc}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{array}\right]
=\left[\begin{array}{ll}
L_{11}U_{11} & L_{11}U_{12} \\
L_{21}U_{12} & L_{21}U_{12} + L_{22} U_{22}
\end{array}\right]
=\left[\begin{array}{cc}
L_{11} & 0 \\
L_{21} & L_{22}
\end{array}\right]\left[\begin{array}{cc}
U_{11} & U_{12} \\
0 & U_{22}
\end{array}\right]
=LU
$$
and then apply rank inequalities of the type $\operatorname{rk}(XY) \ge \operatorname{rk}(X) + \operatorname{rk}(Y) -k$ to the blocks.
Note that $A=LU$ is equivalent to $P^TAP = (P^T L P)(P^T U P)$, i.e. $\overline A = \overline L \cdot \overline U$, hence
$$
\overline A =\left[\begin{array}{cc}
\overline A_{22} & \overline A_{21} \\
\overline A_{12} & \overline A_{11}
\end{array}\right]
=\left[\begin{array}{ll}
\overline L_{21}\overline U_{12} + \overline L_{22} \overline U_{22} & \overline L_{21}\overline U_{12} \\
\overline L_{11}\overline U_{12} & \overline L_{11}\overline U_{11}
\end{array}\right]
=\left[\begin{array}{cc}
\overline L_{22} & \overline L_{21} \\
0 & \overline L_{11}
\end{array}\right]\left[\begin{array}{cc}
\overline U_{22} & 0 \\
\overline U_{12} & \overline U_{11}
\end{array}\right]
=\overline L \overline U
$$
which is a block UL factorization! So we can in principle apply the exact same argumentation of the proof of (1) given in the preprint "module flipping" to conclude (2).

Proof of (3): This now follows immediately because conditions (1) and (2) are equivalent modulo flipping, since for any matrix $X$ holds $\operatorname{rk}(X) = \operatorname{rk}(\overline X)$, and the submatrices in the block decomposition of $\overline A$ are precisely the flips of the submatrices of the block decomposition of $A$ since
$$\begin{aligned}
\forall ij:\; (P_n^T AP_n)[\colon i,\, \colon j] = P_{i}^TA[n-i\colon,\, n-j\colon] P_{j}
\end{aligned}$$
I.e. $\overline{A}[\colon i,\, \colon j] = \overline{A[n-i\colon,\, n-j\colon]}$, which allows us to conclude
$$\begin{aligned}
   &\text{$A$ has LU factorization} 
\\ &\iff \forall k\colon\, \operatorname{rk}(A[\colon k,\, \colon k]) \ge \operatorname{rk}(A[\colon k,\, \colon n]) + \operatorname{rk}(A[\colon n,\, \colon k]) -k
\\&\iff \forall k\colon\, \operatorname{rk}(\overline{A[\colon k,\, \colon k]}) \ge \operatorname{rk}(\overline{A[\colon k,\, \colon n]}) + \operatorname{rk}(\overline{A[\colon n,\, \colon k]}) -k
\\&\iff \forall k\colon\, \operatorname{rk}(\overline{A}[n-k\colon,\, n-k\colon ]) \ge \operatorname{rk}(\overline{A}[n-k\colon,\, n\colon]) + \operatorname{rk}(\overline{A}[n\colon,\, n-k\colon]) -k
\\&\iff \forall k\colon\, \operatorname{rk}(\overline{A}[k\colon,\, k\colon]) \ge \operatorname{rk}(\overline{A}[k\colon,\, n\colon]) + \operatorname{rk}(\overline{A}[n\colon,\, k\colon]) -k
\\ &\text{$\overline A$ has UL factorization} 
\end{aligned}$$
