search
Search
Map of Data Science
search toc
Thanks for the thanks!
close
account_circle
Profile
exit_to_app
Sign out
search
keyboard_voice
close
Searching Tips
Search for a recipe:
"Creating a table in MySQL"
Search for an API documentation: "@append"
Search for code: "!dataframe"
Apply a tag filter: "#python"
Useful Shortcuts
/ to open search panel
Esc to close search panel
to navigate between search results
d to clear all current filters
Enter to expand content preview
Doc Search
Code Search Beta
SORRY NOTHING FOUND!
mic
Start speaking...
Voice search is only supported in Safari and Chrome.
Shrink
Navigate to
near_me
Linear Algebra
52 guides
keyboard_arrow_down
1. Vectors
2. Matrices
3. Linear equations
4. Matrix determinant
5. Vector space
6. Special matrices
7. Eigenvalues and Eigenvectors
8. Orthogonality
9. Matrix decomposition
check_circle
Mark as learned
thumb_up
0
thumb_down
0
chat_bubble_outline
0
auto_stories new
settings

# Comprehensive Guide on Positive Definite Matrices

schedule Mar 5, 2023
Last updated
local_offer
Linear Algebra
Tags
map
Check out the interactive map of data science
Definition.

# Positive definite matrices

A square matrix is called positive definite if and only if the following two properties hold:

We often denote a positive definite matrix $\boldsymbol{A}$ by the following notation:

$$\boldsymbol{A}\succ0$$

Note that there are many equivalent ways of defining a positive definite matrix - we will later show that all the definitions are equivalent!

Example.

## Showing that a matrix is positive definite by definition

Show that the following matrix is positive definite:

$$\boldsymbol{A}= \begin{pmatrix} 2&1\\1&2 \end{pmatrix}$$

Solution. Firstly, we can see that $\boldsymbol{A}$ is symmetric so we're halfway done already 🙂. Next, let's find the eigenvalues of $\boldsymbol{A}$. The characteristic polynomiallink of $\boldsymbol{A}$ is:

\begin{align*} \det(\boldsymbol{A}-\lambda\boldsymbol{I}_2) &=\begin{vmatrix} 2-\lambda&1\\1&2-\lambda \end{vmatrix}\\&= (2-\lambda)^2-1^2 \\&=\lambda^2-4\lambda+3\\ &=(\lambda-3)(\lambda-1) \end{align*}

This means that the eigenvalues of $\boldsymbol{A}$ are $\lambda_1=3$ and $\lambda_2=1$, which are both positive. By definitionlink, $\boldsymbol{A}$ is positive definite.

Theorem.

# Eigenvalues of positive definite matrices are real

If matrix $\boldsymbol{A}$ is positive definite, then the eigenvalues of $\boldsymbol{A}$ are all real.

Proof. By definitionlink, a positive definite matrix is symmetric. By theoremlink, all eigenvalues of symmetric matrices are real. Therefore, the eigenvalues of positive definite matrices are real. This completes the proof.

Theorem.

# Positive definite matrices are invertible and have a positive determinant

If matrix $\boldsymbol{A}$ is positive definite, then $\boldsymbol{A}$ is invertiblelink and $\mathrm{det}(\boldsymbol{A})\gt0$.

Proof. Let $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ be the eigenvalues of a positive definite matrix $\boldsymbol{A}$ that includes duplicates. By propertylink, these eigenvalues are real. This allows us to apply theoremlink to get:

$$\det(\boldsymbol{A})= \prod^n_{i=1}\lambda_i$$

Since the eigenvalues of a positive definite matrix are positive by definitionlink, we have that $\det(\boldsymbol{A})\gt0$. This completes the proof. Note that the converse does not necessarily hold, that is, even if $\mathrm{det}(\boldsymbol{A})\gt0$, $\boldsymbol{A}$ may not be positive definite.

Theorem.

# Inverse of a positive definite matrix is also positive definite

Matrix $\boldsymbol{A}$ is positive definite if and only if $\boldsymbol{A}^{-1}$ is positive definite.

Proof. Assume $\boldsymbol{A}$ is a positive definite matrix. By definitionlink and propertylink, the eigenvalues $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ of $\boldsymbol{A}$ are all positive and real. By propertylink of eigenvalues, we have that the eigenvalues of $\boldsymbol{A}^{-1}$ are $\lambda_1^{-1}$, $\lambda_2^{-1}$, $\cdots$, $\lambda_n^{-1}$. Since the reciprocal of a positive value is also positive, we conclude that $\boldsymbol{A}^{-1}$ has positive eigenvalues as well.

Next, by propertylink of symmetric matrices, since $\boldsymbol{A}$ is an invertible symmetric matrix, $\boldsymbol{A}^{-1}$ is symmetric. Because $\boldsymbol{A}^{-1}$ is a symmetric matrix with positive eigenvalues, $\boldsymbol{A}^{-1}$ is positive definite. This completes the proof.

The next theorem about positive definite matrices is useful in proving future proofs and has important applications in fields such as optimization. In fact, some textbooks use this theorem as the definition of positive definite matrices!

Theorem.

# Matrix A is positive definite if and only if the quadratic form is greater than zero for every non-zero vector x

Let $\boldsymbol{A}$ be a symmetric $n\times{n}$ matrix. $\boldsymbol{A}$ is positive definite if and only if $\boldsymbol{x}^T\boldsymbol{Ax}\gt0$ for every vector $\boldsymbol{x}\ne\boldsymbol{0}$ in $\mathbb{R}^n$. Note that $\boldsymbol{x}^T\boldsymbol{Ax} \in\mathbb{R}$ is known as the quadratic form.

Proof. Before we prove the forward and backward propositions, let's first establish a lemma that will make the proof easier. Let $\boldsymbol{A}$ be a symmetric $n\times{n}$ matrix. By the principal axis theoremlink, $\boldsymbol{A}$ is orthogonally diagonalizablelink, which means that $\boldsymbol{A}$ can be expressed as:

$$$$\label{eq:taBETZVGlBpj1uIsipL} \boldsymbol{A}= \boldsymbol{Q}\boldsymbol{D}\boldsymbol{Q}^T$$$$

Where:

Let $\boldsymbol{x}$ be any vector in $\mathbb{R}^n$. Let $\boldsymbol{y}\in\mathbb{R}^n$ be defined as:

$$$$\label{eq:N4p8gH4ODUpJLGK4WG2} \boldsymbol{y}=\boldsymbol{Q}^T\boldsymbol{x}$$$$

Taking the transpose of both sides and applying propertylink of transpose gives:

\label{eq:BaN5zBAVObjTuptLDAv} \begin{aligned}[b] \boldsymbol{y}^T &=(\boldsymbol{Q}^T\boldsymbol{x})^T\\ &=\boldsymbol{x}^T(\boldsymbol{Q}^T)^T\\ &=\boldsymbol{x}^T\boldsymbol{Q}\\ \end{aligned}

Now, using \eqref{eq:taBETZVGlBpj1uIsipL}, \eqref{eq:N4p8gH4ODUpJLGK4WG2} and \eqref{eq:BaN5zBAVObjTuptLDAv}, we express $\boldsymbol{x}^T\boldsymbol{Ax}$ in terms of $\boldsymbol{y}$ and $\boldsymbol{D}$ like so:

\label{eq:oUP1ptSwuIwE7t75b8E} \begin{aligned}[b] \boldsymbol{x}^T\boldsymbol{Ax}&= \boldsymbol{x}^T(\boldsymbol{QDQ}^T)\boldsymbol{x}\\ &=(\boldsymbol{x}^T\boldsymbol{Q}) \boldsymbol{D}(\boldsymbol{Q}^T\boldsymbol{x})\\ &=\boldsymbol{y}^T\boldsymbol{D}\boldsymbol{y} \end{aligned}

By propertylink of diagonal matrices, $\boldsymbol{y}^T\boldsymbol{D}$ can be expressed as:

\label{eq:hKTc6s9ib53WOKFaa2m} \begin{aligned}[b] \boldsymbol{y}^T\boldsymbol{D}&= \begin{pmatrix}y_1&y_2&\cdots&y_n\end{pmatrix} \begin{pmatrix}\lambda_1&0&\cdots&0\\0&\lambda_2&\cdots&0\\ \vdots&\vdots&\smash\ddots&\vdots\\0&0&\cdots&\lambda_n \end{pmatrix}\\ &= \begin{pmatrix}y_1\lambda_1& y_2\lambda_2& \cdots&y_n\lambda_n\end{pmatrix} \end{aligned}

Where $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ are the eigenvalues of $\boldsymbol{A}$.

Multiplying both sides of \eqref{eq:hKTc6s9ib53WOKFaa2m} by $\boldsymbol{y}$ gives:

\label{eq:eKWQyABlSBnB2DJeI13} \begin{aligned}[b] \boldsymbol{y}^T\boldsymbol{Dy}&= \begin{pmatrix}y_1\lambda_1&y_2\lambda_2& \cdots&y_n\lambda_n\end{pmatrix} \begin{pmatrix}y_1\\y_2\\ \vdots\\y_n\end{pmatrix} \\&= y_1^2\lambda_1+ y_2^2\lambda_2+\cdots+ y_n^2\lambda_n \end{aligned}

Equating \eqref{eq:oUP1ptSwuIwE7t75b8E} and \eqref{eq:eKWQyABlSBnB2DJeI13} gives:

$$$$\label{eq:LEOPQYWBm4fgEUtWnC3} \boldsymbol{x}^T\boldsymbol{Ax}= y_1^2\lambda_1+ y_2^2\lambda_2+\cdots+ y_n^2\lambda_n$$$$

We will now use \eqref{eq:LEOPQYWBm4fgEUtWnC3} to prove the forward and backward proposition.

* * *

Let's first prove the forward proposition. Let $\boldsymbol{A}$ be a positive definite matrix. By definitionlink, the eigenvalues $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ of $\boldsymbol{A}$ are all positive. Therefore, we use \eqref{eq:LEOPQYWBm4fgEUtWnC3} to establish the following inequality:

$$\boldsymbol{x}^T\boldsymbol{Ax}\gt0$$

This proves the forward proposition.

* * *

Let's now prove the converse. Assume $\boldsymbol{x}^T\boldsymbol{Ax}\gt0$ for any vector $\boldsymbol{x}$ in $\mathbb{R}^n$. To show that $\boldsymbol{A}$ is positive definite, we must show that all of its eigenvalues $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ are positive. Since $\boldsymbol{x}$ can be any vector in $\mathbb{R}^n$, we can consider $\boldsymbol{x}$ to be:

$$\boldsymbol{x}=\boldsymbol{Q}\boldsymbol{e}_j$$

Where $\boldsymbol{e}_j\in\mathbb{R}^n$ is the $j$-th column of the identity matrix $\boldsymbol{I}_n$. This means that the $j$-th entry of vector $\boldsymbol{e}_j$ is $1$ while the rest of its entries are $0$. Since $\boldsymbol{y}= \boldsymbol{Q}^T\boldsymbol{x}$ by \eqref{eq:N4p8gH4ODUpJLGK4WG2}, we have that:

\begin{align*} \boldsymbol{y} &=\boldsymbol{Q}^T(\boldsymbol{Qe}_j)\\ &=\boldsymbol{Q}^T\boldsymbol{Qe}_j\\ &=\boldsymbol{e}_j \end{align*}

Here, $\boldsymbol{Q}^T\boldsymbol{Q}= \boldsymbol{I}_n$ by definitionlink of orthogonal matrices. Substituting $\boldsymbol{y}=\boldsymbol{e}_j$ into \eqref{eq:LEOPQYWBm4fgEUtWnC3} gives:

\label{eq:CqSGemXTxC3NK1Jqtdu} \begin{aligned}[b] \boldsymbol{x}^T\boldsymbol{Ax}&= y_1^2\lambda_1+ y_2^2\lambda_2+\cdots+ y_j^2\lambda_j+\cdots+ y_n^2\lambda_n\\ &=(0)^2\lambda_1+ (0)^2\lambda_2+\cdots+ (1)^2\lambda_j+\cdots+ (0)^2\lambda_n\\ &=\lambda_j \end{aligned}

Since $\boldsymbol{x}^T\boldsymbol{Ax}\gt0$ by assumption, we have that:

$$\lambda_j\gt0$$

This is true for $j=1,2,\cdots,n$, which means that every eigenvalue of $\boldsymbol{A}$ is positive. Since $\boldsymbol{A}$ is also symmetric by assumption, we conclude that $\boldsymbol{A}$ is positive definite. This completes the proof.

Theorem.

# Sum of two positive definite matrices is also positive definite

If $\boldsymbol{A}$ and $\boldsymbol{B}$ are positive definite matrices, then $\boldsymbol{A}+\boldsymbol{B}$ is positive definite.

Proof. Let $\boldsymbol{A}$ and $\boldsymbol{B}$ be $n\times{n}$ positive definite matrices. By theoremlink, for any $\boldsymbol{x}$ in $\mathbb{R}^n$, the following equations hold:

\begin{align*} \boldsymbol{x}^T\boldsymbol{Ax}&\gt0\\ \boldsymbol{x}^T\boldsymbol{Bx}&\gt0\\ \end{align*}

\begin{align*} \boldsymbol{x}^T\boldsymbol{Ax} +\boldsymbol{x}^T\boldsymbol{Bx} &\gt0\\ \boldsymbol{x}^T(\boldsymbol{A}+ \boldsymbol{B})\boldsymbol{x} &\gt0\\ \end{align*}

This means that $\boldsymbol{A}+\boldsymbol{B}$ is positive definite by theoremlink. This completes the proof.

Theorem.

# Diagonal entries of a positive definite matrix are all positive

If $\boldsymbol{A}$ is a positive definite matrix, then the diagonal entries of $\boldsymbol{A}$ are all positive.

Proof. Let $\boldsymbol{A}$ be an $n\times{n}$ positive definite matrix. By theoremlink, since $\boldsymbol{A}$ is positive definite, for any $\boldsymbol{x}$ in $\mathbb{R}^n$, the following holds:

$$$$\label{eq:DIrJMHKRNQnbnhYD4eM} \boldsymbol{x}^T\boldsymbol{Ax}\gt0$$$$

Let $\boldsymbol{e}_j$ be the $j$-th column of an $n\times{n}$ identity matrix, which means that the $j$-th entry of $\boldsymbol{e}_j$ is $1$ while the other entries are zero. Since \eqref{eq:DIrJMHKRNQnbnhYD4eM} holds for any $\boldsymbol{x}$ in $\mathbb{R}^n$, we let $\boldsymbol{x}=\boldsymbol{e}_j$ and substitute this into \eqref{eq:DIrJMHKRNQnbnhYD4eM} to get:

\begin{align*} \boldsymbol{e}_j^T\boldsymbol{Ae}_j&\gt0\\ \begin{pmatrix}0&0&\cdots&1&\cdots&0\end{pmatrix} \begin{pmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{j1}&a_{j2}&\cdots&a_{jn}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n1}&a_{n2}&\cdots&a_{nn} \end{pmatrix} \begin{pmatrix}0\\0\\\vdots\\1\\\vdots\\0\end{pmatrix} &\gt0\\ \begin{pmatrix}a_{1j}&a_{2j}&\cdots&a_{jj}&\cdots&a_{nj}\end{pmatrix} \begin{pmatrix}0\\0\\\vdots\\1\\\vdots\\0\end{pmatrix} &\gt0\\ a_{jj}&\gt0 \end{align*}

This is true for $j=1,2,\cdots,n$, which means that the diagonal entries of $\boldsymbol{A}$ are all positive. This completes the proof.

Definition.

# Principal sub-matrices

Let $\boldsymbol{A}$ be any $n\times{n}$ matrix. The $k$-th principal sub-matrix $\boldsymbol{A}_{(k)}$ is defined as the $k\times{k}$ sub-matrix of the top-left corner of $\boldsymbol{A}$.

Example.

## Finding the principal sub-matrices of a matrix

Consider the following matrix:

$$\boldsymbol{A}=\begin{pmatrix} 1&2&3\\ 4&5&6\\ 7&8&9 \end{pmatrix}$$

Find all the principal sub-matrices of $\boldsymbol{A}$.

Solution. Since $\boldsymbol{A}$ is a $3\times3$ matrix, $\boldsymbol{A}$ has $3$ principal sub-matrices:

$$\boldsymbol{A}_{(1)}= \begin{pmatrix}1\end{pmatrix} ,\;\;\;\; \boldsymbol{A}_{(2)}= \begin{pmatrix}1&2\\4&5\end{pmatrix} ,\;\;\;\; \boldsymbol{A}_{(3)}= \begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix}$$
Theorem.

## Every principal sub-matrix of a positive definite matrix is also positive definite

If $\boldsymbol{A}$ is an $n\times{n}$ positive definite matrixlink, then every principal sub-matrix of $\boldsymbol{A}$ is also positive definite, that is:

$$\boldsymbol{A}\succ0 \;\;\;\;{\color{blue}\implies}\;\;\;\; \boldsymbol{A}_{(k)}\succ0, \;\;\;\;\text{for }\;k=1,2,\cdots,n$$

Proof. Let matrix $\boldsymbol{A}$ be an $n\times{n}$ positive definite matrix, which can be expressed as the following block formlink:

$$$$\label{eq:mZ9oyoz09LCGYxMnNHw} \boldsymbol{A}=\begin{pmatrix} \boldsymbol{A}_{(k)}&\boldsymbol{B}\\ \boldsymbol{C}&\boldsymbol{D} \end{pmatrix}$$$$

Where $\boldsymbol{A}_{(k)}$ is the $k$-th principal sub-matrix, which has shape $k\times{k}$.

Let $\boldsymbol{y}$ be any non-zero vector in $\mathbb{R}^k$. We define $\boldsymbol{x}\in\mathbb{R}^n$ such that:

$$$$\label{eq:OcA1HmepVByk8cj3Jz0} \boldsymbol{x}=\begin{pmatrix} \boldsymbol{y}\\\boldsymbol{0} \end{pmatrix}$$$$

Where $\boldsymbol{0}\in\mathbb{R}^{n-k}$ is a zero vector.

Now, by theoremlink, since $\boldsymbol{A}$ is positive definite, the following holds:

$$$$\label{eq:VGnbjlccowPDQweR3nd} \boldsymbol{x}^T\boldsymbol{Ax}\gt0$$$$

Substituting \eqref{eq:mZ9oyoz09LCGYxMnNHw} and \eqref{eq:OcA1HmepVByk8cj3Jz0} into \eqref{eq:VGnbjlccowPDQweR3nd} gives:

$$$$\label{eq:qBLlprZAKgt6INL52FV} \begin{pmatrix} \boldsymbol{y}^T&\boldsymbol{0} \end{pmatrix} \begin{pmatrix} \boldsymbol{A}_{(k)}&\boldsymbol{B}\\ \boldsymbol{C}&\boldsymbol{D} \end{pmatrix} \begin{pmatrix} \boldsymbol{y}\\\boldsymbol{0} \end{pmatrix}\gt0$$$$

Multiplying the block matrices yields:

\begin{align*} \begin{pmatrix} \boldsymbol{y}^T&\boldsymbol{0} \end{pmatrix}\begin{pmatrix} \boldsymbol{A}_{(k)}&\boldsymbol{B}\\ \boldsymbol{C}&\boldsymbol{D} \end{pmatrix}\begin{pmatrix} \boldsymbol{y}\\\boldsymbol{0}\end{pmatrix}\gt0\\ \begin{pmatrix} \boldsymbol{y}^T\boldsymbol{A}_{(k)}& \boldsymbol{y}^T\boldsymbol{B} \end{pmatrix}\begin{pmatrix} \boldsymbol{y}\\\boldsymbol{0}\end{pmatrix}\gt0\\ \boldsymbol{y}^T\boldsymbol{A}_{(k)}\boldsymbol{y}\gt0 \end{align*}

Since $\boldsymbol{y}$ is any non-zero vector in $\mathbb{R}^k$, we conclude that $\boldsymbol{A}_{(k)}$ is positive definite by theoremlink. This completes the proof.

Theorem.

## Principal sub-matrices of symmetric matrices are also symmetric

If $\boldsymbol{A}$ is a symmetric matrixlink, then every principal sub-matrix of $\boldsymbol{A}$ is symmetric.

Proof. We will prove this by induction on the size of the matrix $\boldsymbol{A}$. For the base case, assume $\boldsymbol{A}$ is a symmetric $1\times1$ matrix, which only has a single principal sub-matrix $\boldsymbol{A}_{(1)}=\boldsymbol{A}$. This means that $\boldsymbol{A}_{(1)}$ is symmetric. This proves the base case.

We now assume that the theorem holds for when $\boldsymbol{A}$ is an $(n-1)\times(n-1)$ symmetric matrix, that is, every principal sub-matrix of a symmetric $(n-1)\times(n-1)$ matrix $\boldsymbol{A}$ is symmetric. Our goal is to show that the theorem holds for when $\boldsymbol{A}$ is an $n\times{n}$ symmetric matrix.

Let $\boldsymbol{A}$ be a symmetric $n\times{n}$ matrix. We know that $\boldsymbol{A}_{(k)}$ is symmetric for $k=1,2,\cdots,(n-1)$ by the inductive assumption. $\boldsymbol{A}_{(n)}=\boldsymbol{A}$ is symmetric as well, which means that every principal sub-matrix of $\boldsymbol{A}$ is symmetric. This completes the proof.

Theorem.

# Product of an invertible matrix and its transpose is positive definite

If $\boldsymbol{P}$ is any invertiblelink $n\times{n}$ matrix, then $\boldsymbol{P}^T\boldsymbol{P}$ is positive definite.

Proof. Let $\boldsymbol{A}=\boldsymbol{P}^T\boldsymbol{P}$. If $\boldsymbol{x}$ is any non-zero vector in $\mathbb{R}^n$, then:

\begin{align*} \boldsymbol{x}^T\boldsymbol{Ax} &=\boldsymbol{x}^T(\boldsymbol{P}^T\boldsymbol{P}) \boldsymbol{x}\\ &=(\boldsymbol{x}^T\boldsymbol{P}^T)(\boldsymbol{P} \boldsymbol{x})\\ &=(\boldsymbol{Px})^T(\boldsymbol{P}\boldsymbol{x})\\ &=\Vert\boldsymbol{Px}\Vert^2\\ \end{align*}

Here:

By propertylink, since $\boldsymbol{P}$ is invertible, we have that $\Vert\boldsymbol{Px}\Vert\gt0$. Therefore, we conclude $\boldsymbol{x}^T\boldsymbol{Ax}\gt0$, which means that $\boldsymbol{A}$ is positive definite by theoremlink. This completes the proof.

The next theorem provides more equivalent definitions of positive definite matrices. In particular, the third statement about the so-called Cholesky factorizationlink has important applications in numerical computing.

Theorem.

# Equivalent statements about positive definite matrices, determinant of principal sub-matrices and Cholesky factorization

Let $\boldsymbol{A}$ be a symmetric $n\times{n}$ matrix. The following statements are equivalent:

1. $\boldsymbol{A}$ is positive definite.

2. the determinant of every principal sub-matrix of $\boldsymbol{A}$ is positive, that is, $\det(\boldsymbol{A}_{(k)})\gt0$ for every $k=1,2,\cdots,n$.

3. $\boldsymbol{A}$ can be factorized as $\boldsymbol{A}=\boldsymbol{U}^T\boldsymbol{U}$ where $\boldsymbol{U}$ is an upper triangular matrixlink whose diagonal entries are positive. This is called the Cholesky factorizationlink, which will be discussed further in a future guide.

Proof. Let's prove $(1)\implies(2)\implies(3)\implies(1)$. We shall prove the easy ones first - starting with $(1)\implies(2)$. Assume $\boldsymbol{A}$ is a positive definite $n\times{n}$ matrix. By theoremlink, every principal sub-matrix of $\boldsymbol{A}$ is positive definite. By propertylink, every positive definite matrix has a positive determinant, which means that every principal sub-matrix of $\boldsymbol{A}$ has a positive determinant. This proves $(1)\implies(2)$.

Next, let's show $(3)\implies(1)$. Assume matrix $\boldsymbol{A}$ can be Cholesky-factorized as $\boldsymbol{A}=\boldsymbol{U}^T\boldsymbol{U}$ where $\boldsymbol{U}$ is an upper triangular matrix whose diagonal entries are positive. By propertylink, $\boldsymbol{U}$ is invertiblelink because every diagonal entry of $\boldsymbol{U}$ is non-zero. By theoremlink, $\boldsymbol{A}=\boldsymbol{U}^T\boldsymbol{U}$ is positive definite. This proves $(3)\implies(1)$.

* * *

Finally, let's prove $(2)\implies(3)$. Assume $\boldsymbol{A}$ is an $n\times{n}$ symmetric matrix where $\det(\boldsymbol{A}_{(k)})\gt0$ for every $k=1,2,\cdots,n$. We will prove this by induction on the size $n$ of matrix $\boldsymbol{A}$. For the base case, let $\boldsymbol{A}$ be an $1\times{1}$ symmetric matrix with a single entry $a$. Since $\boldsymbol{A}$ is $1\times1$, it only has one principal sub-matrix:

$$\boldsymbol{A}_{(1)}= \boldsymbol{A}= \begin{pmatrix}a\end{pmatrix}$$

If we let $\boldsymbol{U}= \begin{pmatrix}\sqrt{a}\end{pmatrix}$, then we can factorize $\boldsymbol{A}$ like so:

\begin{align*} \boldsymbol{A}&= \begin{pmatrix}a\end{pmatrix}\\&= \begin{pmatrix}\sqrt{a}\end{pmatrix}^T \begin{pmatrix}\sqrt{a}\end{pmatrix}\\ &=\boldsymbol{U}^T\boldsymbol{U} \end{align*}

Since $\boldsymbol{U}$ is trivially an upper triangular matrix by definitionlink with a positive diagonal entry, the base case holds. We now assume that $(2)\implies(3)$ holds for when $\boldsymbol{A}$ is an $(n-1)\times(n-1)$ matrix. This means that the $(n-1)$-th principal sub-matrix can be factorized as:

$$$$\label{eq:ZdAwzHhzyf2Xdy5EbIc} \boldsymbol{A}_{(n-1)} =\boldsymbol{U} ^T\boldsymbol{U}$$$$

Where $\boldsymbol{U}$ is an $(n-1)\times(n-1)$ upper triangular matrix. whose diagonal entries are positive.

Our goal now is to show that if $\boldsymbol{A}$ is a symmetric $n\times{n}$ matrix and $\det(\boldsymbol{A}_{(k)})\gt0$ for every $k=1,2,\cdots,n$, then $\boldsymbol{A}= \boldsymbol{U}_n^T\boldsymbol{U}_n$ where $\boldsymbol{U}_n$ is an $n\times{n}$ upper triangular matrix whose diagonal entries are positive. Note that we added a subscript $n$ for $\boldsymbol{U}_n$ to distinguish it from the $\boldsymbol{U}$ in \eqref{eq:ZdAwzHhzyf2Xdy5EbIc}.

By theoremlink, since $\boldsymbol{A}$ is symmetric, $\boldsymbol{A}_{(n-1)}$ is also symmetric. We can express $\boldsymbol{A}$ in block formatlink using $\boldsymbol{A}_{(n-1)}$ like so:

$$$$\label{eq:vae6XlpmHQMfT3VnFqm} \boldsymbol{A}=\begin{pmatrix} \boldsymbol{A}_{(n-1)}&\boldsymbol{b}\\ \boldsymbol{b}^T&c \end{pmatrix}$$$$

Where:

• $\boldsymbol{b}$ is a vector in $\mathbb{R}^{n-1}$.

• $c$ is a scalar in $\mathbb{R}$.

Substitute \eqref{eq:ZdAwzHhzyf2Xdy5EbIc} into \eqref{eq:vae6XlpmHQMfT3VnFqm} to get:

$$$$\label{eq:On7Uo2RmWno2sHuJPvD} \boldsymbol{A}=\begin{pmatrix} \boldsymbol{U}^T\boldsymbol{U} &\boldsymbol{b}\\ \boldsymbol{b}^T&c \end{pmatrix}$$$$

Now, define $\boldsymbol{x}\in\mathbb{R}^{n-1}$ such that:

$$$$\label{eq:SUq4ij5TqSwB6phITB2} \boldsymbol{x}= (\boldsymbol{U}^T)^{-1}\boldsymbol{b}$$$$

Here, we know that the inverse of $\boldsymbol{U}^T$ exists because:

1. the diagonal entries of the upper triangular matrix $\boldsymbol{U}$ are positive by assumption.

2. $\boldsymbol{U}^T$ will be a lower triangular matrix with positive diagonals by propertylink.

3. since the diagonal entries of $\boldsymbol{U}^T$ are non-zero, $\boldsymbol{U}^T$ is invertible by propertylink.

Rearranging \eqref{eq:SUq4ij5TqSwB6phITB2} to make $\boldsymbol{b}$ the subject gives:

$$$$\label{eq:Bgkam4eafNYKAW5lXQO} \boldsymbol{b}=\boldsymbol{U}^T\boldsymbol{x}$$$$

By propertylink of transpose, $\boldsymbol{b}^T$ is:

\label{eq:xiZNth1EUQpexBoTzzi} \begin{aligned}[b] \boldsymbol{b}^T &=(\boldsymbol{U}^T\boldsymbol{x})^T\\ &=\boldsymbol{x}^T\boldsymbol{U} \end{aligned}

Next, define $k\in\mathbb{R}$ such that:

$$$$\label{eq:Cvb1rlC5GWOMgq3POoW} k=c-\boldsymbol{x}^T \boldsymbol{x}$$$$

Rearranging \eqref{eq:Cvb1rlC5GWOMgq3POoW} to make $c$ the subject gives:

$$$$\label{eq:yIkEL9EMACSpc1WQhGN} c= \boldsymbol{x}^T\boldsymbol{x}+k$$$$
$$\boldsymbol{A}=\begin{pmatrix} \boldsymbol{U}^T\boldsymbol{U} &\boldsymbol{U}^T\boldsymbol{x}\\ \boldsymbol{x}^T\boldsymbol{U}& \boldsymbol{x}^T\boldsymbol{x}+k \end{pmatrix}$$

Just as we did in the proof of theoremlink, let's express $\boldsymbol{A}$ as a product of two block matrices:

\label{eq:wwopqUA1SZvbGPfr96D} \begin{aligned}[b] \boldsymbol{A} &=\begin{pmatrix} \boldsymbol{U}^T\boldsymbol{U} &\boldsymbol{U}^T\boldsymbol{x}\\ \boldsymbol{x}^T\boldsymbol{U}&\boldsymbol{x}^T\boldsymbol{x}+ k\end{pmatrix} \\&=\begin{pmatrix} \boldsymbol{U}^T\boldsymbol{U}+\boldsymbol{0}\boldsymbol{0} &\boldsymbol{U}^T\boldsymbol{x}+(k)\boldsymbol{0}\\ \boldsymbol{x}^T\boldsymbol{U}+(1)\boldsymbol{0}& \boldsymbol{x}^T\boldsymbol{x}+k \end{pmatrix}\\ &=\begin{pmatrix} \boldsymbol{U}^T&\boldsymbol{0}\\ \boldsymbol{x}^T&1\\ \end{pmatrix} \begin{pmatrix} \boldsymbol{U}&\boldsymbol{x}\\ \boldsymbol{0}&k\\ \end{pmatrix} \end{aligned}

Now, by propertylink of block matrices, notice how the two matrices on the right-hand side of \eqref{eq:wwopqUA1SZvbGPfr96D} will be transposes of one another if the bottom-right entry matched up. Suppose that the bottom-right entry did match up. In such a case, we can let $\boldsymbol{U}_n$ be the right matrix and $\boldsymbol{U}_n^T$ will be equal to the left matrix, that is, $\boldsymbol{A}=\boldsymbol{U}_n^T\boldsymbol{U}_n$. We also know that $\boldsymbol{U}_n$ is an upper triangular matrix because $\boldsymbol{U}$ in \eqref{eq:wwopqUA1SZvbGPfr96D} is upper triangular, which means our theorem is mostly proven.

One clever way of making the bottom-right entries of \eqref{eq:wwopqUA1SZvbGPfr96D} match is to show that $k\gt0$. This will allow us to write the product \eqref{eq:wwopqUA1SZvbGPfr96D} as:

$$\boldsymbol{A} =\begin{pmatrix} \boldsymbol{U}^T&\boldsymbol{0}\\ \boldsymbol{x}^T&\sqrt{k}\\ \end{pmatrix} \begin{pmatrix} \boldsymbol{U}&\boldsymbol{x}\\ \boldsymbol{0}&\sqrt{k} \end{pmatrix}$$

Note also that the diagonal entries of $\boldsymbol{U}_n$ are positive because $\boldsymbol{U}$ has positive diagonals by our inductive assumption. So, our goal now is to show that $k\gt0$. Let's go 🚀!

* * *

Taking the determinantlink of both sides of \eqref{eq:wwopqUA1SZvbGPfr96D} and applying the multiplicative propertylink of determinants gives:

\begin{align*} \det(\boldsymbol{A})&= \det\left[\begin{pmatrix} \boldsymbol{U}^T&\boldsymbol{0}\\ \boldsymbol{x}^T&1\\ \end{pmatrix} \begin{pmatrix} \boldsymbol{U}&\boldsymbol{x}\\ \boldsymbol{0}&k\\ \end{pmatrix}\right]\\ &= \det\left[\begin{pmatrix} \boldsymbol{U}^T&\boldsymbol{0}\\ \boldsymbol{x}^T&1\\ \end{pmatrix}\right]\cdot\det\left[ \begin{pmatrix} \boldsymbol{U}&\boldsymbol{x}\\ \boldsymbol{0}&k\\ \end{pmatrix}\right] \end{align*}

By theoremlink and theoremlink, the determinant terms on the right-hand side evaluate to:

\begin{align*} \det(\boldsymbol{A}) &=\big(\mathrm{det}(\boldsymbol{U}^T)\cdot\det(1)\big) \cdot\big(\mathrm{det}(\boldsymbol{U})\cdot\det(k)\big)\\ &=\det(\boldsymbol{U}^T) \cdot\det(\boldsymbol{U})\cdot{k} \end{align*}

By theoremlink, $\det(\boldsymbol{U}^T)=\det(\boldsymbol{U})$. This gives us:

\begin{align*} \det(\boldsymbol{A}) &=\det(\boldsymbol{U}) \cdot\det(\boldsymbol{U})\cdot{k}\\ &=\big[\mathrm{det}(\boldsymbol{U})\big]^2\cdot{k} \end{align*}

Now, $\boldsymbol{A}=\boldsymbol{A}_{(n)}$, which means that $\det(\boldsymbol{A})\gt0$ by assumption $(2)$ of our theorem. Therefore, we get the following inequality:

$$\big[\mathrm{det}(\boldsymbol{U})\big]^2\cdot{k}\gt0$$

Recall that $\boldsymbol{U}$ is an upper triangular matrix with positive diagonals. This means that $\boldsymbol{U}$ is invertiblelink by propertylink, and thus $\det(\boldsymbol{U})\ne0$ by propertylink. Because $\big[ \mathrm{det}(\boldsymbol{U})\big]^2$ is strictly positive, we have that $k\gt0$. This is what we set out to show - this completes the proof.

Example.

# Showing that a matrix is positive definite using the determinant of principal sub-matrices

Consider the following matrix:

$$\boldsymbol{A}=\begin{pmatrix} 2&3&1\\ 3&6&4\\ 1&4&8\\ \end{pmatrix}$$

Show that $\boldsymbol{A}$ is positive definitelink.

Solution. We compute the determinantlink of every principal sub-matrixlink of $\boldsymbol{A}$ below:

$$\boldsymbol{A}_{(1)}= \begin{pmatrix}2\end{pmatrix}, \;\;\;\;\; \boldsymbol{A}_{(2)}= \begin{pmatrix}2&3\\3&6\end{pmatrix}, \;\;\;\;\; \boldsymbol{A}_{(3)}= \begin{pmatrix}2&3&1\\3&6&4\\1&4&8\end{pmatrix}$$

The determinant of the first principal sub-matrix is:

\begin{align*} \mathrm{det}\big(\boldsymbol{A}_{(1)}\big) &=\begin{vmatrix}2\end{vmatrix}\\ &=2 \end{align*}

The determinant of the second principal sub-matrix is:

\begin{align*} \mathrm{det}\big(\boldsymbol{A}_{(2)}\big) &=\begin{vmatrix}2&3\\3&6\end{vmatrix}\\ &=(2)(6)-(3)(3)\\ &=12-9\\ &=3 \end{align*}

The determinant of the third principal sub-matrix is:

\begin{align*} \mathrm{det}\big(\boldsymbol{A}_{(3)}\big) &=\begin{vmatrix}2&3&1\\3&6&4\\1&4&8\end{vmatrix}\\ &=2\begin{vmatrix}6&4\\4&8\end{vmatrix}- 3\begin{vmatrix}3&4\\1&8\end{vmatrix}+ 1\begin{vmatrix}3&6\\1&4\end{vmatrix}\\ &=2\big((6)(8)-(4)(4)\big)- 3\big((3)(8)-(4)(1)\big)+ \big((3)(4)-(6)(1)\big)\\ &=2(32)-3(20)+(6)\\ &=10 \end{align*}

Since $\mathrm{det}\big(\boldsymbol{A}_{(k)}\big) \gt0$ for $k=1,2,3$, we conclude that $\boldsymbol{A}$ is positive definite by theoremlink.

Edited by 0 others
thumb_up
thumb_down
Comment
Citation
Ask a question or leave a feedback...
thumb_up
0
thumb_down
0
chat_bubble_outline
0
settings
Enjoy our search
Hit / to insta-search docs and recipes!