Learn Linear Algebra

The Gram–Schmidt Process

Given a basis {x⃗1,…,x⃗p} \{ \vec{x}_1, \dots, \vec{x}_p \} for a subspace W W of Rn \mathbb{R}^n , define:

v⃗1=x⃗1 \vec{v}_1 = \vec{x}_1

v⃗2=x⃗2−x⃗2⋅v⃗1v⃗1⋅v⃗1v⃗1 \vec{v}_2 = \vec{x}_2 - \frac{\vec{x}_2 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1

v⃗3=x⃗3−x⃗3⋅v⃗1v⃗1⋅v⃗1v⃗1−x⃗3⋅v⃗2v⃗2⋅v⃗2v⃗2 \vec{v}_3 = \vec{x}_3 - \frac{\vec{x}_3 \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 - \frac{\vec{x}_3 \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2}\vec{v}_2

⋮ \vdots

v⃗p=x⃗p−x⃗p⋅v⃗1v⃗1⋅v⃗1v⃗1−x⃗p⋅v⃗2v⃗2⋅v⃗2v⃗2−⋯−x⃗p⋅v⃗p−1v⃗p−1⋅v⃗p−1v⃗p−1. \vec{v}_p = \vec{x}_p - \frac{\vec{x}_p \cdot \vec{v}_1}{\vec{v}_1 \cdot \vec{v}_1}\vec{v}_1 - \frac{\vec{x}_p \cdot \vec{v}_2}{\vec{v}_2 \cdot \vec{v}_2}\vec{v}_2 - \cdots - \frac{\vec{x}_p \cdot \vec{v}_{p-1}}{\vec{v}_{p-1} \cdot \vec{v}_{p-1}}\vec{v}_{p-1}.

Then {v⃗1,…,v⃗p} \{ \vec{v}_1, \dots, \vec{v}_p \} is an orthogonal basis for W W . In addition:

Span{v⃗1,…,v⃗k}=Span{x⃗1,…,x⃗k}for 1≤k≤p. \text{Span} \{ \vec{v}_1, \dots, \vec{v}_k \} = \text{Span} \{ \vec{x}_1, \dots, \vec{x}_k \} \quad \text{for } 1 \leq k \leq p.

The QR Factorization

If A A is an m×n m \times n matrix with linearly independent columns, then A A can be factored as A=QR A = QR , where Q Q is an m×n m \times n matrix whose columns form an orthonormal basis for Col A A and R R is an n×n n \times n upper triangular invertible matrix with positive entries on its diagonal.