ZoomNotes for Linear Algebra

Part 4: Orthogonal Matrices and Least Squares

4.1 Orthogonality of the Four Subspaces

Orthogonal vectors: $x \perp y$ means $x^T y = 0$.

Orthogonal subspaces: Subspaces $V$ and $W$ are orthogonal if every vector in $V$ is orthogonal to every vector in $W$.

Fundamental Orthogonality:

• Row space $C(A^T)$ $\perp$ Nullspace $N(A)$
• Column space $C(A)$ $\perp$ Left nullspace $N(A^T)$

Proof: For any $x$ in $N(A)$, $Ax = 0$, meaning every row of $A$ (a basis for the row space) is orthogonal to $x$. Similarly for the second pair using $A^T$.

The Big Picture: Rows and nullspace live in $\mathbb{R}^n$; columns and left nullspace live in $\mathbb{R}^m$. The orthogonal subspaces are not just orthogonal -- they are orthogonal complements: together they span the whole space.

Decomposition: Every $x \in \mathbb{R}^n$ can be uniquely written as:

$$x = x_{\text{row}} + x_{\text{null}}$$

where $x_{\text{row}} \in C(A^T)$ and $x_{\text{null}} \in N(A)$. Similarly for $\mathbb{R}^m$.

---

4.2 Projections onto Subspaces

Projection onto a line through $a$:

$$p = \frac{a a^T}{a^T a} \, b = \frac{a^T b}{a^T a} \, a$$

Projection matrix for a line:

$$P = \frac{a a^T}{a^T a}$$

Properties: $P^2 = P$ (idempotent), $P^T = P$ (symmetric).

Projection onto a subspace: Given a matrix $A$ with independent columns, the projection of $b$ onto $C(A)$ is:

$$p = A \hat{x} \quad \text{where} \quad A^T A \hat{x} = A^T b$$

Projection matrix for a subspace:

$$P = A (A^T A)^{-1} A^T$$

Properties of projection matrices:

• $P^2 = P$ (projecting twice is same as once)
• $P^T = P$ (symmetric)
• $I - P$ is the projection onto the orthogonal complement
• $P$ projects onto $C(A)$; $I - P$ projects onto $N(A^T)$

---

4.3 Least Squares Approximations (Regression): $A^T A \hat{x} = A^T b$

When $Ax = b$ has no solution (because $b$ is not in $C(A)$), we find the best approximation by minimizing $\|b - Ax\|^2$.

The Normal Equations:

$$A^T A \hat{x} = A^T b$$

Why this works: The error $e = b - A\hat{x}$ is orthogonal to $C(A)$, so $A^T e = 0$, giving $A^T (b - A\hat{x}) = 0$, hence $A^T A \hat{x} = A^T b$.

Best Fit Line (Linear Regression): Given $m$ points $(t_1, y_1), \dots, (t_m, y_m)$, find the line $y = C + Dt$ that minimizes the sum of squared errors.

Set up $A = \begin{bmatrix} 1 & t_1 \\ 1 & t_2 \\ \vdots & \vdots \\ 1 & t_m \end{bmatrix}$, $x = \begin{bmatrix} C \\ D \end{bmatrix}$, $b = \begin{bmatrix} y_1 \\ \vdots \\ y_m \end{bmatrix}$.

Solve $A^T A \hat{x} = A^T b$:

$$\begin{bmatrix} m & \sum t_i \\ \sum t_i & \sum t_i^2 \end{bmatrix} \begin{bmatrix} C \\ D \end{bmatrix} = \begin{bmatrix} \sum y_i \\ \sum t_i y_i \end{bmatrix}$$

---

4.4 Orthogonal Matrices and Gram-Schmidt

Orthogonal Matrix $Q$ satisfies $Q^T Q = I$. For square $Q$, this means $Q^T = Q^{-1}$.

Properties:

• Columns of $Q$ are orthonormal ($q_i^T q_j = 0$ for $i \neq j$, $q_i^T q_i = 1$)
• $\|Qx\| = \|x\|$ (preserves length)
• $(Qx)^T (Qy) = x^T y$ (preserves angles)
• Product of orthogonal matrices is orthogonal
• $\det Q = \pm 1$

Orthonormal Basis: For a basis $q_1, \dots, q_n$ with $q_i^T q_j = \delta_{ij}$:

Fourier Coefficients: Every vector $v$ can be expressed as:

$$v = (q_1^T v) q_1 + (q_2^T v) q_2 + \cdots + (q_n^T v) q_n$$

The coefficients $c_k = q_k^T v$ are the Fourier coefficients.

Gram-Schmidt Process: Converts independent vectors $a, b, c$ into orthonormal vectors $q_1, q_2, q_3$.

1. $q_1 = a / \|a\|$
2. $B = b - (q_1^T b) q_1$, then $q_2 = B / \|B\|$
3. $C = c - (q_1^T c) q_1 - (q_2^T c) q_2$, then $q_3 = C / \|C\|$

At each step, we subtract the projections onto all previous orthonormal vectors, then normalize.

QR Factorization: Every $m \times n$ matrix $A$ (with independent columns) factors as:

$$A = Q R$$

• $Q$ is $m \times n$ with orthonormal columns
• $R$ is $n \times n$ upper triangular

The entries of $R$ are the dot products $r_{ij} = q_i^T a_j$ (or $q_i^T b$ in the notation above).

Solving $Ax = b$ with QR:

$$A^T A x = A^T b \implies R^T Q^T Q R x = R^T Q^T b \implies R^T R x = R^T Q^T b \implies Rx = Q^T b$$

Since $R$ is triangular, back substitution gives $x$ directly -- no need to form $A^T A$.