Positive definite matrices

A symmetric matrix draws a surface over the plane. Watch it change from a round bowl to a valley, then to a saddle.

Energy

A symmetric matrix $\mathbf{A}$ turns every point $\mathbf{x}$ into one number:

For $\mathbf{A}(s)$ in the picture, $q(x,y)=2x^2+2sxy+2y^2$. Draw that number as a height above each point, and you get the surface. In mechanics and circuits $q$ is often an energy, which is why it matters whether it can go negative.

The matrix is positive definite when the surface is a bowl that touches zero only at the origin:

When $q$ is never negative but can be 0 away from the origin, the matrix is positive semi-definite: a valley.

Which is it? Turn to the matrix’s axes. By Symmetric matrices, $\mathbf{A}=\mathbf{Q}\boldsymbol{\Lambda}\mathbf{Q}^\top$. Write $(u,w)=\mathbf{Q}^\top\mathbf{x}$ for the coordinates of $\mathbf{x}$ along the two eigenvectors. Then

For $\mathbf{A}(s)$ the eigenvectors are $(1,1)/\sqrt2$ and $(1,-1)/\sqrt2$, with eigenvalues $2+s$ and $2-s$. So $q=(2+s)\,u^2+(2-s)\,w^2$. Both eigenvalues positive: a bowl. One of them 0: a valley along that eigenvector. One negative: a saddle. Drag $s$ past 2 and watch the surface bend down exactly when $2-s$ goes below zero.

Four tests, one question

For a symmetric matrix, these four tests always agree. Each is a different way to ask “is the surface a bowl?”

1. Eigenvalues. Every eigenvalue is positive. That is the formula $\lambda_1u^2+\lambda_2w^2$ above.
2. Pivots. Every pivot of elimination, from Elimination, is positive. Elimination writes $q$ as a sum of squares with the pivots as weights: $2x^2+2xy+2y^2=2\big(x+\tfrac12y\big)^2+1.5\,y^2$, with pivots 2 and 1.5.
3. Leading determinants. The determinants of the top-left $1\times1$, $2\times2$, … corners are all positive. Each one is a product of pivots: 2, then $2\cdot1.5=3$.
4. A product. $\mathbf{A}=\mathbf{B}^\top\mathbf{B}$ for some matrix $\mathbf{B}$ with independent columns. Then $\mathbf{x}^\top\mathbf{A}\mathbf{x}=(\mathbf{B}\mathbf{x})^\top(\mathbf{B}\mathbf{x})=\lVert\mathbf{B}\mathbf{x}\rVert^2$, a length squared, and it is 0 only when $\mathbf{B}\mathbf{x}=\mathbf{0}$, which independence allows only for $\mathbf{x}=\mathbf{0}$.

Cholesky: the square root of a bowl

Test 4 has a standard choice of $\mathbf{B}$. Every positive definite matrix factors as

with $\mathbf{L}$ lower triangular and a positive diagonal. This is the Cholesky factorisation, and $\mathbf{B}=\mathbf{L}^\top$. It is the $\mathbf{L}\mathbf{U}$ factorisation of LU factorisation with the pivots shared out evenly between the two factors. For $\begin{bmatrix}2&1\\1&2\end{bmatrix}$:

Check: the top-left entry of $\mathbf{L}\mathbf{L}^\top$ is $\sqrt2^{\,2}=2$, the off-diagonal one $\sqrt2\cdot(1/\sqrt2)=1$, and the bottom-right $0.5+1.5=2$. The diagonal of $\mathbf{L}$ holds the square roots of the pivots.

To solve $\mathbf{A}\mathbf{x}=\mathbf{b}$, solve two triangular systems: first $\mathbf{L}\mathbf{c}=\mathbf{b}$ from the top down, then $\mathbf{L}^\top\mathbf{x}=\mathbf{c}$ from the bottom up. With $\mathbf{b}=(3,3)$, the first gives $\mathbf{c}=(2.121,\;1.225)$ and the second $\mathbf{x}=(1,1)$. Check: $\mathbf{A}(1,1)=(3,3)$.

Bowls, valleys and saddles in calculus

Near a point where a smooth function of two variables is flat, it looks like a surface $\tfrac12\,\mathbf{x}^\top\mathbf{H}\mathbf{x}$, where $\mathbf{H}$ is the symmetric matrix of its second derivatives, the Hessian. So the four tests decide what kind of point it is: positive definite means a minimum, and a negative eigenvalue means a saddle.

• $f=x^2+xy+y^2$ has Hessian $\begin{bmatrix}2&1\\1&2\end{bmatrix}$, positive definite: the origin is a minimum.
• $f=x^2+4xy+y^2$ has $f(1,-1)=1-4+1=-2$: the origin is a saddle.
• $\begin{bmatrix}4&2\\2&1\end{bmatrix}$ has determinant 0: it is only semi-definite, a valley.

Here $\mathbf{H}$ is the Hessian, not the system matrix of signal processing.

Worked example

1. Four tests on one matrix. $\begin{bmatrix}2&1\\1&2\end{bmatrix}$: eigenvalues 3 and 1; pivots 2 and 1.5; leading determinants 2 and 3; Cholesky factor as above. At $\mathbf{x}=(1,-1)$: $q=2-2+2=2>0$.

2. A saddle. $\begin{bmatrix}1&2\\2&1\end{bmatrix}$: pivots 1 and $-3$, eigenvalues 3 and $-1$, $q(1,-1)=-2$.

3. A $3\times3$ product. Take $\mathbf{B}=\begin{bmatrix}1&1&0\\1&0&1\\0&1&1\end{bmatrix}$, whose columns are independent. Then

must be positive definite, and every test agrees: pivots 2, 1.5 and $4/3$; leading determinants 2, 3 and 4; eigenvalues 4, 1 and 1. Its Cholesky factor is

and the last row checks as $0.5+0.1667+1.3333=2$. At $\mathbf{x}=(1,-1,0)$, $\mathbf{B}\mathbf{x}=(0,1,-1)$, so $q=\lVert\mathbf{B}\mathbf{x}\rVert^2=2$.

4. Correlated noise. The covariance matrix $\begin{bmatrix}1&\rho\\\rho&1\end{bmatrix}$ has leading determinants 1 and $1-\rho^2$, so it is positive definite exactly when $\lvert\rho\rvert<1$. For $\rho=0.8$, $\mathbf{L}=\begin{bmatrix}1&0\\0.8&0.6\end{bmatrix}$.

Try these before you read the answers.

• Is $\begin{bmatrix}2&0\\0&-1\end{bmatrix}$ positive definite? No: one eigenvalue is $-1$.
• Is $\begin{bmatrix}4&2\\2&1\end{bmatrix}$? No, only semi-definite: its determinant is 0, a valley.
• Can $\mathbf{x}^\top\mathbf{B}^\top\mathbf{B}\mathbf{x}$ be negative? No: it is $\lVert\mathbf{B}\mathbf{x}\rVert^2$.
• At which $s$ does $\mathbf{A}(s)$ stop being a bowl? At $s=2$, where $2-s$ reaches 0.

Where you’ll meet this

Optimisation. A minimum of a smooth function has a positive definite Hessian. Newton’s method, the fast way to find a minimum, solves a linear system with that Hessian at each step, usually by Cholesky.

Covariance. A covariance matrix is $\mathbf{B}^\top\mathbf{B}$ for the centred data, divided by a count, so it is positive semi-definite, and positive definite unless one measurement is a fixed mix of the others.

Making correlated noise. To draw two Gaussian values with correlation 0.8, draw two independent ones $\mathbf{z}$ and form $\mathbf{x}=\mathbf{L}\mathbf{z}$ with the $\mathbf{L}$ of example 4: $x_2=0.8\,z_1+0.6\,z_2$. The covariance of $\mathbf{x}$ is $\mathbf{L}\mathbf{L}^\top$.

Reference card