Gram–Schmidt and Reduced QR

Lecture 4 · Reading guide

Read the symbols first

Wooseok Ha, MAS110 Lecture 4 (Fall 2026), lec04.pdf: printed slides 34–37, 47, 49–51 (PDF pages 39–42, 55, 57–59). This is the same A used for projection and least squares in 4.4.

The matrix A has $m = 3$ rows and $n = 2$ independent columns. Gram–Schmidt replaces its columns by an orthonormal basis for the same column space; R records the coefficients needed to reconstruct the original columns. The lecture calls the normalized Gram–Schmidt vectors $w_{i}$ before naming the QR columns $q_{i}$. We consistently use $q_{i}$ for normalized directions and $w_{j}$ for an unnormalized remainder.

$\langle u,v\rangle;\quad \lVert u\rVert;\quad u\perp v$

An inner product gives one real number, $\Vert u\Vert = \sqrt{\langle u,u\rangle}$ is its induced norm, and $u \perp v$ means $\langle u,v\rangle = 0$. The lecture writes |u| for this norm. In Euclidean space the default is $u^{\mathsf T}v$ and the norm is $\Vert u\Vert _{2}$; for polynomials it is the stated integral norm.

$\varphi;\quad \theta;\quad \hat\theta$

This chapter uses $\varphi$ for an angle and $\theta$ for model coefficients in Lab 4.4. The lecture sometimes uses $\theta$ for the angle too; the distinction here prevents mixing an angle with a coefficient vector. A hat marks a minimizing coefficient, not a unit vector.

$A;\quad G;\quad Q;\quad R;\quad P$

A stores input columns in the Euclidean QR and least-squares labs. G denotes a Gram matrix of inner products, including the polynomial metric (which the lecture locally calls A). Q stores orthonormal columns, R stores their reconstruction coefficients, and P projects onto a subspace. These matrices have different jobs and shapes.

$A=[a_1\mid a_2]\in\mathbb R^{3\times2}$

$a_{j}$ here means column j, a vector in $\mathbb R^{3}$. In the statistical model of 4.4, the lecture also names a row feature vector $a_{i}$ via row $a_{i}^{\mathsf T}$. Check the index and shape: columns are feature directions in measurement space; rows collect features for one measurement.

$w_j;\quad q_j=\frac{w_j}{\lVert w_j\rVert_2}$

$w_{j}$ is what remains after removing all earlier orthonormal components of $a_{j}$. $q_{j}$ has unit length; $w_{j}$ generally does not. This normalization needs a nonzero remainder. Independent columns guarantee it in exact arithmetic.

$r_{ij}=q_i^{\mathsf T}a_j\ (i<j);\quad r_{jj}=\lVert w_j\rVert_2$

These scalars are the reconstruction coefficients. With the positive-diagonal Gram–Schmidt convention, $r_{jj} > 0$. A library can use different matching signs; that does not change QR or the column space.

$Q\in\mathbb R^{m\times n};\quad R\in\mathbb R^{n\times n},\quad m\ge n$

For full column rank, reduced Q has n orthonormal columns and reduced R is invertible and upper triangular. $Q^{\mathsf T}Q = I_{n}$. For m > n, Q is rectangular and $QQ^{\mathsf T} = P$, not $I_{m}$.

$\text{Complete QR};\quad Q_{\mathrm{full}}\in\mathbb R^{m\times m}$

Complete Q extends the basis to all of $\mathbb R^{m}; R_{\mathrm{full}}$ has shape m × n. The extra Q columns do not all belong to Col(A). $Q_{\mathrm{full}}Q_{\mathrm{full}}^{\mathsf T} = I_{m}$, whereas projection onto Col(A) uses only the relevant column-space basis.

$\varepsilon$; numerical threshold; matrix rank

$\varepsilon$ is a small parameter in the near-dependent example, not a residual vector. In floating point a tiny remainder can indicate numerical dependence. The demonstration routine compares against a threshold scaled by the matrix norm; it is a teaching rank policy, not an exact symbolic rank test.

np.linalg.qr(A, mode="reduced")

This returns a reduced factorization using LAPACK routines. Rank-deficient matrices still have QR factorizations, but R is singular and extra Q directions need not lie in Col(A). The full-column-rank solve $R\theta = Q^{\mathsf T}b$ then cannot be used as an invertible solve.