Gram-Schmidt and QR Factorization

Definition Let $\mathbf{a}_1, \dots, \mathbf{a}_n$ be linearly independent vectors in $\mathbb{R}^m$, so that $n \le m$. The Gram-Schmidt process builds vectors $\mathbf{q}_1, \dots, \mathbf{q}_n$ in order. For $j = 1, \dots, n$,

where the sum is empty for $j = 1$, so $\mathbf{u}_1 = \mathbf{a}_1$. Every $\mathbf{u}_j$ is nonzero, the list $\mathbf{q}_1, \dots, \mathbf{q}_n$ is orthonormal, and for every $j$

The proof is by induction on $j$. In the base case $j = 1$, the vector $\mathbf{a}_1$ is nonzero because the list is independent, so $\mathbf{q}_1$ is a unit vector spanning the same line. For the step, assume that $\mathbf{q}_1, \dots, \mathbf{q}_k$ are orthonormal and span the same space as $\mathbf{a}_1, \dots, \mathbf{a}_k$. The next remainder $\mathbf{u}_{k+1}$ is nonzero and perpendicular to each earlier $\mathbf{q}_i$, as the next card shows, so $\mathbf{q}_{k+1}$ extends the orthonormal list. The formula puts $\mathbf{q}_{k+1}$ in the span of $\mathbf{a}_1, \dots, \mathbf{a}_{k+1}$, since each earlier $\mathbf{q}_i$ lies in the span of $\mathbf{a}_1, \dots, \mathbf{a}_k$, and rearranged it writes $\mathbf{a}_{k+1}$ as a combination of $\mathbf{q}_1, \dots, \mathbf{q}_{k+1}$, so the two spans agree at step $k + 1$.

Definition At step $j$ of the Gram-Schmidt process the orthogonal remainder is the vector $\mathbf{u}_j$ defined above, the part of $\mathbf{a}_j$ left after subtracting its projections onto all earlier directions $\mathbf{q}_1, \dots, \mathbf{q}_{j-1}$. The subtracted sum is the orthogonal projection of $\mathbf{a}_j$ onto $\operatorname{span}\{\mathbf{q}_1, \dots, \mathbf{q}_{j-1}\}$, so $\mathbf{u}_j$ is perpendicular to that whole span. Directly, since $\mathbf{q}_k \cdot \mathbf{q}_i$ is $1$ for $i = k$ and $0$ for $i \ne k$, every $k < j$ gives

For independent inputs the remainder is never zero, because $\mathbf{u}_j = \mathbf{0}$ would put $\mathbf{a}_j$ in the span of the earlier $\mathbf{q}_i$, which is the span of $\mathbf{a}_1, \dots, \mathbf{a}_{j-1}$.

Definition Normalizing a nonzero vector $\mathbf{u}$ means dividing it by its length,

The result has length $1$, spans the same line as $\mathbf{u}$, and gives back $\mathbf{u} = \lVert \mathbf{u} \rVert\,\mathbf{q}$. Normalization is defined only for $\mathbf{u} \ne \mathbf{0}$. Scaling by a positive number keeps every zero dot product zero, so a normalized remainder is still perpendicular to the earlier directions. Normalization changes lengths only and never angles, so it cannot make two vectors perpendicular when they were not.

Definition A real $m \times n$ matrix $Q$ has orthonormal columns if its columns $\mathbf{q}_1, \dots, \mathbf{q}_n$ satisfy $\mathbf{q}_i \cdot \mathbf{q}_j = 1$ for $i = j$ and $\mathbf{q}_i \cdot \mathbf{q}_j = 0$ for $i \ne j$. Entry $(i, j)$ of $Q^{\top}Q$ is $\mathbf{q}_i \cdot \mathbf{q}_j$, so the condition is

Such a matrix has $n \le m$ and preserves dot products and lengths, since $(Q\mathbf{x}) \cdot (Q\mathbf{y}) = \mathbf{x}^{\top}Q^{\top}Q\mathbf{y} = \mathbf{x} \cdot \mathbf{y}$. The other product $QQ^{\top}$ is the $m \times m$ matrix of the orthogonal projection onto $\operatorname{Col} Q$. It equals $I_m$ only when $m = n$, and then $Q$ is an orthogonal matrix with $Q^{-1} = Q^{\top}$.

Definition Let $A$ be a real $m \times n$ matrix with linearly independent columns $\mathbf{a}_1, \dots, \mathbf{a}_n$. A reduced QR factorization of $A$ is a product $A = QR$ in which $Q$ is an $m \times n$ matrix with orthonormal columns and the upper triangular factor $R$ is an $n \times n$ matrix with $r_{ij} = 0$ for $i > j$. Here the diagonal entries of $R$ are also required to be positive, as Gram-Schmidt makes them. Gram-Schmidt on the columns of $A$ produces such a factorization. The columns of $Q$ are $\mathbf{q}_1, \dots, \mathbf{q}_n$, and

Rearranging the Gram-Schmidt formula gives $\mathbf{a}_j = r_{1j}\mathbf{q}_1 + \cdots + r_{jj}\mathbf{q}_j$, which is column $j$ of $QR$. The zeros below the diagonal say that $\mathbf{a}_j$ needs only the first $j$ directions. Dotting this equation with $\mathbf{q}_i$ gives $r_{ij} = \mathbf{q}_i \cdot \mathbf{a}_j$ for every $i$, including $r_{jj} = \mathbf{q}_j \cdot \mathbf{a}_j$ and the zeros, so all entries can be collected as $R = Q^{\top}A$. With positive diagonal entries, $Q$ and $R$ are unique. Without that convention, changing the sign of a column of $Q$ together with the matching row of $R$ gives another factorization. The word reduced means that $Q$ has only the $n$ columns needed for $\operatorname{Col} A$, even when $m > n$.

Definition Let $\mathbf{q}_1, \dots, \mathbf{q}_{j-1}$ be orthonormal with the same span as $\mathbf{a}_1, \dots, \mathbf{a}_{j-1}$, and form the remainder $\mathbf{u}_j$ as above. Then $\mathbf{u}_j = \mathbf{0}$ exactly when $\mathbf{a}_j$ lies in $\operatorname{span}\{\mathbf{a}_1, \dots, \mathbf{a}_{j-1}\}$. If $\mathbf{u}_j = \mathbf{0}$, the formula writes $\mathbf{a}_j$ as a combination of the earlier $\mathbf{q}_i$. Conversely, if $\mathbf{a}_j$ lies in that span, it equals the sum of its components $(\mathbf{q}_i \cdot \mathbf{a}_j)\mathbf{q}_i$, so nothing remains. In exact arithmetic Gram-Schmidt is therefore a test for dependence. A zero remainder cannot be normalized, and the reduced QR factorization above needs every diagonal entry $r_{jj} = \lVert \mathbf{u}_j \rVert$ to be positive. To get an orthonormal basis for the span of a dependent list, skip each zero remainder and continue with the next vector. The number of directions kept equals the rank. In floating-point arithmetic, rounding makes a very small computed remainder hard to interpret, so a tiny value is not by itself proof of dependence.