Positive semidefinite matrix

1 Positive Semidefinite Matrices: Definition and Basic Properties

1.1 Quadratic-form definition

A real symmetric (or complex Hermitian) matrix \(A\) is called positive semidefinite (PSD) if its quadratic form is nonnegative for every vector \(x\): \(x^\ast A x \ge 0\) for all \(x\). This condition means that the matrix never produces a negative “energy” when evaluated on any direction in the underlying vector space.

1.2 Symmetry/Hermiticity requirements

To interpret \(x^\ast A x\) as a real-valued quantity for all \(x\), the matrix must be symmetric (real case) or Hermitian (complex case). Without this property, the quadratic form can be complex or can vary in sign in ways that do not align with a consistent notion of nonnegativity. For most theory and applications, PSD matrices are defined within the symmetric/Hermitian class.

1.3 Spectral characterization via eigenvalues

For a symmetric/Hermitian matrix \(A\), \(A\) is PSD exactly when all its eigenvalues are nonnegative. In finite dimensions, this yields a clean characterization: \(A \succeq 0\) if and only if \(\lambda_i \ge 0\) for every eigenvalue \(\lambda_i\). The equivalence is a standard consequence of the spectral theorem.

1.4 Equivalent conditions (congruence and inner products)

1.5 Examples and non-examples

Examples include covariance matrices and kernel matrices (discussed later), as they naturally satisfy the quadratic-form nonnegativity. Matrices with negative diagonal entries are not automatically non-PSD, but a sufficient condition for non-PSD is the existence of a vector \(x\) for which \(x^\ast A x < 0\). A typical non-example is any Hermitian matrix with at least one negative eigenvalue, such as \(A=\begin{pmatrix}1&0\\0&-1\end{pmatrix}\), which produces both positive and negative quadratic forms.

2 Characterizations and Factorizations

2.1 Cholesky-type factorizations

A classical Cholesky factorization expresses a positive definite matrix as \(A=LL^\ast\) with \(L\) lower triangular. For PSD matrices, a strict Cholesky factorization may fail due to singularity, but a generalized form still exists: PSD matrices can be factored as \(A = LL^\ast\) using a factor \(L\) that may be rank-deficient. Numerically, this appears as “pivoted” or “modified” Cholesky methods.

2.2 Square-root factorization and matrix functions

Every PSD matrix admits a (unique) principal square root \(A^{1/2}\), which is itself PSD and satisfies \((A^{1/2})^2 = A\). This is defined via functional calculus on the eigenvalues: if \(A=U\Lambda U^\ast\) with \(\Lambda\) diagonal and \(\Lambda \ge 0\), then \(A^{1/2}=U\Lambda^{1/2}U^\ast\). Such square-root factorizations are frequently used in optimization, statistics, and numerical linear algebra.

2.3 Gram matrix interpretation

A matrix \(A\) is PSD precisely when it can be realized as a Gram matrix. Concretely, there exist vectors \(v_1,\dots,v_n\) in some inner product space such that \(A_{ij}=\langle v_i, v_j\rangle\). This interpretation ties PSD matrices to geometry: they encode pairwise inner products, ensuring that quadratic forms correspond to squared norms of linear combinations.

2.4 Moore–Penrose pseudoinverse relationships

Singular PSD matrices often appear with pseudoinverses. If \(A \succeq 0\), then its Moore–Penrose pseudoinverse \(A^\dagger\) is also PSD on the appropriate subspace, and relations such as \(A A^\dagger A = A\) hold. In quadratic forms, this connects to least-squares solutions and to regularization limits where small eigenvalues are treated carefully.

2.5 Block-structure and principal submatrices

PSD behavior is stable under taking principal submatrices: if \(A\succeq 0\), then any principal submatrix is also PSD. More generally, PSD properties interact with block partitions in controlled ways, enabling Schur-complement reasoning. Such decompositions support both theoretical proofs and practical checks.

3 Tests and Criteria for Positive Semidefiniteness

3.1 Principal minor (Sylvester-type) criteria

For symmetric matrices, nonnegativity can sometimes be tested by checking minors. A well-known criterion is: a symmetric matrix is PSD if and only if all its principal minors are nonnegative in the appropriate form. This mirrors Sylvester’s criterion for positive definiteness, but with distinctions because semidefinite matrices may be singular.

3.2 Leading principal minors vs. general principal minors

Leading principal minors refer only to determinants of top-left blocks. For positive definiteness, checking leading minors suffices; for PSD, leading minors alone are not generally enough. The gap is important in practice: one may incorrectly conclude PSD from incomplete minor checks unless the matrix satisfies additional structural conditions.

3.3 Eigenvalue-based verification

Since PSD is equivalent to having nonnegative eigenvalues, eigenvalue-based tests are conceptually direct. In computational settings, one computes the spectrum (or bounds on it) and verifies that the smallest eigenvalue is nonnegative, often with a tolerance to account for floating-point error.

3.4 Numerical considerations and stability

Numerical computations rarely yield exact zero or exact nonnegativity due to rounding. Robust algorithms treat “near-zero” eigenvalues carefully and choose tolerances based on matrix norms and conditioning. Methods based on Cholesky failures or on iterative eigenvalue bounds can be used to reduce sensitivity.

3.5 Semidefinite checks for structured matrices

Structured matrices—such as Toeplitz, banded, or kernel matrices—allow specialized checks that are more efficient than generic spectral decompositions. For instance, exploiting symmetry and sparsity can accelerate factorizations, while regular sampling approaches can test PSD properties in learning contexts with scalable approximations.

4 Operations and Closure Properties

4.1 Scaling by nonnegative scalars

If \(A\succeq 0\) and \(\alpha \ge 0\), then \(\alpha A \succeq 0\). This follows immediately from the quadratic form: \(x^\ast(\alpha A)x = \alpha (x^\ast A x)\), which cannot become negative when \(\alpha\) is nonnegative.

4.2 Sum of PSD matrices

The sum of PSD matrices remains PSD. If \(A\succeq 0\) and \(B\succeq 0\), then for every \(x\), \(x^\ast(A+B)x = x^\ast A x + x^\ast B x \ge 0\). This closure property under addition makes PSD matrices natural building blocks in models that aggregate effects.

4.3 Congruence transformations with arbitrary matrices

For any matrix \(M\), the transformation \(M^\ast A M\) preserves PSD. The quadratic form becomes \((Mx)^\ast A (Mx)\), which is nonnegative because \(A\) is PSD. This invariance is central in deriving PSD constraints under change of variables and linear re-parameterizations.

4.4 Hadamard (elementwise) product and Schur’s theorem

Schur’s theorem states that the Hadamard product of two PSD matrices is PSD, provided both matrices are PSD and Hermitian. This is a powerful closure result for elementwise operations and underlies many kernel construction techniques where PSD structure must be maintained after pointwise modifications.

4.5 Limits, closures, and continuity properties

The PSD cone is closed: if \(A_k\succeq 0\) and \(A_k \to A\), then \(A\succeq 0\). This topological stability supports convergence arguments in optimization and numerical analysis. Continuity also applies to matrix functions such as the square root on PSD matrices, though eigenvalue multiplicities can influence differentiability.

5 Geometry and Interpretation

5.1 PSD cone and its structure

The set of \(n\times n\) PSD matrices forms a convex cone, often called the PSD cone. Convexity means that mixtures of PSD matrices remain PSD, while conic structure means scaling by nonnegative factors preserves membership. This geometry supports efficient optimization algorithms.

5.2 Null space, range, and geometric meaning

If \(A\succeq 0\), then the null space \(\ker(A)\) consists of vectors \(x\) for which the quadratic form vanishes: \(x^\ast A x = 0\). Geometrically, directions in the null space have zero “energy,” while directions orthogonal to the null space contribute positively. The range of \(A\) aligns with the span of eigenvectors having nonzero eigenvalues.

5.3 Rank, degeneracy, and induced subspaces

PSD matrices may be full rank (positive definite) or rank-deficient (semidefinite). The rank determines the dimension of the subspace where quadratic forms are strictly positive. In applications, rank deficiency often signals redundancy, constraints, or limited identifiability.

5.4 Least-squares and projection viewpoints

PSD structure appears in least-squares problems through normal equations. When a matrix is represented as \(A=B^\ast B\), solving least squares corresponds to minimizing residual norms, and the PSD matrix describes how errors are weighted in the objective. Projections onto column spaces also connect: directions outside the span do not contribute to the fitted component.

5.5 Correlation matrices as a normalized PSD subclass

Correlation matrices are PSD matrices with unit diagonal entries. This normalization ensures that the entries can be interpreted as correlations between standardized variables, while PSD guarantees consistency with an underlying covariance structure. The PSD condition enforces feasible dependence patterns.

6 Applications and Contexts

6.1 Covariance matrices in statistics

In statistics, covariance matrices are PSD because variances are nonnegative and covariances arise from inner products of centered random variables. The PSD condition ensures that any linear combination of variables has nonnegative variance, matching the quadratic-form interpretation.

6.2 Kernel matrices in machine learning

Kernel methods use similarity functions that induce PSD Gram matrices \(K\), where \(K_{ij}=k(x_i,x_j)\). The PSD requirement guarantees that the method corresponds to an inner product in a feature space, enabling algorithms such as support vector machines and Gaussian process regression to operate with well-defined geometry.

6.3 Least-squares and regularization (Ridge/Tikhonov) connections

Regularization frequently adds a PSD term to a system matrix. For example, ridge regression introduces \(\lambda I\), which is positive semidefinite (and often positive definite if \(\lambda>0\)), stabilizing inversion or improving conditioning. More generally, PSD penalties correspond to enforcing smoothness or energy constraints in parameter estimation.

6.4 Energy functions and stability in linear systems

In dynamical systems and control, quadratic energy functions are commonly written as \(V(x)=x^\ast A x\) with \(A\succeq 0\). Nonnegativity is interpreted as an “energy cannot be negative” principle, supporting Lyapunov-like stability analyses. Semidefinite cases correspond to systems where energy may remain constant along certain directions.

6.5 Entrywise constraints and graph-based models

Graph-related models can impose PSD constraints on matrices encoding node similarities or flows. When graph Laplacians or related operators are used, PSD properties ensure nonnegative quadratic forms tied to costs along edges or cuts. Entrywise constraints also appear via kernel composition rules, where Schur-product closure preserves PSD structure.

7 Positive Semidefinite Ordering and Related Concepts

7.1 Loewner (semidefinite) partial order

The Loewner order compares Hermitian matrices by their difference: \(A\succeq B\) means \(A-B\succeq 0\). This relation is a partial order because not all matrices are comparable. It encodes dominance of quadratic forms: \(x^\ast A x \ge x^\ast B x\) for every \(x\).

7.2 Dominance relations and monotonicity

Under Loewner ordering, many quantities behave monotonically for operator-convex or operator-monotone functions. While not every function preserves monotonicity, the order provides a framework for statements such as “larger” PSD matrices yield larger quadratic forms and influence eigenvalue bounds.

7.3 Strictly positive definite vs. semidefinite

A matrix is positive definite if \(x^\ast A x > 0\) for all nonzero \(x\), equivalently all eigenvalues are strictly positive. PSD relaxes this by allowing zero eigenvalues. The distinction matters for inversion: positive definite matrices are invertible, while semidefinite matrices may require pseudoinverses.

7.4 Indefinite matrices and sign patterns

Indefinite Hermitian matrices have both positive and negative eigenvalues, so the quadratic form changes sign depending on direction. The PSD/NSD (negative semidefinite) cases are extremes of this spectrum, while indefinite matrices lie outside these cones and typically complicate optimization due to lack of convexity.

7.5 Interlacing and bounds for eigenvalues

Eigenvalue interlacing describes how eigenvalues of principal submatrices relate to those of the full matrix. For PSD matrices, this yields bounds on how many directions have nonzero curvature when restricting to subsets of variables. Such results are used in algorithm analysis and in matrix completion methods.

8 PSD Matrices in Semidefinite Programming (SDP)

8.1 Primal and dual problem overview (conceptual)

Semidefinite programming optimizes a linear objective over an affine set intersected with the PSD cone. A typical primal form chooses a variable matrix constrained to be PSD while satisfying linear equalities. The dual problem introduces Lagrange multipliers and often produces certificate-like conditions interpreted through PSD matrices and orthogonality.

8.2 Feasible set as the PSD cone

The feasible region is defined by PSD constraints of the type \(X\succeq 0\), sometimes alongside additional linear constraints such as \(A_i\cdot X = b_i\). Because the PSD cone is convex, the overall problem is convex, enabling reliable polynomial-time algorithms under standard assumptions.

8.3 Complementary slackness intuition

In SDP duality, complementary slackness links primal and dual slackness. Intuitively, when the primal constraint \(X\succeq 0\) is tight in certain directions, the dual variables reflect that tightness, often via a product or trace condition that forces alignment of null spaces or supports. This provides insight into optimal structure.

8.4 Common constraints and variable encodings

Many problems encode quantities as linear functions of entries of a matrix variable. For instance, quadratic expressions in vectors can be represented using \(X = zz^\ast\) or its relaxation, turning nonconvex terms into convex PSD constraints. This “lifting” technique is a key reason PSD matrices appear in many practical formulations.

8.5 Illustrative toy formulations

A basic SDP might minimize a linear function of a PSD matrix subject to matching a prescribed diagonal or fitting a moment constraint. Another common toy example is finding the “closest” PSD matrix to a given symmetric matrix under a norm, constrained by linear equalities such as fixed trace. These illustrate how PSD constraints enforce nonnegativity while other conditions tailor the solution.

9 Common Misconceptions and Edge Cases

9.1 Why symmetry/Hermiticity matters

A matrix that is not symmetric/Hermitian cannot reliably be treated as PSD under the standard definition because the quadratic form may not correspond to a consistent real nonnegativity property. Ensuring Hermiticity typically involves replacing \(A\) with \((A+A^\ast)/2\) when symmetry is intended, since only the Hermitian part contributes to \(x^\ast A x\) as a real expression.

9.2 PSD vs. elementwise nonnegative matrices

Elementwise nonnegative entries do not imply PSD. A matrix can have all entries \(\ge 0\) yet still have negative eigenvalues. Conversely, PSD matrices can contain negative entries, as long as the overall quadratic form remains nonnegative for every vector.

9.3 Handling singular PSD matrices

Singular PSD matrices are common and not pathological. However, operations involving inversion must be modified: one uses pseudoinverses or restricts attention to the range of the matrix. In optimization, singularity often corresponds to flat directions where the objective or constraints do not enforce curvature.

9.4 Misuse of determinant tests

Determinant-based tests can be misleading. While a positive determinant implies invertibility, it does not guarantee PSD in higher dimensions, and a zero determinant does not rule out PSD. Checking the entire spectrum or using a correct minor/principal criterion is more reliable than relying on a single determinant value.

9.5 Numerical artifacts in computed eigenvalues

Software routines compute eigenvalues approximately, and small negative values may appear due to rounding even when a matrix is theoretically PSD. Interpreting results requires tolerances and awareness of conditioning. A typical practice is to treat eigenvalues above \(-\varepsilon\) as nonnegative when \(\varepsilon\) accounts for numerical error.