Positive Definite Matrices

All the eigenvalues of any symmetric matrix are real (proved later in cor:ews_symmetric_real); this section is about the case in which those eigenvalues are positive. These matrices, which arise whenever optimization (maximum and minimum) problems are encountered, have countless applications throughout science and engineering. They also arise in statistics (for example, in factor analysis used in the social sciences) and in geometry (quadratic forms, for instance). We will encounter them again in Inner Product Spaces when describing all inner products in \(\RR ^n\).

Because these matrices are symmetric, the Real Spectral Theorem (th:PrinAxes) plays a central role in the theory.

If \(A\) is \(n \times n\) and the eigenvalues are \(\lambda _{1}, \lambda _{2}, \dots , \lambda _{n}\), then \(\det A = \lambda _{1}\lambda _{2} \cdots \lambda _{n} > 0\) by the Real Spectral Theorem (or, more specifically, cor:det_and_tr).

If \(\vec {x}\) is a column in \(\RR ^n\) and \(A\) is any real \(n \times n\) matrix, we view the \(1 \times 1\) matrix \(\vec {x}^{T}A\vec {x}\) as a real number. With this convention, we have the following characterization of positive definite matrices.

\(A\) is symmetric. Using the Real Spectral Theorem, let \(Q^{T}AQ = D = \mbox {diag}(\lambda _{1}, \lambda _{2}, \dots , \lambda _{n})\) where \(Q^{-1} = Q^{T}\) and the \(\lambda _{i}\) are the eigenvalues of \(A\). Given a column \(\vec {x}\) in \(\RR ^n\), write \(\vec {y} = Q^{T}\vec {x} = \left [ \begin{array}{cccc} y_{1} & y_{2} & \dots & y_{n} \end{array}\right ]^T\). Then

\begin{equation} \label {symmetricEq} \vec {x}^TA\vec {x} = \vec {x}^T(QDQ^T)\vec {x} = \vec {y}^TD\vec {y} = \lambda _{1}y_{1}^2 + \lambda _{2}y_{2}^2 + \dots + \lambda _{n}y_{n}^2 \end{equation}
If \(A\) is positive definite and \(\vec {x} \neq \vec {0}\), then \(\vec {x}^{T}A\vec {x} > 0\) by (symmetricEq) because some \(y_{j} \neq 0\) and every \(\lambda _{i} > 0\). Conversely, if \(\vec {x}^{T}A\vec {x} > 0\) whenever \(\vec {x} \neq \vec {0}\), let \(\vec {x} = Q\vec {e}_{j} \neq \vec {0}\) where \(\vec {e}_{j}\) is column \(j\) of \(I_{n}\). Then \(\vec {y} = \vec {e}_{j}\), so (symmetricEq) reads \(\lambda _{j} = \vec {x}^{T}A\vec {x} > 0\).

Note that Theorem thm:024830 shows that the positive definite matrices are exactly the symmetric matrices \(A\) for which the quadratic form \(q = \vec {x}^{T}A\vec {x}\) takes only positive values.

The next example of a positive definite matrix is one we will see again in SVD Decomposition

It is remarkable that the converse to Example exa:024865 is also true. In fact every positive definite matrix \(A\) can be factored as \(A = U^{T}U\) where \(U\) is an upper triangular matrix with positive elements on the main diagonal. However, before verifying this, we introduce another concept that is central to any discussion of positive definite matrices.

If \(A\) is any \(n \times n\) matrix, let \(^{(r)}A\) denote the \(r \times r\) submatrix in the upper left corner of \(A\); that is, \(^{(r)}A\) is the matrix obtained from \(A\) by deleting the last \(n - r\) rows and columns. The matrices \(^{(1)}A, ^{(2)}A, ^{(3)}A, \dots \), \(^{(n)}A = A\) are called the principal submatrices of \(A\).

Write \(A = \left [ \begin{array}{rr} ^{(r)}A & P \\ Q & R \end{array}\right ]\) in block form. If \(\vec {y} \neq \vec {0}\) in \(\RR ^r\), write \(\vec {x} = \left [ \begin{array}{r} \vec {y} \\ \vec {0} \end{array}\right ]\) in \(\RR ^n\).

Then \(\vec {x} \neq \vec {0}\), so the fact that \(A\) is positive definite gives

\begin{equation*} 0 < \vec {x}^TA\vec {x} = \left [ \begin{array}{rr} \vec {y}^T & \vec {0} \end{array}\right ] \left [ \begin{array}{rr} ^{(r)}A & P \\ Q & R \end{array}\right ] \left [ \begin{array}{r} \vec {y} \\ \vec {0} \end{array}\right ] = \vec {y}^T(^{(r)}A)\vec {y} \end{equation*}
This shows that \(^{(r)}A\) is positive definite by Theorem thm:024830. (A similar argument shows that, if \(B\) is any matrix obtained from a positive definite matrix \(A\) by deleting certain rows and deleting the same columns, then \(B\) is also positive definite.)

If \(A\) is positive definite, Lemma lem:024890 and Theorem thm:024815 show that \(\mbox {det}(^{(r)}A) > 0\) for every \(r\). This proves part of the following theorem which contains the converse to Example exa:024865, and characterizes the positive definite matrices among the symmetric ones.

First, thm:024907c \(\Rightarrow \) thm:024907a by Example exa:024865, and thm:024907a \(\Rightarrow \) thm:024907b by Lemma lem:024890 and Theorem thm:024815.

thm:024907b \(\Rightarrow \) thm:024907c. Assume thm:024907b and proceed by induction on \(n\). If \(n = 1\), then \(A = \left [ a \right ]\) where \(a > 0\) by thm:024907b, so take \(U = \left [ \sqrt {a} \right ]\). If \(n > 1\), write \(B =^{(n-1)}A\). Then \(B\) is symmetric and satisfies thm:024907b so, by induction, we have \(B = U^{T}U\) as in thm:024907c where \(U\) is of size \((n - 1) \times (n - 1)\). Then, as \(A\) is symmetric, it has block form \(A = \left [ \begin{array}{cc} B & \vec {p} \\ \vec {p}^T & b \end{array}\right ]\) where \(\vec {p}\) is a column in \(\RR ^{n-1}\) and \(b\) is in \(\RR \). If we write \(\vec {x} = (U^{T})^{-1}\vec {p}\) and \(c = b - \vec {x}^{T}\vec {x}\), block multiplication gives

\begin{equation*} A = \left [ \begin{array}{cc} U^TU & \vec {p} \\ \vec {p}^T & b \end{array}\right ] = \left [ \begin{array}{cc} U^T & 0 \\ \vec {x}^T & 1 \end{array}\right ] \left [ \begin{array}{cc} U & \vec {x} \\ 0 & c \end{array}\right ]. \end{equation*}
Taking determinants gives \(\det A = \mbox {det}(U^{T}) \mbox {det} U \cdot c = c(\mbox {det}U)^{2}\). Hence \(c > 0\) because \(\det A > 0\) by thm:024907b, so the above factorization can be written
\begin{equation*} A = \left [ \begin{array}{cc} U^T & 0 \\ \vec {x}^T & \sqrt {c} \end{array}\right ] \left [ \begin{array}{cc} U & \vec {x} \\ 0 & \sqrt {c} \end{array}\right ] \end{equation*}
Since \(U\) has positive diagonal entries, this proves thm:024907c.

To prove uniqueness, suppose that \(A = U^TU = U_{1}^TU_{1}\) are two Cholesky factorizations. Now write \(D = UU_{1}^{-1} = (U^T)^{-1}U_{1}^T\). Then \(D\) is upper triangular, because \(D = UU_{1}^{-1}\), and lower triangular, because \(D = (U^T)^{-1}U_{1}^T\), and so it is a diagonal matrix. Thus \(U = DU_{1}\) and \(U_{1} = DU\), so it suffices to show that \(D = I\). But eliminating \(U_{1}\) gives \(U = D^{2}U\), so \(D^{2} = I\) because \(U\) is invertible. Since the diagonal entries of \(D\) are positive (this is true of \(U\) and \(U_{1}\)), it follows that \(D = I\).

The remarkable thing is that the matrix \(U\) in the Cholesky factorization is easy to obtain from \(A\) using row operations. The key is that Step 1 of the following algorithm is possible for any positive definite matrix \(A\). A proof of the algorithm is given following Example exa:024959.

If \(A\) is positive definite, let \(A = U^{T}U\) be the Cholesky factorization, and let \(D = \mbox {diag}(d_{1}, \dots , d_{n})\) be the common diagonal of \(U\) and \(U^{T}\). Then \(U^{T}D^{-1}\) is lower triangular with ones on the diagonal (call such matrices LT-1). Hence \(L = (U^{T}D^{-1})^{-1}\) is also LT-1, and so \(I_{n} \to L\) by a sequence of row operations each of which adds a multiple of a row to a lower row (modify columns right to left). But then \(A \to LA\) by the same sequence of row operations. Since \(LA = [D(U^{T})^{-1}][U^{T}U] = DU\) is upper triangular with positive entries on the diagonal, this shows that Step 1 of the algorithm is possible.

Turning to Step 2, let \(A \to U_{1}\) as in Step 1 so that \(U_{1} = L_{1}A\) where \(L_{1}\) is LT-1. Since A is symmetric, we get

\begin{equation} \label {symmetricEq2} L_{1}U_{1}^T = L_{1}(L_{1}A)^T = L_{1}A^TL_{1}^T = L_{1}AL_{1}^T = U_{1}L_{1}^T \end{equation}
Let \(D_{1} = \mbox {diag}(e_{1}, \dots , e_{n})\) denote the diagonal of \(U_{1}\). Then (symmetricEq2) gives \(L_{1}(U_{1}^TD_{1}^{-1}) = U_{1}L_{1}^TD_{1}^{-1}\). This is both upper triangular (right side) and LT-1 (left side), and so must equal \(I_{n}\). In particular, \(U_{1}^TD_{1}^{-1} = L_{1}^{-1}\). Now let \(D_{2} = \mbox {diag}(\sqrt {e_{1}}, \dots , \sqrt {e_{n}})\), so that \(D_{2}^2 = D_{1}\). If we write \(U = D_{2}^{-1}U_{1}\) we have
\begin{equation*} U^TU = (U_{1}^TD_{2}^{-1})(D_{2}^{-1}U_{1}) = U_{1}^T(D_{2}^2)^{-1}U_{1} = (U_{1}^TD_{1}^{-1})U_{1} = (L_{1}^{-1})U_{1} = A \end{equation*}
This proves Step 2 because \(U = D_{2}^{-1}U_{1}\) is formed by dividing each row of \(U_{1}\) by the square root of its diagonal entry (verify).

Practice Problems

Find the Cholesky decomposition of each of the following matrices.
1.
\(\left [ \begin{array}{rr} 4 & 3 \\ 3 & 5 \end{array}\right ]\)
2.
\(\left [ \begin{array}{rr} 2 & -1 \\ -1 & 1 \end{array}\right ]\)

Click the arrow to see the answer.

\(U = \frac {\sqrt {2}}{2} \left [ \begin{array}{rr} 2 & -1 \\ 0 & 1 \end{array}\right ]\)
3.
\(\left [ \begin{array}{rrr} 12 & 4 & 3 \\ 4 & 2 & -1 \\ 3 & -1 & 7 \end{array}\right ]\)
4.
\(\left [ \begin{array}{rrr} 20 & 4 & 5 \\ 4 & 2 & 3 \\ 5 & 3 & 5 \end{array}\right ]\)

Click the arrow to see the answer.

\(U = \frac {1}{30} \left [ \begin{array}{ccc} 60\sqrt {5} & 12\sqrt {5} & 15\sqrt {5} \\ 0 & 6\sqrt {30} & 10\sqrt {30} \\ 0 & 0 & 5\sqrt {15} \end{array}\right ]\)
a.
If \(A\) is positive definite, show that \(A^{k}\) is positive definite for all \(k \geq 1\).
b.
Prove the converse to (a) when \(k\) is odd.
If \(\lambda ^{k} > 0\), \(k\) odd, then \(\lambda > 0\).
c.
Find a symmetric matrix \(A\) such that \(A^{2}\) is positive definite but \(A\) is not.
Let \(A = \left [ \begin{array}{rr} 1 & a \\ a & b \end{array}\right ]\). If \(a^{2} < b\), show that \(A\) is positive definite and find the Cholesky factorization.
If \(A\) and \(B\) are positive definite and \(r > 0\), show that \(A + B\) and \(rA\) are both positive definite.

Click the arrow to see the answer.

If \(\vec {x} \neq \vec {0}\), then \(\vec {x}^{T}A\vec {x} > 0\) and \(\vec {x}^{T}B\vec {x} > 0\). Hence \(\vec {x}^{T}(A + B)\vec {x} = \vec {x}^{T}A\vec {x} + \vec {x}^{T}B\vec {x} > 0\) and \(\vec {x}^{T}(rA)\vec {x} = r(\vec {x}^{T}A\vec {x}) > 0\), as \(r > 0\).
If \(A\) and \(B\) are positive definite, show that \(\left [ \begin{array}{rr} A & 0 \\ 0 & B \end{array}\right ]\) is positive definite.
If \(A\) is an \(n \times n\) positive definite matrix and \(U\) is an \(n \times m\) matrix of rank \(m\), show that \(U^{T}AU\) is positive definite.
Let \(\vec {x} \neq \vec {0}\) in \(\RR ^n\). Then \(\vec {x}^{T}(U^{T}AU)\vec {x} = (U\vec {x})^{T}A(U\vec {x}) > 0\) provided \(U\vec {x} \neq 0\). But if \(U = \left [ \begin{array}{cccc} \vec {c}_{1} & \vec {c}_{2} & \dots & \vec {c}_{n} \end{array}\right ]\) and \(\vec {x} = (x_{1}, x_{2}, \dots , x_{n})\), then \(U\vec {x} = x_{1}\vec {c}_{1} + x_{2}\vec {c}_{2} + \dots + x_{n}\vec {c}_{n} \neq \vec {0}\) because \(\vec {x} \neq \vec {0}\) and the \(\vec {c}_{i}\) are independent.
If \(A\) is positive definite, show that each diagonal entry is positive.
Let \(A_{0}\) be formed from \(A\) by deleting rows 2 and 4 and deleting columns 2 and 4. If \(A\) is positive definite, show that \(A_{0}\) is positive definite.
If \(A\) is positive definite, show that
\(A = CC^{T}\) where \(C\) has orthogonal columns.
If \(A\) is positive definite, show that \(A = C^{2}\) where \(C\) is positive definite.

Click the arrow for answer.

Let \(P^{T}AP = D = \mbox {diag}(\lambda _{1}, \dots , \lambda _{n})\) where \(P^{T} = P\). Since \(A\) is positive definite, each eigenvalue \(\lambda _{i} > 0\). If \(B = \mbox {diag}(\sqrt {\lambda _{1}}, \dots , \sqrt {\lambda _{n}})\) then \(B^{2} = D\), so \(A = PB^{2}P^{T} = (PBP^{T})^{2}\). Take \(C = PBP^{T}\). Since \(C\) has eigenvalues \(\sqrt {\lambda _{i}} > 0\), it is positive definite.
Let \(A\) be a positive definite matrix. If \(a\) is a real number, show that \(aA\) is positive definite if and only if \(a > 0\).
1.
Suppose an invertible matrix \(A\) can be factored in \(\mathbb {M}_{nn}\) as \(A = LDU\) where \(L\) is lower triangular with \(1\)s on the diagonal, \(U\) is upper triangular with \(1\)s on the diagonal, and \(D\) is diagonal with positive diagonal entries. Show that the factorization is unique: If \(A = L_{1}D_{1}U_{1}\) is another such factorization, show that \(L_{1} = L\), \(D_{1} = D\), and \(U_{1} = U\).
2.
Show that a matrix \(A\) is positive definite if and only if \(A\) is symmetric and admits a factorization \(A = LDU\) as in (a).

Click the arrow for answer.

If \(A\) is positive definite, use Theorem 2 to write \(A = U^{T}U\) where \(U\) is upper triangular with positive diagonal \(D\). Then \(A = (D^{-1}U)^{T}D^{2}(D^{-1}U)\) so \(A = L_{1}D_{1}U_{1}\) is such a factorization if \(U_{1} = D^{-1}U\), \(D_{1} = D^{2}\), and \(L_{1} = U^T_1\). Conversely, let \(A^{T} = A = LDU\) be such a factorization. Then \(U^{T}D^{T}L^{T} = A^{T} = A = LDU\), so \(L = U^{T}\) by (a). Hence \(A = LDL^{T} = V^{T}V\) where \(V = LD_{0}\) and \(D_{0}\) is diagonal with \(D^2_0 = D\) (the matrix \(D_{0}\) exists because \(D\) has positive diagonal entries). Hence \(A\) is symmetric, and it is positive definite by Example 6.
Let \(A\) be positive definite and write \(d_{r} = \det {\left (^{(r)}A\right )}\) for each \(r = 1, 2, \dots , n\). If \(U\) is the upper triangular matrix obtained in step 1 of the algorithm, show that the diagonal elements \(u_{11}, u_{22}, \dots , u_{nn}\) of \(U\) are given by \(u_{11} = d_{1}\), \(u_{jj} = d_{j} / d_{j-1}\) if \(j > 1\).
If \(LA = U\) where \(L\) is lower triangular with \(1\)s on the diagonal, use block multiplication to show that \(\det {\left (^{(r)}A\right )} = \det {\left (^{(r)}U\right )}\) for each \(r\).

Text Source

This section was adapted from Section 8.3 of Keith Nicholson’s Linear Algebra with Applications. (CC-BY-NC-SA)

W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p. 433-437.