Timeline for Showing a matrix is negative definite [formerly Showing a sum is always positive]
Current License: CC BY-SA 2.5
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 6, 2010 at 17:03 | comment | added | J. M. isn't a mathematician | For the purpose of merely proving that a symmetric matrix is positive/negative definite, eigendecomposition is a bit too much effort to do. The best way is to appeal to Sylvester's inertia theorem, and compute the $LDL^T$ (modified Cholesky) decomposition ($L$ unit lower triangular; $D$ diagonal), and then check the signs of the entries of $D$. If they are all negative, the original matrix is negative definite, and similarly for proving positive-definiteness. | |
| Mar 29, 2010 at 14:40 | history | edited | bandini | CC BY-SA 2.5 |
deleted 107 characters in body; edited title
|
| Mar 29, 2010 at 7:07 | answer | added | Martin Rubey | timeline score: 1 | |
| Mar 29, 2010 at 2:03 | vote | accept | bandini | ||
| Mar 29, 2010 at 0:49 | answer | added | fedja | timeline score: 18 | |
| Mar 28, 2010 at 20:46 | answer | added | Bjorn Poonen | timeline score: 8 | |
| Mar 28, 2010 at 18:55 | comment | added | bandini | I want a result for all d so computing eigenvalues is tricky. I tried computing a couple of eigenvalues and eigenvectors with maple but the expressions obtained were too messy to suggest a nice expression for eigenvalues/eigenvectors. | |
| Mar 28, 2010 at 18:53 | history | edited | bandini | CC BY-SA 2.5 |
added 1469 characters in body
|
| Mar 28, 2010 at 17:50 | comment | added | Qiaochu Yuan | If I wanted to show that a matrix with entries I understood was negative-definite I would try to write down its eigenvectors explicitly. Have you tried something like that? | |
| Mar 28, 2010 at 17:18 | comment | added | Theo Johnson-Freyd | @Bandini: You should include that motivation as a section of the original post. | |
| Mar 28, 2010 at 17:10 | comment | added | David E Speyer | A third idea would be to show that some parts of the sum are much larger than others. In this case, I would expect the main contribution to be from $i$ and $j$ near $\min(k, d/2)$. The terms in this neighborhood are positive; maybe you can show they are dominant? | |
| Mar 28, 2010 at 16:20 | comment | added | bandini | Induction on k is no good, as $f(d,k)-f(d,k-1)$ is negative for values of $k$ close to $d$. | |
| Mar 28, 2010 at 16:16 | comment | added | bandini | The problem comes from wanted to show that a particular matrix is negative definite by showing that the determinant of each upper left square submatrix has sign $(-1)^k$. The expression for this is $$(-1)^k\left(\sum_{j=0}^{k}\binom{d}{j}^2 - \frac{2}{d\binom{2d}{d}}\sum_{0 \leq i,j \leq k}(j-i)^2\binom{d}{i}^2\binom{d}{j}^2\right)\,.$$ Using the identity $$\frac{d}{2}\binom{2d}{d} = \sum_{j=0}^{k}i\binom{d}{i}^2$$ we can re-write the two sums as $$\frac{d}{2}\binom{2d}{d}\left( \sum_{j=k+1}^{d}\binom{d}{j}^2 + \sum_{0 \leq i,j \leq k}(i-(j-i)^2)\binom{d}{i}^2\binom{d}{j}^2\right)$$ | |
| Mar 28, 2010 at 16:08 | comment | added | Gerhard Paseman | What happens when you try induction on k? Gerhard "Ask Me About System Design" Paseman, 2010.03.28 | |
| Mar 28, 2010 at 15:54 | comment | added | Qiaochu Yuan | There are two general techniques I'm aware of: 1) giving a combinatorial interpretation, and 2) writing the sum as a sum of squares. Could you give a little more background on the question? | |
| Mar 28, 2010 at 15:47 | history | edited | Reid Barton | CC BY-SA 2.5 |
added 4 characters in body; added 2 characters in body; added 4 characters in body
|
| Mar 28, 2010 at 15:46 | history | asked | bandini | CC BY-SA 2.5 |