Lesson overview | Lesson overview | Next part

Orthogonality and Orthonormality: Part 1: Intuition to 8. The Spectral Theorem for Symmetric Matrices

1. Intuition

1.1 What Orthogonality "Buys" You

Orthogonality is the key that makes linear algebra computationally tractable. Without it, working in a basis requires solving systems of equations. With it, everything simplifies to dot products.

Five computational miracles of orthogonality:

Miracle 1: Coordinates become dot products. In a general basis $\{\mathbf{b}_1, \ldots, \mathbf{b}_n\}$, finding the coordinates of a vector $\mathbf{v} = \sum c_i \mathbf{b}_i$ requires solving an $n \times n$ linear system. In an orthonormal basis $\{\mathbf{q}_1, \ldots, \mathbf{q}_n\}$, the coordinate $c_i = \langle \mathbf{v}, \mathbf{q}_i \rangle$ - just a dot product. No system to solve.

Miracle 2: Length is preserved component-wise. In an ONB: $\|\mathbf{v}\|^2 = \sum_i c_i^2$ (Parseval's identity). The squared norm is simply the sum of squared coordinates - no cross terms.

Miracle 3: Orthogonal matrices have condition number 1. The condition number of $Q$ is $\|Q\| \cdot \|Q^{-1}\| = 1 \cdot 1 = 1$. This is the best possible - orthogonal systems are maximally well-conditioned. Solving $Q\mathbf{x} = \mathbf{b}$ is trivially $\mathbf{x} = Q^\top \mathbf{b}$.

Miracle 4: Projection is the best approximation. The orthogonal projection of $\mathbf{b}$ onto a subspace $S$ gives the closest point in $S$ to $\mathbf{b}$. This is the geometric foundation of least squares, PCA, and low-rank approximation.

Miracle 5: Composition of orthogonal maps is free. Two isometries composed give another isometry. Chaining rotations, reflections, and permutations never accumulates numerical error.

THE ORTHOGONALITY ADVANTAGE
========================================================================

  General basis {b_1, ..., b_n}         Orthonormal basis {q_1, ..., q_n}
  -----------------------------        ----------------------------------

  Coordinates:  solve Bc = v           Coordinates:  c^i = <v, q^i> (dot!)
  Norm:         v^T B^T B v            Norm:         \Sigma c^i^2 (Parseval)
  Projection:   A(A^T A)^-^1 A^T b      Projection:   QQ^T b (just Q^T then Q)
  Solve Ax=b:   Gaussian elim.         Solve Qx=b:   x = Q^T b (trivial)
  Condition#:   can be >> 1            Condition#:   exactly 1

========================================================================

1.2 Geometric Picture

In Euclidean space, two vectors are orthogonal if they meet at a right angle. The dot product measures "how much they point in the same direction":

$$\langle \mathbf{u}, \mathbf{v} \rangle = \|\mathbf{u}\| \|\mathbf{v}\| \cos\theta$$

• $\theta = 0 degrees$: $\langle\mathbf{u},\mathbf{v}\rangle = \|\mathbf{u}\|\|\mathbf{v}\|$ (parallel, maximum alignment)
• $\theta = 90 degrees$: $\langle\mathbf{u},\mathbf{v}\rangle = 0$ (orthogonal, zero alignment)
• $\theta = 180 degrees$: $\langle\mathbf{u},\mathbf{v}\rangle = -\|\mathbf{u}\|\|\mathbf{v}\|$ (antiparallel, maximum anti-alignment)

The projection picture. The orthogonal projection of $\mathbf{v}$ onto $\mathbf{u}$ is the "shadow" of $\mathbf{v}$ cast perpendicularly onto the line through $\mathbf{u}$:

$$\text{proj}_{\mathbf{u}}\mathbf{v} = \frac{\langle\mathbf{v},\mathbf{u}\rangle}{\|\mathbf{u}\|^2}\mathbf{u}$$

The error $\mathbf{v} - \text{proj}_{\mathbf{u}}\mathbf{v}$ is orthogonal to $\mathbf{u}$. This Pythagorean decomposition is the geometric core of all least-squares theory.

Orthonormal bases as "rulers." A set of orthonormal vectors $\{\mathbf{q}_1, \ldots, \mathbf{q}_n\}$ forms a perfect coordinate system: each $\mathbf{q}_i$ is a unit "ruler" pointing in an independent direction. The coordinate of $\mathbf{v}$ along $\mathbf{q}_i$ is exactly $\langle\mathbf{v}, \mathbf{q}_i\rangle$ - how far $\mathbf{v}$ extends in the $i$-th direction.

1.3 Why Orthogonality Matters for AI

PCA finds orthogonal directions of variance. The principal components are the eigenvectors of the sample covariance matrix $C = X^\top X/(n-1)$. By the spectral theorem (7), these eigenvectors are orthogonal. PCA is possible - and gives uncorrelated components - precisely because of orthogonality.

Attention subspaces. In multi-head attention, each head projects queries and keys into a $d_k$-dimensional subspace. The heads are designed to attend to different aspects of the input. The more orthogonal the subspaces, the more independent information each head extracts.

Orthogonal weight initialization (Saxe et al., 2013) initializes weight matrices as random orthogonal matrices (via QR decomposition of a random Gaussian matrix). This preserves the norm of activations and gradients through linear layers, enabling training of very deep networks without vanishing/exploding gradients.

RoPE (Su et al., 2023) encodes position $m$ by rotating the query/key vectors by angle $m\theta_i$ in each 2D subspace. The key property: the dot product between a rotated query at position $m$ and a rotated key at position $n$ depends only on $(m-n)$ - position appears as a relative rotation. This works because rotation is orthogonal: it preserves the magnitude of inner products.

Numerical stability. QR decomposition is the backbone of numerical linear algebra. Householder QR is used to solve least-squares problems, compute eigenvalues (QR iteration), and factor matrices. Its superiority over LU (for rectangular systems) stems from orthogonality: the Householder reflectors are orthogonal transformations that never amplify errors.

1.4 Historical Timeline

---

2. Formal Definitions

2.1 Inner Products and the Angle Formula

Definition (Inner Product). A real inner product on a vector space $V$ is a function $\langle \cdot, \cdot \rangle: V \times V \to \mathbb{R}$ satisfying:

1. Symmetry: $\langle \mathbf{u}, \mathbf{v} \rangle = \langle \mathbf{v}, \mathbf{u} \rangle$
2. Linearity in first argument: $\langle a\mathbf{u} + b\mathbf{v}, \mathbf{w} \rangle = a\langle\mathbf{u},\mathbf{w}\rangle + b\langle\mathbf{v},\mathbf{w}\rangle$
3. Positive definiteness: $\langle \mathbf{v}, \mathbf{v} \rangle \geq 0$ with equality iff $\mathbf{v} = \mathbf{0}$

The standard inner product (dot product) on $\mathbb{R}^n$ is $\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^\top \mathbf{v} = \sum_{i=1}^n u_i v_i$.

The induced norm: $\|\mathbf{v}\| = \sqrt{\langle\mathbf{v},\mathbf{v}\rangle}$ is the Euclidean length of $\mathbf{v}$.

Theorem 2.1.1 (Cauchy-Schwarz Inequality). For any $\mathbf{u}, \mathbf{v}$ in an inner product space:

$$|\langle\mathbf{u},\mathbf{v}\rangle| \leq \|\mathbf{u}\| \cdot \|\mathbf{v}\|$$

with equality iff $\mathbf{u}$ and $\mathbf{v}$ are linearly dependent (one is a scalar multiple of the other).

Proof. For any $t \in \mathbb{R}$, $\|\mathbf{u} + t\mathbf{v}\|^2 \geq 0$. Expanding:

$$\|\mathbf{u}\|^2 + 2t\langle\mathbf{u},\mathbf{v}\rangle + t^2\|\mathbf{v}\|^2 \geq 0$$

This is a quadratic in $t$ that is always non-negative, so its discriminant must be $\leq 0$:

$$4\langle\mathbf{u},\mathbf{v}\rangle^2 - 4\|\mathbf{u}\|^2\|\mathbf{v}\|^2 \leq 0$$

which gives $|\langle\mathbf{u},\mathbf{v}\rangle| \leq \|\mathbf{u}\|\|\mathbf{v}\|$. Equality holds iff $t^* = -\langle\mathbf{u},\mathbf{v}\rangle/\|\mathbf{v}\|^2$ gives $\|\mathbf{u} + t^*\mathbf{v}\| = 0$, i.e., $\mathbf{u} = -t^*\mathbf{v}$. $\square$

The angle formula. By Cauchy-Schwarz, $-1 \leq \langle\mathbf{u},\mathbf{v}\rangle/(\|\mathbf{u}\|\|\mathbf{v}\|) \leq 1$, so it is valid to define the angle $\theta$ between $\mathbf{u}$ and $\mathbf{v}$ by:

$$\cos\theta = \frac{\langle\mathbf{u},\mathbf{v}\rangle}{\|\mathbf{u}\|\|\mathbf{v}\|}, \quad \theta \in [0, \pi]$$

Corollary (Triangle Inequality). $\|\mathbf{u} + \mathbf{v}\| \leq \|\mathbf{u}\| + \|\mathbf{v}\|$.

Proof: $\|\mathbf{u}+\mathbf{v}\|^2 = \|\mathbf{u}\|^2 + 2\langle\mathbf{u},\mathbf{v}\rangle + \|\mathbf{v}\|^2 \leq \|\mathbf{u}\|^2 + 2\|\mathbf{u}\|\|\mathbf{v}\| + \|\mathbf{v}\|^2 = (\|\mathbf{u}\|+\|\mathbf{v}\|)^2$. $\square$

2.2 Orthogonal and Orthonormal Vectors

Definition. Two vectors $\mathbf{u}, \mathbf{v}$ are orthogonal (written $\mathbf{u} \perp \mathbf{v}$) if $\langle\mathbf{u},\mathbf{v}\rangle = 0$.

A vector $\mathbf{v}$ is a unit vector if $\|\mathbf{v}\| = 1$. The normalization of nonzero $\mathbf{v}$ is $\hat{\mathbf{v}} = \mathbf{v}/\|\mathbf{v}\|$.

Two vectors are orthonormal if they are both orthogonal AND both unit vectors:

$$\langle\mathbf{q}_i, \mathbf{q}_j\rangle = \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases}$$

Key consequences of orthogonality:

1. Zero maps to everything: $\mathbf{0} \perp \mathbf{v}$ for all $\mathbf{v}$ (since $\langle\mathbf{0},\mathbf{v}\rangle = 0$).

2. Pythagorean theorem: If $\mathbf{u} \perp \mathbf{v}$, then $\|\mathbf{u} + \mathbf{v}\|^2 = \|\mathbf{u}\|^2 + \|\mathbf{v}\|^2$. Proof: $\|\mathbf{u}+\mathbf{v}\|^2 = \langle\mathbf{u}+\mathbf{v},\mathbf{u}+\mathbf{v}\rangle = \|\mathbf{u}\|^2 + 2\underbrace{\langle\mathbf{u},\mathbf{v}\rangle}_{=0} + \|\mathbf{v}\|^2$. $\square$

3. Generalized Pythagorean theorem: For mutually orthogonal $\mathbf{v}_1, \ldots, \mathbf{v}_k$:

$$\left\|\sum_{i=1}^k \mathbf{v}_i\right\|^2 = \sum_{i=1}^k \|\mathbf{v}_i\|^2$$

4. Linearity of orthogonality: If $\mathbf{u} \perp \mathbf{v}$ and $\mathbf{u} \perp \mathbf{w}$, then $\mathbf{u} \perp (a\mathbf{v} + b\mathbf{w})$ for all scalars $a, b$.

2.3 Orthogonal Sets and Linear Independence

Definition. A set $\{\mathbf{v}_1, \ldots, \mathbf{v}_k\}$ is an orthogonal set if $\langle\mathbf{v}_i,\mathbf{v}_j\rangle = 0$ for all $i \neq j$. It is an orthonormal set if additionally each $\|\mathbf{v}_i\| = 1$.

Theorem 2.3.1. Any orthogonal set of nonzero vectors is linearly independent.

Proof. Suppose $\sum_{i=1}^k c_i \mathbf{v}_i = \mathbf{0}$. Take the inner product of both sides with $\mathbf{v}_j$:

$$\left\langle \sum_i c_i \mathbf{v}_i, \mathbf{v}_j \right\rangle = c_j \langle\mathbf{v}_j,\mathbf{v}_j\rangle = c_j \|\mathbf{v}_j\|^2 = 0$$

Since $\mathbf{v}_j \neq \mathbf{0}$, we have $\|\mathbf{v}_j\|^2 > 0$, so $c_j = 0$. This holds for all $j$. $\square$

Remark. This theorem gives an effortless proof of linear independence for orthogonal sets - no row reduction needed. The inner product "isolates" each coefficient.

Non-examples:

• $\{(1,0), (1,1)\}$ is not orthogonal: $\langle(1,0),(1,1)\rangle = 1 \neq 0$.
• $\{(1,1,0)/\sqrt{2}, (0,0,1), (1,-1,0)/\sqrt{2}, (1,0,0)\}$ - the last vector breaks orthogonality.

2.4 Orthonormal Bases

Definition. An orthonormal basis (ONB) for $V$ is a set $\{\mathbf{q}_1, \ldots, \mathbf{q}_n\}$ that is both orthonormal and a basis for $V$.

Theorem 2.4.1 (Fourier Coefficients). If $\{\mathbf{q}_1, \ldots, \mathbf{q}_n\}$ is an ONB for $V$, then for any $\mathbf{v} \in V$:

$$\mathbf{v} = \sum_{i=1}^n \langle\mathbf{v}, \mathbf{q}_i\rangle \mathbf{q}_i$$

The coefficients $\hat{v}_i = \langle\mathbf{v}, \mathbf{q}_i\rangle$ are called Fourier coefficients (or coordinates of $\mathbf{v}$ in the ONB).

Proof. Since $\{\mathbf{q}_i\}$ is a basis, $\mathbf{v} = \sum_j c_j \mathbf{q}_j$ for some unique $c_j$. Taking the inner product with $\mathbf{q}_i$:

$$\langle\mathbf{v}, \mathbf{q}_i\rangle = \sum_j c_j \langle\mathbf{q}_j, \mathbf{q}_i\rangle = \sum_j c_j \delta_{ji} = c_i \quad \square$$

Theorem 2.4.2 (Parseval's Identity). Under the same conditions:

$$\|\mathbf{v}\|^2 = \sum_{i=1}^n |\langle\mathbf{v}, \mathbf{q}_i\rangle|^2 = \sum_{i=1}^n |\hat{v}_i|^2$$

Proof. $\|\mathbf{v}\|^2 = \langle\sum_i \hat{v}_i\mathbf{q}_i, \sum_j \hat{v}_j\mathbf{q}_j\rangle = \sum_{i,j} \hat{v}_i\hat{v}_j \langle\mathbf{q}_i,\mathbf{q}_j\rangle = \sum_i \hat{v}_i^2$. $\square$

Remark. Parseval's identity says: in an ONB, the squared norm equals the sum of squared coordinates. There are no cross terms - the orthonormality kills them all. This is the high-dimensional Pythagorean theorem.

Matrix form. Assembling the ONB into a matrix $Q = [\mathbf{q}_1 | \cdots | \mathbf{q}_n]$, the Fourier decomposition is simply $\mathbf{v} = Q(Q^\top\mathbf{v})$: first compute coordinates $\hat{\mathbf{v}} = Q^\top\mathbf{v}$, then reconstruct $\mathbf{v} = Q\hat{\mathbf{v}}$.

2.5 Orthogonal Complements

Definition. Given a subspace $S \subseteq V$, the orthogonal complement is:

$$S^\perp = \{\mathbf{v} \in V : \langle\mathbf{v},\mathbf{s}\rangle = 0 \text{ for all } \mathbf{s} \in S\}$$

Theorem 2.5.1. $S^\perp$ is a subspace of $V$.

Proof: If $\mathbf{u}, \mathbf{v} \in S^\perp$ and $a, b \in \mathbb{R}$, then for any $\mathbf{s} \in S$: $\langle a\mathbf{u}+b\mathbf{v}, \mathbf{s}\rangle = a\langle\mathbf{u},\mathbf{s}\rangle + b\langle\mathbf{v},\mathbf{s}\rangle = 0$. $\square$

Theorem 2.5.2 (Orthogonal Decomposition). If $V$ is finite-dimensional and $S$ is a subspace, then:

$$V = S \oplus S^\perp \quad (\text{direct sum})$$

Every $\mathbf{v} \in V$ decomposes uniquely as $\mathbf{v} = \mathbf{v}_S + \mathbf{v}_{S^\perp}$ with $\mathbf{v}_S \in S$ and $\mathbf{v}_{S^\perp} \in S^\perp$.

Moreover: $\dim(S) + \dim(S^\perp) = \dim(V)$.

Proof. Let $\{\mathbf{q}_1, \ldots, \mathbf{q}_k\}$ be an ONB for $S$. Define $\mathbf{v}_S = \sum_{i=1}^k \langle\mathbf{v},\mathbf{q}_i\rangle\mathbf{q}_i$ (projection onto $S$) and $\mathbf{v}_{S^\perp} = \mathbf{v} - \mathbf{v}_S$. Then $\mathbf{v} = \mathbf{v}_S + \mathbf{v}_{S^\perp}$ with $\mathbf{v}_S \in S$. For any $\mathbf{q}_j$:

$$\langle\mathbf{v}_{S^\perp}, \mathbf{q}_j\rangle = \langle\mathbf{v},\mathbf{q}_j\rangle - \langle\mathbf{v}_S,\mathbf{q}_j\rangle = \langle\mathbf{v},\mathbf{q}_j\rangle - \langle\mathbf{v},\mathbf{q}_j\rangle = 0$$

So $\mathbf{v}_{S^\perp} \perp \mathbf{q}_j$ for all $j$, hence $\mathbf{v}_{S^\perp} \in S^\perp$. Uniqueness: if $\mathbf{v} = \mathbf{w}_S + \mathbf{w}_{S^\perp}$ also, then $\mathbf{v}_S - \mathbf{w}_S = \mathbf{w}_{S^\perp} - \mathbf{v}_{S^\perp} \in S \cap S^\perp = \{\mathbf{0}\}$. $\square$

Connection to the four fundamental subspaces. For $A \in \mathbb{R}^{m \times n}$:

• $\operatorname{null}(A) = \operatorname{row}(A)^\perp$ in $\mathbb{R}^n$
• $\operatorname{null}(A^\top) = \operatorname{col}(A)^\perp$ in $\mathbb{R}^m$

These orthogonality relations are the deep structure behind the four fundamental subspaces (see 04: Linear Transformations 4.5).

2.6 Orthogonality in Complex Inner Product Spaces

The theory extends to complex vector spaces with a Hermitian (sesquilinear) inner product:

$$\langle\mathbf{u},\mathbf{v}\rangle = \sum_{k=1}^n \overline{u_k}v_k$$

The complex analog of orthogonal matrices is unitary matrices $U \in \mathbb{C}^{n \times n}$ satisfying $U^*U = I$, where $U^* = \overline{U}^\top$ is the conjugate transpose.

Unitary group: $\mathcal{U}(n) = \{U \in \mathbb{C}^{n \times n} : U^*U = I\}$ contains all $n \times n$ unitary matrices. It reduces to $O(n)$ when restricted to real matrices.

Special unitary group: $\mathcal{SU}(n) = \{U \in \mathcal{U}(n) : \det(U) = 1\}$.

Key properties of unitary matrices:

• $|\det(U)| = 1$ (complex number of modulus 1, not just $\pm 1$)
• Eigenvalues lie on the unit circle: $|\lambda_i| = 1$
• Preserve complex inner products: $\langle U\mathbf{u}, U\mathbf{v}\rangle = \langle\mathbf{u},\mathbf{v}\rangle$
• The DFT matrix $F_n/\sqrt{n}$ is unitary (not orthogonal, since its entries are complex)

Hermitian matrices ($A = A^*$) are the complex analogs of real symmetric matrices. The spectral theorem holds: every Hermitian matrix has real eigenvalues and a unitary eigenbasis.

For AI, complex-valued neural networks and quantum computing naturally use unitary matrices. The DFT, crucial for signal processing and some positional encoding schemes, is a unitary transform in $\mathbb{C}^n$.

2.7 Abstract Inner Product Spaces: Axioms

We have been working with the Euclidean inner product $\langle\mathbf{u},\mathbf{v}\rangle = \mathbf{u}^\top\mathbf{v}$. More generally, an inner product on a real vector space $V$ is a bilinear map $\langle\cdot,\cdot\rangle: V \times V \to \mathbb{R}$ satisfying:

Any positive definite symmetric matrix $M \succ 0$ defines an inner product:

$$\langle\mathbf{u},\mathbf{v}\rangle_M = \mathbf{u}^\top M\mathbf{v}$$

Example (precision-weighted inner product): In Bayesian statistics, the Mahalanobis distance between $\mathbf{x}$ and $\boldsymbol{\mu}$ is:

$$d_M(\mathbf{x},\boldsymbol{\mu}) = \sqrt{(\mathbf{x}-\boldsymbol{\mu})^\top \Sigma^{-1}(\mathbf{x}-\boldsymbol{\mu})}$$

This is the distance induced by the inner product $\langle\mathbf{u},\mathbf{v}\rangle_{\Sigma^{-1}} = \mathbf{u}^\top\Sigma^{-1}\mathbf{v}$. In this metric, vectors along high-variance directions of $\Sigma$ are "shorter" (the precision $\Sigma^{-1}$ down-weights those directions).

Orthogonality is metric-dependent. Vectors that are orthogonal in the Euclidean metric may not be orthogonal in the Mahalanobis metric, and vice versa. The choice of inner product determines what "perpendicular" means.

For ML: The natural gradient method (Amari 1998) uses the Fisher information matrix $F$ to define the inner product, giving rise to a geometry where parameter updates are $\Delta\theta = F^{-1}\nabla\mathcal{L}$. This is gradient descent in the Riemannian metric $\langle\Delta\theta_1, \Delta\theta_2\rangle_F = \Delta\theta_1^\top F \Delta\theta_2$.

---

3. Orthogonal Matrices

3.1 Definition and Characterizations

Definition. A square matrix $Q \in \mathbb{R}^{n \times n}$ is orthogonal if:

$$Q^\top Q = QQ^\top = I_n$$

Equivalently, $Q^{-1} = Q^\top$ - the transpose is the inverse.

Characterization via columns. $Q$ is orthogonal if and only if its columns $\mathbf{q}_1, \ldots, \mathbf{q}_n$ form an orthonormal basis for $\mathbb{R}^n$:

$$\mathbf{q}_i^\top \mathbf{q}_j = \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases}$$

The condition $Q^\top Q = I$ encodes exactly these $n^2$ inner products.

Characterization via rows. By the symmetry $QQ^\top = I$, the rows of $Q$ also form an orthonormal basis. This is a non-trivial statement: a matrix whose columns are orthonormal must also have orthonormal rows (and vice versa).

Characterization via norms (isometry property). $Q$ is orthogonal if and only if it preserves the Euclidean norm:

$$\|Q\mathbf{x}\|_2 = \|\mathbf{x}\|_2 \quad \text{for all } \mathbf{x} \in \mathbb{R}^n$$

Proof: $\|Q\mathbf{x}\|^2 = (Q\mathbf{x})^\top(Q\mathbf{x}) = \mathbf{x}^\top Q^\top Q \mathbf{x} = \mathbf{x}^\top I \mathbf{x} = \|\mathbf{x}\|^2$. $\square$

Characterization via inner products. $Q$ preserves inner products:

$$\langle Q\mathbf{x}, Q\mathbf{y}\rangle = \langle\mathbf{x},\mathbf{y}\rangle \quad \text{for all } \mathbf{x}, \mathbf{y}$$

Proof: $(Q\mathbf{x})^\top(Q\mathbf{y}) = \mathbf{x}^\top Q^\top Q \mathbf{y} = \mathbf{x}^\top \mathbf{y}$. $\square$

This means orthogonal matrices preserve angles and distances - they are isometries of Euclidean space.

3.2 The Orthogonal Group and Special Orthogonal Group

The set of all $n \times n$ orthogonal matrices forms the orthogonal group:

$$O(n) = \{Q \in \mathbb{R}^{n \times n} : Q^\top Q = I\}$$

Group axioms:

• Closure: If $Q_1, Q_2 \in O(n)$, then $(Q_1 Q_2)^\top (Q_1 Q_2) = Q_2^\top Q_1^\top Q_1 Q_2 = I$, so $Q_1 Q_2 \in O(n)$.
• Identity: $I \in O(n)$.
• Inverses: $Q^{-1} = Q^\top \in O(n)$ (since $(Q^\top)^\top Q^\top = QQ^\top = I$).
• Associativity: Inherited from matrix multiplication.

Determinant. Since $\det(Q^\top Q) = \det(Q)^2 = \det(I) = 1$, we have $\det(Q) = \pm 1$.

• $\det(Q) = +1$: rotations - orientation-preserving isometries
• $\det(Q) = -1$: improper rotations - reflections (or rotation composed with a reflection)

The special orthogonal group $SO(n) = \{Q \in O(n) : \det(Q) = +1\}$ consists of pure rotations.

In 2D:

$$SO(2) = \left\{\begin{pmatrix}\cos\theta & -\sin\theta \\ \sin\theta & \cos\theta\end{pmatrix} : \theta \in [0,2\pi)\right\}$$

This is the group of rotations of the plane.

In 3D: $SO(3)$ parameterizes 3D rotations. This group is the configuration space of a rigid body and appears throughout robotics, computer vision, and physics. Its double cover $SU(2)$ appears in quaternion-based rotation representations used in game engines and IMUs.

3.3 Condition Number and Numerical Properties

The condition number of a matrix measures how much it amplifies errors:

$$\kappa(A) = \|A\| \cdot \|A^{-1}\| = \frac{\sigma_{\max}}{\sigma_{\min}}$$

For orthogonal matrices $Q$: all singular values equal 1, so $\kappa(Q) = 1/1 = 1$. Orthogonal matrices have the best possible condition number.

This means:

• Multiplying by $Q$ never amplifies rounding errors
• Solving $Q\mathbf{x} = \mathbf{b}$ is trivially stable: $\mathbf{x} = Q^\top\mathbf{b}$
• QR factorization (which uses orthogonal matrices) is numerically stable

For AI: Deep learning systems that maintain orthogonal weight matrices throughout training benefit from gradient signals that are neither exploding nor vanishing. The isometry property means the network's "signal amplification" is exactly 1 at those layers.

3.4 Eigenvalues of Orthogonal Matrices

Theorem. The eigenvalues of a real orthogonal matrix lie on the unit circle in $\mathbb{C}$: $|\lambda| = 1$.

Proof: If $Q\mathbf{v} = \lambda\mathbf{v}$ with $\mathbf{v} \neq \mathbf{0}$:

$$\|\mathbf{v}\| = \|Q\mathbf{v}\| = \|\lambda\mathbf{v}\| = |\lambda|\|\mathbf{v}\|$$

Dividing by $\|\mathbf{v}\| > 0$: $|\lambda| = 1$. $\square$

For real eigenvalues: $\lambda = +1$ (rotation-like) or $\lambda = -1$ (reflection-like). Complex eigenvalues come in conjugate pairs $e^{i\theta}, e^{-i\theta}$ corresponding to 2D rotations.

3.5 The Cayley Transform

The Cayley transform establishes a correspondence between orthogonal matrices and skew-symmetric matrices (matrices satisfying $S^\top = -S$).

Definition. For a skew-symmetric matrix $S$ (such that $I + S$ is invertible):

$$Q = (I - S)(I + S)^{-1}$$

Claim: $Q$ is orthogonal.

Proof: Using $(I + S)^\top = I - S$ (since $S^\top = -S$):

$$Q^\top Q = ((I+S)^{-1})^\top (I-S)^\top (I-S)(I+S)^{-1}$$ $$= (I-S)^{-1}(I+S)(I-S)(I+S)^{-1}$$

Since $S$ is skew-symmetric, $I-S$ and $I+S$ commute (they differ only by sign of $S$, which is a normal matrix in this context), so:

$$(I+S)(I-S) = I - S^2 = (I-S)(I+S)$$

Hence $Q^\top Q = (I-S)^{-1}(I-S)(I+S)(I+S)^{-1} = I$. $\square$

Inverse Cayley transform. Given orthogonal $Q$ without eigenvalue $-1$:

$$S = (I - Q)(I + Q)^{-1}$$

Why this matters:

• Skew-symmetric matrices form a vector space (easy to parameterize)
• The Cayley transform maps this space bijectively to "most" orthogonal matrices
• This gives a smooth parameterization of $O(n)$ near the identity - useful for Riemannian optimization

Example in 2D: $S = \begin{pmatrix}0 & -t \\ t & 0\end{pmatrix}$ (skew-symmetric) gives:

$$Q = \frac{1}{1+t^2}\begin{pmatrix}1-t^2 & -2t \\ 2t & 1-t^2\end{pmatrix}$$

With $t = \tan(\theta/2)$ (the Weierstrass substitution), this gives the rotation matrix $R_\theta$. The Cayley transform thus rationalizes the trigonometric functions appearing in rotation matrices.

Applications in neural networks: Neural networks that maintain orthogonal weight matrices throughout training can parameterize them via their skew-symmetric "log" and exponentiate via the matrix exponential or Cayley transform. This enables gradient descent on $O(n)$ using Lie algebra tools.

---

4. Orthogonal Projections

4.1 The Projection Formula

Definition. The orthogonal projection of $\mathbf{v}$ onto a subspace $S$ is the unique vector $\mathbf{v}_S \in S$ such that $\mathbf{v} - \mathbf{v}_S \perp S$.

Formula (1D case). Projection onto the line spanned by unit vector $\hat{\mathbf{u}}$:

$$\operatorname{proj}_{\hat{\mathbf{u}}}(\mathbf{v}) = \langle\mathbf{v},\hat{\mathbf{u}}\rangle\,\hat{\mathbf{u}} = \hat{\mathbf{u}}\hat{\mathbf{u}}^\top\mathbf{v}$$

The matrix $P = \hat{\mathbf{u}}\hat{\mathbf{u}}^\top$ is the rank-1 projection matrix.

Formula (general case). If $S = \operatorname{col}(A)$ for a matrix $A$ with linearly independent columns:

$$\operatorname{proj}_S(\mathbf{v}) = A(A^\top A)^{-1}A^\top\mathbf{v}$$

The matrix $P = A(A^\top A)^{-1}A^\top$ is the projection matrix onto $\operatorname{col}(A)$.

When $A$ has orthonormal columns (i.e., $A = Q$ with $Q^\top Q = I$), this simplifies dramatically:

$$P = QQ^\top$$

This is why orthonormal bases make projections computationally trivial.

4.2 Projection Matrices: Properties

A matrix $P$ is a projection if and only if it is idempotent: $P^2 = P$.

A projection is an orthogonal projection if and only if it is also symmetric: $P^\top = P$.

Verification: For $P = QQ^\top$ with $Q^\top Q = I$:

• Idempotent: $P^2 = QQ^\top QQ^\top = Q(Q^\top Q)Q^\top = QIQ^\top = QQ^\top = P$ OK
• Symmetric: $P^\top = (QQ^\top)^\top = QQ^\top = P$ OK

Eigenvalues of projections. $P$ is a projection if and only if its eigenvalues are 0 and 1.

Proof: If $P\mathbf{v} = \lambda\mathbf{v}$, then $\lambda\mathbf{v} = P\mathbf{v} = P^2\mathbf{v} = \lambda P\mathbf{v} = \lambda^2\mathbf{v}$, so $\lambda^2 = \lambda$, giving $\lambda = 0$ or $\lambda = 1$. $\square$

Geometrically: eigenvectors with $\lambda = 1$ lie in the range of $P$ (they are unchanged), while eigenvectors with $\lambda = 0$ lie in the null space (they are annihilated).

4.3 Best Approximation Theorem

Theorem (Best Approximation). The projection $\mathbf{v}_S = \operatorname{proj}_S(\mathbf{v})$ is the closest point in $S$ to $\mathbf{v}$:

$$\|\mathbf{v} - \mathbf{v}_S\|^2 \leq \|\mathbf{v} - \mathbf{s}\|^2 \quad \text{for all } \mathbf{s} \in S$$

with equality only when $\mathbf{s} = \mathbf{v}_S$.

Proof. For any $\mathbf{s} \in S$:

$$\|\mathbf{v} - \mathbf{s}\|^2 = \|(\mathbf{v}-\mathbf{v}_S) + (\mathbf{v}_S - \mathbf{s})\|^2 = \|\mathbf{v}-\mathbf{v}_S\|^2 + 2\langle\mathbf{v}-\mathbf{v}_S, \mathbf{v}_S-\mathbf{s}\rangle + \|\mathbf{v}_S-\mathbf{s}\|^2$$

Since $\mathbf{v}-\mathbf{v}_S \perp S$ and $\mathbf{v}_S - \mathbf{s} \in S$, the cross term vanishes:

$$= \|\mathbf{v}-\mathbf{v}_S\|^2 + \|\mathbf{v}_S-\mathbf{s}\|^2 \geq \|\mathbf{v}-\mathbf{v}_S\|^2 \quad \square$$

This theorem is everywhere in machine learning:

• Least squares: The normal equations give the projection of $\mathbf{b}$ onto $\operatorname{col}(A)$
• PCA: Principal components are the projection onto the subspace of maximum variance (-> 03: PCA)
• Attention: Softmax attention can be viewed as computing a weighted projection of value vectors
• Linear regression: The fitted values $\hat{\mathbf{y}} = H\mathbf{y}$ where $H = X(X^\top X)^{-1}X^\top$ is the hat matrix

4.4 Projection in Coordinate Systems

Given an ONB $\{\mathbf{q}_1, \ldots, \mathbf{q}_n\}$ for $\mathbb{R}^n$, the projection onto the subspace $S = \operatorname{span}(\mathbf{q}_1, \ldots, \mathbf{q}_k)$ (for $k \leq n$) is:

$$P_S = \sum_{i=1}^k \mathbf{q}_i\mathbf{q}_i^\top$$

This is a sum of rank-1 projectors, one per basis direction. The decomposition:

$$I = P_S + P_{S^\perp} = \sum_{i=1}^k \mathbf{q}_i\mathbf{q}_i^\top + \sum_{i=k+1}^n \mathbf{q}_i\mathbf{q}_i^\top$$

is the resolution of the identity - every vector is split into its $S$ and $S^\perp$ components.

---

5. Gram-Schmidt Orthogonalization

5.1 The Algorithm: Classical Gram-Schmidt

Problem. Given linearly independent vectors $\mathbf{a}_1, \ldots, \mathbf{a}_k$, construct an orthonormal basis for $\operatorname{span}(\mathbf{a}_1, \ldots, \mathbf{a}_k)$.

Classical Gram-Schmidt (CGS):

Initialization: $\mathbf{q}_1 = \mathbf{a}_1 / \|\mathbf{a}_1\|$

Iteration: For $j = 2, \ldots, k$:

$$\mathbf{u}_j = \mathbf{a}_j - \sum_{i=1}^{j-1}\langle\mathbf{a}_j, \mathbf{q}_i\rangle\,\mathbf{q}_i \qquad \mathbf{q}_j = \frac{\mathbf{u}_j}{\|\mathbf{u}_j\|}$$

What it does geometrically: At step $j$, we subtract the projection of $\mathbf{a}_j$ onto the span of the already-processed vectors, leaving the component orthogonal to everything before it. Normalizing gives the $j$-th orthonormal vector.

Inductive proof of correctness. After step $j$, $\{\mathbf{q}_1, \ldots, \mathbf{q}_j\}$ is an ONB for $\operatorname{span}(\mathbf{a}_1, \ldots, \mathbf{a}_j)$.

Base: $j=1$: $\mathbf{q}_1 = \mathbf{a}_1/\|\mathbf{a}_1\|$ is a unit vector spanning the same subspace. OK

Step: Assume true for $j-1$. Then $\mathbf{u}_j = \mathbf{a}_j - P_{j-1}\mathbf{a}_j$ where $P_{j-1}$ projects onto $\operatorname{span}(\mathbf{q}_1,\ldots,\mathbf{q}_{j-1})$.

For any $\ell < j$: $\langle\mathbf{u}_j, \mathbf{q}_\ell\rangle = \langle\mathbf{a}_j,\mathbf{q}_\ell\rangle - \langle\mathbf{a}_j,\mathbf{q}_\ell\rangle = 0$ OK

Since $\mathbf{a}_1,\ldots,\mathbf{a}_j$ are independent, $\mathbf{u}_j \neq \mathbf{0}$ (otherwise $\mathbf{a}_j \in \operatorname{span}(\mathbf{a}_1,\ldots,\mathbf{a}_{j-1})$). So $\mathbf{q}_j = \mathbf{u}_j/\|\mathbf{u}_j\|$ is a valid unit vector. $\square$

5.2 Modified Gram-Schmidt

The numerical problem with CGS. In floating-point arithmetic, CGS can catastrophically lose orthogonality. This happens when $\mathbf{a}_j$ is nearly in the span of $\{\mathbf{a}_1,\ldots,\mathbf{a}_{j-1}\}$ - rounding errors in the projection subtraction can accumulate, producing a $\mathbf{u}_j$ that isn't truly orthogonal to earlier vectors.

Modified Gram-Schmidt (MGS) reorders the computation to orthogonalize against already-computed $\mathbf{q}_i$ sequentially rather than all at once:

for j = 1 to k:
    v = a_j
    for i = 1 to j-1:
        v = v - <v, q_i> q_i    # orthogonalize against q_i using CURRENT v
    q_j = v / ||v||

Why MGS is more stable. In CGS, all projections use the original $\mathbf{a}_j$. In MGS, after each orthogonalization step, the updated $\mathbf{v}$ is used - so numerical errors from the first projection are themselves projected away in subsequent steps.

Theorem (Bjorck 1967). MGS is backward stable: the computed $\hat{\mathbf{q}}_i$ satisfy $\hat{\mathbf{q}}_i^\top \hat{\mathbf{q}}_j = \delta_{ij} + O(\epsilon_{\text{mach}}\kappa(A))$ where $\kappa(A)$ is the condition number of the input matrix. CGS satisfies only $O(\epsilon_{\text{mach}}\kappa(A)^2)$.

Practical advice: Use MGS for explicit basis construction; use Householder for QR factorization (even more stable).

5.3 Gram-Schmidt and QR Factorization

Gram-Schmidt applied to the columns of $A = [\mathbf{a}_1|\cdots|\mathbf{a}_n]$ produces a QR factorization:

$$A = QR$$

where $Q = [\mathbf{q}_1|\cdots|\mathbf{q}_n]$ has orthonormal columns and $R$ is upper triangular with:

$$R_{ij} = \begin{cases}\langle\mathbf{a}_j, \mathbf{q}_i\rangle & i < j \\ \|\mathbf{u}_j\| & i = j \\ 0 & i > j\end{cases}$$

The diagonal entries $R_{jj} = \|\mathbf{u}_j\|$ are positive (since $\mathbf{u}_j \neq \mathbf{0}$ for independent columns).

This gives a unique QR factorization of $A$ with positive diagonal entries of $R$.

For AI: Gram-Schmidt implicitly occurs in layer normalization variants, in computing orthogonal weight bases for LoRA, and in the derivation of stable training algorithms.

---

6. Householder Reflectors and Givens Rotations

6.1 Householder Reflectors

Motivation. While Gram-Schmidt produces QR by building $Q$ column by column, Householder applies successive orthogonal transformations to reduce $A$ to upper triangular form $R$ directly - achieving greater numerical stability.

Definition. The Householder reflector determined by unit vector $\mathbf{n}$ (the normal to the mirror) is:

$$H = I - 2\mathbf{n}\mathbf{n}^\top$$

Properties:

• Symmetric: $H^\top = H$ OK
• Orthogonal: $H^\top H = H^2 = (I - 2\mathbf{n}\mathbf{n}^\top)^2 = I - 4\mathbf{n}\mathbf{n}^\top + 4\mathbf{n}\mathbf{n}^\top\mathbf{n}\mathbf{n}^\top = I - 4\mathbf{n}\mathbf{n}^\top + 4\mathbf{n}\mathbf{n}^\top = I$ OK
• Involution: $H^2 = I$, so $H = H^{-1}$ OK
• Determinant: $\det(H) = -1$ (it's a reflection, not a rotation)

Action: $H$ reflects any vector across the hyperplane with normal $\mathbf{n}$:

• Vectors in $\mathbf{n}^\perp$ are unchanged: $H\mathbf{v} = \mathbf{v}$ if $\langle\mathbf{v},\mathbf{n}\rangle = 0$
• The vector $\mathbf{n}$ is negated: $H\mathbf{n} = \mathbf{n} - 2\mathbf{n} = -\mathbf{n}$

Zeroing a column. To zero out all components of $\mathbf{a}$ below the first entry: choose:

$$\mathbf{n} = \frac{\mathbf{a} + \|\mathbf{a}\|\mathbf{e}_1}{\|\mathbf{a} + \|\mathbf{a}\|\mathbf{e}_1\|} \quad \Rightarrow \quad H\mathbf{a} = -\|\mathbf{a}\|\mathbf{e}_1$$

(The $\pm$ sign choice avoids catastrophic cancellation when $a_1 > 0$.)

6.2 QR via Householder

To factor $A \in \mathbb{R}^{m \times n}$:

1. Find $H_1$ to zero the first column below row 1: $H_1 A$ has $\ast$ in position $(1,1)$ and zeros below
2. Find $H_2$ (acting on the $(n-1) \times (n-1)$ submatrix) to zero the second column below row 2
3. Continue: $H_{n} \cdots H_2 H_1 A = R$ (upper triangular)

Then $Q = H_1 H_2 \cdots H_n$ (product of reflectors, hence orthogonal), and $A = QR$.

Complexity: $O(mn^2 - n^3/3)$ flops - same asymptotic complexity as Gram-Schmidt but with better numerical constants.

Stability: Householder QR is backward stable, meaning the computed factors satisfy $\hat{Q}\hat{R} = A + E$ where $\|E\| = O(\epsilon_{\text{mach}}\|A\|)$.

6.3 Givens Rotations

Definition. The Givens rotation $G(i,j,\theta) \in \mathbb{R}^{n \times n}$ rotates in the $(i,j)$-plane:

$$G(i,j,\theta)_{kl} = \begin{cases} \cos\theta & k=l=i \text{ or } k=l=j \\ -\sin\theta & k=i, l=j \\ \sin\theta & k=j, l=i \\ \delta_{kl} & \text{otherwise} \end{cases}$$

Purpose: Choose $\theta$ to zero a specific element $a_{ji}$ by rotating in the $(i,j)$-plane.

When to use: Givens rotations are preferred when $A$ is sparse (each rotation affects only two rows/columns), for parallel computation, and in eigenvalue algorithms like QR iteration.

---

7. QR Decomposition: Theory and Applications

7.1 Existence and Uniqueness

Theorem (QR Decomposition). Every matrix $A \in \mathbb{R}^{m \times n}$ with $m \geq n$ admits a factorization:

$$A = QR$$

where $Q \in \mathbb{R}^{m \times n}$ has orthonormal columns ($Q^\top Q = I_n$) and $R \in \mathbb{R}^{n \times n}$ is upper triangular.

This is the thin (reduced) QR decomposition. There is also a full QR decomposition where $Q \in \mathbb{R}^{m \times m}$ is a full orthogonal matrix and $R \in \mathbb{R}^{m \times n}$ is upper trapezoidal.

Uniqueness (when $A$ has full column rank). If we require $R_{ii} > 0$ for all $i$, the thin QR decomposition is unique.

Proof sketch: Two decompositions $Q_1 R_1 = Q_2 R_2$ give $Q_2^\top Q_1 = R_2 R_1^{-1}$. The left side is orthogonal; the right side is upper triangular. An upper triangular orthogonal matrix must be diagonal with $\pm 1$ entries. With the sign convention $R_{ii} > 0$, this diagonal must be $I$. $\square$

When $A$ has rank $r < n$: The decomposition still exists but $R$ has $n - r$ zero diagonal entries. The columns of $Q$ corresponding to zero $R_{ii}$ can be chosen as any completion to an orthonormal set.

7.2 QR for Least Squares

Problem. Given $A \in \mathbb{R}^{m \times n}$ ($m > n$) and $\mathbf{b} \in \mathbb{R}^m$, solve:

$$\min_{\mathbf{x} \in \mathbb{R}^n} \|A\mathbf{x} - \mathbf{b}\|_2^2$$

Solution via QR. Let $A = QR$ (thin QR, $Q^\top Q = I$):

$$\|A\mathbf{x} - \mathbf{b}\|^2 = \|QR\mathbf{x} - \mathbf{b}\|^2 = \|R\mathbf{x} - Q^\top\mathbf{b}\|^2 + \|(I - QQ^\top)\mathbf{b}\|^2$$

The second term is independent of $\mathbf{x}$, so the minimum occurs at:

$$R\mathbf{x} = Q^\top\mathbf{b}$$

This is an upper triangular system, solved by back substitution in $O(n^2)$ operations.

Comparison with normal equations. The normal equations $(A^\top A)\mathbf{x} = A^\top\mathbf{b}$ are equivalent but form $A^\top A$, which squares the condition number: $\kappa(A^\top A) = \kappa(A)^2$. QR avoids this squaring and is numerically preferred whenever $\kappa(A)$ is moderate.

7.3 QR Algorithm for Eigenvalues

Preview. The QR algorithm - the standard method for computing eigenvalues of symmetric matrices - works by iterating:

$$A_0 = A, \quad A_{k+1} = R_k Q_k \quad \text{where } A_k = Q_k R_k$$

Under mild conditions, $A_k \to$ upper triangular (Schur form) and the diagonal entries converge to eigenvalues. This connects orthogonal matrices directly to spectral theory.

Forward Reference: The full QR algorithm with shifts is covered in 08: Matrix Decompositions. The eigenvalue theory it computes is developed in 01: Eigenvalues and Eigenvectors.

---

8. The Spectral Theorem for Symmetric Matrices

8.1 Statement and Proof

Theorem (Spectral Theorem). Every real symmetric matrix $A = A^\top \in \mathbb{R}^{n \times n}$ has:

1. All eigenvalues are real: $\lambda_i \in \mathbb{R}$
2. Eigenvectors for distinct eigenvalues are orthogonal
3. There exists an orthonormal basis of eigenvectors: $A = Q\Lambda Q^\top$ where $Q \in O(n)$ and $\Lambda = \operatorname{diag}(\lambda_1, \ldots, \lambda_n)$

Proof of (1): Suppose $A\mathbf{v} = \lambda\mathbf{v}$ with $\mathbf{v} \in \mathbb{C}^n$, $\mathbf{v} \neq \mathbf{0}$. Take the Hermitian inner product:

$$\bar{\mathbf{v}}^\top A\mathbf{v} = \lambda\bar{\mathbf{v}}^\top\mathbf{v} = \lambda\|\mathbf{v}\|^2$$ $$\overline{\bar{\mathbf{v}}^\top A\mathbf{v}} = \bar{\mathbf{v}}^\top A^\top\mathbf{v} = \bar{\mathbf{v}}^\top A\mathbf{v} \quad (\text{since } A = A^\top)$$

So $\lambda\|\mathbf{v}\|^2$ is real, hence $\lambda \in \mathbb{R}$. $\square$

Proof of (2): If $A\mathbf{u} = \lambda\mathbf{u}$ and $A\mathbf{v} = \mu\mathbf{v}$ with $\lambda \neq \mu$:

$$\lambda\langle\mathbf{u},\mathbf{v}\rangle = \langle A\mathbf{u},\mathbf{v}\rangle = \langle\mathbf{u},A^\top\mathbf{v}\rangle = \langle\mathbf{u},A\mathbf{v}\rangle = \mu\langle\mathbf{u},\mathbf{v}\rangle$$

$(\lambda - \mu)\langle\mathbf{u},\mathbf{v}\rangle = 0$. Since $\lambda \neq \mu$: $\langle\mathbf{u},\mathbf{v}\rangle = 0$. $\square$

Proof of (3): By induction. The base case ($n=1$) is trivial. For the inductive step: let $\mathbf{q}_1$ be a unit eigenvector for eigenvalue $\lambda_1$. Let $W = \mathbf{q}_1^\perp$ (the orthogonal complement). Since $A$ is symmetric, $W$ is $A$-invariant (if $\langle\mathbf{w},\mathbf{q}_1\rangle = 0$, then $\langle A\mathbf{w},\mathbf{q}_1\rangle = \langle\mathbf{w},A\mathbf{q}_1\rangle = \lambda_1\langle\mathbf{w},\mathbf{q}_1\rangle = 0$). Apply the inductive hypothesis to the $(n-1)\times(n-1)$ symmetric restriction $A|_W$. $\square$

8.2 The Rayleigh Quotient

Definition. The Rayleigh quotient of a symmetric matrix $A$ at vector $\mathbf{x} \neq \mathbf{0}$ is:

$$R_A(\mathbf{x}) = \frac{\mathbf{x}^\top A\mathbf{x}}{\mathbf{x}^\top\mathbf{x}}$$

Key properties:

• $R_A(\mathbf{q}_i) = \lambda_i$ for eigenvectors $\mathbf{q}_i$
• $\lambda_{\min} \leq R_A(\mathbf{x}) \leq \lambda_{\max}$ for all $\mathbf{x}$
• $\max_{\mathbf{x}} R_A(\mathbf{x}) = \lambda_{\max}$, achieved at the top eigenvector
• $\min_{\mathbf{x}} R_A(\mathbf{x}) = \lambda_{\min}$, achieved at the bottom eigenvector

Proof of bounds: Expand $\mathbf{x} = \sum_i c_i \mathbf{q}_i$ in the eigenbasis:

$$R_A(\mathbf{x}) = \frac{\sum_i c_i^2 \lambda_i}{\sum_i c_i^2}$$

This is a weighted average of eigenvalues, hence bounded by $[\lambda_{\min}, \lambda_{\max}]$. $\square$

Courant-Fischer Min-Max Theorem. The $k$-th largest eigenvalue satisfies:

$$\lambda_k = \max_{\dim S = k}\, \min_{\mathbf{x} \in S \setminus \{0\}} R_A(\mathbf{x}) = \min_{\dim S = n-k+1}\, \max_{\mathbf{x} \in S \setminus \{0\}} R_A(\mathbf{x})$$

This variational characterization is fundamental to perturbation theory and numerical linear algebra.

8.3 Quadratic Forms and Symmetric Matrices

A quadratic form is $f(\mathbf{x}) = \mathbf{x}^\top A\mathbf{x} = \sum_{i,j} A_{ij} x_i x_j$ for symmetric $A$.

Positive definiteness via the spectral theorem: $A \succ 0$ (positive definite) $\Leftrightarrow$ all eigenvalues $> 0$.

Proof: In the eigenbasis, $\mathbf{x}^\top A\mathbf{x} = \sum_i \lambda_i c_i^2$. This is positive for all $\mathbf{x} \neq \mathbf{0}$ iff all $\lambda_i > 0$. $\square$

For AI: The Hessian $\nabla^2\mathcal{L}$ of a loss function is symmetric. Its eigenvalues tell us the curvature in each direction - large eigenvalues are "sharp" directions (fast loss change), small eigenvalues are "flat" directions. The Rayleigh quotient appears in sharpness-aware minimization (SAM), gradient clipping analysis, and understanding training dynamics.

---