Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  1. How does one check whether symmetric $4\times4$ matrix is positive semi-definite?

  2. What if this matrix has also rank deficiency: is it rank 3?

share|improve this question
3  
You can use the determinant criterion: the upper-left $1\times 1$, $2\times 2$, $3\times 3$ and $4 \times 4$ squares should all have non-negative determinant. –  Yuval Filmus May 23 '11 at 16:00
1  
But that determinant criterion isn't enough in general, as $\begin{bmatrix}0&0&0&0\\0&-1&0&0\\0&0&-1&0\\0&0&0&-1\end{bmatrix}$ shows. –  Jonas Meyer May 23 '11 at 16:07
2  
@Yuval - I believe the determinant criterion holds for positive definite matrices but not necessarily for positive semidefinite ones. In other words, if some of the principal minors are zero, it does not necessarily imply the matrix is positive semidefinite. –  svenkatr May 23 '11 at 16:16
3  
In that case, you can add $\epsilon > 0$ (to the diagonal) and then rerun all your computations (just when the matrix doesn't have full rank). A suitable $\epsilon$ can be found by looking at the magnitude of the entries (we want to guarantee that we don't miss any small negative eigenvalue). –  Yuval Filmus May 23 '11 at 16:48
add comment

7 Answers

Since the matrix is symmetric, the eigenvalues will be real. Calculate the eigenvalues and see if they are all $\geq 0$. If this is true,the matrix is positive semidefinite.

share|improve this answer
1  
You don't even need the eigenvalues. Once you have the polynomial invariants (coefficients of the characteristic polynomial), you can use Descarte's rule of signs. –  Willie Wong Aug 24 '11 at 16:22
1  
Even computing the characteristic polynomial here is overkill. Robert's suggestion takes less effort... –  J. M. Aug 25 '11 at 4:21
add comment

Another method is to check there are no negative pivots in row reduction (after taking into account the possibility of 0's on the diagonal). The procedure can be written recursively as follows:

1) If $A$ is $1 \times 1$, then it is positive semidefinite iff $A_{11} \ge 0$.

Otherwise:

2) If $A_{11} < 0$, then $A$ is not positive semidefinite.

3) If $A_{11} = 0$, then $A$ is positive semidefinite iff the first row of $A$ is all 0 and the submatrix obtained by deleting the first row and column is positive semidefinite.

4) If $A_{11} > 0$, for each $j > 1$ subtract $A_{j1}/A_{11}$ times row 1 from row $j$, and then delete the first row and column. Then $A$ is positive semidefinite iff the resulting matrix is positive semidefinite.

share|improve this answer
add comment

As stated above, Sylvester's criterion doesn't work in this case, so you can't simply check the four leading principal minors. However, it does suffice to check that all 15 of the principal minors are nonnegative. See here for a reference.

Another basic approach involves symmetric row reduction. This involves operations of the following type:

  1. Perform a row operation, and then
  2. Immediately perform the corresponding column operation.

For example, you can multiply any row by a constant, as long as you immediately multiply the corresponding column by a constant. Note that this multiplies the diagonal entry by the square of the constant.

Using these operations, you can use a variant of Gaussian elimination to reduce any symmetric matrix to a diagonal matrix with 1's, 0's, and -1's along the diagonal. A matrix is positive semidefinite if and only if the resulting diagonal entries are all 0's and 1's.

share|improve this answer
add comment

Let's say your matrix is $A$.

You can check the eigenvalues. If all eigenvalues $\geq 0$, the matrix is positive semi-definite (if all eigenvalues $>0$ it is positive definite).

It might be possible to use the Gershgorin circle theorem instead of calculating the eigenvalues explicitly. If all the diagonal elements are positive and are larger than or equal to the sum of the absolute values of the other elements in same row (or column) (for every diagonal element), then the matrix is positive semi-definite.

You can try to find a simpler semi-definite matrix $B$ such that $B^2 = A$ ($B$ is unique). This is in general done using the diagonalization of the matrix, so it will probably be easier just calculating the eigenvalues.

You can not use a modification of Sylvester's criterion ("all leading principal minors are non-negative") to determine positive semidefiniteness.

If $A$ is $4 \times 4$ and rank 3, it has 0 as an eigenvalue (since there exists a vector $v$ such that $Av = 0v$). This does not affect the positive semi-definiteness of the matrix, but it will not be positive definite.

share|improve this answer
add comment

One quick first check, if any element $A_{ii}$ on the diagonal is negative, the matrix has a negative eigenvalue (for real symmetric matrices only of course)

share|improve this answer
add comment

Perform the Cholesky decomposition on the matrix, say $\mathbf{A}=\mathbf{L}\mathbf{L}^{\textrm{T}}$, if equation $\mathbf{v}\mathbf{L}=0$ has a unique solution, then $\mathbf{A}$ is positive semi-definite.

share|improve this answer
add comment

Here is a test that you can perform relatively easily by hand. Since positive semidefinite matrices must have nonnegative diagonal entries, suppose $M$ is a real symmetric matrix that has a nonnegative diagonal.

  1. If $M$ has at most one positive diagonal entry, then $M\succeq0$ if and only if $M$ is a diagonal matrix.
  2. If $M$ has two (or more) positive diagonal entries, permute the rows and columns of $M$ so that its first two diagonal entries are positive. Partition $M$ as $\pmatrix{A&B^\top\\ B&C}$, where $A,B,C$ are $2\times2$ submatrices. Then $M\succeq0$ if and only if $A\succeq0$ and $C-BA^{-1}B^\top\succeq0$ (see Schur complement). I suppose you know how to check whether a $2\times2$ matrix is positive semidefinite or not.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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