Visual linear algebra

Three geometric routes to QR factorization

Gram-Schmidt orthogonalization, Givens rotations and Householder reflections applied to the same matrices

Gram-Schmidt

Reshape the columns of A into an orthonormal frame, then compute R from QᵀA

Givens rotations

Rotate coordinate planes so entries below the diagonal are eliminated one at a time

Householder reflections

Reflect across hyperplanes so a whole column tail is eliminated in one step

One matrix, one goal, three mechanisms

QR factorization is a basic tool behind least-squares fitting and many stable numerical algorithms. Yet the same formula A = QR, where Q has orthonormal columns and R is upper triangular, can be reached through three very different geometric actions: column orthogonalization, coordinate-plane rotations and hyperplane reflections

Applying all three methods to the same full-rank and rank-deficient matrices makes their common goal—and their essential differences—visible

The comparison uses two shared examples for all three algorithms: one full-rank matrix and one flat rank-deficient matrix. Click any animation or summary image to open it full size

First, the idea in 2D

In two dimensions, the three methods are almost minimal, which makes their different motions easiest to see. Gram-Schmidt reshapes the two columns into an orthonormal pair. Givens rotations and Householder reflections instead move A into triangular position by an orthogonal transformation. In higher dimensions, Givens repeats rotations one entry at a time, while Householder reflections can eliminate a whole column tail at once.

One detail worth noticing: Gram-Schmidt, in its standard form, produces non-negative diagonal entries in R. Givens and Householder versions may produce different signs depending on rotation or reflection sign choices. This is normal: QR is unique only after an extra sign convention is imposed, such as requiring non-negative diagonal entries in R.

Gram-Schmidt in 2D

The two columns are orthogonalized and normalized to form Q directly.

Animated 2D Gram-Schmidt QR factorization — Column orthogonalization in the plane
Open full-size animation

Givens rotation in 2D

A single rotation places the first column on the horizontal axis, eliminating the lower-left entry.

Animated 2D Givens rotation QR factorization — Triangularization by rotation in the plane
Open full-size animation

Householder reflection in 2D

A single reflection places the first column on the horizontal axis in one orthogonal step.

Animated 2D Householder reflection QR factorization — Triangularization by reflection in the plane
Open full-size animation

Full-rank 3D example

In the full-rank case, the original parallelepiped has nonzero volume and the three methods produce an upper triangular R with three nonzero diagonal entries

Gram-Schmidt orthogonalization

Projection subtraction and scaling reshape the columns of A into the orthonormal columns of Q

Animated Gram-Schmidt QR factorization for the full-rank matrix — A is transformed into Q, and R is computed as QᵀA
Open full-size animation

Givens rotations

Successive rotations in coordinate planes reorient the figure so selected entries below the diagonal become zero

Animated Givens rotation QR factorization for the full-rank matrix — A is transformed into R by accumulated coordinate-plane rotations
Open full-size animation

Householder reflections

Successive reflections across hyperplanes reorient the figure so whole column tails below pivots become zero

Animated Householder reflection QR factorization for the full-rank matrix — A is transformed into R by accumulated hyperplane reflections
Open full-size animation

Flat rank-deficient 3D example

In the flat case, the columns of A lie in a lower-dimensional shape. QR still separates orthogonal directions from triangular coordinates, but the final diagonal reveals the missing dimension

Gram-Schmidt orthogonalization

The residual direction can become zero after projections remove the part already explained by previous directions

Animated Gram-Schmidt QR factorization for the flat rank-deficient matrix — The flat shape leaves a zero residual direction
Open full-size animation

Givens rotations

Coordinate-plane rotations place the flat shape into triangular position while preserving lengths and angles

Animated Givens rotation QR factorization for the flat rank-deficient matrix — The flat shape is rotated into place
Open full-size animation

Householder reflections

Hyperplane reflections place the same flat shape into triangular position by larger orthogonal steps

Animated Householder reflection QR factorization for the flat rank-deficient matrix — The flat shape is reflected into place
Open full-size animation

Visual summary

The same factorization can be viewed from two complementary directions: Gram-Schmidt transforms the column figure into Q, while Givens and Householder transformations move A into R

Visual comparison of Gram-Schmidt orthogonalization, Givens rotation and Householder reflection for QR decomposition — Three geometric routes to the same QR factorization

Comparison of the algorithms

The methods differ in what each step does geometrically, what factor appears first and what computational behavior is expected

Question	Gram-Schmidt orthogonalization	Givens rotations	Householder reflections
Transforms A into	Q	R	R
Remaining factor computed as	R = QᵀA	Q = (Gₖ ··· G₁)⁻¹	Q = (Hₖ ··· H₁)⁻¹
Algebraic step operation	Right-multiplication by scaling and shear matrices	Left-multiplication by rotation matrices	Left-multiplication by reflection matrices
Geometric step operation	Subtracts projections onto previous directions and normalizes the remaining component	Rotates in a coordinate plane	Reflects across a hyperplane
Full-rank A: geometric behavior	A is reshaped into an orthonormal frame	A is rotated into triangular position	A is reflected into triangular position
Flat rank-deficient A: geometric behavior	One residual direction becomes zero	The flat shape is rotated into place	The flat shape is reflected into place
Sign of diagonal entries of R	Non-negative	Whatever sign comes out	Whatever sign comes out
Numerical stability	Small residual directions amplify error	Stable	Stable
Efficiency	Less efficient	Efficient for sparse A	Preferred for dense A

For the displayed examples, the Givens and Householder algorithms happen to produce non-negative diagonal entries of R without sign-correction steps. Gram-Schmidt produces non-negative diagonal entries by construction.

Takeaway

Gram-Schmidt builds Q directly from the columns of A. Givens rotations and Householder reflections instead transform A into R, then recover Q from the accumulated orthogonal transformations

The same formula A = QR therefore hides three different geometric stories: orthogonalization, rotation and reflection