# How to invert the matrix [n choose 2j - i] ?

In a certain model of a stat-physics type, one encounters a matrix $$A_n:=\left[\binom{n}{2j-i}\right]_{i,j=1}^{n-1}.$$ The determinant of this matrix (equal to $2^{\binom n2}$) counts the number of all possible configurations, and our understanding of the model would greatly increase if we would know the inverse of this matrix. So the question is,

is there a closed-form expression for the inverse of the matrix $A_n$?

A little more information about the matrix: its eigenvalues are $2^i\colon i=1,\dots,n-1$. The eigenvectors are not orthogonal to each other (and $A_n$ is not a symmetric matrix, for sure), but the vectors corresponding to even $i$'s are orthogonal to the ones which correspond to the odd $i$'s (i.e., the whole space orthogonally decomposes into the "even" and the "odd" parts).

PS I would appreciate any help or reference. I've looked through Krattenthaler's seminal "Advanced determinant calculus", but didn't find such a matrix there.

-
Did you try using the formula $A^{-1}=\frac{1}{\det(A)}(\text{adjoint of } A)$ for $n=2,3$ (to start with) just to get an idea of what the inverse looks like? – Johan Öinert Jun 26 '11 at 20:32
If you clear the denominators, it looks like the even-odd pattern of the rows is the same as the even-odd pattern of Pascal's triangle. For example, the first column of $2^{19}A_{12}^{-1}$ is $88179, -533860, 1556475, -2842320, 3564470, -3182088, 2034942, -915824, 276471, -50388, 4199$ which has the same pattern $\mod 2$ as $1,10,45,120,210,252,210,120,45,10,1.$ The exponents of $2$ in the prime factorizations are symmetric, but not the same as in Pascal's triangle. – Douglas Zare Jun 26 '11 at 22:37

This is more an idea to explore than a complete answer.

You may interpret the binomial coefficient $\binom{n}{k}$ as the elementary symmetric function $e_k$ of $1,1,\ldots,1$ ($n$ variables evaluated at $1$). The coefficients of the adjoint matrix of $A_n$ become skew Schur functions of $1,1,\ldots,1$. Then there may be some further simplifications.

(By the way, this approach gives a nice proof for the value of the determinant of $A_n$: it is the value of the staircase Schur function $s_{(n-1,n-2,\ldots,1,0)}$ evaluated at $1,1,\ldots,1$. Note that the staircase Schur function at $x_1,x_2,\ldots,x_n$ is equal to $\prod_{i \lt j} (x_i+x_j)$).

EDIT: I find that the coefficient $(i,j)$ of the inverse is $(-1)^{i+j} s_{[j]'/(n-i)}(1,1,\ldots,1)/2^{\binom{n}{2}}$, where $[j]$ stands for the partition obtained from $(n-1,n-2,\ldots,1)$ by removing $j$, and $[j]'$ is its conjugate. At this point there is some hope to find a nice formula. First by expressing the skew Schur function as a sum a Schur functions by means of dual Pieri rule: $$s_{\lambda/(k)}=\sum s_{\nu}$$ where the sum is carried over all partitions $\nu$ obtained from $\lambda$ by removing a horizontal strip with $k$ boxes. After that by using the following formula found in Macdonald, I.3. Ex. 4: $$s_{\lambda'}(1,1,\ldots,1)=\prod_{x \in \lambda} \frac{n-c(x)}{h(x)}$$ where the evaluation is at $(1,1,\ldots,1)$ with $n$ ones, $\lambda'$ is the conjugate of $\lambda$ and $h(x)$ and $c(x)$ are the hook length and content respectively of the box $x$ in the diagram of $\lambda$.

Hopefully the formulas simplify.

-
There is more on this sort of thing in: Symmetric Polynomials, Pascal Matrices, and Stirling Matrices Michael Z. Spivey1, Andrew M. Zimmer (full text seems to be readily available). – Igor Rivin Jun 27 '11 at 1:56
Thank you very much for this idea, I think it could really lead to something. – Leonid Petrov Jun 27 '11 at 6:12
@Igor: Full text is available via my web site here: math.pugetsound.edu/~mspivey/Symmetric.pdf. – Mike Spivey Jun 27 '11 at 19:57
@Mike: Many thanks for the link! So I have managed to write the inverse in terms of the skew Schur functions as is suggested in the answer. Does your paper give any other, better way of writing the inverse? – Leonid Petrov Jun 28 '11 at 0:47
@Leonid: My apologies for responding so late to your question; somehow I didn't get pinged by your use of "@Mike." All of the matrices in our paper are lower triangular, so the methods may not directly apply. However, one of the core ideas is that elementary and complete symmetric polynomials are inverse to each other, in some sense, and maybe you can adapt that idea to your situation. See, for example, p. 296 of Richard Stanley's Enumerative Combinatorics, Vol. II. – Mike Spivey Oct 31 '11 at 4:18

You probably know the following already. Oh, well.

Anyway, Eric Nordenstam and I answered exactly this problem.

It is a special case of Theorem 1 in our preprint, http://arxiv.org/abs/1201.4138 and it also appears in the proceedings of FPSAC 2012. Our method was inspired (and suggested) by Krattenthaler: We guessed the answer from empirical data, and then proved our guess was right by multiplying the matrices out and confirming that the answer was the identity matrix.

-
Thank you! And probably my computation of correlation kernel of lozenge tilings can give explicit inverse of something like $\binom{n}{a_j-i}$ matrix - though I have not checked that in detail. – Leonid Petrov Dec 8 '13 at 14:20