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.



Rational congruence of binomial coefficient matrices
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}$. (With some work, the proof below works just as well if $Q$ is any polynomial of degree $n-1$ (not less!), but let me use $t^{n-1}$ for simplicity's sake.) 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$. For any fixed $t$ and $s$, the term $Q\_i\left(t\right)Q\_i\left(s\right)$ is a polynomial in $i$ of degree $2\left(2\left(n-1\right)+1\right)<4n$, and thus 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$ 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$ (or alternatively, just take their coefficients), and get a contradiction because Vandermonde's determinant is nonzero.


