Rational congruence of binomial coefficient matrices - MathOverflow

Rational congruence of binomial coefficient matrices

2010-05-31T00:28:26Z

Skip Garibaldi asks if there is an elementary proof of the following fact that "accidentally" fell out of some high-powered machinery he was working on.

Say that two matrices $A$ and $B$ over the rationals are rationally congruent if there exists a nonsingular matrix $S$ over the rationals such that $S^t A S = B$.

Theorem (Garibaldi). Suppose $n \equiv 0 \pmod 4$. Then the diagonal matrices $$A = diag\left[\binom{n}{0}, \binom{n}{2}, \binom{n}{4}, \ldots, \binom{n}{n/2 - 2}\right]$$ and $$B = diag\left[\binom{n}{1}, \binom{n}{3}, \binom{n}{5}, \ldots, \binom{n}{n/2 - 1}\right]$$ are rationally congruent. Similarly, suppose $ n \equiv 2 \pmod 4$. Then the matrices $$A = diag\left[\binom{n}{0}, \binom{n}{2}, \binom{n}{4}, \ldots, \binom{n}{n/2 - 1}\right]$$ and $$B = diag\left[\binom{n}{1}, \binom{n}{3}, \binom{n}{5}, \ldots, \binom{n}{n/2 - 2}, \frac{1}{2}\binom{n}{n/2}\right]$$ are rationally congruent.

Answer by Will Jagy for Rational congruence of binomial coefficient matrices

2010-05-31T17:39:35Z

This is far too long for a comment. From a pantload of experience finding explicit rational congruences, I can suggest that this problem could be decided by actual formulas. In any case finding some specific matrices ought to be instructive. My difficulty is that the numbers have passed what I can manage with my C++ programs ( I do not have n=12 explicit), plus I never wrote anything for 4 by 4 or larger.

Well, if we multiply both sides of a rational congruence by the square of the LCM $k$ of the "denominators" we get an integral "congruence" $$ P^t A P = k^2 B.$$ where $P$ is integral. For $n=4,$ where $A$ is diag(1) and $B$ is diag(4) we just get $k=2$ and $P$ is diag(2).

For $n=6,$ with $A= diag(1,15)$ and $B=diag(6,10)$ we get $k=2$ and
$$ P \; \; = \; \;
\left( \begin{array}{cc} 3 & 5\\ -1 & 1
\end{array} \right) . $$

For $n=8,$ with $A= diag(1,28)$ and $B=diag(8,56)$ we get $k=2$ and
$$ P \; \; = \; \; \left( \begin{array}{cc} 2 & 14\\ -1 & 1
\end{array} \right) . $$

For $n=10,$ with $A= diag(1,45,210)$ and $B=diag(10,120,126)$ we get $k=7$ and
$$ P \; \; = \; \; \left( \begin{array}{ccc} 10 & 30 & -63\\ 2 & 6 & 7 \\ 1 & -4 & 0
\end{array} \right) . $$

The bad news for me is that $n=12$ began to run into bounds on my C++ program. So I wanted to show others how to find these matrices in computer languages with unbounded integers. The main things are that you should assume that, while there will be infinitely many possible "denominators" $k$ that work, both for computational and perceptual purposes it is worth investigating the smallest values $k= 1,2,3,\ldots$ first. Next, given a value $k,$ we do not attempt to vary all $n^2$ elements in the matrix $P.$ This is computationally infeasible. Instead, make a list of possible column 1's, then a list of possible column 2's, and so on. Once the $n$ lists of columns are complete, do what probably amounts to what they call "backtracking," meaning that you pick a column 1 ( meaning $c_1^t \; A \; c_1 = k^2 B_{11}$), then a column 2, if those are compatible so far ($ c_2^t \; A \; c_1 = 0 $) then pick a column 3, and so on.

As $A$ and $B$ are diagonal we automatically get multiple copies of essentially the same matrices with the only change being $\pm$ signs. But I am really impressed that there has been essentially one matrix $P$ for each $k.$ This tells me that there may be predictable patterns in the triple $(n,k,P),$ different for $n \equiv 0,2 \pmod 4$ but perhaps related in some way all the same.

Please contact me with any questions. Just click on http://www.ams.org/cml and search for my last name.

Answer by Wadim Zudilin for Rational congruence of binomial coefficient matrices

2010-06-01T01:03:03Z

Expecting to be criticised, I nevertheless try to explain an approach to the problem (for the first case). Assume that there exist two family of polynomials $P_i(t)$ and $\hat P_i(t)$, $i=0,1,\dots,n-1$, each spanning the space of polynomials of degree less than $n$ such that $$ \sum_{i=0}^{n-1}\binom{4n}{2i}P_i(t)^2 =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i(t)^2 $$ identically in $t$; this, for example, happens if the both sides are equal for $n$ distinct points. Then replacing the monomials $t^0,t^1,\dots,t^{n-1}$ by variables $t_0,t_1,\dots,t_{n-1}$ we obtain the linear forms $L_i(t_0,t_1,\dots,t_{n-1})$ and $\hat L_i(t_0,t_1,\dots,t_{n-1})$ such that $L_i(1,t,\dots,t^{n-1})=P_i(t)$ and $\hat L_i(1,t,\dots,t^{n-1})=\hat P_i(t)$, $i=0,1,\dots,n-1$, and $$ \sum_{i=0}^{n-1}\binom{4n}{2i}L_i(t_0,t_1,\dots,t_{n-1})^2 =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat L_i(t_0,t_1,\dots,t_{n-1})^2, $$ the desired equivalence. So far, I could only manage some examples of the polynomial expansions, like $$ \frac{(1+t)^{4n}+(1-t)^{4n}}{2t^{2n}} =\sum_{i=0}^{2n}\binom{4n}{2i}t^{2i-2n} =\sum_{i=0}^{n-1}\binom{4n}{2i}(t^{-2(n-i)}+t^{2(n-i)})+\binom{4n}{2n} $$ $$ =\sum_{i=0}^{n-1}\binom{4n}{2i}(t^{n-i}-t^{-(n-i)})^2+\sum_{i=0}^{2n}\binom{4n}{2i} $$ $$ =\biggl(t-\frac1t\biggr)\sum_{i=0}^{n-1}\binom{4n}{2i}P_i\biggl(t+\frac1t\biggr)^2+2^{4n-1}, $$ in other words, $$ \sum_{i=0}^{n-1}\binom{4n}{2i}P_i\biggl(t+\frac1t\biggr)^2 =\frac{(1+t)^{4n}+(1-t)^{4n}-2^{4n}t^{2n}}{2t^{2n}(t-1/t)}. $$ So, the question is whether we can write the rational function on the right-hand side as $$ \sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i\biggl(t+\frac1t\biggr)^2. $$

Answer by darij grinberg for Rational congruence of binomial coefficient matrices

2010-06-01T10:54:26Z

Wadim, isn't that 95% of the proof? First let me correct your first displayed equation (thanks to fherzig for pointing this out): It is not sufficient for the proof, but $$ \sum_{i=0}^{n-1}\binom{4n}{2i}P_i(t)P_i(s) =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i(t)\hat P_i(s) $$ is, where $t$ and $s$ are two independent variables.

Let me rename your $P_i$ as $Q_{2i}$ and your $\hat{P_i}$ as $Q_{2i+1}$, so that your equation $$ \sum_{i=0}^{n-1}\binom{4n}{2i}P_i(t)P_i(s) =\sum_{i=0}^{n-1}\binom{4n}{2i+1}\hat P_i(t)\hat P_i(s) $$ becomes $$ \sum_{i=0}^{2n-1}\left(-1\right)^i\binom{4n}{i}Q_i(t)Q_i(s)=0. $$ Now let $Q$ be the polynomial $Q\left(t\right)=t^{n-1}$ (I suspect the below proof works with any polynomial $Q$ of degree $n-1$ (not less!), but I'm not completely sure and don't have the time to check) and let $Q_i\left(t\right)=\left(2n-i\right)Q\left(t-\left(2n-i\right)^2\right)$ for every $i\in\mathbb Z$. Being a polynomial in $i$ of degree $2\left(2\left(n-1\right)+1\right)<4n$ (for fixed $t$ and $s$), the term $Q_i\left(t\right)Q_i\left(s\right)$ satisfies $$ \sum_{i=0}^{4n}\left(-1\right)^i\binom{4n}{i}Q_i(t)Q_i(s)=0, $$ since the $4n$-th finite difference of a polynomial of degree $< 4n$ is zero. Due to the symmetry of the function $i\mapsto Q_i\left(t\right)Q_i\left(s\right)$ around $i=2n$, and due to $Q_{2n}\left(t\right)=0$, this becomes $$ \sum_{i=0}^{2n-1}\left(-1\right)^i\binom{4n}{i}Q_i(t)Q_i(s)=0. $$ Now it remains to prove that each of the families $\left(Q_1,Q_3,...,Q_{2n-1}\right)$ and $\left(Q_0,Q_2,...,Q_{2n-2}\right)$ spans the space of all polynomials in $t$ of degree $< n$. This is a particular case of a more general fact: If $x_1$, $x_2$, ..., $x_n$ are $n$ pairwise distinct reals, then the polynomials $\left(t-x_1\right)^{n-1}$, $\left(t-x_2\right)^{n-1}$, ..., $\left(t-x_n\right)^{n-1}$ are linearly independent. In order to prove this, assume that they are linearly dependent, take their derivatives of all possible orders, evaluate at $t=0$, and get a contradiction because Vandermonde's determinant is nonzero.

Answer by fherzig for Rational congruence of binomial coefficient matrices

2010-06-01T16:38:16Z

There is a problem with this approach (I refer to Wadim Zudilin's answer). At least I don't see how to get from the first displayed equation (involving the $P_i$) to the second (involving the $L_i$) in his post.

Here is an example:

$(t^2+t-2)^2 + (3t+2)^2 + 1^2 = (t^2+t+2)^2 + (t+2)^2 + 1^2$

but

$(t_2+t_1-2t_0)^2 + (3t_1+2t_0)^2 + t_0^2 \ne (t_2+t_1+2t_0)^2 + (t_1+2t_0)^2 + t_0^2$,

by considering the coefficient of $t_0t_2$ or of $t_1^2$. Clearly, if the second equation were true it would imply the first. But the problem with the converse is that the first involves 5 degrees of freedom (the coefficients of $t^i$ with $0 \le i \le 4$), whereas the second has 6 (the coefficients of the $t_it_j$ with $i \le j$).

Edit: Here is a better example:

$(t^2+1)^2 -2 (t)^2 + 1^2 = (t^2-1)^2 + 2 (t)^2 + 1^2$,

but the two forms $diag(1,-2,1)$ and $diag(1,2,1)$ don't even have the same signature.