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$$
Any advice/techniques would be appreciated.
Best Answer
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.