13
$\begingroup$

Motivated by this MO question. Consider the two matrices $A_n$ and $B_n$ with entries $\binom{2j}i$ and $\binom{n+1}{2j-i}$, respectively; for $1\leq i, \,j\leq n$.

I can show $\det A_n=\det B_n=2^{\binom{n+1}2}$; it is not a problem (see, for instance, my answer here).

Question.

(1) Is there a transformation converting $A_n$ into $B_n$ (or vice-versa)?

(2) Is there a combinatorial interpretation/bijection revealing the counts by $\det A_n$ and $\det B_n$?

My asking for (2) is due to the fact that $2^{\binom{n+1}2}$ enumerates domino tilings of an Aztec diamond.

(3) Let $s(k)=$the number of $1$'s in the binary expansion of $k$. Then, $A_n$ and $B_n$ share the same Smith normal form (showing the diagonal vector) given by $$[2^{\max(4k-2n+s(n-k)-s(k),0)}:\, 1\leq k\leq n].$$ This claim is based on data from Noam Elkies' comments seen below. Any proof?

Remark. Let $\lceil x\rceil=$the smallest integer greater than or equal to $x$ (ceiling function). So, (3) implies $$\sum_{k=1}^n\max(4k-2n+s(n-k)-s(k),0)=\frac{n(n+1)}2;$$ Or, equivalently $\sum_{k=\lceil\frac{n}2\rceil}^n(s(k)-s(n-k))=\lceil\frac{n}2\rceil$.

$\endgroup$
  • 4
    $\begingroup$ FWIW $A$ and $B$ have the same Smith normal form for $n\leq 40$. Here are the exponents of $2$ in the SNF for $n\leq 16$; the formula might be complicated . . . $$[1],[3],[4,2],[7,3],[8,6,1],[10,7,4],[11,9,5,3],[15,10,7,4],[16,14,8,6,1],[18,15,12,7,3],[19,17,13,11,4,2],[22,18,15,12,8,3],[23,21,16,14,9,7,1],[25,22,19,15,11,8,5],[26,24,20,18,12,10,6,4],[31,25,22,19,15,11,8,5]$$ $\endgroup$ – Noam D. Elkies Dec 31 '16 at 20:43
  • 3
    $\begingroup$ Aztec diamonds, lattice paths, and Schur functions are closely related. Might be something there. $\endgroup$ – Per Alexandersson Dec 31 '16 at 20:53
  • 1
    $\begingroup$ @NoamD.Elkies: the leading numbers $1,3,4,7,8,10,11,15,16,18,19,22,\dots$ are the $2$-adic valuations $\nu((2n)!)$ $\endgroup$ – T. Amdeberhan Dec 31 '16 at 21:06
  • 1
    $\begingroup$ gp code: A(n) = matrix(n,n,i,j,binomial(2*j,i)) $\phantom{000000000000000000000}$ B(n)=matrix(n,n,i,j,binomial(n+1,2*j-i)) $\phantom{000000000000000000000}$ S(M)=round(log(matsnf(M,4))/log(2)) $$ $$ and then the vector in my first comment is both vector(16,n,S(A(n))) and vector(16,n,S(B(n))) $\endgroup$ – Noam D. Elkies Dec 31 '16 at 21:17
  • 1
    $\begingroup$ @NoamD.Elkies: I've made a conjecture on these Smith normal forms, see above. $\endgroup$ – T. Amdeberhan Jan 1 '17 at 15:17
9
$\begingroup$

There is such a transformation, of the form predicted in Linear transformation that preserves the determinant.

Denoting $R$ the involution matrix $e_i\mapsto e_{n+1-i}$, it turns out that the matrix $A$ has an $LU$-decomposition in which $U:=\left[{j\choose i}\right]_{{1\le i\le n}\atop{1\le j\le n}}$, and the lower triangular part is $L=RCR$, where $C$ is the upper triangular matrix in Suvrit's decomposition , $B=VCV^{-1}$ (warning: $B$ of this question is named "$A$" there). So $B= (VR) A(VRU)^{-1}$, with $\det(VR)=\det(VRU)^{-1}=1$.

$$*$$ [edit] The description becomes a bit more gracious if we include the indices $i=0$ and $j=0$. So, if we define the $n\times n$ matrices with integer entries $$A_n:=\left[{2j\choose i}\right]_{{0\le i< n}\atop{0\le j< n}}\qquad B_n:=\left[{n\choose 2j-i}\right]_{{0\le i< n}\atop{0\le j< n}}$$ $$U_n:=\left[{j\choose i}\right]_{{0\le i< n}\atop{0\le j< n}}\qquad L_n:=\left[2^{2j-i}{j\choose2j- i}\right]_{{0\le i< n}\atop{0\le j< n}}$$ $$N_n:=\Big[ \delta_{i+1,j}\Big]_{{0\le i< n}\atop{0\le j< n}}\qquad R_n:=\Big[ \delta_{n-i,j}\Big]_{{0\le i< n}\atop{0\le j< n}}$$ Then, (hiding the subscript $n$) $$A=LU$$ and $$B=VCV^{-1}$$ with $$V:=U^{T}R\qquad C:=(I+N)AU^{-1}\ .$$

$\endgroup$
  • 3
    $\begingroup$ Nice! I almost had a similar LU decomposition but did not get exactly what I wanted. It is also interesting to note that there exist numerous diagonal matrices for which $D^{-1}AD$ has an LU decomposition with the eigenvalues of $B$ on its diagonal, which reveals the same determinant but does not yet transform one matrix into another... $\endgroup$ – Suvrit Jan 3 '17 at 16:29
  • 2
    $\begingroup$ I enjoyed this. $\endgroup$ – T. Amdeberhan Jan 3 '17 at 18:46
9
$\begingroup$

This doesn't answer the original question but answers the later SNF question for the matrix $B_n$. Let $C_n$ be the $n\times n$ matrix whose $(i,j)$-entry ($1\leq i,j\leq n$) is $\binom{x+1}{2j-i}$. Up to row and column permutations that preserve the sign of the determinant, this is the dual Jacobi-Trudi matrix for the Schur function $s_{n,n-1,\dots,1}$, specialized by setting $x+1$ variables equal to 1 and the others to 0. I compute the SNF of this matrix over the field $\mathbb{Q}[x]$ in http://math.mit.edu/~rstan/papers/jtsnf.pdf. Now set $x=n$ and consider the SNF over $\mathbb{Z}_{(2)}$ (the integers localized at 2, i.e., invert all primes except 2). My proof technique can still be used since all hook lengths are odd and therefore units in $\mathbb{Z}_{(2)}$. Namely, one shows that the bottom-left $k\times k$ minor $M$ divides all $k\times k$ minors (with a special argument when $M=0$), etc. (Actually, we can deduce the SNF of $B_n$ directly from that of $C_n$ since for the partition $(n,n-1,\dots,1)$ we can work over $\mathbb{Z}_{(2)}[x]$ rather than $\mathbb{Q}[x]$.) We get that the $i$th largest diagonal element of the SNF is $\prod_u(n+1+c(u))$, where $u$ ranges over all squares of the $i$th diagonal hook of the partition $(n,n-1,\dots,1)$, and $c(u)$ is the content of the square $u$. This product is just $(2n-2i+2)!/(2i-1)!$, so over the integers the $i$th
largest diagonal element of the SNF of $B_n$ is the largest power of 2 dividing $(2n-2i+2)!/(2i-1)!$.

$\endgroup$
  • $\begingroup$ Very nice, indeed. $\endgroup$ – T. Amdeberhan Jan 3 '17 at 18:46

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.