# How to check if a symmetric $4\times4$ matrix is positive semi-definite?

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?

-
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
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
@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
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

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.

-
Robert, could you please provide a working example lets say for $A= \left( \begin{array}{ccc} 1 & 1 & 0 \\ 1& 1 & -1 \\ 0 & -1 & 1 \end{array} \right)$. – Rahul Sep 24 at 21:03

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.

-
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
Even computing the characteristic polynomial here is overkill. Robert's suggestion takes less effort... – J. M. Aug 25 '11 at 4:21

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.

-

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.

-

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)

-

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.

-

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.
-

You can use a modified version of Sylvestor's Criterion which requires all the principal minors to be non-negative (instead of the leading principal minors as in the criterion to check positive definiteness). You can check the Wikipedia article on Sylvester's Criterion for reference. I am quoting the statement here.

"An analogous theorem holds for characterizing positive-semidefinite Hermitian matrices, except that it is no longer sufficient to consider only the leading principal minors: a Hermitian matrix M is positive-semidefinite if and only if all principal minors of M are nonnegative."

-