How does one check whether symmetric $4\times4$ matrix is positive semidefinite?
What if this matrix has also rank deficiency: is it rank $3$?
$\begingroup$
$\endgroup$
5
asked May 23, 2011 at 15:57
-
4$\begingroup$ 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. $\endgroup$– Yuval FilmusCommented May 23, 2011 at 16:00
-
5$\begingroup$ 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. $\endgroup$– Jonas MeyerCommented May 23, 2011 at 16:07
-
2$\begingroup$ @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. $\endgroup$– svenkatrCommented May 23, 2011 at 16:16
-
4$\begingroup$ 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). $\endgroup$– Yuval FilmusCommented May 23, 2011 at 16:48
-
$\begingroup$ The matrix is positive semidefinite (and not strictly) iff the main determinant is zero, no? $\endgroup$– leonbloyCommented Feb 3, 2016 at 19:59
Add a comment
|
8 Answers
$\begingroup$
$\endgroup$
4
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.
answered May 23, 2011 at 19:03
-
3$\begingroup$ 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) $. $\endgroup$– RahulCommented Sep 24, 2015 at 21:03
-
1$\begingroup$ Rather than making substantive changes in someone else's answer, please write a comment or your own answer. Note that the matrix is supposed to be symmetric, and alick's example wasn't. I'm going to revert to the original. $\endgroup$ Commented Feb 3, 2016 at 22:23
-
-
$\begingroup$ @djechlin Yes. For symmetric matrices the signs of the pivots correspond with the signs of the eigenvalues. Otherwise we only know that their products are equal, and in fact equal to the determinant. $\endgroup$– marnixCommented May 22, 2020 at 20:08
$\begingroup$
$\endgroup$
3
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.
-
3$\begingroup$ 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. $\endgroup$ Commented Aug 24, 2011 at 16:22
-
3$\begingroup$ Even computing the characteristic polynomial here is overkill. Robert's suggestion takes less effort... $\endgroup$ Commented Aug 25, 2011 at 4:21
-
$\begingroup$ For those using programming languages, this method is the simplest. $\endgroup$– SARoseCommented Nov 28, 2017 at 3:10
$\begingroup$
$\endgroup$
2
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:
- Perform a row operation, and then
- 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.
answered May 23, 2011 at 19:09
-
1$\begingroup$ Hmm very nice comment! So in the case of $n\times n$ matrix i have to check that $2^n-1$ principal minors are non-negative right? Where can I find the proof of this result? $\endgroup$– RFZCommented Mar 4, 2020 at 21:30
-
1$\begingroup$ Could you give me the name of the book which contains the proof of this fact? $\endgroup$– RFZCommented Mar 4, 2020 at 23:47
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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)
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
- If $M$ has at most one positive diagonal entry, then $M\succeq0$ if and only if $M$ is a diagonal matrix.
- 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.
$\begingroup$
$\endgroup$
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."
