Probability
The Analysis of Data, volume 1
Linear Algebra: Positive Semidefinite Matrices
$
\def\P{\mathsf{\sf P}}
\def\E{\mathsf{\sf E}}
\def\Var{\mathsf{\sf Var}}
\def\Cov{\mathsf{\sf Cov}}
\def\std{\mathsf{\sf std}}
\def\Cor{\mathsf{\sf Cor}}
\def\R{\mathbb{R}}
\def\c{\,|\,}
\def\bb{\boldsymbol}
\def\diag{\mathsf{\sf diag}}
\def\col{\mathsf{\sf col}}
\def\row{\mathsf{\sf row}}
\def\rank{\mathsf{\sf rank}}
\def\defeq{\stackrel{\tiny\text{def}}{=}}
$
C.4. Positive Semidefinite Matrices
Definition C.4.1.
A square symmetric matrix $H\in\R^{n\times n}$ is positive semi-definite (psd) if
\[ {\bb v}^{\top}H{\bb v}\geq 0, \qquad \forall \bb v \in\R^{n}\] and positive definite (pd) if the inequality holds with equality only for vectors $\bb v=\bb 0$. A square symmetric matrix $H\in\R^{n\times n}$ is negative semi-definite (nsd) if
\[ {\bb v}^{\top}H{\bb v}\leq 0, \qquad \forall \bb v \in\R^{n}\] and negative definite (nd) if the inequality holds with equality only for vectors $\bb v=\bb 0$.
We make the following observations.
- The matrix $A$ is psd if any only if $-A$ is nsd, and similarly a matrix $A$ is pd if and only if $-A$ is nd.
- The psd and pd concepts are denoted by $0\preceq A$ and $0\prec A$, respectively. The nsd and nd concepts are denoted by $A\preceq 0$ and $A\prec 0$, respectively.
- The notations above can be extended to denote a partial order on matrices: $A\preceq B$ if and only if $A-B\preceq 0$ and $A\prec B$ if any only if $A-B\prec 0$. Note that $A\prec B$ does not imply that all entries of $A$ are smaller than all entries of $B$.
Proposition C.4.1.
A symmetric matrix is psd if and only if all eigenvalues are non-negative. It is nsd if and only if all eigenvalues are non-positive. It is pd if and only if all eigenvalues are positive. It is nd if and only if all eigenvalues are negative.
Proof.
Let $\bb v$ be an arbitrary vector. Using the spectral decomposition, we have
\[\bb v^{\top} A\bb v=(\bb v^{\top} U)\diag(\bb\lambda)(U^{\top}\bb v)=\sum_{i=1}^n \lambda_i ([\bb v^{\top} T]_i)^2,\]
where $U$ is a matrix containing the $n$ orthogonal eigenvectors of $A$. The above expression is non-negative for all $\bb v$ if and only if $\lambda_i\geq 0$ for all $i=1,\ldots,n$. The rest of the proof is similar.
Proposition C.4.2.
Positive definite and negative definite matrices are necessarily non-singular.
Proof.
Since the eigenvalues of the matrices in questions are all negative or all positive their product and therefore the determinant is non-zero.
Proposition C.4.3.
A symmetric matrix of rank $r$ is psd if and only if there exists a square matrix $R$ of rank $r$ such that $A=R^{\top}R$. If $A$ is pd then $R$ is singular.
Proof.
Let $A$ be a psd matrix $A$ of rank $r$. Then it has $r$ non-zero eigenvalues and we can write its spectral decomposition as
\begin{align*}
A = V\diag(\lambda_1,\ldots,\lambda_r) V^{\top}=
V\diag(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_r}) \diag(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_r}) V^{\top},
\end{align*}
where $V$ is a matrix whose columns contain the $r$ eigenvectors corresponding to non-zero eigenvalues. Conversely, if $A=RR^{\top}$ then $\rank(A)=\rank(R)=r$ (see Proposition C.2.5) and
\[({\bb v}^{\top}R)(R^{\top}\bb v) = {\bb w}^{\top}\bb w \geq 0.\]
Finally, if $A=R^{\top}R$ is pd then it is non-singular and therefore of full rank. It follows that $R$ is also non-singular and of full rank (see Proposition C.2.5).
Proposition C.4.4.
If $A$ is pd then so is $A^{-1}$
Proof.
Let $A$ be a pd matrix. Using the previous proposition, we have
\[A^{-1} = (RR^{\top})^{-1} = R^{-1}(R^{\top})^{-1} = R^{-1}(R^{-1})^{\top}\]
where $R$ is a non-singular square matrix. Using the previous proposition again (the converse part), we get that $A^{-1}$ is pd.
Proposition C.4.5.
The diagonal elements of a pd matrix are all positive.
Proof.
Using the standard basis ${\bb e}^{(i)}$ (see Example C.1.4), we have \[({\bb e}^{(i)})^{\top} A {\bb e}^{(i)} =A_{ii}, \qquad i=1,\ldots,n.\]
It follows that if $A$ is pd, $A_{ii} > 0, i=1,\ldots,n$.
Proposition C.4.6.
If $A$ is positive definite there exists a square root matrix $A^{1/2}$ for which $A^{1/2}A^{1/2}=A$.
Proof.
Let $A$ be a pd matrix with positive eigenvalues. Using the spectral decomposition, we have
\begin{align*}
A&= U^{\top} \diag(\lambda_1,\ldots,\lambda_n) U \\ &=
(U^{\top} \diag(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_n})
U)(U^{\top}
\diag(\sqrt{\lambda_1},\ldots,\sqrt{\lambda_n})U) \\&= A^{1/2} A^{1/2}.
\end{align*}