Positive definite matrices

A square matrix \(\boldsymbol A \in \mathbb R^n\) is called

• positive definite if \(\boldsymbol x^\mathsf{T}\boldsymbol{Ax} > 0\) for all \(\boldsymbol x \in \mathbb R^n\), \(\boldsymbol x \ne \boldsymbol 0\);

• positive semidefinite if \(\boldsymbol x^\mathsf{T}\boldsymbol{Ax} \geqslant 0\) for all \(\boldsymbol x \in \mathbb R^n\);

• negative definite if \(\boldsymbol x^\mathsf{T}\boldsymbol{Ax} < 0\) for all \(\boldsymbol x \in \mathbb R^n\), \(\boldsymbol x \ne \boldsymbol 0\);

• negative semidefinite if \(\boldsymbol x^\mathsf{T}\boldsymbol{Ax} \leqslant 0\) for all \(\boldsymbol x \in \mathbb R^n\).

For example, matrix \(\boldsymbol A = \begin{pmatrix} 1 & 0 \\ -1 & 2 \end{pmatrix}\) is positive definite since for any nonzero vector \(\begin{pmatrix} x \\ y \end{pmatrix}\) we have

\[\begin{split} (x \; y) \begin{pmatrix} 1 & 0 \\ -1 & 2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = x^2 - xy + 2y^2 = \Big(x - \frac y2\Big)^2 + \frac 74 y^2 > 0. \end{split}\]

Symmetric matrices

The positive definiteness of a symmetric matrix \(\boldsymbol A = \boldsymbol A^\mathsf{T}\) of shape \(n\times n\) is equivalent to any of the following statements:

1. all \(n\) eigenvalues of \(\boldsymbol A\) are positive

2. all \(n\) pivots of \(\boldsymbol A\) are positive

3. all \(n\) upper left determinants are positive

4. \(\boldsymbol A = \boldsymbol B^\mathsf{T} \boldsymbol B\) for some full column rank matrix \(\boldsymbol B\)

Proof of statement 1

According to spectral theorem

\[ \boldsymbol A = \boldsymbol Q^\mathsf{T} \boldsymbol \Lambda \boldsymbol Q, \]

where \(\boldsymbol Q\) is orthogonal, and diagonal matrix \(\boldsymbol \Lambda\) consists of eigenvalues of \(\boldsymbol A\). Hence,

\[ \boldsymbol x^\mathsf{T}\boldsymbol{Ax} = \boldsymbol x^\mathsf{T}\boldsymbol Q^\mathsf{T} \boldsymbol {\Lambda Q x} = (\boldsymbol{Qx})^\mathsf{T}\boldsymbol {\Lambda Q x} = \boldsymbol{y}^\mathsf{T}\boldsymbol {\Lambda y}, \quad \boldsymbol y = \boldsymbol{Qx}. \]

Note that \(\boldsymbol x \ne \boldsymbol 0\) iff \(\boldsymbol y \ne \boldsymbol 0\) (why?). Finally observe that expression

\[ \boldsymbol{y}^\mathsf{T}\boldsymbol {\Lambda y} = \sum \limits_{i=1}^n \lambda_i y_i^2 \]

is positive for any \(\boldsymbol y \ne \boldsymbol 0\) iff \(\lambda_i>0\) for all \(i\).

Numeric example

Create some random positive definite matrix using statement 4, and check theat all other statements are fulfilled:

import numpy as np

A = np.random.normal(size=(5, 4))
B = A.T @ A
eigvals, _ = np.linalg.eig(B)
print("eigenvalues:", eigvals)
print("left upper determinants:", [float(np.linalg.det(B[:i, :i])) for i in range(4)])

eigenvalues: [8.3450636  2.98702351 0.76122108 0.48962739]
left upper determinants: [1.0, 2.195774261287806, 13.876758598100098, 8.106837599831954]

To find pivots use LU-decomposition from scipy:

from scipy.linalg import lu
_, _, U = lu(B)
print("Echelon form:")
print(U)

Echelon form:
[[ 2.19577426 -0.30395801  0.36388171  1.38597395]
 [ 0.          6.31975647  0.6802934  -2.76674215]
 [ 0.          0.          0.58420254  0.20999453]
 [ 0.          0.          0.          1.14602299]]

Ellipses and ellipsoids

The canonical ellipse equation is

\[\begin{split} \frac{x^2}{a^2} + \frac{y^2}{b^2} = 1 \iff (x \; y) \begin{pmatrix} a^{-2} & 0 \\ 0 & b^{-2} \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = 1. \end{split}\]

It is specified by a diagonal matrix \(\mathrm{diag}\{\frac 1{a^2}, \frac 1{b^2}\}\) with positive diagonal elements. \(a\) and \(b\) are the axis lengths of the ellipse.

A tilted ellipse is defined by equations

\[ a x^2 + 2bxy + cy^2 = 1 \iff \boldsymbol x^{\mathsf T}\boldsymbol{Ax} = 1 \]

where \(\boldsymbol x = (x, y)^\mathsf T\), and matrix

\[\begin{split} \boldsymbol A = \begin{pmatrix} a & b \\ b & c \end{pmatrix} \end{split}\]

is positive definite. The axis of such ellipse come from the spectral theorem:

\[ \boldsymbol x^{\mathsf T} \boldsymbol Q \boldsymbol{\Lambda} \boldsymbol Q^{\mathsf T} \boldsymbol x = 1 \iff \boldsymbol y^{\mathsf T}\boldsymbol{\Lambda}\boldsymbol y = 1, \quad \boldsymbol y = \boldsymbol Q^{\mathsf T} \boldsymbol x. \]

The lined-up ellipse \(\boldsymbol y^{\mathsf T}\boldsymbol{\Lambda}\boldsymbol y = 1\) has axes of \(\frac 1{\sqrt \lambda_i}\), and then it is rotated by (orthogonal) rotation matrix \(\boldsymbol Q\). This also works for \(n\)-dimensional ellipsoids.

Exercises

1. Show that diagonal matrix \(\mathrm{diag}\{\lambda_1, \ldots, \lambda_n\}\) is positive definite iff all \(\lambda_i >0\).

2. Prove that matrix \(\boldsymbol A^\mathsf{T} \boldsymbol A\) is always semipositive definite, and it is positive definit iff \(\boldsymbol A\) has full column rank.

3. Prove that matrix \(\boldsymbol A\) is positive definite if

\[\begin{split} \boldsymbol A = \begin{pmatrix} 2 & -1 & 0 & 0 & \dots & 0 & 0 \\ -1 & 2 & -1 & 0 & \dots & 0 & 0 \\ 0 & -1 & 2 & -1 &\dots & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & -1 & 2 & -1 & 0 \\ 0 & 0 & \dots & 0 & -1 & 2 & -1 \\ 0 & 0 & \dots & 0 & 0 & -1 & 2 \\ \end{pmatrix} \end{split}\]

4. Prove that inverse to a positive definite symmetric matrix is also symmetric and positive definite.

5. Find the axes of this tilted ellipse \(5x^2 + 8xy + 5y^2 = 1\).

6. Show that \(\boldsymbol A^\mathsf{T} \boldsymbol A\) and \(\boldsymbol{AA}^\mathsf{T}\) have same positive eigenvalues \(\sigma_1, \ldots, \sigma_r\) for any \(\boldsymbol A \in \mathbb R^{m\times n}\) of rank \(r\).