QR Decomposition by Gram-Schmidt

Orthonormalize a matrix's columns to factor it into an orthogonal Q and upper-triangular R - the basis of stable least squares.

The factorization

QR writes A = Q R, with Q having orthonormal columns and R upper-triangular. Classical Gram-Schmidt builds Q one column at a time: subtract from each column its projections onto the already-orthonormalized columns, then normalize.

import numpy as np
def gram_schmidt(A):
    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]
    return Q,R
A=np.array([[1.0,1.0],[1.0,0.0],[0.0,1.0]])
Q,R=gram_schmidt(A)
print(np.round(Q.T@Q,6))       # identity -> columns orthonormal
print(np.allclose(Q@R,A))

Why QR matters

QR solves least-squares problems stably. To minimize ||Ax - b|| you form A = QR and solve R x = Q^T b by back-substitution, avoiding the ill-conditioned normal equations A^T A x = A^T b. QR is also the engine of the QR algorithm for eigenvalues.

Numerical caution

Classical Gram-Schmidt loses orthogonality badly when columns are nearly dependent - rounding accumulates. Modified Gram-Schmidt, which subtracts projections sequentially against the running vector, is markedly more stable, and Householder reflections are the industrial standard, giving Q to full machine accuracy without forming it explicitly.

Reading R

The diagonal of R measures how much new direction each column adds; a tiny R[j,j] signals that column j is nearly a combination of the earlier ones - a rank deficiency, exactly what column-pivoted QR is designed to expose.