From Independent Columns to QR
Gram–Schmidt is a way to replace an independent list of vectors by an orthonormal list that spans the same vectors, one step at a time. Applied to the columns of a matrix, it gives a factorization into two useful pieces: a matrix whose columns are orthonormal and an upper-triangular matrix that records how the original columns are assembled from them. The order of the columns matters, because each new orthonormal vector is made perpendicular to all the ones constructed before it.
Throughout this tutorial the scalars are real. For vectors \(\mathbf{x},\mathbf{y}\in\mathbb{R}^m\), their inner product is \(\mathbf{x}\cdot\mathbf{y}=\mathbf{x}^{\top}\mathbf{y}\), and their norm is \(\|\mathbf{x}\|=\sqrt{\mathbf{x}\cdot\mathbf{x}}\). Vectors are orthogonal if their inner product is zero. A list is orthonormal if every vector has norm \(1\) and distinct vectors in the list are orthogonal. An \(m\times n\) matrix has full column rank when its \(n\) columns are linearly independent.
The formula subtracts from \(\mathbf{a}_j\) its components in the directions already constructed. The coefficients are inner products with the unit vectors \(\mathbf{q}_i\); using the original columns \(\mathbf{a}_i\) in place of those unit vectors would not, in general, give the right components. The residual \(\mathbf{u}_j\) is then normalized to make the next column of \(\mathbf{Q}\) have norm \(1\).
Why the Projection Subtraction Works
Proof. Fix any \(j\) with \(1\le j\le k\). Take the inner product of the displayed expression for \(\mathbf{u}\) with \(\mathbf{q}_j\). By linearity of the real inner product and orthonormality, $$ \mathbf{u}\cdot\mathbf{q}_j =\mathbf{v}\cdot\mathbf{q}_j-\sum_{i=1}^{k}(\mathbf{v}\cdot\mathbf{q}_i)(\mathbf{q}_i\cdot\mathbf{q}_j) =\mathbf{v}\cdot\mathbf{q}_j-(\mathbf{v}\cdot\mathbf{q}_j) =0. $$ This holds for each \(j\), so \(\mathbf{u}\) is orthogonal to every vector in the list. \(\square\)
This lemma explains the subtraction in Gram–Schmidt. It also gives a practical check on a computation: after calculating a residual, take its inner product with each earlier \(\mathbf{q}_i\). Every such inner product should be zero. The formula only guarantees a usable next vector if the residual is nonzero, so the independence hypothesis is essential.
Constructing and Proving the Factorization
Proof. We prove successively that the construction is defined, that the vectors \(\mathbf{q}_1,\dots,\mathbf{q}_j\) are orthonormal, and that the first \(j\) original columns lie in their span. For \(j=1\), independence implies \(\mathbf{a}_1\ne\mathbf{0}\). Hence \(\mathbf{u}_1=\mathbf{a}_1\) has nonzero norm, so \(\mathbf{q}_1\) is defined and has norm \(1\), and \(\mathbf{a}_1=\|\mathbf{u}_1\|\mathbf{q}_1\).
Now suppose the construction has reached step \(j\), where \(2\le j\le n\), and that \(\mathbf{q}_1,\dots,\mathbf{q}_{j-1}\) are orthonormal and span the first \(j-1\) columns. By the lemma, the vector \(\mathbf{u}_j\) specified by Gram–Schmidt is orthogonal to each of these \(\mathbf{q}_i\). We must also show that \(\mathbf{u}_j\ne\mathbf{0}\). If it were zero, its defining equation would give $$ \mathbf{a}_j=\sum_{i=1}^{j-1}(\mathbf{a}_j\cdot\mathbf{q}_i)\mathbf{q}_i. $$ The right-hand side belongs to the span of \(\mathbf{q}_1,\dots,\mathbf{q}_{j-1}\), which by the induction hypothesis is the span of \(\mathbf{a}_1,\dots,\mathbf{a}_{j-1}\). Thus \(\mathbf{a}_j\) would be a linear combination of the preceding columns, contradicting independence of the columns of \(\mathbf{A}\). Therefore \(\mathbf{u}_j\ne\mathbf{0}\), and \(\mathbf{q}_j=\mathbf{u}_j/\|\mathbf{u}_j\|\) is defined and has norm \(1\). Since \(\mathbf{u}_j\) is orthogonal to each earlier \(\mathbf{q}_i\), the list through \(\mathbf{q}_j\) is orthonormal. The defining formula also expresses \(\mathbf{a}_j\) as a combination of \(\mathbf{q}_1,\dots,\mathbf{q}_j\), so the induction continues.
For each \(j\), the definition of \(\mathbf{u}_j\) rearranges to $$ \mathbf{a}_j=\sum_{i=1}^{j-1}(\mathbf{a}_j\cdot\mathbf{q}_i)\mathbf{q}_i+\mathbf{u}_j =\sum_{i=1}^{j-1}(\mathbf{q}_i\cdot\mathbf{a}_j)\mathbf{q}_i+\|\mathbf{u}_j\|\mathbf{q}_j. $$ For \(j=1\), the same column equation is \(\mathbf{a}_1=\|\mathbf{u}_1\|\mathbf{q}_1\). Thus column \(j\) is \(\sum_{i=1}^{j}r_{ij}\mathbf{q}_i\), where \(r_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\) for \(i<j\) and \(r_{jj}=\|\mathbf{u}_j\|\). Setting \(r_{ij}=0\) for \(i>j\) makes \(\mathbf{R}\) upper triangular. The column equations for all \(j\) together are exactly \(\mathbf{A}=\mathbf{Q}\mathbf{R}\). The induction has also shown that the columns of \(\mathbf{Q}\) are orthonormal. \(\square\)
The diagonal entries \(r_{jj}=\|\mathbf{u}_j\|\) are positive because each residual is nonzero. The entries above the diagonal record inner products between an already constructed unit vector and a later original column. This triangular pattern follows from the order of the construction: column \(j\) uses only \(\mathbf{q}_1,\dots,\mathbf{q}_j\), not any later vectors.
Worked Constructions
Worked Example: Two Columns in \(\mathbb{R}^3\)
Construct \(\mathbf{A}=\mathbf{Q}\mathbf{R}\) for $$ \mathbf{a}_1=\begin{bmatrix}1\\1\\0\end{bmatrix}, \qquad \mathbf{a}_2=\begin{bmatrix}1\\0\\1\end{bmatrix}. $$ These columns are independent: if \(c_1\mathbf{a}_1+c_2\mathbf{a}_2=\mathbf{0}\), the second coordinate gives \(c_1=0\), and the third gives \(c_2=0\).
First, \(\|\mathbf{a}_1\|=\sqrt{1+1}=\sqrt{2}\), so $$ \mathbf{u}_1=\begin{bmatrix}1\\1\\0\end{bmatrix}, \qquad \mathbf{q}_1=\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\end{bmatrix}. $$ The coefficient of \(\mathbf{q}_1\) in the second column is $$ r_{12}=\mathbf{q}_1\cdot\mathbf{a}_2 =\frac{1+0+0}{\sqrt{2}}=\frac{1}{\sqrt{2}}. $$ Therefore $$ \mathbf{u}_2 =\begin{bmatrix}1\\0\\1\end{bmatrix} -\frac{1}{\sqrt{2}}\frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\\0\end{bmatrix} =\begin{bmatrix}\tfrac12\\-\tfrac12\\1\end{bmatrix}. $$ Its squared norm is \(\tfrac14+\tfrac14+1=\tfrac32\), so \(\|\mathbf{u}_2\|=\tfrac{\sqrt{6}}{2}\) and $$ \mathbf{q}_2=\frac{1}{\sqrt{6}}\begin{bmatrix}1\\-1\\2\end{bmatrix}. $$ Thus $$ \mathbf{Q}=\begin{bmatrix} \tfrac{1}{\sqrt{2}}&\tfrac{1}{\sqrt{6}}\\ \tfrac{1}{\sqrt{2}}&-\tfrac{1}{\sqrt{6}}\\ 0&\tfrac{2}{\sqrt{6}} \end{bmatrix}, \qquad \mathbf{R}=\begin{bmatrix} \sqrt{2}&\tfrac{1}{\sqrt{2}}\\ 0&\tfrac{\sqrt{6}}{2} \end{bmatrix}. $$ Check the columns of the product. The first is \(\sqrt{2}\mathbf{q}_1=(1,1,0)^{\top}=\mathbf{a}_1\). The second is $$ \frac{1}{\sqrt{2}}\mathbf{q}_1+\frac{\sqrt{6}}{2}\mathbf{q}_2 =\begin{bmatrix}\tfrac12\\\tfrac12\\0\end{bmatrix} +\begin{bmatrix}\tfrac12\\-\tfrac12\\1\end{bmatrix} =\begin{bmatrix}1\\0\\1\end{bmatrix} =\mathbf{a}_2. $$ Also, \(\mathbf{q}_1\cdot\mathbf{q}_2=(1-1+0)/\sqrt{12}=0\), and both columns have norm \(1\).
Worked Example: Three Columns in \(\mathbb{R}^3\)
Apply Gram–Schmidt to the columns $$ \mathbf{a}_1=\begin{bmatrix}1\\1\\0\end{bmatrix},\quad \mathbf{a}_2=\begin{bmatrix}1\\0\\1\end{bmatrix},\quad \mathbf{a}_3=\begin{bmatrix}0\\1\\1\end{bmatrix}. $$ The preceding calculation gives \(\mathbf{q}_1=(1,1,0)^{\top}/\sqrt{2}\), \(\mathbf{q}_2=(1,-1,2)^{\top}/\sqrt{6}\), \(r_{11}=\sqrt{2}\), \(r_{12}=1/\sqrt{2}\), and \(r_{22}=\sqrt{6}/2\).
For the third column, $$ r_{13}=\mathbf{q}_1\cdot\mathbf{a}_3=\frac{1}{\sqrt{2}}, \qquad r_{23}=\mathbf{q}_2\cdot\mathbf{a}_3=\frac{1}{\sqrt{6}}. $$ Subtract the two components: $$ \mathbf{u}_3 =\begin{bmatrix}0\\1\\1\end{bmatrix} -\begin{bmatrix}\tfrac12\\\tfrac12\\0\end{bmatrix} -\begin{bmatrix}\tfrac16\\-\tfrac16\\\tfrac13\end{bmatrix} =\begin{bmatrix}-\tfrac23\\\tfrac23\\\tfrac23\end{bmatrix}. $$ Its norm is \(2/\sqrt{3}\), hence \(\mathbf{q}_3=(-1,1,1)^{\top}/\sqrt{3}\) and \(r_{33}=2/\sqrt{3}\). We obtain $$ \mathbf{Q}=\begin{bmatrix} \tfrac{1}{\sqrt{2}}&\tfrac{1}{\sqrt{6}}&-\tfrac{1}{\sqrt{3}}\\ \tfrac{1}{\sqrt{2}}&-\tfrac{1}{\sqrt{6}}&\tfrac{1}{\sqrt{3}}\\ 0&\tfrac{2}{\sqrt{6}}&\tfrac{1}{\sqrt{3}} \end{bmatrix}, \qquad \mathbf{R}=\begin{bmatrix} \sqrt{2}&\tfrac{1}{\sqrt{2}}&\tfrac{1}{\sqrt{2}}\\ 0&\tfrac{\sqrt{6}}{2}&\tfrac{1}{\sqrt{6}}\\ 0&0&\tfrac{2}{\sqrt{3}} \end{bmatrix}. $$ The first two columns of \(\mathbf{Q}\mathbf{R}\) are the same as in the preceding example. For the third, the three terms are $$ \frac{1}{\sqrt{2}}\mathbf{q}_1=\begin{bmatrix}\tfrac12\\\tfrac12\\0\end{bmatrix},\quad \frac{1}{\sqrt{6}}\mathbf{q}_2=\begin{bmatrix}\tfrac16\\-\tfrac16\\\tfrac13\end{bmatrix},\quad \frac{2}{\sqrt{3}}\mathbf{q}_3=\begin{bmatrix}-\tfrac23\\\tfrac23\\\tfrac23\end{bmatrix}. $$ Their sum is \((0,1,1)^{\top}=\mathbf{a}_3\). The unit lengths follow from the numerators having squared lengths \(2\), \(6\), and \(3\), respectively. Their pairwise inner products have numerators \(1-1\), \(-1+1\), and \(1+1-2\), all zero.
Worked Example: A Two-by-Two Factorization
Let $$ \mathbf{A}=\begin{bmatrix}1&2\\2&1\end{bmatrix}. $$ Its columns are independent: if \(c_1(1,2)^{\top}+c_2(2,1)^{\top}=\mathbf{0}\), then \(c_1+2c_2=0\) and \(2c_1+c_2=0\); subtracting twice the first equation from the second gives \(-3c_2=0\), so both coefficients vanish.
For \(\mathbf{a}_1=(1,2)^{\top}\), the norm is \(\sqrt{5}\), so \(\mathbf{q}_1=(1,2)^{\top}/\sqrt{5}\). Next, $$ r_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=\frac{2+2}{\sqrt{5}}=\frac{4}{\sqrt{5}}, \qquad \mathbf{u}_2=\begin{bmatrix}2\\1\end{bmatrix} -\frac45\begin{bmatrix}1\\2\end{bmatrix} =\begin{bmatrix}\tfrac65\\-\tfrac35\end{bmatrix}. $$ The norm of this residual is \(3/\sqrt{5}\), giving \(\mathbf{q}_2=(2,-1)^{\top}/\sqrt{5}\). Therefore $$ \mathbf{Q}=\begin{bmatrix}\tfrac{1}{\sqrt{5}}&\tfrac{2}{\sqrt{5}}\\ \tfrac{2}{\sqrt{5}}&-\tfrac{1}{\sqrt{5}}\end{bmatrix}, \qquad \mathbf{R}=\begin{bmatrix}\sqrt{5}&\tfrac{4}{\sqrt{5}}\\ 0&\tfrac{3}{\sqrt{5}}\end{bmatrix}. $$ Multiplying back, the first column is \(\sqrt{5}\mathbf{q}_1=(1,2)^{\top}\). The second is $$ \frac{4}{\sqrt{5}}\mathbf{q}_1+\frac{3}{\sqrt{5}}\mathbf{q}_2 =\begin{bmatrix}\tfrac45\\\tfrac85\end{bmatrix} +\begin{bmatrix}\tfrac65\\-\tfrac35\end{bmatrix} =\begin{bmatrix}2\\1\end{bmatrix}. $$ Thus \(\mathbf{Q}\mathbf{R}=\mathbf{A}\). The columns of \(\mathbf{Q}\) each have norm \(1\), and their inner product is \((2-2)/5=0\).
Common Mistake: Projecting onto an Unnormalized Vector
A frequent error is to subtract \((\mathbf{a}_2\cdot\mathbf{a}_1)\mathbf{a}_1\) instead of subtracting \((\mathbf{a}_2\cdot\mathbf{q}_1)\mathbf{q}_1\). For example, take \(\mathbf{a}_1=(2,0)^{\top}\) and \(\mathbf{a}_2=(1,1)^{\top}\). The incorrect calculation gives $$ \mathbf{a}_2-(\mathbf{a}_2\cdot\mathbf{a}_1)\mathbf{a}_1 =\begin{bmatrix}1\\1\end{bmatrix}-2\begin{bmatrix}2\\0\end{bmatrix} =\begin{bmatrix}-3\\1\end{bmatrix}. $$ This is not orthogonal to \(\mathbf{a}_1\), since \((-3,1)\cdot(2,0)=-6\ne0\). The correction is to normalize first: \(\mathbf{q}_1=(1,0)^{\top}\). Then \(r_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=1\), and $$ \mathbf{u}_2=\mathbf{a}_2-r_{12}\mathbf{q}_1 =\begin{bmatrix}1\\1\end{bmatrix}-\begin{bmatrix}1\\0\end{bmatrix} =\begin{bmatrix}0\\1\end{bmatrix}, $$ which satisfies \(\mathbf{u}_2\cdot\mathbf{q}_1=0\).
Another useful check is the shape and zero pattern of the result. The columns of \(\mathbf{Q}\) are the newly constructed unit vectors, while \(\mathbf{R}\) records their coefficients in the original columns. Since column \(j\) only uses the first \(j\) vectors, entries below the diagonal of \(\mathbf{R}\) must be zero. Finally, multiply \(\mathbf{Q}\mathbf{R}\) by columns: each product column should reconstruct the corresponding column of \(\mathbf{A}\).
Check Your Understanding
For each question, use the Gram–Schmidt definitions and check your result by inner products or multiplication.
- For \(\mathbf{a}_1=(1,0,1)^{\top}\) and \(\mathbf{a}_2=(1,1,0)^{\top}\), find \(\mathbf{q}_1,\mathbf{q}_2\) and the resulting \(\mathbf{R}\).
- Why must each residual \(\mathbf{u}_j\) be nonzero when the columns of \(\mathbf{A}\) are independent?
- For \(\mathbf{a}_1=(1,1)^{\top}\) and \(\mathbf{a}_2=(1,-1)^{\top}\), construct \(\mathbf{Q}\) and \(\mathbf{R}\), then multiply them back.
- State which entries of \(\mathbf{R}\) must be zero and explain why the construction forces them to vanish.
- For the vectors \(\mathbf{q}_1=(1,0)^{\top}\) and \(\mathbf{q}_2=(0,1)^{\top}\), verify directly that subtracting \((\mathbf{v}\cdot\mathbf{q}_1)\mathbf{q}_1+(\mathbf{v}\cdot\mathbf{q}_2)\mathbf{q}_2\) from any \(\mathbf{v}\in\mathbb{R}^2\) gives the zero vector.
