Week 12: Symmetric and Positive Definite Matrices

You fill in a covariance matrix by hand, call np.linalg.cholesky, and get LinAlgError: Matrix is not positive definite. The matrix, $\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$, is symmetric with every entry positive. It is still no covariance. The signs of the eigenvalues decide that, and they set the shape of $z = x^TAx$.

The surface is $z = x^TAx$ for a symmetric $A$ with eigenvalues $3$ and $\lambda_2$. The slider moves $\lambda_2$: above $0$ a bowl, at $0$ a trough, below $0$ a saddle. The solid contour is $x^TAx = 1$. The caption prints the three tests.

The spectral theorem#

A real matrix is symmetric when $A = A^T$, as covariance matrices and Hessians are. The spectral theorem says that every real symmetric $n \times n$ matrix has $n$ real eigenvalues and an orthonormal basis of eigenvectors:

Against $A = S\Lambda S^{-1}$ from Week 10, no eigenvalue is complex, and $S^{-1}$ is just $Q^T$.

Why the eigenvectors are orthogonal. Take $Aq_1 = \lambda_1 q_1$ and $Aq_2 = \lambda_2 q_2$ with $\lambda_1 \neq \lambda_2$. Then

so $(\lambda_1 - \lambda_2)\, q_2^T q_1 = 0$ and $q_2^T q_1 = 0$. The middle step uses $A^T = A$. Within a repeated eigenvalue, Gram–Schmidt (Week 8) picks an orthonormal basis.

The scene builds $A$ from this formula. It fixes $q_1 = (1, 1)/\sqrt{2}$ with $\lambda_1 = 3$, and $q_2 = (1, -1)/\sqrt{2}$ with eigenvalue $\lambda_2$:

At the default $\lambda_2 = 1$ this is $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$. Trace $4$ and determinant $3$ give $\lambda^2 - 4\lambda + 3 = 0$, so the eigenvalues are $3$ and $1$.

The quadratic form in eigen-coordinates#

The quadratic form of a symmetric $A = \begin{pmatrix} a & b \\ b & c \end{pmatrix}$ is

Change to eigen-coordinates $y = Q^Tx$, so $x = Qy$. The cross term disappears:

In the scene that is $3y_1^2 + \lambda_2 y_2^2$. Two parabolas are drawn on the surface. The dashed one, along $q_1$, is $z = 3t^2$ at every setting. The amber one, along $q_2$, is $z = \lambda_2 t^2$, which goes flat and then opens down as the slider crosses $0$.

Three tests for positive definiteness#

$A$ is positive definite ($A \succ 0$) when $x^TAx > 0$ for every $x \neq 0$. It is positive semidefinite when $x^TAx \ge 0$, and indefinite when the form takes both signs. A Hessian that is positive definite everywhere makes a function strictly convex (Optimization Week 2). Three tests agree for every real symmetric $A$ (Strang, §6.4):

1. Eigenvalues. Every $\lambda_i > 0$. Use $x^TAx = \sum \lambda_i y_i^2$ with $\|y\| = \|x\|$.
2. Pivots. Elimination without row exchanges gives positive pivots. Equivalently, $A = LDL^T$ has a positive $D$, and Cholesky succeeds.
3. Leading determinants. Every upper-left $k \times k$ determinant is positive (Sylvester's criterion). For $2 \times 2$ that is $a > 0$ and $ac - b^2 > 0$.

In the scene, $a = (3 + \lambda_2)/2$ and $\det A = 3\lambda_2$, so the second pivot is

At $\lambda_2 = 1$ the pivots are $2$ and $1.5$, the determinants are $2$ and $3$, and all three tests pass. All three change sign at the same slider setting, $\lambda_2 = 0$, because each one carries the factor $\lambda_2$.

Positive entries prove nothing. Set the slider to $\lambda_2 = -1$. Then $A = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$, the matrix from the opening. Every entry is positive, and the surface is a saddle: at $x = (1, -1)$ the form is $1 - 4 + 1 = -2$. A positive diagonal is necessary, since $a = e_1^TAe_1$, but not sufficient.

Level sets: ellipse, lines, hyperbola#

In eigen-coordinates the level set $x^TAx = 1$ is $3y_1^2 + \lambda_2 y_2^2 = 1$.

• $\lambda_2 > 0$: an ellipse with half-axes $1/\sqrt{3}$ along $q_1$ and $1/\sqrt{\lambda_2}$ along $q_2$. A large eigenvalue gives a short axis.
• $\lambda_2 = 0$: two lines $y_1 = \pm 1/\sqrt{3}$, parallel to the trough's floor along $q_2$.
• $\lambda_2 < 0$: a hyperbola. The form is positive near $q_1$ and negative near $q_2$.

Next week. For any $B$, $B^TB$ is positive semidefinite, since $x^TB^TBx = \|Bx\|^2$.

Knowledge Check#

Browser lab: three tests at three slider settings#

Build the scene's matrix at three slider settings, run the three tests and Cholesky, and plot $x^TAx = 1$.

import numpy as np
import matplotlib.pyplot as plt

def scene_matrix(lam2):
    # 3 q1 q1ᵀ + lam2 q2 q2ᵀ with q1 = (1, 1)/√2 and q2 = (1, −1)/√2
    return 0.5 * np.array([[3 + lam2, 3 - lam2], [3 - lam2, 3 + lam2]])

u, v = np.meshgrid(np.linspace(-1.5, 1.5, 301), np.linspace(-1.5, 1.5, 301))
fig, axes = plt.subplots(1, 3, figsize=(10, 3.6))

for ax, lam2 in zip(axes, [1.0, 0.0, -1.0]):
    A = scene_matrix(lam2)
    eig = np.linalg.eigvalsh(A)
    det = A[0, 0] * A[1, 1] - A[0, 1] ** 2
    pivots = [A[0, 0], det / A[0, 0]]
    minors = [A[0, 0], det]
    try:
        np.linalg.cholesky(A)
        chol = "succeeds"
    except np.linalg.LinAlgError:
        chol = "fails"
    print(f"lam2 = {lam2:+.0f}  A = {A.round(2).tolist()}")
    print(f"   eigenvalues {eig.round(3)}  pivots {np.round(pivots, 3)}  minors {np.round(minors, 3)}  Cholesky {chol}")

    f = A[0, 0] * u**2 + 2 * A[0, 1] * u * v + A[1, 1] * v**2
    ax.contour(u, v, f, levels=[1.0])
    ax.set_aspect("equal")
    ax.set_title(f"λ₂ = {lam2:+.0f}: xᵀAx = 1")

plt.tight_layout()
plt.show()

The printed values match the caption at each setting. At $0$ the exact second pivot is $0$, so Cholesky's verdict there turns on rounding. Test a semidefinite matrix by its eigenvalues, with a tolerance. The plots show an ellipse, two lines and a hyperbola. Add -2.0 to the list and predict the second pivot first: $6\lambda_2/(3 + \lambda_2) = -12$.

Key takeaways#

The signs of the eigenvalues of a symmetric $A$ set the shape of $z = x^TAx$. With $\lambda_1 = 3$, a positive $\lambda_2$ gives a bowl, zero a trough, and negative a saddle. Eigenvalues, pivots and leading determinants agree, and in the scene all three flip at $\lambda_2 = 0$. Positive entries prove nothing, since $\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ is a saddle. The level set $x^TAx = 1$ is an ellipse with half-axes $1/\sqrt{\lambda_i}$ only when every $\lambda_i > 0$.

Further reading#

• Strang, G. Introduction to Linear Algebra, 6th ed. — §6.2 Symmetric Matrices, §6.4 Positive Definite Matrices
• Trefethen, L.N. & Bau, D. Numerical Linear Algebra — Lecture 25 (Spectral Theorem)