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