Positive Definite Matrices and Cholesky Factorization

Definition Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$. A matrix $A \in \mathbb{F}^{n \times n}$ is positive definite if it is Hermitian (real symmetric when $\mathbb{F} = \mathbb{R}$) and

For a Hermitian $A$ the following are equivalent. The matrix is positive definite. Every eigenvalue of $A$ is positive. The inertia of $A$ is $(n, 0, 0)$. The matrix equals $B^{*}B$ for some invertible $B \in \mathbb{F}^{n \times n}$. A positive definite matrix is invertible, its diagonal entries $a_{ii} = e_i^{*}Ae_i$ are positive, and each leading block, formed by the first $k$ rows and the first $k$ columns, is again positive definite, as one sees by testing $A$ on vectors whose last $n - k$ coordinates are $0$. Over $\mathbb{R}$ the symmetry is part of the definition, because $x^{\mathsf{T}}Ax$ only detects the symmetric part of $A$.

Definition A matrix $A \in \mathbb{F}^{n \times n}$ is positive semidefinite if it is Hermitian and $x^{*}Ax \ge 0$ for every $x \in \mathbb{F}^n$. For a Hermitian $A$ this holds exactly when every eigenvalue is nonnegative, exactly when the inertia is $(r, 0, n - r)$ with $r = \operatorname{rank} A$, and exactly when $A = B^{*}B$ for some matrix $B$ with $n$ columns. The eigenvalue test needs the Hermitian hypothesis, since the real matrix with rows $(1, 4)$ and $(0, 1)$ has both eigenvalues equal to $1$, but its form takes the value $-2$ at $(1, -1)$. For a positive semidefinite matrix the form vanishes exactly on the kernel, since $0 = x^{*}B^{*}Bx = \lVert Bx \rVert^2$ forces $Bx = 0$ and hence $Ax = 0$. A positive semidefinite matrix is positive definite exactly when it is invertible. A singular one has no factorization $A = R^{*}R$ with $R$ triangular and every diagonal entry positive, because such a factor would give $\det A = \lvert \det R \rvert^2 > 0$. An indefinite Hermitian matrix has no factorization $A = B^{*}B$ at all, since $x^{*}B^{*}Bx = \lVert Bx \rVert^2$ is never negative.

Definition Let $A \in \mathbb{F}^{n \times n}$ be Hermitian with first diagonal entry $a \ne 0$, which is real because $A$ is Hermitian, and write

with $b \in \mathbb{F}^{n-1}$ and $C \in \mathbb{F}^{(n-1) \times (n-1)}$ Hermitian. Split an input as $x = (x_1, y)$ with $x_1 \in \mathbb{F}$ and $y \in \mathbb{F}^{n-1}$. Then

where $S = C - bb^{*}/a$. To check the last line, expand the square and use that the conjugate of the scalar $b^{*}y$ is $y^{*}b$. Every appearance of $x_1$ is now inside one square, and the rest is a form in $y$ alone. Repeating the step on $S$, as long as the pivots are nonzero, writes $x^{*}Ax$ as a sum of real multiples of squared absolute values of triangular combinations of the coordinates.

Definition For a Hermitian $A$ partitioned as in the previous card, with first diagonal entry $a \ne 0$, the Schur complement of the entry $a$ is the $(n-1) \times (n-1)$ Hermitian matrix

It is exactly what Gaussian elimination leaves in the lower right block after the first column is cleared below the pivot, by subtracting $b_i/a$ times the first row from row $i + 1$. That elimination does not change determinants and produces a block triangular matrix with diagonal blocks $a$ and $S$, so $\det A = a \det S$. The same step inside the leading block of size $k + 1$ shows that its determinant is $a$ times the determinant of the leading $k \times k$ block of $S$. If $A$ is positive definite, then $a = e_1^{*}Ae_1 > 0$ and $S$ is positive definite. Indeed, for $y \ne 0$ choose $x_1 = -b^{*}y/a$. The square then vanishes, the input $x = (x_1, y)$ is nonzero, and the identity from completing the square gives $y^{*}Sy = x^{*}Ax > 0$.

Definition Let $\mathbb{F}$ be $\mathbb{R}$ or $\mathbb{C}$, and let $A \in \mathbb{F}^{n \times n}$ be positive definite. Then there is exactly one upper triangular $R \in \mathbb{F}^{n \times n}$ with real positive diagonal entries such that

When $\mathbb{F} = \mathbb{R}$ the factor is real and $A = R^{\mathsf{T}}R$. Many books write the same factorization as $A = LL^{*}$ with $L = R^{*}$ lower triangular. Existence follows by induction on $n$. For $n = 1$ take $R = \sqrt{a}$. For $n > 1$ the Schur complement $S$ is positive definite of size $n - 1$, so $S = \tilde{R}^{*}\tilde{R}$ with $\tilde{R}$ upper triangular with positive diagonal, and

satisfies $R^{*}R = A$, since its lower right block is $bb^{*}/a + \tilde{R}^{*}\tilde{R} = C$. For uniqueness, any such factor has $r_{11}^2 = a$ with $r_{11} > 0$, so $r_{11} = \sqrt{a}$. The first row equations $r_{11}r_{1j} = a_{1j}$ then force the rest of the first row to be $b^{*}/\sqrt{a}$, and the remaining block must factor the same $S$, which by induction has only one such factor. The positive diagonal is what pins the factor down. Multiplying the rows of $R$ by signs, or over $\mathbb{C}$ by complex numbers of modulus $1$, gives other triangular factors. Conversely, every $A = R^{*}R$ with $R$ invertible is positive definite, because $x^{*}Ax = \lVert Rx \rVert^2$.

Definition For $A \in \mathbb{F}^{n \times n}$ and $1 \le k \le n$, the leading principal submatrix $A_k$ is the $k \times k$ block in the first $k$ rows and the same first $k$ columns, and the leading principal minor is $\Delta_k = \det A_k$, with $\Delta_0 = 1$. Sylvester’s criterion says that a Hermitian matrix $A$ is positive definite if and only if

If $A$ is positive definite, each $A_k$ is positive definite, so $A_k = R_k^{*}R_k$ and $\Delta_k = \lvert \det R_k \rvert^2 > 0$. Conversely, $\Delta_1 = a > 0$, and the Schur complement step gives $\Delta_{k+1} = a \det S_k$, where $S_k$ is the leading $k \times k$ block of $S$. So every leading principal minor of $S$ is positive, $S$ is positive definite by induction, and the identity from completing the square gives $x^{*}Ax > 0$ for every $x \ne 0$. Because $A_k = R_k^{*}R_k$ with $R_k$ the leading block of the Cholesky factor, the pivots satisfy

The hypotheses matter. The real matrix with rows $(1, -3)$ and $(0, 1)$ has $\Delta_1 = \Delta_2 = 1$, but it is not symmetric and its form $x_1^2 - 3x_1x_2 + x_2^2$ equals $-1$ at $(1, 1)$. The criterion also has no semidefinite version with leading minors alone. The matrix $\operatorname{diag}(0, -1)$ has $\Delta_1 = \Delta_2 = 0$, yet its form is $-1$ at $e_2$. A Hermitian matrix is positive semidefinite exactly when all of its principal minors, taken from any set of rows and the same set of columns, are nonnegative.