Is there a criterion for positive semidefiniteness of a matrix in terms of dimension reduction, i.e, such that positive semi-definiteness of $n \times n$ matrix is expressed as positive semidefiniteness of smaller matrices and possibly some additional condition?

Could anyone give me hint? Thanks for replies.

UPD: besides the version of Sylvester's criterion for semi-definite case.


An alternative approach to modified Sylvester's criterion has been given under a related question. It is a recursive approach based on row reduction (or Gaussian elimination).

(Restated below for completeness.)

  1. A $1\times1$ matrix is positive semi-definite iff its entry is non-negative.

For a $n\times n$ Hermitian (symmetric) matrix $A$:

  1. If $A_{11}<0$, $A$ is not positive semi-definite;
  2. If $A_{11}=0$, $A$ is positive semi-definite iff the first row entries are all zeros, and the submatrix after removing the first row and column is positive semi-definite;
  3. If $A_{11}>0$, $A$ is positive semi-definite iff after row reduction (or Gaussian elimination, which makes the entries in the first column are all zeros except the entry in the first row), the submatrix after removing the first row and column is positive semi-definite.
  • $\begingroup$ Does this answer require symmetry? Robert's Comment seems to imply that, but I'm not sure. $\endgroup$ – lucidbrot Jul 25 '18 at 6:35
  • 1
    $\begingroup$ @lucidbrot Yes (usually) for real valued matrices. Positive (semi-)definiteness requires symmetry in most definitions, although sometimes a non-symmetric matrix is called positive (semi-)definite if its symmetric part is positive (semi-)definite. Ref: link.springer.com/content/pdf/bbm%3A978-0-306-47819-2%2F1.pdf $\endgroup$ – alick Jan 23 at 2:23

It seems Sylvester's criterion gives the answer: if $S$ is an $n\times n$-matrix, say $S=(s_{i,j})_{1\leqslant i,j\leqslant n}$, then $S$ is positive semi-definite if and only if both conditions

  1. the sub-matrices $S_k=(s_{i,j})_{1\leqslant i,j\leqslant k}$ are positive semi-definite;
  2. $\det S$ is non-negative;

are satisfied.

  • $\begingroup$ I guess, I should have added: "besides Sylvester's criterion", I mean. First,doesn't it only work for positive definiteness? And second, it looks like an over-kill, because, it seems, you don't need to require semi-definiteness of sub matrices, only positiveness of their determinate, am I right? $\endgroup$ – Alex Sep 30 '13 at 20:40
  • $\begingroup$ @Alex Wikipedia: "It turns out that a matrix is positive definite if and only if all these determinants are positive." So it seems like it is not overkill. This is for positive definiteness, but I would assume that semidefiniteness can be done the same way, just with a greater-equals instead of a strictly-greater $\endgroup$ – lucidbrot Jul 25 '18 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.