Given a possibly rectangular $m\times n$ matrix $A$ with rank $k$, the LUQ Decomposition takes the form:

$$A=\hat{L}\hat{U}\hat{Q}$$

where $\hat{L}$ is an invertible $m\times m$ matrix, $\hat{Q}$ is an invertible $n\times n$ matrix and $\hat{U}$ has the form:

$$\hat{U}=\left(\begin{array}{cc}{\hat{U}}_{11}& 0\\ 0& 0\end{array}\right),$$

where ${\hat{U}}_{11}$ is a $k\times k$ invertible upper triangular matrix.

To construct the LUQ decompostion, we start with a standard LU decomposition with pivoting determines matrices such that:

$$PAQ=LU,$$

where $P$ is a $m\times m$ permutation matrix, $Q$ is a $n\times n$ permutation matrix, $L$ is an invertible $m\times m$ lower triangular matrix, and $U$ is a $m\times n$ upper triangular matrix.

Lemma 1: There exists an $m\times m$ row permutation $R$ and a $n\times n$ column permutation $C$ of $U$ from the decomposition of $A$ above such that the matrix:

$$\overline{U}=RUC$$

has the form

$$\overline{U}=\left(\begin{array}{cc}{\overline{U}}_{11}& {\overline{U}}_{12}\\ {\overline{U}}_{21}& {\overline{U}}_{22}\end{array}\right)$$

where ${\overline{U}}_{11}$ is a square $r\times r$ matrix has a non-zero diagonal and ${\overline{U}}_{22}$ has a zero diagonal. Further, if $A$ has rank $k\le m\le n$ then $r\le k$.

Proof: (invoke some property of $U$ maintained during LU decomposition) █

We can plug this into our decomposition:

$$PAQ=LU$$

$$PAQ=L{R}^{T}RUC{C}^T$$

$$PAQ=L{R}^T\overline{U}{C}^T$$

$$PAQC=L{R}^T\overline{U}$$

Let’s let $Q$ and $L$ swallow these permutations: $\overline{Q}=QC$ and $\overline{L}=L{R}^T$, so that we have,

$$PA\overline{Q}=\overline{L}\overline{U}$$

where $\overline{Q}$ is an $n\times n$ permutation matrix and $\overline{L}$ is an invertible (not necessarily lower triangular) $m\times n$ matrix.

Now we will transform $\overline{U}$ into a block diagonal matrix by creating zeros below ${\overline{U}}_{11}$ and to the right of ${\overline{U}}_{11}$. Accomplish this by constructing an $m\times m$ matrix $K$ and a $n\times n$ matrix $S$ over the following form:

$$\overline{U}=\underset{K}{\underset{}{\left(\begin{array}{cc}I& 0\\ {\overline{U}}_{21}{\overline{U}}_{11}^{–1}& I\end{array}\right)}}\underset{\tilde{U}}{\underset{}{\left(\begin{array}{cc}{\overline{U}}_{11}& 0\\ 0& {\overline{U}}_{22}-{\overline{U}}_{21}{\overline{U}}_{11}^{–1}{\overline{U}}_{12}\end{array}\right)}}\underset{S}{\underset{}{\left(\begin{array}{cc}I& {\overline{U}}_{11}^{–1}{\overline{U}}_{12}\\ 0& I\end{array}\right)}},\overline{U}=K\tilde{U}S.$$

Again, let $\overline{Q}$ and $\overline{L}$ absorb $S$ and $K$ by letting $\tilde{Q}=\overline{Q}{S}^{-1}$ and $\tilde{L}=\overline{L}K$, so that:

$$PA\tilde{Q}=\tilde{L}\tilde{U}$$

$$PA\tilde{Q}=\tilde{L}\left(\begin{array}{cc}{\overline{U}}_{11}& 0\\ 0& {\tilde{U}}_{22}\end{array}\right)$$

Now we focus our attention on ${\tilde{U}}_{22}$, the $(m-r)\times (n-r)$ bottom right block of $\tilde{U}$. If this block is empty we’re done. In general though, there will have been rows or columns in $U$ that have a zero on the diagaonal, but have non-zeros elsewhere. These show up as non-zeros in ${\tilde{U}}_{22}$. We would like to move these to the upper left corner of this block and then we’d like this block to become upper triangular (invertible).

Start by permuting all rows and columns with all zeros to the bottom right corner:

$$\left(\begin{array}{cc}{A}_0& 0\\ 0& 0\end{array}\right)=\tilde{R}{\tilde{U}}_{22}\tilde{C}$$

Let $A_0={\hat{L}}_0{\hat{U}}_0{\hat{Q}}_0$ be the LUQ decomposition of $A_0$, computed recursively (base cases are trivial). This means we have,

$${\tilde{U}}_{22}={\tilde{R}}^T\left(\begin{array}{cc}{A}_0& 0\\ 0& 0\end{array}\right){\tilde{C}}^T$$

$${\tilde{U}}_{22}={\tilde{R}}^T\left(\begin{array}{cc}{\hat{L}}_0{\hat{U}}_0{\hat{Q}}_0& 0\\ 0& 0\end{array}\right){\tilde{C}}^T$$

$${\tilde{U}}_{22}=\underset{X}{\underset{}{{\tilde{R}}^T\left(\begin{array}{cc}{\hat{L}}_0& 0\\ 0& I\end{array}\right)}}\underset{{\tilde{U}}_0}{\underset{}{\left(\begin{array}{cc}{\hat{U}}_0& 0\\ 0& 0\end{array}\right)}}\underset{Y}{\underset{}{\left(\begin{array}{cc}{\hat{Q}}_0& 0\\ 0& I\end{array}\right){\tilde{C}}^T}}$$

$${\tilde{U}}_{22}=X{\tilde{U}}_{0}Y$$

Popping up, we substitute this in form ${\tilde{U}}_{22}$ above:

$$PA\tilde{Q}=\tilde{L}\left(\begin{array}{cc}{\overline{U}}_{11}& 0\\ 0& {\tilde{U}}_{22}\end{array}\right)$$

$$PA\tilde{Q}=\tilde{L}\left(\begin{array}{cc}{\overline{U}}_{11}& 0\\ 0& X{\tilde{U}}_{0}Y\end{array}\right)$$

$$PA\tilde{Q}=\tilde{L}\left(\begin{array}{cc}I& 0\\ 0& X\end{array}\right)\left(\begin{array}{cc}{\overline{U}}_{11}& 0\\ 0& {\tilde{U}}_0\end{array}\right)\left(\begin{array}{cc}I& 0\\ 0& Y\end{array}\right)$$

Finally, absorb $P$ and these new matrices into $\tilde{L}$ and $\tilde{Q}$ and absorb the top left corner of ${\tilde{U}}_0$ into the top left block of ${\overline{U}}_{11}$:

$$A=P^T\tilde{L}\left(\begin{array}{cc}I& 0\\ 0& X\end{array}\right)\left(\begin{array}{cc}{\hat{U}}_{11}& 0\\ 0& 0\end{array}\right)\left(\begin{array}{cc}I& 0\\ 0& Y\end{array}\right){\tilde{Q}}^T$$

$$A=\hat{L}\hat{U}\hat{Q}$$