Exercises Notebook

Converted from exercises.ipynb for web reading.

Orthogonality and Orthonormality - Exercises

This notebook contains 10 progressive exercises for 05-Orthogonality-and-Orthonormality. Each exercise has a learner workspace followed by a complete reference solution. Use the solution cells after making a serious attempt.

Difficulty grows from direct computation to AI-facing interpretation. Formulas use LaTeX-in-Markdown with $...$ and `

$$...$$

`.

Code cell 2

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

try:
    import seaborn as sns
    sns.set_theme(style="whitegrid", palette="colorblind")
    HAS_SNS = True
except ImportError:
    plt.style.use("seaborn-v0_8-whitegrid")
    HAS_SNS = False

mpl.rcParams.update({
    "figure.figsize":    (10, 6),
    "figure.dpi":         120,
    "font.size":           13,
    "axes.titlesize":      15,
    "axes.labelsize":      13,
    "xtick.labelsize":     11,
    "ytick.labelsize":     11,
    "legend.fontsize":     11,
    "legend.framealpha":   0.85,
    "lines.linewidth":      2.0,
    "axes.spines.top":     False,
    "axes.spines.right":   False,
    "savefig.bbox":       "tight",
    "savefig.dpi":         150,
})
np.random.seed(42)
print("Plot setup complete.")

Code cell 3

import numpy as np
import numpy.linalg as la
import scipy.linalg as sla
from scipy import stats

np.set_printoptions(precision=8, suppress=True)
np.random.seed(42)

COLORS = {
    "primary": "#0077BB",
    "secondary": "#EE7733",
    "tertiary": "#009988",
    "error": "#CC3311",
    "neutral": "#555555",
    "highlight": "#EE3377",
}

def header(title):
    print("\n" + "=" * len(title))
    print(title)
    print("=" * len(title))

def check_true(name, cond):
    ok = bool(cond)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    return ok

def check_close(name, got, expected, tol=1e-8):
    ok = np.allclose(got, expected, atol=tol, rtol=tol)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    if not ok:
        print("  got     =", got)
        print("  expected=", expected)
    return ok

def softmax(z, axis=-1):
    z = np.asarray(z, dtype=float)
    z = z - np.max(z, axis=axis, keepdims=True)
    e = np.exp(z)
    return e / np.sum(e, axis=axis, keepdims=True)

def gram_schmidt_columns(A, tol=1e-12):
    A = np.asarray(A, dtype=float)
    Q = []
    for j in range(A.shape[1]):
        v = A[:, j].copy()
        for q in Q:
            v -= (q @ v) * q
        n = la.norm(v)
        if n > tol:
            Q.append(v / n)
    return np.column_stack(Q) if Q else np.empty((A.shape[0], 0))

def projection_matrix(A):
    Q = gram_schmidt_columns(A)
    return Q @ Q.T

def numerical_rank(A, tol=1e-10):
    return int(np.sum(la.svd(np.asarray(A, dtype=float), compute_uv=False) > tol))

def stable_rank(A):
    s = la.svd(np.asarray(A, dtype=float), compute_uv=False)
    return float(np.sum(s**2) / (s[0]**2 + 1e-15))

def make_spd(n, seed=0, ridge=0.5):
    rng = np.random.default_rng(seed)
    A = rng.normal(size=(n, n))
    return A.T @ A + ridge * np.eye(n)

print("Chapter 03 helper setup complete.")

Exercise 1: Projection Decomposition

Project a vector onto a subspace and verify orthogonal residual.

Code cell 5

# Your Solution
# Exercise 1 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 1.")

Code cell 6

# Solution
# Exercise 1 - Projection Decomposition
header("Exercise 1: projection")
A = np.array([[1.0, 0.0], [1.0, 1.0], [0.0, 1.0]])
v = np.array([3.0, 1.0, 2.0])
P = projection_matrix(A)
pv = P @ v; r = v - pv
check_close("residual orthogonal to columns", A.T @ r, np.zeros(A.shape[1]))
check_close("Pythagorean", la.norm(v)**2, la.norm(pv)**2 + la.norm(r)**2)

Exercise 2: Gram-Schmidt QR

Build $Q,R$ by Gram-Schmidt and verify $A=QR$.

Code cell 8

# Your Solution
# Exercise 2 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 2.")

Code cell 9

# Solution
# Exercise 2 - Gram-Schmidt QR
header("Exercise 2: Gram-Schmidt QR")
A = np.array([[1.0,1.0,0.0],[1.0,0.0,1.0],[0.0,1.0,1.0]])
Q = gram_schmidt_columns(A)
R = Q.T @ A
check_close("Q^T Q", Q.T @ Q, np.eye(3))
check_close("QR=A", Q @ R, A)

Exercise 3: Orthogonal Matrices Preserve Norms

Verify $\|Qx\|=\|x\|$ and inner products are preserved.

Code cell 11

# Your Solution
# Exercise 3 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 3.")

Code cell 12

# Solution
# Exercise 3 - Orthogonal Matrices Preserve Norms
header("Exercise 3: orthogonal isometry")
t = np.pi/5
Q = np.array([[np.cos(t), -np.sin(t)], [np.sin(t), np.cos(t)]])
x = np.array([2.0, -1.0]); y = np.array([0.5, 3.0])
check_close("norm preserved", la.norm(Q@x), la.norm(x))
check_close("inner product preserved", (Q@x)@(Q@y), x@y)

Exercise 4: Householder Reflector

Construct a reflector that maps $a$ to a multiple of $e_1$.

Code cell 14

# Your Solution
# Exercise 4 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 4.")

Code cell 15

# Solution
# Exercise 4 - Householder Reflector
header("Exercise 4: Householder")
a = np.array([3.0, 4.0, 0.0])
e1 = np.array([1.0, 0.0, 0.0])
v = a + np.sign(a[0]) * la.norm(a) * e1
v = v / la.norm(v)
H = np.eye(3) - 2*np.outer(v, v)
Ha = H @ a
check_close("H orthogonal", H.T @ H, np.eye(3))
check_true("zeros below first", la.norm(Ha[1:]) < 1e-12)

Exercise 5: Modified Gram-Schmidt Stability

Compare orthogonality errors on a Hilbert matrix.

Code cell 17

# Your Solution
# Exercise 5 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 5.")

Code cell 18

# Solution
# Exercise 5 - Modified Gram-Schmidt Stability
header("Exercise 5: MGS stability")
def cgs(A):
    Q=[]
    for j in range(A.shape[1]):
        v=A[:,j].copy()
        for q in Q: v -= (q@A[:,j])*q
        Q.append(v/la.norm(v))
    return np.column_stack(Q)
def mgs(A):
    V=A.copy().astype(float); Q=[]
    for j in range(V.shape[1]):
        q=V[:,j]/la.norm(V[:,j]); Q.append(q)
        for k in range(j+1,V.shape[1]): V[:,k]-=(q@V[:,k])*q
    return np.column_stack(Q)
H = sla.hilbert(10)
err_c = la.norm(cgs(H).T@cgs(H)-np.eye(10), ord=np.inf)
err_m = la.norm(mgs(H).T@mgs(H)-np.eye(10), ord=np.inf)
print("CGS error", err_c, "MGS error", err_m)
check_true("MGS improves orthogonality", err_m < err_c)

Exercise 6: QR Least Squares

Solve least squares via QR and compare with lstsq.

Code cell 20

# Your Solution
# Exercise 6 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 6.")

Code cell 21

# Solution
# Exercise 6 - QR Least Squares
header("Exercise 6: QR least squares")
A = np.vander(np.linspace(0,1,20), 4, increasing=True)
y = np.sin(np.linspace(0,1,20))
Q, R = la.qr(A, mode='reduced')
x_qr = sla.solve_triangular(R, Q.T@y)
x_ref = la.lstsq(A, y, rcond=None)[0]
check_close("QR matches lstsq", x_qr, x_ref)

Exercise 7: RoPE Rotation

Show that block rotations preserve inner products used by attention.

Code cell 23

# Your Solution
# Exercise 7 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 7.")

Code cell 24

# Solution
# Exercise 7 - RoPE Rotation
header("Exercise 7: RoPE inner products")
theta = 0.7
R = np.array([[np.cos(theta), -np.sin(theta)], [np.sin(theta), np.cos(theta)]])
q = np.array([1.0, 2.0]); k = np.array([-0.5, 0.3])
check_close("same rotation preserves dot", (R@q)@(R@k), q@k)
check_close("rotation orthogonal", R.T@R, np.eye(2))

Exercise 8: Orthogonal Initialization

Generate an orthogonal weight matrix and verify singular values equal one.

Code cell 26

# Your Solution
# Exercise 8 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 8.")

Code cell 27

# Solution
# Exercise 8 - Orthogonal Initialization
header("Exercise 8: orthogonal init")
rng = np.random.default_rng(8)
Q, _ = la.qr(rng.normal(size=(6,6)))
s = la.svd(Q, compute_uv=False)
check_close("all singular values one", s, np.ones(6))
check_close("gradient norm preserved", la.norm(Q@np.ones(6)), la.norm(np.ones(6)))

Exercise 9: Rayleigh Quotient Extremes

For symmetric $A$, evaluate quotient at eigenvectors.

Code cell 29

# Your Solution
# Exercise 9 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 9.")

Code cell 30

# Solution
# Exercise 9 - Rayleigh Quotient Extremes
header("Exercise 9: Rayleigh extremes")
A = np.array([[3.0, 1.0], [1.0, 2.0]])
vals, Q = la.eigh(A)
for i in range(2):
    r = Q[:,i] @ A @ Q[:,i]
    check_close(f"eigenvector {i} quotient", r, vals[i])

Exercise 10: Principal Angle

Compute the smallest principal angle between two subspaces.

Code cell 32

# Your Solution
# Exercise 10 - learner workspace
# Write your solution here, then run the reference solution below to compare.
print("Learner workspace ready for Exercise 10.")

Code cell 33

# Solution
# Exercise 10 - Principal Angle
header("Exercise 10: principal angle")
A = np.eye(3)[:, :2]
B = np.array([[1.0,0.0],[1.0,1.0],[0.0,1.0]])
QA = gram_schmidt_columns(A); QB = gram_schmidt_columns(B)
cosines = la.svd(QA.T @ QB, compute_uv=False)
angles = np.degrees(np.arccos(np.clip(cosines, -1, 1)))
print("principal angles:", angles)
check_true("angles in valid range", np.all((angles >= -1e-9) & (angles <= 90+1e-9)))