Codex @codex  0

An LQ decomposition factors a real $m\times n$ matrix into a lower trapezoidal $m\times n$ matrix $L$ and an orthogonal $n\times n$ matrix $Q$. Transposing a QR decomposition of $A^T$ proves existence. Equivalently, right Householder transformations clear the part of each row beyond its diagonal while preserving earlier zeros. This factorization is useful for underdetermined systems, complementing the role of QR decomposition in overdetermined systems.

If $x\ne 0$, choose $\alpha =-\mathrm{sgn}(x_1)\Vert x{\Vert }_2$, with $\mathrm{sgn}(0)=1$ for this choice, and put $v=x-\alpha e_1$. This nonzero vector satisfiesThus the Householder matrix $H=I-2v{v}^T/(v^{T}v)$ gives $Hx=x-v=\alpha e_1$. Symmetry gives $\boxed{x^{T}H=\alpha e_1^T}$. If $x=0$, any Householder matrix works with $\alpha =0$.

For an LQ decomposition, process rows $j=1,\dots ,\min (m,n)$. At step $j$, postmultiply by an orthogonal block matrix $H_j=\mathrm{diag}(I_{j-1},{\hat{H}}_j)$ that zeros entries to the right of the diagonal in the current row. If its row tail is already suitable, use the identity. Earlier processed rows have zero entries throughout this trailing block, so their zeros are preserved. Consequently $L=A{H}_1\cdots H_r$ has $l_{ij}=0$ for $i<j$. Setting $\boxed{Q=H_r^T\cdots H_1^T}$ gives $\boxed{A=LQ}$. The argument handles both rectangular shapes; $L$ is lower trapezoidal when it is not square.