Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the inverse of the following matrix ? $$ \begin{bmatrix} \binom{N}{0} &\binom{N+1}{0} &... &\binom{2N-1}{0} \\ \binom{N}{1} &\binom{N+1}{1} &... &\binom{2N-1}{1}\\ ...& ... &... &... \\ \binom{N}{N-1} &\binom{N+1}{N-1} &... &\binom{2N-1}{N-1} \end{bmatrix} $$

share|improve this question
7  
That matrix has $N+1$ rows and $N$ columns. –  Jonas Meyer Apr 15 '11 at 2:53
7  
Now it has $N$ rows and $N+1$ columns... –  sos440 Apr 15 '11 at 3:22
    
What's the motivation and the background of the question? –  Jack Apr 15 '11 at 4:27
    
Sorry folks. I Hope it is now N*N, if not feel free to add/remove few columns at the end :) @Jack: It came up in an optimization problem, and I got fascinated by the fact that the inverse elements are also integers. (at least for some specific N), for some related problems please see this math.stackexchange.com/questions/32490/any-pattern-here-revised –  mghandi Apr 15 '11 at 5:11
    
You may find mathoverflow.net/questions/49878/… helpful. –  Gerry Myerson Apr 15 '11 at 6:13
add comment

1 Answer

up vote 14 down vote accepted

Your matrix, call it $A_N$, can be factorized as $B_N C_N$, where $$B_N = \left[ \binom{N}{i-j} \right]_{i,j=0,\dots,N-1}$$ and $$C_N = \left[ \binom{j}{j-i} \right]_{i,j=0,\dots,N-1}.$$ For example, for $N=5$ this will be $$ \left( \begin{array}{lllll} 1 & 1 & 1 & 1 & 1 \\ 5 & 6 & 7 & 8 & 9 \\ 10 & 15 & 21 & 28 & 36 \\ 10 & 20 & 35 & 56 & 84 \\ 5 & 15 & 35 & 70 & 126 \end{array} \right) = \left( \begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 5 & 1 & 0 & 0 & 0 \\ 10 & 5 & 1 & 0 & 0 \\ 10 & 10 & 5 & 1 & 0 \\ 5 & 10 & 10 & 5 & 1 \end{array} \right) \left( \begin{array}{lllll} 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 1 & 3 & 6 \\ 0 & 0 & 0 & 1 & 4 \\ 0 & 0 & 0 & 0 & 1 \end{array} \right). $$ The inverses of these factors are $$B_N^{-1} = \left[ (-1)^{i+j} \binom{N-1+i-j}{N-1} \right]_{i,j=0,\dots,N-1}$$ and $$C_N^{-1} = \left[ (-1)^{i+j} \binom{j}{j-i} \right]_{i,j=0,\dots,N-1}.$$ Then $A_N^{-1}=C_N^{-1} B_N^{-1}$ of course, but I don't know if that simplifies to something nice. (I didn't find any hits in OEIS.) In any case, the fact that $B_N$ and $C_N$ have determinant one (since they are triangular with ones on the diagonal) explains why $A_N^{-1}$ has integer entries.

Edit: Here's the picture promised in my comment. It illustrates the situation for $N=5$.

Planar network

Entry $(i,j)$ (counting from zero) in the matrix $A_5 = B_5 C_5$ equals the number of paths through the directed graph from source number $i$ on the left to sink number $j$ on the right.

Incidentally, the network shows that $B_N$ can be factorized further, just for fun: $$ B_5 = \left( \begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 4 & 1 & 0 & 0 & 0 \\ 6 & 4 & 1 & 0 & 0 \\ 4 & 6 & 4 & 1 & 0 \\ 1 & 4 & 6 & 4 & 1 \end{array} \right) \left( \begin{array}{lllll} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 2 & 1 & 0 & 0 \\ 1 & 3 & 3 & 1 & 0 \\ 1 & 4 & 6 & 4 & 1 \end{array} \right). $$ (The first factor corresponds to the first four blue arrows, and the second factor to the next four blue arrows.)

share|improve this answer
    
+1: very nice :-) –  joriki Apr 15 '11 at 10:06
2  
@joriki: Thanks! Another nice thing is that these matrices are path matrices for planar networks, so that one can compute subdeterminants using the Karlin–McGregor–Lindström–Gessel–Viennot Theorem (or whatever one wants to call it), and the factorization corresponds to concatenating the networks. I'll see if I can make a picture to explain that later. –  Hans Lundmark Apr 15 '11 at 10:28
    
Sweet answer! $$$$ –  The Chaz 2.0 Sep 30 '11 at 1:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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