# Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

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?

• Do $i, j$ start with $1$? – T. Amdeberhan Dec 29 '16 at 5:11
• @T.Amdeberhan yes – user42804 Dec 29 '16 at 5:11
• Then, the determinant equals $2^{\binom{2m}2}\neq0$ and hence the matrix is regular/invertible. – T. Amdeberhan Dec 29 '16 at 5:14
• Well, it's pretty exciting that this matrix seems to count domino tilings of an Aztec diamond. – Douglas Zare Dec 29 '16 at 6:51
• It seems that the eigenvalues of $\left({n+1\choose 2j-i}\right)_{i,j=1}^{n}$ are ${2,2^2,\dots\,2^n}.$ – Johann Cigler Dec 29 '16 at 11:53

## 5 Answers

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.

• Neat. You might also like this problem mathoverflow.net/questions/258448/… – T. Amdeberhan Jan 2 '17 at 23:42
• @T.Amdeberhan I actually saw that cool question of yours, and while thinking about it, realized that $V$ triangularizes your matrix :-) For that problem of yours, I found some transformations, but not yet a full answer! – Suvrit Jan 2 '17 at 23:51
• Looking forward. – T. Amdeberhan Jan 3 '17 at 0:20
• Given the abundance of factors of $2$ in the eigenvalues I wonder if there is a further decomposition of this matrix (and the one in the other question). – Pietro Majer Jan 3 '17 at 11:41
• @PietroMajer The matrix $V$ above is the famous Pascal matrix, and there are several papers exploring more refined decompositions involving Pascal matrices, so I wouldn't be surprised if there were more refined decompositions available. – Suvrit Jan 3 '17 at 16:02

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$

• Often such identities are provable by induction using Desnanot–Jacobi (also known as Lewis Carroll's) identity en.wikipedia.org/wiki/Dodgson_condensation – Fedor Petrov Dec 29 '16 at 8:26
• Have you looked at the eigenvalues of $A_m(x)$? There may be a a generalization of Holte's result. – Mark Wildon Dec 29 '16 at 15:46
• It seems (3.13) in "advanced determinant calculus" contains this as a special case. – Suvrit Dec 29 '16 at 16:41
• Conjecture. All the diagonal entries of the Smith normal of $A_m(x)$ over the ring $\mathbb{Q}[x]$ are squarefree (as polynomials in $x$). This uniquely determines the SNF. I checked this for $m\leq 10$ and could easily check some further cases. On the other hand, the eigenvalues do not look nice. The characteristic polynomial of $A_m(x)$ is irreducible for $1\leq m\leq 4$. – Richard Stanley Dec 29 '16 at 22:07
• I agree with @Suvrit that this is a special case of (3.13) in Krattenthaler's Advanced determinant calculus by setting $B=0, A=x, L_j = x-2j-\lambda$, and interchanging $i$ and $j$. Quote from the author's introduction In fact, I claim that about 80 % of the determinants that you meet in “real life,” and which can apparently be evaluated, are a special case of just the very first of these [lemmas]. – Christian Stump Dec 30 '16 at 9:18

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.