25
$\begingroup$

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?

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

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.

$\endgroup$
26
$\begingroup$

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.

$\endgroup$
21
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Neat. You might also like this problem mathoverflow.net/questions/258448/… $\endgroup$ – T. Amdeberhan Jan 2 '17 at 23:42
  • $\begingroup$ @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! $\endgroup$ – Suvrit Jan 2 '17 at 23:51
  • $\begingroup$ Looking forward. $\endgroup$ – T. Amdeberhan Jan 3 '17 at 0:20
  • $\begingroup$ 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). $\endgroup$ – Pietro Majer Jan 3 '17 at 11:41
  • $\begingroup$ @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. $\endgroup$ – Suvrit Jan 3 '17 at 16:02
15
$\begingroup$

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$

$\endgroup$
  • 3
    $\begingroup$ Often such identities are provable by induction using Desnanot–Jacobi (also known as Lewis Carroll's) identity en.wikipedia.org/wiki/Dodgson_condensation $\endgroup$ – Fedor Petrov Dec 29 '16 at 8:26
  • $\begingroup$ Have you looked at the eigenvalues of $A_m(x)$? There may be a a generalization of Holte's result. $\endgroup$ – Mark Wildon Dec 29 '16 at 15:46
  • 2
    $\begingroup$ It seems (3.13) in "advanced determinant calculus" contains this as a special case. $\endgroup$ – Suvrit Dec 29 '16 at 16:41
  • 7
    $\begingroup$ 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$. $\endgroup$ – Richard Stanley Dec 29 '16 at 22:07
  • 3
    $\begingroup$ 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]. $\endgroup$ – Christian Stump Dec 30 '16 at 9:18
14
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.