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.

Suppose that I have a symmetric square $n\times n$ matrix $A$ such that:

$a_{ii}\geq 0$ for all $1\leq i\leq n$, and that $a_{ii}a_{jj} - a_{ij}^2 \geq 0$ for all $1\leq i\leq n$ and $i < j \leq n$.

Clearly this is a necessary condition for positive semidefiniteness because of Sylvester's criterion, and the fact that $P^TAP$ is positive semidefinite for any positive semidefinite $A$ and permutation matrix $P$.

This question hints that this condition is not sufficient. Can you list any simple counterexamples to the claim that this condition is sufficient for $A$ to be positive semidefinite? Thanks.

P.S. I won't be offended if you flag this as a duplicate, but it's the counterexamples I'm interested in, so please consider that before you flag.

share|improve this question
    
So for example (referencing the previous question) you'd be interested in an example that satisfies the above condition but doesn't have a Cholesky decomposition ? –  Suresh Venkat Nov 11 '12 at 21:43
    
@SureshVenkat That would be a good example, yes. –  John Moeller Nov 11 '12 at 21:45
1  
John, I put a third answer generalizing things. I had to do it. The voices made me. –  Will Jagy Nov 12 '12 at 1:20

3 Answers 3

up vote 2 down vote accepted

Sorry for being slow. There is a good reason this did not occur to me first, but still an error of sorts. Take

$$ \left( \begin{array}{rrr} 1 & -1 & -1 \\ -1 & 1 & -1 \\ -1 & -1 & 1 \end{array} \right) $$

Your conditions are fulfilled but it is evident that $-1$ is an eigenvalue with eigenvector $$ \left( \begin{array}{r} 1 \\ 1 \\ 1 \end{array} \right) $$

To get strict inequalities use some $0 < \delta < 1$ and the matrix

$$ \left( \begin{array}{ccc} 1 + \delta & -1 & -1 \\ -1 & 1 + \delta & -1 \\ -1 & -1 & 1 + \delta \end{array} \right) $$ which keeps that eigenvector but now the eigenvalue is $\delta -1.$

share|improve this answer
1  
This is great. I changed this one to be the accepted answer. –  John Moeller Nov 11 '12 at 23:06

$$ \left( \begin{array}{rrr} 1 & -2 & -3 \\ -2 & 4 & -6 \\ -3 & -6 & 9 \end{array} \right) $$

determinant is $-144.$

If you want strict inequalities, $$ \left( \begin{array}{rrr} 1001 & -2000 & -3000 \\ -2000 & 4001 & -6000 \\ -3000 & -6000 & 9001 \end{array} \right) $$

This determinant is $-143999985999.$

share|improve this answer
    
This is a great example because all of the 2x2 submatrices are p.s.d., but the matrix isn't (edit: actually I just realized that that's exactly what I asked for). May I ask how you thought of this example? –  John Moeller Nov 11 '12 at 22:13
1  
@JohnMoeller, I mostly do integral quadratic forms in three variables. So I just programmed my calculator to do the determinant. Putting squares on the diagonal allowed your conditions, but when I had positive elements off-diagonal the determinant was $0.$ Then I realized that if I negated all off-diagonal entries, I would be subtracting off a strictly positive quantity and that would do it. –  Will Jagy Nov 11 '12 at 22:23

I won't need to show a matrix this time. For a square $n$ by $n$ matrix with $n \geq 3,$ let $M$ be the symmetric matrix with all off-diagonal entries equal to $-1$ and all diagonal entries equal to $n-2.$ It is not difficult to show, using the eigenvalues, that all the principal minors up to size $n-1$ are nonnegative, so those submatrices are positive semidefinite. However, once again we get an eigenvalue of $-1$ with the eigenvector made up of all $1$'s. To get the submatrices positive definite, make the diagonal entries $n-2+ \delta$ with $0 < \delta < 1.$

Lost my nerve: $$ \left( \begin{array}{rrrr} 2 & -1 & -1 & -1 \\ -1 & 2 & -1 & -1 \\ -1 & -1 & 2 & -1 \\ -1 & -1 & -1 & 2 \end{array} \right) $$ and $$ \left( \begin{array}{rrrrr} 3 & -1 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 & -1 \\ -1 & -1 & 3 & -1 & -1 \\ -1 & -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & -1 & 3 \end{array} \right) $$

Anyway, a $k$ by $k$ matrix consisting of all $1$'s has eigenvalues $0,0,0,\ldots, 0,k.$ If all the entries are $-1$ instead the eigenvalues are $0,0,0,\ldots, 0,-k.$ In order to put some number $w$ on the diagonal we need to add $(1 + w)I,$ where $I$ is the identity matrix. So the eigenvalues of the $k$ by $k$ matrix with all off-diagonal entries $-1$ and all diagonal entries $w$ are $1+w, \; 1+w, \; 1+w,\ldots, \; 1+w, \; 1 + w-k.$ This is how you quickly confirm the example above.

share|improve this answer

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.