Exercises Notebook

Converted from exercises.ipynb for web reading.

Positive Definite Matrices - Exercises

This notebook contains 10 progressive exercises for 07-Positive-Definite-Matrices. 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: Classify Definiteness

Use eigenvalues to classify PD, PSD, NSD, ND, or indefinite.

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 - Classify Definiteness
header("Exercise 1: definiteness")
def classify(A,tol=1e-10):
    vals=la.eigvalsh((A+A.T)/2)
    if np.all(vals>tol): return 'PD'
    if np.all(vals>=-tol): return 'PSD'
    if np.all(vals<-tol): return 'ND'
    if np.all(vals<=tol): return 'NSD'
    return 'Indefinite'
checks=[(np.eye(2),'PD'),(np.diag([1.,0.]),'PSD'),(-np.eye(2),'ND'),(np.diag([1.,-1.]),'Indefinite')]
for A,expected in checks:
    got=classify(A); print(got); check_true("classification", got==expected)

Exercise 2: Sylvester Criterion

Check positive definiteness by leading principal minors.

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 - Sylvester Criterion
header("Exercise 2: Sylvester")
A=np.array([[4.,1.,0.],[1.,3.,1.],[0.,1.,2.]])
minors=[la.det(A[:k,:k]) for k in range(1,4)]
print("leading minors", minors)
check_true("all positive", all(m>0 for m in minors))
check_true("eigenvalues positive", np.all(la.eigvalsh(A)>0))

Exercise 3: Cholesky Factorization

Compute $A=LL^T$ for an SPD matrix.

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 - Cholesky Factorization
header("Exercise 3: Cholesky")
A=make_spd(3,seed=3)
L=la.cholesky(A)
check_close("A = L L^T", L@L.T, A)
check_true("positive diagonal", np.all(np.diag(L)>0))

Exercise 4: Quadratic Bowl

Minimize rac12 x^T A x-b^T x for SPD $A$.

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 - Quadratic Bowl
header("Exercise 4: quadratic minimizer")
A=make_spd(3,seed=4); b=np.array([1.,-2.,0.5])
x=la.solve(A,b)
grad=A@x-b
check_close("stationary gradient", grad, np.zeros(3))
check_true("unique minimizer because PD", np.all(la.eigvalsh(A)>0))

Exercise 5: Gaussian Sampling

Use Cholesky to sample from $N(\mu,\Sigma)$.

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 - Gaussian Sampling
header("Exercise 5: Gaussian sampling")
rng=np.random.default_rng(5); Sigma=np.array([[2.,0.6],[0.6,1.]])
L=la.cholesky(Sigma); Z=rng.normal(size=(20000,2)); X=Z@L.T
emp=np.cov(X,rowvar=False)
print("empirical covariance\n", emp)
check_close("sample covariance near Sigma", emp, Sigma, tol=0.05)

Exercise 6: Schur Complement

Use the Schur complement to test a block matrix for positive definiteness.

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 - Schur Complement
header("Exercise 6: Schur complement")
A=np.array([[3.,0.5],[0.5,2.]]); B=np.array([[0.2],[0.4]]); D=np.array([[1.5]])
M=np.block([[A,B],[B.T,D]])
S=D-B.T@la.inv(A)@B
check_true("A PD", np.all(la.eigvalsh(A)>0))
check_true("Schur PD", np.all(la.eigvalsh(S)>0))
check_true("block PD", np.all(la.eigvalsh(M)>0))

Exercise 7: Log-Det Gradient

Finite-difference check $abla_A \log\det A=A^{-T}$ for symmetric perturbations.

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 - Log-Det Gradient
header("Exercise 7: logdet gradient")
A=make_spd(3,seed=7); E=np.array([[0.,1.,0.],[1.,0.,0.],[0.,0.,0.]])
eps=1e-6
fd=(np.log(la.det(A+eps*E))-np.log(la.det(A-eps*E)))/(2*eps)
inner=np.sum(la.inv(A).T*E)
print("finite diff", fd, "inner", inner)
check_close("gradient check", fd, inner, tol=1e-6)

Exercise 8: Gram Matrices are PSD

Show $K=X X^T$ has nonnegative eigenvalues.

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 - Gram Matrices are PSD
header("Exercise 8: Gram PSD")
rng=np.random.default_rng(8); X=rng.normal(size=(6,3)); K=X@X.T
vals=la.eigvalsh(K)
print("min eigenvalue", vals[0])
check_true("PSD", vals[0] > -1e-10)
check_true("rank bound", la.matrix_rank(K) <= X.shape[1])

Exercise 9: Ridge Improves Conditioning

Add $\lambda I$ to a PSD matrix and observe condition number improvement.

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 - Ridge Improves Conditioning
header("Exercise 9: ridge conditioning")
A=np.diag([10.,1.,1e-4]); lam=0.1
print("cond before", la.cond(A), "after", la.cond(A+lam*np.eye(3)))
check_true("condition improves", la.cond(A+lam*np.eye(3)) < la.cond(A))
check_true("becomes PD", np.all(la.eigvalsh(A+lam*np.eye(3))>0))

Exercise 10: Gaussian Conditioning

Compute conditional covariance via a Schur complement.

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 - Gaussian Conditioning
header("Exercise 10: Gaussian conditioning")
Sxx=np.array([[2.,0.4],[0.4,1.5]]); Sxy=np.array([[0.3],[0.2]]); Syy=np.array([[1.]])
cond_cov=Sxx-Sxy@la.inv(Syy)@Sxy.T
print("conditional covariance\n", cond_cov)
check_true("conditional covariance PSD", np.all(la.eigvalsh(cond_cov)>0))
check_true("conditioning reduces determinant", la.det(cond_cov) < la.det(Sxx))