Positive Semidefinite Matrix: Complete Guide with Examples

Quick Navigation

• What is a Positive Semidefinite Matrix?
• How to Check if a Matrix is Positive Semidefinite
• Properties of Positive Semidefinite Matrices
• Positive Definite vs Positive Semidefinite
• Real-World Applications
• Step-by-Step Examples
• Common Mistakes to Avoid
• Frequently Asked Questions
• Related Topics

---

What is a Positive Semidefinite Matrix?

Definition

A symmetric matrix $A$ is called positive semidefinite (PSD) if the quadratic form $x^T A x$ is non-negative for every vector $x$:

$$ \boxed{x^T A x \geq 0 \quad \text{for all } x \in \mathbb{R}^n} $$

The key difference from positive definite is that zero is allowed for some non-zero vectors $x$.

Simple Analogy

Think of a positive semidefinite matrix as the matrix equivalent of a non-negative number:

Numbers	Matrices
$a \geq 0$	$A \succeq 0$ (positive semidefinite)
$a > 0$	$A \succ 0$ (positive definite)
$a = 0$	Zero matrix or singular PSD

Geometric Interpretation

For a 2×2 positive semidefinite matrix, the equation $x^T A x = 1$ can represent:

• Full ellipse: If both eigenvalues are $> 0$ (Positive Definite).
• Parallel lines: If one eigenvalue is $0$ and the other $> 0$ (Singular PSD).
• Empty set/Point: If both eigenvalues are $0$ (Zero Matrix).

Simple Examples

✅ Positive Semidefinite: $$ A = \left[\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}\right],\quad B = \left[\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array}\right],\quad C = \left[\begin{array}{cc} 2 & -1 \\ -1 & 0.5 \end{array}\right] $$

❌ Not Positive Semidefinite: $$ D = \left[\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right],\quad E = \left[\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}\right],\quad F = \left[\begin{array}{cc} -1 & 0 \\ 0 & -1 \end{array}\right] $$

Special Cases

Zero Matrix: $A = 0$ is positive semidefinite (all eigenvalues are 0).

Rank-1 PSD: $A = v v^T$ for any vector $v$ is always PSD.

Example: Let $v = \left[\begin{array}{c} 1 \\ 2 \end{array}\right]$. Then: $$ v v^T = \left[\begin{array}{c} 1 \\ 2 \end{array}\right] \left[\begin{array}{cc} 1 & 2 \end{array}\right] = \left[\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}\right] $$ This matrix is PSD with eigenvalues $5$ and $0$.

---

How to Check if a Matrix is Positive Semidefinite

Method 1: Eigenvalue Test (Definitive)

A symmetric matrix is positive semidefinite if and only if all its eigenvalues are non-negative:

$$ \lambda_i \geq 0 \quad \text{for all } i = 1, \dots, n $$

Procedure:

1. Compute all eigenvalues $\lambda_1, \dots, \lambda_n$.
2. Verify that every $\lambda_i \geq 0$.
3. The number of zero eigenvalues determines the rank deficiency.

Example: $$ A = \left[\begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array}\right] $$ Eigenvalues: $\lambda_1 = 2$, $\lambda_2 = 0$. Both are $\geq 0$ ✓ Positive semidefinite! Rank = 1 (one non-zero eigenvalue).

Method 2: Cholesky Decomposition

A matrix is positive semidefinite if it admits a Cholesky decomposition (possibly with zeros on the diagonal):

$$ A = L L^T $$

where $L$ is lower triangular. If the algorithm encounters a negative number under a square root, the matrix is not PSD.

Example: $$ A = \left[\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}\right] = \left[\begin{array}{cc} 1 & 0 \\ 2 & 0 \end{array}\right] \left[\begin{array}{cc} 1 & 2 \\ 0 & 0 \end{array}\right] $$

Method 3: Principal Minors Test

Unlike positive definite matrices (where only leading principal minors matter), a matrix is positive semidefinite if and only if ALL principal minors are non-negative.

$$ \det(A_{I,I}) \geq 0 \quad \text{for all subsets of indices } I $$

Example for 2×2: $$ A = \left[\begin{array}{cc} a & b \\ c & d \end{array}\right] $$ Must check:

• $a \geq 0$
• $d \geq 0$
• $\det(A) = ad - bc \geq 0$

Method 4: Factorization Test

A matrix is positive semidefinite if it can be written as:

$$ A = M^T M $$

for some real matrix $M$ (not necessarily square). This is often used to generate PSD matrices.

Example: $$ A = \left[\begin{array}{cc} 1 & 2 \\ 2 & 5 \end{array}\right] = \left[\begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array}\right]^T \left[\begin{array}{cc} 1 & 2 \\ 0 & 1 \end{array}\right] $$

---

Properties of Positive Semidefinite Matrices

1. 🎯 Non-Negative Eigenvalues

All eigenvalues satisfy $\lambda_i \geq 0$. The number of strictly positive eigenvalues equals the rank of the matrix.

2. 📊 Rank Revealing

$$ \text{rank}(A) = |{i : \lambda_i > 0}| $$

3. 🔄 Singular (Not Invertible)

If any eigenvalue is zero, the matrix is singular (non-invertible). Only full-rank PSD matrices (which are Positive Definite) are invertible.

4. 📈 Non-Negative Diagonal Entries

Since $e_i^T A e_i = a_{ii} \geq 0$:

$$ a_{ii} \geq 0 \quad \text{for all } i $$

5. 🔗 Sum of PSD Matrices

The sum of positive semidefinite matrices is always positive semidefinite:

$$ A \succeq 0,\ B \succeq 0 \Rightarrow A + B \succeq 0 $$

6. ⚡ Cauchy-Schwarz Inequality

For any PSD matrix $A$, the entries satisfy:

$$ |a_{ij}| \leq \sqrt{a_{ii} a_{jj}} $$

This implies that if a diagonal entry is zero, the entire corresponding row and column must be zero.

7. 🧩 Schur Complement

If $A$ is PSD and partitioned as: $$ A = \left[\begin{array}{cc} B & C \\ C^T & D \end{array}\right] $$ then the Schur complement $D - C^T B^{\dagger} C$ is also PSD (where $B^{\dagger}$ is the pseudo-inverse).

8. 📐 Square Root Existence

Positive semidefinite matrices have a unique positive semidefinite square root $S$:

$$ A = S^2 \quad \text{where } S = Q \sqrt{D} Q^T $$

---

Positive Definite vs Positive Semidefinite

Property	Positive Definite ($A \succ 0$)	Positive Semidefinite ($A \succeq 0$)
Quadratic form	$x^T A x > 0$ (strict)	$x^T A x \geq 0$
Eigenvalues	All $\lambda_i > 0$	All $\lambda_i \geq 0$
Zero eigenvalues	None	Possible (one or more)
Invertible	Yes (non-singular)	No (singular if any $\lambda_i=0$)
Determinant	$> 0$	$\geq 0$
Cholesky	Unique (positive diag)	Exists (diag may have zeros)
Geometry	Ellipse (non-degenerate)	Degenerate (lines/points)
Optimization	Unique strict minimum	May have flat directions
Null space	Only ${0}$	Non-trivial possible

Example Comparison

Positive Definite (full rank): $$ A = \left[\begin{array}{cc} 2 & 1 \\ 1 & 2 \end{array}\right],\quad \lambda_1 = 3,\ \lambda_2 = 1 $$

Positive Semidefinite (rank 1): $$ B = \left[\begin{array}{cc} 1 & 1 \\ 1 & 1 \end{array}\right],\quad \lambda_1 = 2,\ \lambda_2 = 0 $$

Positive Semidefinite (rank 0): $$ C = \left[\begin{array}{cc} 0 & 0 \\ 0 & 0 \end{array}\right],\quad \lambda_1 = 0,\ \lambda_2 = 0 $$

---

Real-World Applications

📊 Statistics: Covariance Matrices

Every covariance matrix is positive semidefinite:

$$ \Sigma = \mathbb{E}[(X-\mu)(X-\mu)^T] \succeq 0 $$

Interpretation:

• Positive definite: All variables are linearly independent.
• Positive semidefinite: Some variables are linearly dependent (redundant information).

🤖 Machine Learning: Kernel Matrices

Valid kernel functions produce positive semidefinite Gram matrices:

$$ K_{ij} = k(x_i, x_j) \succeq 0 $$

Examples:

• RBF kernel: $k(x,y) = \exp(-\gamma\|x-y\|^2)$
• Linear kernel: $k(x,y) = x^T y$

🔬 Physics: Mass Matrices

In structural dynamics with constraints, mass matrices can be singular (semidefinite). Rigid body modes correspond to zero eigenvalues.

📈 Optimization: Quadratic Programming

For quadratic programming problems minimizing $\frac{1}{2}x^T Q x + c^T x$:

• $Q \succ 0$: Strictly convex (unique solution).
• $Q \succeq 0$: Convex (may have multiple solutions).
• $Q$ indefinite: Non-convex (hard to solve).

🎯 Principal Component Analysis (PCA)

In PCA, the covariance matrix is PSD. Zero eigenvalues indicate dimensions with zero variance, which can be dropped to reduce dimensionality.

🧮 Graph Theory: Laplacian Matrices

The graph Laplacian $L = D - A$ is always positive semidefinite. The number of zero eigenvalues equals the number of connected components in the graph.

---

Step-by-Step Examples

Example 1: 2×2 Rank-1 PSD Matrix

Problem: Check if $A = \left[\begin{array}{cc} 4 & 2 \\ 2 & 1 \end{array}\right]$ is positive semidefinite.

Solution using Eigenvalues:

Step 1: Compute characteristic equation: $$ \det(A - \lambda I) = \det\left[\begin{array}{cc} 4-\lambda & 2 \\ 2 & 1-\lambda \end{array}\right] = (4-\lambda)(1-\lambda) - 4 = 0 $$

Step 2: Expand: $$ 4 - 5\lambda + \lambda^2 - 4 = \lambda^2 - 5\lambda = \lambda(\lambda - 5) = 0 $$

Step 3: Eigenvalues: $$ \lambda_1 = 5,\ \lambda_2 = 0 $$

Step 4: Conclusion: Both eigenvalues $\geq 0$ → Positive semidefinite ✓

Example 2: 2×2 Full-Rank PSD (Positive Definite)

Problem: Check if $A = \left[\begin{array}{cc} 3 & 1 \\ 1 & 2 \end{array}\right]$ is PSD.

Solution using Cholesky:

Step 1: Attempt Cholesky decomposition: $$ l_{11} = \sqrt{3} \approx 1.732 $$ $$ l_{21} = \frac{1}{l_{11}} \approx 0.577 $$ $$ l_{22} = \sqrt{2 - (0.577)^2} = \sqrt{1.667} \approx 1.291 $$

Step 2: Since all square roots were of non-negative numbers, Cholesky exists.

Step 3: Conclusion: Positive definite (and therefore also PSD) ✓

Example 3: 3×3 PSD from Outer Product

Problem: Show that $A = v v^T$ is always PSD for $v = \left[\begin{array}{c} 1 \\ 2 \\ 1 \end{array}\right]$.

Solution:

Step 1: Compute $A = v v^T$: $$ A = \left[\begin{array}{c} 1 \\ 2 \\ 1 \end{array}\right] \left[\begin{array}{ccc} 1 & 2 & 1 \end{array}\right] = \left[\begin{array}{ccc} 1 & 2 & 1 \\ 2 & 4 & 2 \\ 1 & 2 & 1 \end{array}\right] $$

Step 2: Check quadratic form for any $x$: $$ x^T A x = x^T (v v^T) x = (x^T v)(v^T x) = (v^T x)^2 \geq 0 $$

Step 3: Conclusion: Since $(v^T x)^2$ is always non-negative, $A$ is PSD ✓

Example 4: Matrix That Is NOT PSD

Problem: Check if $A = \left[\begin{array}{cc} 1 & 2 \\ 2 & 3 \end{array}\right]$ is PSD.

Solution using Determinant:

Step 1: Check diagonal entries: $1 \geq 0$ and $3 \geq 0$ ✓

Step 2: Check determinant: $$ \det(A) = (1)(3) - (2)(2) = 3 - 4 = -1 $$

Step 3: Since $\det(A) < 0$, the product of eigenvalues is negative. This implies one eigenvalue is positive and one is negative.

Step 4: Conclusion: Not PSD (Indefinite) ✗

---

Common Mistakes to Avoid

❌ Mistake 1: Assuming PSD Means All Entries Non-Negative

Wrong: "All entries are $\geq 0$, so the matrix is PSD."

Counterexample: $$ A = \left[\begin{array}{cc} 1 & 2 \\ 2 & 1 \end{array}\right] $$ All entries are positive, but eigenvalues are $3$ and $-1$. Since $-1 < 0$, it is not PSD.

❌ Mistake 2: Only Checking Leading Principal Minors

Wrong: "All leading principal minors $\geq 0$, so matrix is PSD."

Counterexample: $$ A = \left[\begin{array}{ccc} 0 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 0 \end{array}\right] $$ Leading minors are $0, 0, 0$ (all $\geq 0$), but the matrix has a negative eigenvalue ($-1$).

Right: For PSD, you must check all principal minors, or simply use the eigenvalue test.

❌ Mistake 3: Confusing PSD with Positive Definite

Wrong: "If a matrix is PSD, it must be invertible."

Right: PSD matrices are often singular. If any eigenvalue is 0, the matrix is not invertible.

❌ Mistake 4: Ignoring Symmetry

Wrong: Applying PSD tests to non-symmetric matrices.

Right: Positive semidefiniteness is defined for symmetric matrices. If a matrix is not symmetric, check its symmetric part $\frac{A+A^T}{2}$.

❌ Mistake 5: Numerical Rounding Errors

Wrong: Declaring a matrix not PSD because an eigenvalue is $-10^{-15}$.

Right: Use a small tolerance $\epsilon$ (e.g., $10^{-10}$). If $\lambda_i > -\epsilon$, treat it as non-negative.

---

Frequently Asked Questions

Q: Is the zero matrix positive semidefinite?

A: Yes! The zero matrix has all eigenvalues equal to 0, so $x^T 0 x = 0 \geq 0$ for all $x$.

Q: Is the identity matrix PSD?

A: Yes! The identity matrix is positive definite (all eigenvalues are 1), which is a stronger condition than PSD.

Q: Can a PSD matrix have negative off-diagonal entries?

A: Yes! Example: $\left[\begin{array}{cc} 2 & -1 \\ -1 & 2 \end{array}\right]$ is PSD (eigenvalues 3 and 1).

Q: What is the relationship between PSD and covariance?

A: All covariance matrices are PSD. Zero eigenvalues indicate linear dependence between variables (redundancy).

Q: How do I generate a random PSD matrix?

A: Generate any random matrix $M$ and compute $A = M^T M$. This guarantees $A$ is PSD.