$UL$ factorization from $LU$ factorization with permutation matrix

Question

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.

Answer 1

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}$$