# Showing a matrix is negative definite [formerly Showing a sum is always positive]

For each $d$, I have a matrix $M$ with values $$M_{ij} = \begin{cases} \frac{4ij}{d} - \binom{2d}{d} & i \neq j & \\\\ \frac{4i^2}{d} - \binom{2d}{d} - \frac{\binom{2d}{d}}{\binom{d}{i}^{2}} & i = j \end{cases}$$

I want to show that, for every $d=2,3,\ldots$, the matrix is negative-definite.

An elegant answer has been provided by fedja, without needing to look at the determinants

My approach is to compute the determinant of the upper left-square matrix of size $k$, for each $k=1,2,\ldots,d$. The value for this is $$D_k = (-1)^k\left[\frac{\binom{2d}{d}^k}{\prod_{i=1}^{k}\binom{d}{i}^2}\right] \left[\sum_{j=1}^{k}\left(\binom{d}{j}^2 - \frac{4j^2\binom{d}{j}^2}{d\binom{2d}{d}}\right) - \frac{4}{d\binom{2d}{d}} \sum_{1 \leq i < j \leq k}(j-i)^2\binom{d}{i}^2\binom{d}{j}^2\right]$$ Hence, $D_k$ has sign $(-1)^k$ if this expression is positive $$\sum_{j=1}^{k}\left(\binom{d}{j}^2 - \frac{4j^2\binom{d}{j}^2}{d\binom{2d}{d}}\right) - \frac{4}{d\binom{2d}{d}} \sum_{1 \leq i < j \leq k}(j-i)^2\binom{d}{i}^2\binom{d}{j}^2$$

I can re-write this as $$\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\,,$$ and, then, after observing that $\sum_{i=0}^{d}i\binom{d}{i}^2 = \frac{d}{2}\binom{2d}{d}$, I can deduce that this will certainly be positive when the following sum is positive $$\sum_{0 \leq i, j \leq k}(i-(j-i)^2){\binom{d}{i}}^2{\binom{d}{j}}^2$$

-
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? –  Qiaochu Yuan Mar 28 '10 at 15:54
What happens when you try induction on k? Gerhard "Ask Me About System Design" Paseman, 2010.03.28 –  Gerhard Paseman Mar 28 '10 at 16:08
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)$$ –  bandini Mar 28 '10 at 16:16
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? –  David Speyer Mar 28 '10 at 17:10
@Bandini: You should include that motivation as a section of the original post. –  Theo Johnson-Freyd Mar 28 '10 at 17:18

It's easier to prove the result about the matrix without resorting to determinants. What we need is the inequality $$\left(\sum_{i=0}^d 2ix_i\right)^2\le d{2d\choose d}\left(\sum_{i=0}^d x_i\right)^2 +d\sum_{i=0}^d \frac{{2d\choose d}}{{d\choose i}^2}x_i^2$$ Now recall that $\sum_{i=0}^d (2i-d)^2{d\choose i}^2=\frac{d^2}{2d-1}{2d\choose d}$ (elementary computation with generating functions; should have some combinatorial proof as well) and that $(A+B)^2\le \frac{2d-1}dA^2+\frac{2d-1}{d-1}B^2$. Putting $$A=\sum_{i=0}^d(2i-d)x_i\,,\qquad B=d\sum_{i=0}^d x_i$$ we see that we can use Cauchy-Schwarz to get $$A^2\le \frac{d^2}{2d-1}\sum_{i=0}^d \frac{{2d\choose d}}{{d\choose i}^2}x_i^2$$ so we just need to check that $d^2\frac{2d-1}{d-1}\le d{2d\choose d}$ for $d\ge 2$, which is rather trivial.

-
Thanks. Nice argument. –  bandini Mar 29 '10 at 2:05
Sorry, one more question. Could you provide justification for the inequality $(A+B)^2 \leq \frac{2d-1}{d}A^2 + \frac{2d-1}{d-1}$? –  bandini Mar 29 '10 at 11:27
Subtracting $A^2+B^2$ from both sides, we get $2AB\le \frac{d-1}{d}A^2+\frac{d}{d-1}B^2$, which is pura AM_GM –  fedja Mar 29 '10 at 12:57
Of course, thanks. –  bandini Mar 29 '10 at 13:26

Here is a sketch of a solution; the details would be tedious, but doable by someone with enough patience I think.

The point is that the terms with $i$ and $j$ both of the form $d/2 + O(\sqrt{d})$ are so much larger than the others that they are the only ones that matter, unless of course $k$ is significantly less than $d/2$ in which case those terms are not present in the sum and then the terms that matter are the ones where $i$ and $j$ are very close to $k$. The rest of the terms are "error terms".

More precisely, for fixed $B$ and fixed $C>|B|$, and for $k \ge d/2 - B \sqrt{d}$, the sum of the terms with $|i-d/2| \le C \sqrt{d}$ and $|j-d/2| \le C \sqrt{d}$ can be approximated by using Stirling's formula to estimate the binomial coefficients (this amounts to replacing the double sum by a double integral involving the product of two copies of the square of the normal distribution). The result of this is that the double sum can be bounded below by a positive constant times $2^{4d}$, where the constant depends only on $B$.

On the other hand, still for $k$ in this range, bounding the absolute values of the rest of the terms in the sum (i.e., with $(i,j)$ outside that "central square") shows that they contribute a total whose absolute value is at most $\epsilon 2^{4d}$ where $\epsilon$ can be made arbitrarily small by taking $C$ large enough. So this proves that your sum $f(d,k)$ is positive for $k \ge d/2 - B \sqrt{d}$.

For smaller values of $k$, the same Stirling's approximation estimates apply. This time the largest terms are not as large as they were in the central square, but the strategy is the same: to show that the sum of the terms with $(i,j)$ outside a small neighborhood of $(k,k)$ are negligible compared to the sum of the terms inside the neighborhood, which can be estimated analytically. $\square$

There may be some shortcuts that would save you some of the work involved above. For instance, Mathematica gave me a formula that I think is equivalent to $$f(d,d) = \frac{d(d-1)}{2(2d-1)} \binom{2d}{d}^2,$$ which is certainly positive, so if one could show that for fixed $d$, the sequence of values $f(d,k)$ for $k=0,1,\ldots,d$ is increasing up to a point and decreasing thereafter, that would suffice. Perhaps using the Stirling approximation you can show that $f(d,k)-f(d,k-1)>0$ for $k<d/2$, in which case you could avoid the last paragraph of the argument above dealing with small $k$.

-
I just noticed that David Speyer suggested the same approach as mine in the comments, a few hours before I posted my answer. –  Bjorn Poonen Mar 28 '10 at 22:14
(At the time it was buried under so many other comments that I missed it.) –  Bjorn Poonen Mar 28 '10 at 22:15

(That's a comment, but too large for it)

I find it quite surprising how large the recurrence (in k) for the sum is. (the last expression is slightly edited)

I guess I should have taken out factors and denominators first...

Martin

(1) -> s(k,d)==reduce(+, [reduce(+, [(i-(j-i)^2)*binomial(d,i)^2*binomial(d,j)^2 for j in 0..k]) for i in 0..k])

(2) -> l := [s(k,d+k)::FRAC POLY INT for k in 1..];

(3) -> degree numer l.110

440
(3)  d
Time: 0.06 (IN) + 2427.09 (EV) = 2427.15 sec
(4) -> first guessPRec([l.i for i in 1..110], debug==true, safety==3, maxShift==3, indexName=='k)
Guess: trying order 2, guessDegree is 106
Guess: The list of expressions is
[1,f(k)]
Guess: trying order 3, guessDegree is 104
Guess: The list of expressions is
[1,f(k),f(k + 1)]
Guess: trying order 4, guessDegree is 102
Guess: The list of expressions is
[1,f(k),f(k + 1),f(k + 2)]
Guess: trying order 5, guessDegree is 100
Guess: The list of expressions is
[1,f(k),f(k + 1),f(k + 2),f(k + 3)]
Guess: checking solution

(4)
2           3                          2
8(k + d + 1) (k + d + 2) (2k + 2d + 1)(2k + 2d + 3)
*
12                  11         2                    10
270k   + (1188d + 9504)k   + (1656d  + 38610d + 153009)k
+
3         2                      9
(- 116d  + 48240d  + 571376d + 1489089)k
+
4        3          2                       8
(- 2666d  - 8318d  + 640067d  + 5080910d + 9750705)k
+
5         4          3           2                         7
(- 2712d  - 75352d  - 144860d  + 5097112d  + 30152366d + 45222990)k
+
6         5          4           3            2
- 544d  - 70724d  - 893378d  - 1202954d  + 26971038d  + 125308378d
+
152181519
*
6
k
+
7         6          5           4           3            2
1048d  - 19800d  - 751644d  - 5860034d  - 5680006d  + 98975636d
+
371833908d + 373944705
*
5
k
+
8         7          6           5            4            3
1114d  + 11020d  - 221734d  - 4281882d  - 23393024d  - 16084158d
+
2
254633531d  + 787080350d + 664926981
*
4
k
+
9         8         7           6            5            4
564d  + 11864d  + 37516d  - 1169112d  - 14238926d  - 58395350d
+
3             2
- 26812252d  + 452450736d  + 1163442386d + 832838016
*
3
k
+
10        9         8         7           6            5
168d   + 4754d  + 46225d  + 26490d  - 3233406d  - 27783310d
+
4            3             2
- 89191951d  - 23344502d  + 530077080d  + 1142360248d + 695795004
*
2
k
+
11       10         9         8         7           6
28d   + 968d   + 13180d  + 77505d  - 88154d  - 4556092d
+
5            4           3             2
- 29552520d  - 76278129d  - 6191322d  + 368831168d  + 669627480d
+
347006160
*
k
+
12      11        10         9         8          7           6
2d   + 82d   + 1379d   + 11996d  + 46607d  - 127926d  - 2588027d
+
5            4           3             2
- 13249144d  - 27965237d  + 2606896d  + 115473628d  + 177244848d
+
77770368
*
f(k)
+
-
2(k + d + 2)(2k + 2d + 3)
*
18                     17           2                       16
5670k   + (39528d + 258444)k   + (113778d  + 1713798d + 5529195)k
+
3           2                         15
(162048d  + 4654728d  + 34823670d + 73733391)k
+
4           3            2                           14
(76728d  + 6124868d  + 89177838d  + 440257948d + 686343696)k
+
5           4             3              2
- 123488d  + 2235048d  + 108706318d  + 1061766807d
+
3876600070d + 4732061217
*
13
k
+
6           5            4              3
- 269816d  - 5382452d  + 30806122d  + 1202294670d
+
2
8789176564d  + 25214080538d + 25020442332
*
12
k
+
7            6            5             4
- 243584d  - 10216568d  - 98938602d  + 274619579d
+
3               2
9265135210d  + 53604597366d  + 125347850332d + 103621453509
*
11
k
+
8           7             6              5
- 97260d  - 8888236d  - 167857490d  - 1045958504d
+
4               3                2
1826594266d  + 52653304516d  + 248980923640d  + 486082748456d
+
340295700846
*
10
k
+
9           8             7              6              5
42416d  - 4101728d  - 137667362d  - 1604963581d  - 7196598712d
+
4                3                2
9729686227d  + 227651863384d  + 897610283243d  + 1487117805450d
+
891303186771
*
9
k
+
10         9            8              7               6
103708d   - 52872d  - 64851112d  - 1220301710d  - 10026401450d
+
5               4                3
- 34278603518d  + 42187499548d  + 761200428262d
+
2
2535868200670d  + 3605785405692d + 1862377092597
*
8
k
+
11           10            9             8              7
94720d   + 1571288d   - 10799886d  - 553358067d  - 6956791196d
+
6                5                4
- 43322060052d  - 116690555740d  + 146445210390d
+
3                 2
1980644060602d  + 5626722123544d  + 6919765473706d + 3088514052372
*
7
k
+
12           11           10             9              8
58008d   + 1445196d   + 9138842d   - 122602404d  - 2920292956d
+
7                6                5
- 26962188176d  - 133150000764d  - 287694058128d
+
4                 3                 2
396367260782d  + 4002157151664d  + 9761612663250d
+
10434014431088d + 4019726986560
*
6
k
+
13          12           11            10             9
26144d   + 794904d   + 9114906d   + 22172005d   - 676345530d
+
8               7                6
- 10127998241d  - 72795977076d  - 293837293734d
+
5                4                 3
- 512963445426d  + 814925167770d  + 6216119636214d
+
2
13085501379904d  + 12186586428796d + 4028372348280
*
5
k
+
14          13           12            11           10
8808d   + 305364d   + 4439526d   + 30436658d   - 3767856d
+
9               8                7                6
- 2200664298d  - 23597144760d  - 137295986980d  - 462549783234d
+
5                 4                 3
- 650626901900d  + 1238284194352d  + 7274138624156d
+
2
13269220092572d  + 10767289193264d + 3015053973024
*
4
k
+
15         14           13            12            11
2176d   + 83480d   + 1400834d   + 12889449d   + 56856434d
+
10              9               8                7
- 148804002d   - 4441906656d  - 36679126379d  - 177592267906d
+
6                5                 4
- 506717213928d  - 566027709866d  + 1341110383956d
+
3                 2
6197205974456d  + 9825259748784d  + 6927364346768d + 1603928086560
*
3
k
+
16         15          14           13            12
374d   + 15644d   + 291658d   + 3149104d   + 20415794d
+
11             10              9               8
56672012d   - 351741276d   - 5485743352d  - 36536805044d
+
7                6                5
- 150224444680d  - 366621880970d  - 314972463128d
+
4                 3                 2
976645527640d  + 3623057801312d  + 5001697010032d
+
3044512809600d + 556390852416
*
2
k
+
17        16         15          14           13
40d   + 1812d   + 36858d   + 444609d   + 3460908d
+
12            11             10              9
16601453d   + 24254652d   - 358711413d   - 3806913824d
+
8               7                6               5
- 21113505629d  - 74849048982d  - 157188594152d  - 97326057604d
+
4                 3                 2
427927433112d  + 1297863680048d  + 1560991504352d
+
810741422592d + 105783045120
*
k
+
18      17        16         15          14           13
2d   + 98d   + 2157d   + 28430d   + 249126d   + 1482894d
+
12          11             10              9              8
5348576d   + 996158d   - 141411444d   - 1139119288d  - 5384120397d
+
7               6               5               4
- 16648919316d  - 30162754084d  - 11621062000d  + 85154681520d
+
3                2
214477217792d  + 224478599616d  + 97472885760d + 6766986240
*
f(k+1)
+
2
(k + 3)
*
18                     17           2                       16
5670k   + (39528d + 249264)k   + (113778d  + 1652238d + 5134995)k
+
3           2                         15
(162048d  + 4478832d  + 32300466d + 65845395)k
+
4           3            2                           14
(76728d  + 5853388d  + 82322862d  + 392208488d + 588701226)k
+
5           4            3             2
- 123488d  + 2013024d  + 98697962d  + 938080539d  + 3312445788d
+
3895081245
*
13
k
+
6           5            4              3              2
- 269816d  - 5419404d  + 23142946d  + 1032068074d  + 7418719924d
+
20644565084d + 19751629848
*
12
k
+
7            6            5             4              3
- 243584d  - 10086064d  - 99965006d  + 152654767d  + 7494756658d
+
2
43178189496d  + 98284521786d + 78420152943
*
11
k
+
8           7             6              5             4
- 97260d  - 8709764d  - 163549810d  - 1060233724d  + 641727004d
+
3                2
40077202126d  + 191300616888d  + 364906725584d + 246840943500
*
10
k
+
9           8             7              6              5
42416d  - 3954592d  - 132229574d  - 1543695449d  - 7329419834d
+
4                3                2
1894812761d  + 163116338038d  + 657984258553d  + 1068960577696d
+
619645294287
*
9
k
+
10         9            8              7              6
103708d   + 59920d  - 60770176d  - 1149322114d  - 9525990850d
+
5              4                3                 2
- 35180201210d  + 4977781984d  + 514561955102d  + 1774919285310d
+
2482708325190d + 1240920211461
*
8
k
+
11           10           9             8              7
94720d   + 1662736d   - 8148090d  - 505502183d  - 6428880572d
+
6                5               4                 3
- 40701365552d  - 121227411084d  + 15987533238d  + 1267774881906d
+
2
3765293827566d  + 4566558491032d + 1972245476610
*
7
k
+
12           11            10            9              8
58008d   + 1510628d   + 10871770d   - 96268192d  - 2605556158d
+
7                6                5               4
- 24470179932d  - 123890325264d  - 304511727072d  + 54854785886d
+
3                 2
2436964417526d  + 6256043101258d  + 6604615438776d + 2459291696868
*
6
k
+
13          12            11            10             9
26144d   + 829792d   + 10125262d   + 35986257d   - 531377128d
+
8               7                6                5
- 8840504425d  - 64966859892d  - 271315906990d  - 558332967514d
+
4                 3                 2
148150253368d  + 3619568169844d  + 8047755772806d  + 7405005134584d
+
2359137024576
*
5
k
+
14          13           12            11            10
8808d   + 318220d   + 4881038d   + 36846726d   + 56268752d
+
9               8                7                6
- 1715265216d  - 20186325416d  - 120682371252d  - 424928116874d
+
5                4                 3
- 738137474014d  + 280426909520d  + 4072222583640d
+
2
7848514286380d  + 6285092230368d + 1686486937680
*
4
k
+
15         14           13            12            11
2176d   + 86576d   + 1531158d   + 15094117d   + 78221898d
+
10              9               8                7
4795192d   - 3427436638d  - 30812147221d  - 154052421794d
+
6                5                4
- 464626918334d  - 683211178528d  + 358091576646d
+
3                 2
3352919503824d  + 5601803500496d  + 3886295460384d + 852635257632
*
3
k
+
16         15          14           13            12
374d   + 16084d   + 315498d   + 3637620d   + 25840696d
+
11             10              9               8
96091918d   - 120452472d   - 4191432800d  - 30207584234d
+
7                6                5                4
- 128902508230d  - 336866389218d  - 418240355984d  + 294849021836d
+
3                 2
1903667434272d  + 2754953030688d  + 1641370291200d + 277684428096
*
2
k
+
17        16         15          14           13            12
40d   + 1840d   + 39182d   + 504877d   + 4262918d   + 23173171d
+
11             10              9               8
62388590d   - 168967835d   - 2884320006d  - 17223690775d
+
7                6                5                4
- 63703285388d  - 145437318286d  - 151105838136d  + 141752435920d
+
3                2
665185270816d  + 832381981152d  + 419544755712d + 47789803008
*
k
+
18      17        16         15          14           13           12
2d   + 98d   + 2237d   + 31442d   + 299134d   + 1969118d   + 8480832d
+
11            10             9              8               7
16090726d   - 76015620d   - 857640920d  - 4345835293d  - 14097829472d
+
6               5               4                3
- 28272052844d  - 24147321024d  + 30297440848d  + 107641275264d
+
2
116098181568d  + 48252630528d + 2262629376
*
f(k+2)
+
-
3       3
(k + 3) (k + 4) (k + d + 2)(k + d + 4)
*
12                  11         2                   10
270k   + (1188d + 6264)k   + (1656d  + 25542d + 66285)k
+
3         2                     9
(- 116d  + 31680d  + 250616d + 422319)k
+
4        3          2                       8
(- 2666d  - 7274d  + 280427d  + 1479956d + 1799799)k
+
5         4         3           2                       7
(- 2712d  - 54024d  - 82492d  + 1514496d  + 5833462d + 5385954)k
+
6         5          4          3           2
- 544d  - 51740d  - 440562d  - 412094d  + 5508730d  + 16070956d
+
11547375
*
6
k
+
7         6          5           4           3            2
1048d  - 16536d  - 384252d  - 1932862d  - 1053150d  + 14005936d
+
31464878d + 17742855
*
5
k
+
8        7          6           5           4           3
1114d  + 5780d  - 130894d  - 1489602d  - 5042824d  - 1225982d
+
2
24996211d  + 43590054d + 19174947
*
4
k
+
9        8        7          6           5           4
564d  + 7408d  + 3916d  - 469296d  - 3308278d  - 8044058d
+
3            2
169364d  + 30660820d  + 41652760d + 13943088
*
3
k
+
10        9         8         7          6           5
168d   + 3062d  + 17317d  - 30418d  - 866634d  - 4245292d
+
4           3            2
- 7656631d  + 2156388d  + 24555672d  + 25970148d + 6228828
*
2
k
+
11       10        9         8         7          6
28d   + 632d   + 5364d  + 16191d  - 67426d  - 805416d
+
5           4           3            2
- 2928010d  - 3954219d  + 2266732d  + 11523892d  + 9420648d
+
1384992
*
k
+
12      11       10        9        8         7          6
2d   + 54d   + 579d   + 3006d  + 4577d  - 40826d  - 298707d
+
5          4          3           2
- 839258d  - 837391d  + 795520d  + 2394108d  + 1484640d + 67392
*
f(k+3)
Time: 3.58 (EV) + 0.02 (OT) = 3.60 sec

-
That is insanely large! It does not seem `natural' in any way. Are you sure that can't be reduced? That it is order 4 is not so surprising, but those coefficient degrees are just crazy. –  Jacques Carette Mar 29 '10 at 12:38
Unless there is a bug in the program, it is the recurrence of order 4 with minimal coefficient degrees. There might be a recurrence of larger order with lower coefficient degrees, but not much lower. Strange, isn't it? –  Martin Rubey Mar 29 '10 at 15:15