Quadratic forms & positive definiteness

Loss surfaces, covariance matrices, and curvature in optimization all wear the same algebraic dress: a quadratic form. Reading the signs of the eigenvalues tells you whether the bowl opens up everywhere, flattens out, or has saddle directions.

Definition

A quadratic form in $x \in \mathbb{R}^n$ is a scalar function[1]

where $A \in \mathbb{R}^{n \times n}$. Without loss of generality, $A$ can always be taken symmetric: $x^\top A x = x^\top \frac{A + A^\top}{2} x$, so replace $A$ by its symmetrization. The cross-term $a_{ij} x_i x_j + a_{ji} x_j x_i = (a_{ij} + a_{ji}) x_i x_j$ shows that only the symmetric part matters.

For $n = 2$:

The level sets $q(x) = c$ are ellipses (when the form is definite) or hyperbolas (when it is indefinite).

Definiteness

A symmetric matrix $A$ is called:

Proof that eigenvalue signs determine definiteness. By the spectral theorem $A = Q\Lambda Q^\top$. Substitute $x = Qy$ (bijective since $Q$ is invertible):

If all $\lambda_i > 0$, the sum is positive whenever $y \neq 0$, i.e. whenever $x \neq 0$. If some $\lambda_i < 0$, choose $y = e_i$ (so $x = Qe_i = q_i$) to get $q(q_i) = \lambda_i < 0$. The sign pattern of the eigenvalues is exactly the definiteness. $\qquad\blacksquare$

Covariance matrices are PSD

If $X \in \mathbb{R}^{n \times d}$ is a data matrix (rows are observations), the sample covariance $\Sigma = \frac{1}{n} X^\top X$ (after centering) satisfies

so $\Sigma$ is PSD. Its eigenvalues are the squared singular values of $\frac{1}{\sqrt{n}} X$, and they are nonnegative.

Sylvester's criterion (practical test)

For a symmetric $A$, positive definiteness is equivalent to all leading principal minors being positive[2]. The $k$-th leading principal minor is the determinant of the top-left $k \times k$ block of $A$:

This gives an $O(n^3)$ test (compute $n$ determinants, each $O(k^3)$, amortized via Cholesky: if Cholesky succeeds, the matrix is PD).

Check it on arrays

import numpy as np

# PD matrix: A = Q diag(3,1) Q^T, eigenvalues 3 and 1
theta = np.pi / 6
Q = np.array([[np.cos(theta), -np.sin(theta)],
              [np.sin(theta),  np.cos(theta)]])
A = Q @ np.diag([3.0, 1.0]) @ Q.T

# Visualize q(x) on a grid and confirm q > 0 everywhere
x1, x2 = np.meshgrid(np.linspace(-1, 1, 40), np.linspace(-1, 1, 40))
X = np.stack([x1.ravel(), x2.ravel()])
q_vals = np.einsum("ij,jk,ik->i", X.T, A, X.T)   # batched x^T A x
print("min quadratic form value:", q_vals.min())    # > 0 (PD)

# Indefinite matrix: eigenvalues 3 and -1
A_indef = Q @ np.diag([3.0, -1.0]) @ Q.T
q_indef = np.einsum("ij,jk,ik->i", X.T, A_indef, X.T)
print("indefinite: min =", q_indef.min(), "max =", q_indef.max())  # neg and pos

# Cholesky as PD test
try:
    np.linalg.cholesky(A)
    print("A is PD: Cholesky succeeded")
except np.linalg.LinAlgError:
    print("not PD")

try:
    np.linalg.cholesky(A_indef)
    print("A_indef is PD")
except np.linalg.LinAlgError:
    print("A_indef is not PD: Cholesky failed")

The PD matrix's quadratic form stays positive; the indefinite one has both signs. Cholesky succeeds only for PD.

Exercises

Exercise 1. Classify $A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$ by computing its eigenvalues, then confirm the classification with Sylvester's criterion.

Exercise 2. Prove that if $A$ is positive definite then $A$ is invertible, and that $A^{-1}$ is also positive definite.

Exercise 3 (code). Generate a random symmetric matrix, shift it by $\mu I$ until it becomes positive definite, and confirm that Cholesky succeeds exactly when the smallest eigenvalue turns positive.

import numpy as np

rng = np.random.default_rng(5)
M = rng.normal(size=(6, 6))
S = (M + M.T) / 2                    # symmetric, generally indefinite

eigs = np.linalg.eigvalsh(S)
lam_min = eigs.min()

def is_pd(A):
    try:
        np.linalg.cholesky(A)
        return True
    except np.linalg.LinAlgError:
        return False

# Shift just below and just above the threshold -lam_min.
I = np.eye(6)
below = S + (-lam_min - 0.01) * I    # smallest eigenvalue still negative
above = S + (-lam_min + 0.01) * I    # smallest eigenvalue now positive

assert not is_pd(below)
assert is_pd(above)
print("min eigenvalue of S:", round(float(lam_min), 4),
      "-> PD once shifted past", round(float(-lam_min), 4))

The spectral decomposition of a rectangular matrix, where the same geometry extends to non-square transforms, is the SVD of the next lesson.