Gram–Schmidt and QR Factorization

Remove directions already represented

Gram–Schmidt turns an independent list $a_1,\ldots,a_n$ into orthonormal vectors spanning the same successive subspaces. First set $q_1=a_1/\|a_1\|$ . At step $j$ , remove projections onto earlier directions:

v_j=a_j-\sum_{i<j}(q_i^Ta_j)q_i,

q_j=v_j/\|v_j\|.

If the input columns are dependent, a residual becomes zero and cannot be normalized. This reveals redundancy rather than a new basis direction.

Visual guide

VISUAL GUIDERemove the part already explained

Projection direction

Starting from a₁ = (1, 1) and a₂ = (2, 0), project a₂ onto a₁ to get (1, 1). Subtracting leaves (1, −1), perpendicular to a₁. Normalizing these two directions produces an orthonormal basis for QR.

Worked example: two columns

Let $a_1=(1,1,0)^T$ and $a_2=(1,0,1)^T$ . Then $q_1=(1,1,0)^T/\sqrt2$ and $q_1^Ta_2=1/\sqrt2$ . Subtracting gives $v_2=(1/2,-1/2,1)^T$ , with norm $\sqrt{3/2}$ . Hence $q_2=(1,-1,2)^T/\sqrt6$ .

Check $q_1^Tq_2=0$ and both norms equal one. These checks catch arithmetic mistakes before using the basis in later calculations.

Worked example: read the factorization

Stack the orthonormal vectors as columns of $Q$ . The coefficients used above give

A=QR,

R=\begin{pmatrix}\sqrt2&1/\sqrt2\\0&\sqrt{3/2}\end{pmatrix}.

The matrix $Q$ has size $3\times2$ and satisfies $Q^TQ=I_2$ . But $QQ^T$ is a projection onto the two-dimensional column space, not the $3\times3$ identity. This distinction matters for rectangular matrices.

For full column rank, a least-squares solution satisfies $R\hat x=Q^Tb$ . Solve this triangular system instead of explicitly inverting $R$ . In numerical libraries, Householder QR is generally preferred to classical Gram–Schmidt because it better preserves orthogonality under rounding; modified Gram–Schmidt also improves on the classical algorithm.

Practice

Apply Gram–Schmidt to $(1,0)^T,(1,1)^T$ .
What occurs for $(1,0)^T,(2,0)^T$ ?
If $Q$ has three orthonormal columns in $\mathbb R^5$ , what are the shapes of $Q^TQ$ and $QQ^T$ ?

Show worked solutions

$q_1=(1,0)^T$ , residual $(0,1)^T$ , so $q_2=(0,1)^T$ .
The second residual is zero, revealing dependent inputs.
$Q^TQ$ is the $3\times3$ identity; $QQ^T$ is a $5\times5$ projection of rank three.