Efficient Sylvester Criterion for Positive Semidefinite Matrices
Sylvester's classic criterion certifies a symmetric matrix as positive semidefinite only by checking the nonnegativity of all its principal minors, of which there are exponentially many. This stronger criterion reduces the test to m(m+1)/2 determinants by using consecutive principal submatrices and 'inner-saturated' submatrices formed from a maximal linearly independent set of the inner columns. It also yields elementwise conditions for positive definiteness and semidefiniteness, with applications to matrix completion and semidefinite programming.
A stronger Sylvester’s criterion for positive semidefinite matrices Mingrui Zhang and Peng Ding ∗
Sylvester's criterion tests positive definiteness (PD) and positive semidefiniteness (PSD) of a symmetric matrix through determinants of submatrices, avoiding eigendecomposition: a matrix is PD iff i…