QR Decomposition via Gram-Schmidt

Orthonormalize the columns of a small matrix with Gram-Schmidt to produce Q and R, and check orthogonality.

Problem

QR decomposition writes A = Q R with Q orthonormal columns and R upper triangular. It is the workhorse behind least-squares solving and eigenvalue algorithms. Classical Gram-Schmidt builds Q by subtracting projections onto previously found directions.

Procedure

Take each column of A, subtract its projection onto the already-normalized columns, and normalize the remainder. The projection coefficients and the norms fill the entries of R.

python

import numpy as np
A=np.array([[1.,1.],[1.,0.],[0.,1.]])
m,n=A.shape; Q=np.zeros((m,n)); R=np.zeros((n,n))
for j in range(n):
    v=A[:,j].copy()
    for i in range(j):
        R[i,j]=Q[:,i]@A[:,j]
        v=v-R[i,j]*Q[:,i]
    R[j,j]=np.linalg.norm(v)
    Q[:,j]=v/R[j,j]
print('Q^T Q orthonormal',np.allclose(Q.T@Q,np.eye(n)))
print('reconstruct',np.allclose(Q@R,A))

Result

The output Q has orthonormal columns (Q'Q equals the identity) and Q R reconstructs A. Once you have QR, least squares becomes solving R x = Q' b by back-substitution, which is stable and fast. Classical Gram-Schmidt can lose orthogonality on ill-conditioned inputs; the modified variant or Householder reflections are used in production.

• QR turns least squares into a triangular solve without forming the normal equations, avoiding squared condition numbers.
• Repeated QR steps drive a matrix toward triangular form, the basis of the QR eigenvalue algorithm.
• Kronos least-squares fits of diagnostic data use QR-based solvers for numerical stability.