Gram-Schmidt Orthonormalization- LQ decomposition

437 Views Asked by At

Assume $A$ is an $m \times n$ matrix, $m < n$, and $\operatorname{rank} (A) = m$.

Prove that $A$ can be written in the form $A = LQ$,

where $L$ is a $m \times m$ lower-triangular matrix and $Q$ is an $m\times n$ matrix with orthonormal rows.

This question is a work and don't know how resolve

Thank you very much!

1

There are 1 best solutions below

0
On

It is the same as proving QR-decomposition for $A^T$.

Let $A \in \Bbb R^{m \times n}$, $w_i^T$ be the $i$-th row of $A$, $m \lt n$, $rank(A) = m$.

Consider $A^T = (w_1, ..., w_m)$. We know that $rank(A) = rank(A^T) = m$, so $A^T$ has full column rank. In particular, $\{w_1, ..., w_m\}$ is a linearly independant set of $\Bbb R^n$.

We can use Gram-Schmidt to make it orthonormal. By using it, we get another set $\{v_1, ..., v_m\}$ such that $v_1^T = w_1^T$ and $$v_i = w_i - \sum_{j=0}^{i-1} \left( \langle w_i, v_j \rangle / \langle v_j, v_j \rangle \right) v_j = w_i^T - \sum_{j=0}^{i-1} \alpha_{i, j} \cdot v_j, \ i = 2, ..., m$$ and they span the same set. Notice that $\{v_1, ..., v_m\}$ is an orthogonal set.

We write $$w_i = v_i + \sum_{j=0}^{i-1} \alpha_{i, j} \cdot v_j$$ so $A^T = Q'R'$, where $Q' = (v_1, ..., v_m) \in \Bbb R^{n \times m}$, $R' \in \Bbb R^{m \times m}$ is upper triangular such that $R'_{i, i} = 1$ and $R'_{i, j} = \alpha_{j, i}$, $i \lt j$.

Then divide the $i$-th column of $Q'$ by the norm of $v_i$ and multiply the $i$-th row of $R'$ by the norm of $v_i$ so that you get $A^T = QR$, $Q$ has orthonormal columns and $R$ is upper triangular. Then take the transpose.