Probability

The Analysis of Data, volume 1

Linear Algebra: Positive Semidefinite Matrices

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.

  1. 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.
  2. 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.
  3. 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*}