A stronger Sylvester's criterion for positive semidefinite matrices

Basic Information

• Paper ID: 2501.00894
• Title: A stronger Sylvester's criterion for positive semidefinite matrices
• Authors: Mingrui Zhang (UC Berkeley), Peng Ding (UC Berkeley)
• Classification: math.RA (Ring and Algebra), math.ST (Statistics Theory), stat.TH (Statistics Theory)
• Publication Date: January 1, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2501.00894

Abstract

Sylvester's criterion is a classical method for determining positive definite (PD) and positive semidefinite (PSD) matrices without eigenvalue decomposition. The classical criterion requires that a symmetric matrix is positive definite if and only if all leading principal minors are positive; a symmetric matrix is positive semidefinite if and only if all principal minors are non-negative. For an $m \times m$ symmetric matrix, Sylvester's criterion requires computing $m$ and $2^m-1$ determinants to verify positive definiteness and positive semidefiniteness, respectively. Due to the exponential growth in the number of principal submatrices, this criterion has limited practical utility for positive semidefinite matrices. This paper proposes a stronger Sylvester's criterion for positive semidefinite matrices, requiring verification of only $m(m+1)/2$ determinant non-negativity conditions. Based on the new criterion, the authors provide a method for deriving element-wise criteria for positive definite and positive semidefinite matrices, and demonstrate applications in matrix completion and nonlinear semidefinite programming.

Research Background and Motivation

Problem Definition

This research addresses the problem of excessive computational complexity in the classical Sylvester's criterion for determining positive semidefiniteness. Specifically:

1. Computational Complexity Issue: For an $m \times m$ matrix, verifying positive semidefiniteness requires checking $2^m-1$ principal minors, exhibiting exponential growth with matrix dimension
2. Limited Practical Utility: The exponential computational burden renders the classical criterion impractical for determining positive semidefiniteness of high-dimensional matrices
3. Need for Theoretical Refinement: Existing literature contains misapplications and improper extensions of Sylvester's criterion

Research Significance

Positive semidefinite matrices hold important positions in mathematics, statistics, optimization, and related fields:

• Covariance matrices must be positive semidefinite
• Core constraints in semidefinite programming problems
• Key properties in matrix completion problems
• Fundamental tools in statistical inference

Limitations of Existing Methods

1. Classical Sylvester's Criterion: Requires $O(2^m)$ determinant computations for positive semidefinite matrices
2. Eigenvalue Decomposition Method: High computational complexity and lacks intuitive appeal in certain applications
3. Graph-Theoretic Methods: Applicable only to specific structures (e.g., chordal graphs) with limited generality

Core Contributions

1. Proposes a Stronger Positive Semidefinite Sylvester's Criterion: Reduces required determinant computations from $2^m-1$ to $m(m+1)/2$
2. Introduces the Concept of Inner-Saturated Submatrices: Provides theoretical foundation for the new criterion
3. Establishes Element-Wise Determination Methods: Provides systematic approaches for determining element ranges
4. Demonstrates Practical Applications: Validates method effectiveness in matrix completion and nonlinear semidefinite programming
5. Provides Complete Theoretical Proofs: Includes rigorous mathematical proofs and supporting lemmas

Methodology Details

Core Concept Definitions

Consecutive Principal Submatrices

Definition 2: For an $m \times m$ matrix $X$ and integers $a \leq b$, $X_{a:b,a:b}$ is called a consecutive principal submatrix of $X$.

Inner-Saturated Submatrices

Definition 3: For a symmetric $m \times m$ matrix $X$, define $X_{I,I}$ as an inner-saturated submatrix, where $I = \{1,m\} \cup J$, and the index set $J$ satisfies:

• When $m \leq 2$, $J = \emptyset$
• When $m \geq 3$, $\{X_{2:(m-1),j} : j \in J\}$ is a maximal linearly independent set of column vectors of $X_{2:(m-1),2:(m-1)}$

Main Theorem

Theorem 2 (New Sylvester's Criterion): For a symmetric $m \times m$ matrix $X$, the following conditions are equivalent:

1. $X$ is a positive semidefinite matrix
2. For any consecutive principal submatrix of $X$, some inner-saturated submatrix has non-negative determinant
3. For any consecutive principal submatrix of $X$, every inner-saturated submatrix has non-negative determinant

Technical Innovations

1. Complexity Optimization: Reduction from $O(2^m)$ to $O(m^2)$
2. Equivalence Proof: The equivalence of conditions (ii) and (iii) is the key innovation
3. Constructive Method: Provides concrete algorithms for determining matrix element ranges

Element-Wise Determination Method

Partial Order Relation

Define a partial order relation $\preceq$ on upper triangular elements: $X_{i',j'} \preceq X_{i,j}$ if and only if $i \leq i' \leq j' \leq j$.

Determination Procedure

1. Diagonal Elements: Must be non-negative
2. k-Diagonal Elements: Ranges determined sequentially according to partial order relations
3. Recursive Determination: Utilizes determinant constraints from inner-saturated submatrices of consecutive principal submatrices

Experimental Setup

Theoretical Verification

The paper primarily validates theoretical correctness through mathematical proofs, including:

• Proofs of three key lemmas
• Inductive proof of the main theorem
• Constructive proofs of Propositions 1 and 2

Application Examples

Matrix Completion Problem

Example 3: Consider a partially observed $5 \times 5$ symmetric matrix containing three missing elements $x_1, x_2, x_3$. The new criterion determines the feasible region of missing elements and verifies whether a positive definite completion exists.

Nonlinear Semidefinite Programming

Example 4: Optimization problem $\max X_{11}^2 + X_{22}^2 + X_{33}^2 + X_{44}^2 - X_{12}X_{23}X_{34} - X_{13}X_{24} + X_{14}$ Subject to: $X$ is positive semidefinite, $0 \leq X_{ii} \leq 1$

Experimental Results

Complexity Comparison

• Classical Method: $2^m-1$ determinant computations
• New Method: $m(m+1)/2$ determinant computations
• Improvement: Reduction from exponential to polynomial complexity

Application Effectiveness

1. Matrix Completion: Successfully determines completion feasibility for non-chordal graph cases
2. Semidefinite Programming: Provides reparameterization methods for element-wise constraints
3. Computational Efficiency: Significantly reduces required determinant computations

Related Work

Classical Theory

• Sylvester's Criterion: Criterion for determining positive definite matrices proposed by James Joseph Sylvester (1814-1897)
• Positive Semidefinite Extension: Prussing (1986) first provided the correct Sylvester's criterion for positive semidefinite matrices

Matrix Completion

• Grone et al. (1984): Theory of positive definite/semidefinite matrix completion on chordal graphs
• Barrett et al. (1989): Determinant formulas for matrix completion related to chordal graphs
• Johnson (1990): Survey on matrix completion problems

Semidefinite Programming

• Yamashita and Yabe (2015): Survey of numerical methods for nonlinear semidefinite programming

Conclusions and Discussion

Main Conclusions

1. Theoretical Breakthrough: Reduces complexity of positive semidefinite matrix determination from exponential to polynomial level
2. Practical Value: Provides feasible tools for determining positive semidefiniteness of high-dimensional matrices
3. Broad Applicability: Demonstrates practical utility in matrix completion and semidefinite programming

Limitations

1. Special Case Handling: Additional boundary case analysis required when certain submatrices are singular
2. Computational Implementation: Although theoretical complexity is reduced, numerical stability must be considered in practical implementation
3. High-Dimensional Extension: For extremely high-dimensional matrices, $O(m^2)$ complexity may still become a bottleneck

Future Directions

1. Numerical Algorithms: Develop efficient and stable numerical implementation algorithms
2. Parallel Computing: Leverage parallel computation for further efficiency improvements
3. Application Extension: Explore applications in machine learning, signal processing, and related fields

In-Depth Evaluation

Strengths

1. Strong Theoretical Innovation: Fundamentally improves efficiency of classical Sylvester's criterion
2. High Mathematical Rigor: Provides complete theoretical proof system
3. Significant Practical Value: Solves practical problems in determining positive semidefiniteness of high-dimensional matrices
4. Rich Application Examples: Demonstrates method operability through concrete examples

Weaknesses

1. Insufficient Implementation Details: Lacks concrete numerical implementation algorithms and complexity analysis
2. Missing Large-Scale Validation: Lacks large-scale numerical experiments validating theoretical advantages
3. Complex Boundary Cases: Special case handling increases implementation complexity

Impact

1. Significant Theoretical Contribution: Provides important theoretical tools for matrix theory
2. Broad Application Prospects: Holds application potential in optimization, statistics, machine learning, and related fields
3. Good Reproducibility: Theoretical results are fully reproducible, providing foundation for subsequent research

Applicable Scenarios

1. High-Dimensional Covariance Matrix Analysis: Verification of covariance matrix positive semidefiniteness in statistics
2. Semidefinite Programming Solution: Provides new constraint handling methods for semidefinite programming
3. Matrix Completion Problems: Particularly suitable for matrix completion with non-chordal graph structures
4. Machine Learning: Verification of positive semidefiniteness for kernel matrices and similarity matrices

References

The paper cites 18 related references covering classical and frontier work in matrix theory, semidefinite programming, matrix completion, and related fields, providing solid theoretical foundation for the research.

Overall Evaluation: This is a high-quality theoretical mathematics paper achieving important breakthroughs based on the classical Sylvester's criterion. Although lacking large-scale numerical experiments, its theoretical contributions and practical value make it an important advance in matrix theory.