ConceptLinear Algebra used inMSIAI-written · not yet proofread

Positive Semidefinite Matrix

Also PSD Matrix · Positive Semi-Definite Matrix · Positive Definite Matrix · Positive Semidefiniteness · Positiv semidefinite Matrix · Positiv definite Matrix

A symmetric matrix B is positive semidefinite (B ≽ 0) if zᵀBz ≥ 0 for all z, equivalently if all its eigenvalues are ≥ 0; positive definite (B ≻ 0) if zᵀBz > 0 for all z ≠ 0.

Know these firstMatrix Rank Eigenvalue

Properties#

Proof

By the spectral theorem $B = Q \Lambda Q^\top$ with orthogonal $Q$ and $\Lambda = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ . Substituting $w = Q^\top z$ (a bijection of $\mathbb{R}^n$ , with $w = 0 \iff z = 0$ ) gives $z^\top B z = w^\top \Lambda w = \sum_i \lambda_i w_i^2$ . This is $\geq 0$ for all $w$ iff every $\lambda_i \geq 0$ (take $w = e_i$ for “only if”), and $> 0$ for all $w \neq 0$ iff every $\lambda_i > 0$ .

Positive definite ⇒ invertible: $B \succ 0$ has no zero eigenvalue, so it is an invertible matrix. A PSD matrix is invertible iff it is positive definite.
Gram matrices: for any $A \in \mathbb{R}^{n \times m}$ the matrix $A^\top A \in \mathbb{S}^m$ is positive semidefinite, and $A^\top A \succ 0 \iff \operatorname{rank}(A) = m$ (full column rank). In MSI: $\Phi^\top\Phi \succ 0 \iff \operatorname{rank}(\Phi) = d$ . Similarly $BB^\top \succcurlyeq 0$ for any $B$ .
Diagonal entries: $B \succcurlyeq 0 \Rightarrow B_{ii} = e_i^\top B e_i \geq 0$ . A negative diagonal entry rules out PSD, but nonnegative diagonal entries don’t prove it.
Sums: if $A \succcurlyeq 0$ and $B \succcurlyeq 0$ , then $A + B \succcurlyeq 0$ . If additionally one of them is $\succ 0$ , the sum is $\succ 0$ (used for regularization, e.g. adding a small $Q \succ 0$ ).
Where it appears in MSI: covariance matrices are PSD; a weighted norm $\|x\|_W^2 = x^\top W x$ needs $W \succ 0$ ; second-order optimality conditions ask for a PSD/PD Hessian; the Gauss–Newton Hessian approximation $J^\top J$ is PSD but not necessarily PD.

Example#

Sources#

MSI script p. 10 (notation $\mathbb{S}^n$ , $\succcurlyeq$ , $\succ$ ), MSI_VL01 > Sets, vectors, matrices
MSI script p. 23–24 (Definition 5, generalized inequality for symmetric matrices)
MSI script p. 52 (Gauss–Newton Hessian approximation is PSD)
Exercise: MSI Sheet 00, task 3 (not published) ( $A^\top A$ is symmetric and PSD)

Connections

Mentioned in inline links10

Eigenvalue
Symmetric matrices have only real eigenvalues (spectral theorem, Eigenvector). A symmetric matrix is positive semidefinite iff all its eigenvalues are $\ge 0$ , and positive definite iff all are $> 0$ . §
Eigenvector
Eigenvectors of a symmetric matrix for different eigenvalues are automatically orthogonal. Within one eigenspace of dimension $> 1$ an orthonormal basis can be chosen with Gram–Schmidt (MML Example 4.8). This is the decomposition behind th… §
Use in MSI: spectral decomposition behind the eigenvalue test for PSD matrices §
Invertible Matrix
Positive definite ⇒ invertible: if $A \succ 0$ (positive definite), all eigenvalues are $> 0$ , so $0$ is not an eigenvalue. MSI: $\Phi^\top \Phi \succ 0 \iff \operatorname{rank}(\Phi) = d$ . §
Matrix Rank
Gram matrix: $\operatorname{rank}(A^\top A) = \operatorname{rank}(A)$ . So the $n \times n$ matrix $A^\top A$ (always PSD) is invertible iff $A$ has full column rank. MSI uses this for least squares: $(\Phi^\top \Phi)^{-1}$ exists iff… §
Determinants and Eigenvalues
Symmetric matrices in MSI. The symmetric case is the one that matters for least squares and covariances. A symmetric matrix is positive (semi)definite iff all its eigenvalues are $> 0$ ( $\ge 0$ ). By $\det = \prod\lambda_i$ , a positive defi… §
Inner Products and Norms
Matrix form: the dot products of a vector $q$ with all columns $a_1, \dots, a_n$ of $A$ are the entries of $q^\top A$ ; all pairwise dot products of the columns form the Gram matrix $A^\top A$ , which is positive semidefinite because… §
Rank and Invertibility
Positive Semidefinite Matrix — Gram matrices $A^\top A$ are PSD, and positive definite exactly in the full column rank case §
Definiteness as a rank test for Gram matrices: the chain behind the least squares case is $A^\top A \succcurlyeq 0$ always (since $x^\top A^\top A x = \|Ax\|_2^2$ ), with $x^\top A^\top A x = 0 \iff x \in \ker(A)$ . So full column rank ⇔… §
Covariance MatrixPROB
Symmetric and positive semidefinite: $\Sigma_X = \Sigma_X^\top$ and $z^\top\Sigma_X z = \mathbb{E}\{(z^\top(X - \mu_X))^2\} = \operatorname{Var}(z^\top X) \ge 0$ for all $z$ (Positive Semidefinite Matrix). The Multivariate Normal Distribut… §
Multivariate Normal DistributionPROB
$\Sigma$ must be positive definite for the PDF to exist: $\Sigma^{-1}$ appears in the exponent and $\det(2\pi\Sigma) = (2\pi)^n \det\Sigma$ must be positive (Positive Semidefinite Matrix). §
Moments of Random VariablesPROB
Why matrices. For a parameter vector $\theta \in \mathbb{R}^d$ the uncertainty of an estimate is not one number: errors in different components can be correlated. The covariance matrix is symmetric positive semidefinite, and “smaller uncer… §

Search in these mentions →