Positive definite and semidefinite matrices

WHY do we care? (the 80/20)

In ML almost every "energy", "loss curvature", "covariance", or "kernel" is a symmetric matrix, and we constantly need to know: does this thing behave like a valid bowl-shaped cost?

Optimization: a function's Hessian being PD ⇒ a strict local minimum, so gradient descent converges nicely.
Covariance matrices are always PSD (variance can't be negative).
Kernels (SVMs, Gaussian processes) must be PSD (Mercer's condition) to correspond to a valid inner product.
Cholesky / solving $Ax=b$ is fast and stable exactly when $A$ is PD.

So this single concept quietly powers loss landscapes, statistics, and kernel methods.

WHAT are the definitions?

We write $A \succ 0$ (PD) and $A \succeq 0$ (PSD). Negative (semi)definite flips the sign; indefinite means $x^\top A x$ takes both signs (a saddle).

HOW: deriving the eigenvalue test from scratch

We claim: for symmetric $A$ , " $x^\top A x>0$ for all $x\neq0$ " ⟺ "all eigenvalues $>0$ ".

Step 1 — Spectral theorem. A real symmetric matrix can be written $A = Q\Lambda Q^\top,\qquad Q^\top Q = I,\ \Lambda=\mathrm{diag}(\lambda_1,\dots,\lambda_n).$ Why this step? Symmetric matrices have real eigenvalues and an orthonormal eigenbasis — this is the key structural fact that lets us change coordinates without distortion.

Step 2 — Change of variables. Let $y = Q^\top x$ . Since $Q$ is orthogonal, $x\neq0 \iff y\neq0$ . Then $x^\top A x = x^\top Q\Lambda Q^\top x = (Q^\top x)^\top \Lambda (Q^\top x) = y^\top \Lambda y.$ Why this step? Rotating into the eigenbasis makes the matrix diagonal — the "cross terms" disappear.

Step 3 — Diagonal form. $y^\top \Lambda y = \sum_{i=1}^n \lambda_i\, y_i^2.$ Why this step? A diagonal quadratic form is just a weighted sum of squares — trivially readable.

Step 4 — Conclude. Each $y_i^2 \ge 0$ .

If all $\lambda_i>0$ , the sum is $>0$ whenever some $y_i\neq0$ ⇒ PD.
If some $\lambda_j\le 0$ , pick $y=e_j$ (i.e. $x=Q e_j$ , the $j$ -th eigenvector): the sum equals $\lambda_j\le0$ ⇒ not PD.

$\blacksquare$ Same argument with $\ge$ gives the PSD ⟺ $\lambda_i\ge0$ result.

Figure — Positive definite and semidefinite matrices

Formula The practical tests for symmetric

$A$

Property	Test
PD	all $\lambda_i>0$ • all leading principal minors $>0$ (Sylvester) • $A=R^\top R$ with $R$ full column rank • Cholesky exists
PSD	all $\lambda_i\ge0$ • all principal minors $\ge0$ • $A=B^\top B$ for some $B$

Worked examples

Common mistakes (steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine a skateboard bowl. Drop a marble anywhere: if the ground curves up in every direction, the marble always rolls back to the bottom — that's a positive definite bowl. If part of the bowl is a flat gutter, the marble can sit still along that gutter (not roll down but not fall either) — that's semidefinite. If it's a mountain-pass saddle, it rolls down one way and up the other — that's indefinite. The " $x^\top A x$ " number is just the height of the ground when you walk in direction $x$ ; positive definite means that height is always positive except right at the center.

Recall flashcards

What defines a positive definite symmetric matrix?

x^\top A x>0

for all

x\neq0

; equivalently all eigenvalues

>0

PD vs PSD difference in one word?

Strict (

>0

, no zero eigenvalues) vs allows-flat (

\ge0

, zero eigenvalues permitted).

Why must we assume

A

symmetric before testing definiteness?

Only the symmetric part affects

x^\top Ax

, since the antisymmetric part contributes zero.

Sylvester's criterion for PD?

All leading principal minors are positive.

Why does

A=B^\top B

guarantee PSD?

x^\top B^\top B x=\|Bx\|^2\ge0

always.

When is a Hessian being PD useful?

At a critical point it certifies a strict local minimum.

Is a covariance matrix always PD?

No — always PSD; PD only if data isn't confined to a lower-dim subspace.

Counterexample: positive entries but not PD?

\begin{bmatrix}1&2\\2&1\end{bmatrix}

, eigenvalues

3,-1

(indefinite).

Does

\det A>0

imply PD?

No;

-I

has

\det=1>0

but is negative definite.

Connections

Eigenvalues and Eigenvectors — the definitive test lives here.
Spectral Theorem — supplies the orthonormal diagonalization used in the derivation.
Cholesky Decomposition — exists iff PD; the fast solver.
Covariance Matrix — canonical PSD object in statistics.
Kernels and Mercer's Theorem — valid kernels ⟺ PSD Gram matrices.
Hessian and Convexity — PD Hessian ⇒ strictly convex ⇒ unique minimum.
Quadratic Forms — $x^\top A x$ as a scalar function of direction.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, ek symmetric matrix $A$ ko samajhne ka asaan tareeka hai uska "bowl shape". Har direction $x$ ke liye ek number nikalta hai $x^\top A x$ — ye us direction mein ground ki height jaisa hai. Agar ye number har non-zero direction mein positive hai, to matrix positive definite hai — matlab ek perfect bowl jahan marble kahin se bhi choro to neeche center pe hi aayega. Agar kuch directions mein number zero ho sakta hai (flat gutter), tab wo positive semidefinite hai. Aur agar kabhi positive kabhi negative, to wo saddle yaani indefinite.

Test kaise karein? Sabse pakka tareeka: eigenvalues nikalo. Saare positive ⇒ PD, saare non-negative ⇒ PSD, mixed ⇒ indefinite. Chhote matrices ke liye Sylvester shortcut hai: saare leading principal minors positive ⇒ PD. Ek badi galti se bachna — entries ka positive hona kaafi nahi hai, jaise $\begin{bmatrix}1&2\\2&1\end{bmatrix}$ ke entries positive hain par eigenvalue $-1$ aata hai, to wo indefinite hai.

Ye cheez ML mein har jagah chhupi hai. Covariance matrix hamesha PSD hoti hai kyunki variance negative nahi ho sakta — aur wo $X^\top X$ form mein hoti hai jo automatically $\|Xv\|^2\ge0$ deta hai. Kernels (SVM, Gaussian process) valid tabhi hote hain jab unki Gram matrix PSD ho. Aur optimization mein, agar Hessian kisi point pe PD hai, to wahan strict minimum hai — gradient descent aaraam se converge karega. Isliye ye ek chhota concept poore loss landscape aur statistics ko chalata hai.

Test yourself — Linear Algebra Essentials

Connections