MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this community
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows: $$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 & 0\newline 1 & 15 & 15 & 1 & 0 \newline 0 & 6 & 20 & 6 & 0 \newline 0 & 1 & 15 & 15 & 1 \newline 0 & 0 & 6 & 20 & 6 \end{pmatrix}$$
Can anyone tell me how to prove it is nonsingular?
This is an instance of Holte's Amazing matrix. Consider addition of binary digits. Start with a carry of $c \in \{0,1,\ldots,2(m-1)\}$. Choose $2m-1$ bits uniformly at random, and add their sum to $c$. If the total is in $2c' + \{0,1\}$ then the new carry is $c' \in \{0,1,\ldots,2(m-1)\}$. Amazingly enough the matrix in the question is the transition matrix for this Markov process, scaled by $2^{2m-1}$.
Holte proves that the eigenvalues of the transition matrix are $1$, $1/2$, $1/4$, $\ldots$, $1/2^{2(m-1)}$. (This agrees with Johann Cigler's comment above.) The eigenvectors can be expressed using Eulerian numbers: see Theorem 3 in Holte. Anyway, this shows the matrix is non-singular.
The Lindstrom-Gessel-Viennot lemma says that the number of families of nonintersecting lattice paths can be counted by a determinant. Let $a_i = (2m-i,i)$. Let $b_j = (2m-2j,-2m+2j)$. Then the number of $(1,0)-(0,1)$ lattice paths from $b_j$ to $a_i$ is $2m \choose 2j-i$. By the Lindstrom-Gessel-Viennot lemma, the number of nonintersecting families of lattice paths from $\{b_j\}$ to $\{ a_i\}$ is $Det\left( {2m \choose 2j-i} \right)$. So, if we find a single nonintersecting family then the matrix is nonsingular. One such family is to connect the points in reverse order, connecting $(-2m+2k,2m-2k)$ to $(k,2m-k)$, and on each path, taking all $k$ vertical steps before all $2m-k$ horizontal steps. So, the determinant is positive.
Of course, it would be nice to evaluate this determinant which seemsto be $2^{2m \choose 2}$. I suspect that there is a correspondence with domino tilings of an Aztec diamond, but I don't see it yet.
Here is a very low-brow answer to the original question.
Consider the lower-triangular matrix \begin{equation*} V = [V_{ij}] = \left[\binom{i-1}{j-1}\right]\quad \text{for}\quad i \ge j. \end{equation*}
Let $A$ be the matrix in the OP. Then, a quick induction shows that $V^{-1}AV$ is upper triangular (use that $V^{-1}$ has entries $(-1)^{i-j}V_{ij}$), with the diagonal: $[2^n,2^{n-1},\ldots,2]$, which not only establishes invertibility of $A$, but also yields its eigenvalues.
Let $A_n(x,\lambda)$ be the $n\times n$ matrix $$\left[\binom{x}{2j-i+\lambda}\right]_{i,j=1}^n.$$ Let's "generalize to trivialize". Sometimes, generalizations offer more elbow room to maneuver, such as in the present problem.
Lemma. We have the determinantal formula $$\det A_n(x,\lambda)=2^{\binom{n}2}\prod_{i=1}^n\binom{n+x-1}{\lambda+2i-1}\binom{n+x-1}{n-i}^{-1}.$$ Proof. We employ the Method of Condensation. Denote $k\times k$ sub-matrices with left-corner at $(a,b)$: $$Z_k^{a,b}(x,\lambda)=\left[\binom{x}{2(j+b)-(i+a)+\lambda}\right]_{i,j=1}^k.$$ Notice that $Z_n^{0,0}(x,\lambda)=A_n(x,\lambda)$. In general $Z_k^{a,b}(x,\lambda)=A_k(x,\lambda+2b-a)$, therefore the inductive proofs neatly work with this Dodgson's recursive relation $$\det Z_n^{a,b}=\frac{\det Z_{n-1}^{a,b}\cdot\det Z_{n-1}^{a+1,b+1}-\det Z_{n-1}^{a,b+1}\cdot\det Z_{n-1}^{a+1,b}}{\det Z_{n-2}^{a+1,b+1}}.$$ So, it remains to prove that the (explicit) formula on the RHS of the lemma does satisfy the same equation. However, this is quite a routine simplification (preferably with symbolic sofwares). The proof is complete. $\square$
Corollary 1. Your determinant evaluates as $2^{\binom{2m}2}$.
Proof. Take $n=2m-1, x=2m, \lambda=0$ in $A_n(x,\lambda)$ and simplify the RHS of the lemma. $\square$
Given a function $F(y_1,\cdots,y_{2m-1})$, denote the constant term of $F$ w.r.t. $y_i$ by $CT_i(F)$ and let $CT=\prod_{i=1}^{2m-1}CT_i$. We now register a nice consequence. A bonus, say to say.
Corollary 2. If $V(z_1,\dots,z_{2m-1})$ denotes the determinant of the Vandermonde matrix then $$CT\left(\prod_{i=1}^{2m-1}y_i^{i-2}(1+y_i)^{2m}V(y_1^{-2},\dots,y_{2m-1}^{-2})\right)=2^{\binom{2m}2}.$$ Proof. Since $\binom{2m}{2j-i}=CT_i(y_i^{i-2j}(1+y_i)^{2m})$, \begin{align} \det\left[\binom{2m}{2j-i}\right] &=\det\left[CT_i(y_i^{i-2j}(1+y_i)^{2m})\right] =CT\prod_{i=1}^{2m-1}y_i^i(1+y_i)^{2m}\det\left[y_i^{-2j}\right] \\ &=CT\prod_{i=1}^{2m-1}y_i^{i-2}(1+y_i)^{2m}\cdot\left(\det\left[(y_i^{-2})^{j-1}\right]\right) \\ &=CT\prod_{i=1}^{2m-1}y_i^{i-2}(1+y_i)^{2m}\cdot V(y_1^{-2},\dots,y_{2m-1}^{-2}). \end{align} The assertion follows from Corollary 1. $\square$
The matrix $A_n(x,\lambda)$ is obtained from the dual Jacobi matrix for the partition $\mu=(n+\lambda,n-1+\lambda,...,1+\lambda)$ by setting $x$ variables equal to 1 and the remaining variables equal to 0, and then permuting some rows and columns in such a way that keeps the sign of the determinant the same. Thus the determinant is just $s_\mu(1^x)$, whose factorization is well-known. Moreover, my conjecture (appearing in a comment) about the Smith normal form of $A_n(x,\lambda)$ follows from my paper http://math.mit.edu/~rstan/papers/jtsnf.pdf.
