# Inverse of a matrix with binomial entries

This is closely related to this question: Eigenvalues of a matrix with binomial entries.

We consider the matrix:

$$M_{ij} = 4^{-j}\binom{2j}{i}$$

where it is understood that the binomial coefficient $\binom{m}{k}$ is zero if $k<0$ or $k>m$. The indices $i,j$ traverse a discrete finite range, $i,j \in \{a, a+1, \dots, b\}$, from $a$ to $b$, where $a,b$ are non-negative integers with $0\le a\le b$. Therefore the matrix $M_{ij}$ has dimensions $(b-a+1) \times (b-a+1)$.

Can we find the inverse matrix, $M^{-1}$? Numerical computations of the determinant suggest that this is a non-singular matrix (for all $0 \le a < b$).

A close-form expression for the determinant could be useful.

Why this question is not a duplicate: Although in principle the eigenvalues and eigenvectors of a matrix are enough to invert it, the other question focuses on the largest positive eigenvalue alone. Moreover the eigenvalues/eigenvectors (not even the largest alone) have not been solved, so maybe finding the inverse of this matrix turns out to be easier. So, if the other question suddenly received a complete response and all the eigenvalues / eigenvectors were found, then yes, this question would be automatically solved. But that does not seem likely to happen.

Let's refer everything to square matrices indexed from $0$ to $h$, that I will denote as $${\bf M}_{\,h} = \left\| {\;f(n,m)\;} \right\|_{\,h}$$ with $n$ being the row index and $m$ the column index.

I will then denote by $$\left( {f(n) \circ {\bf I}_{\,h} } \right)$$ the diagonal matrix whose entries are equal to $f(n)$.

So I write the matrix you proposed as $$\bbox[lightyellow] { {\bf M}_{\,h} (a) = \left\| {\;4^{ - n - a} \left( \matrix{ 2n + 2a \cr m + a \cr} \right)\;} \right\|_{\,h} = \left( {4^{ - n - a} \circ {\bf I}_{\,h} } \right)\;\left\| {\;\left( \matrix{ 2n + 2a \cr m + a \cr} \right)\;} \right\|_{\,h} }$$ where $h=b-a$.

That premised, consider that in general \eqalign{ & \left( \matrix{ r\,n + t \cr m + q \cr} \right) = {{\left( {r\,n + t} \right)^{\,\underline {\,m + q} } } \over {\left( {m + q} \right)!}} = {{\left( {r\,n + t} \right)^{\,\underline {\,q} } \left( {r\,n + t - q} \right)^{\,\underline {\,m} } } \over {\left( {m + q} \right)^{\,\underline {\,q} } \;m^{\,\underline {\,m} } }} = \cr & = \left( {r\,n + t} \right)^{\,\underline {\,q} } \left( \matrix{ r\,n + t - q \cr m \cr} \right){1 \over {\left( {m + q} \right)^{\,\underline {\,q} } }} \cr} where $x^{\,\underline {\,a} }$ denotes the falling factorial ($x^{\overline {\,a\,} }$ the rising) and where, for the present problem, we consider $q$ to be a non-negative integer, while $r$ and $t$ could be real (or even complex).

Then we have that we can write the binomial as $$\begin{gathered} \left( \begin{gathered} r\,n + s \\ m \\ \end{gathered} \right) = \frac{1} {{m!}}\left( {r\,n + s} \right)^{\,\underline {\,m\,} } = \frac{1} {{m!}}\sum\limits_{\left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \;h} \right)} {\left( \begin{gathered} m \\ k \\ \end{gathered} \right)s^{\,\underline {\,m - k\,} } \left( {r\,n} \right)^{\,\underline {\,k\,} } } = \hfill \\ = \frac{1} {{m!}}\sum\limits_{\left\{ \begin{subarray}{l} \left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \;h} \right) \\ \left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \;h} \right) \end{subarray} \right.} {\left( \begin{gathered} m \\ k \\ \end{gathered} \right)s^{\,\underline {\,m - k\,} } \left( { - 1} \right)^{\,k - j} \left[ \begin{gathered} k \\ j \\ \end{gathered} \right]r^{\,j} n^{\,j} } = \hfill \\ = \sum\limits_{\left\{ \begin{subarray}{l} \left( {0\, \leqslant } \right)\,k\,\left( { \leqslant \;h} \right) \\ \left( {0\, \leqslant } \right)\,j\,\left( { \leqslant \;h} \right) \end{subarray} \right.} {n^{\,j} r^{\,j} \left( { - 1} \right)^{\,k - j} \left[ \begin{gathered} k \\ j \\ \end{gathered} \right]\frac{1} {{k!}}\left( \begin{gathered} s \\ m - k \\ \end{gathered} \right)} \hfill \\ \end{gathered}$$

Then in the last line we can replace $n^m$ with $$n^{\,m} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \;h} \right)} {\left\{ \matrix{ m \cr k \cr} \right\}n^{\,\underline {\,k\,} } } = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \;h} \right)} {\left( \matrix{ n \cr k \cr} \right)k!\left\{ \matrix{ m \cr k \cr} \right\}}$$

Thus we arrive finally to \bbox[lightyellow] { \eqalign{ & {\bf M}_{\,h} (a) = \left\| {\;4^{ - n - a} \left( \matrix{ 2n + 2a \cr m + a \cr} \right)\;} \right\|_{\,h} = \left( {4^{ - n - a} \circ {\bf I}_{\,h} } \right)\;\left\| {\;\left( \matrix{ 2n + 2a \cr m + a \cr} \right)\;} \right\|_{\,h} = \cr & = \left( {4^{ - n - a} \circ {\bf I}_{\,h} } \right)\left( {\left( {2\,n + 2a} \right)^{\,\underline {\,a} } \circ {\bf I}_{\,h} } \right)\;\left\| {\;\left( \matrix{ 2n + a \cr m \cr} \right)\;} \right\|_{\,h} \left( {{1 \over {\left( {n + a} \right)^{\,\underline {\,a} } }} \circ {\bf I}_{\,h} } \right) = \cr & = \left( {4^{ - n - a} \circ {\bf I}_{\,h} } \right)\left( {\left( {2\,n + 2a} \right)^{\,\underline {\,a} } \circ {\bf I}_{\,h} } \right)\;{\bf B}_{\,h} \left( {n! \circ {\bf I}_{\,h} } \right)\;\overline {{\bf St}_{{\bf 2}\,h} } \left( {2^{\,n} \circ {\bf I}_{\,h} } \right)\;\overline {{\bf St}_{{\bf 2}\,h} } ^{\,{\bf - }\,{\bf 1}} \left( {n! \circ {\bf I}_{\,h} } \right)^{\,{\bf - }\,{\bf 1}} \left( {{\bf I}_{\,h} + \overline {{\bf E}_{\,h} } } \right)^{\,{\bf a}} \left( {{1 \over {\left( {n + a} \right)^{\,\underline {\,a} } }} \circ {\bf I}_{\,h} } \right) \cr} \tag{1} } with \eqalign{ & {\bf B}_{\,h} = \;\left\| {\;\left( \matrix{ n \cr m \cr} \right)\;} \right\|_{\,h} \quad {\bf St}_{{\bf 2}\,h} = \;\left\| {\;\left\{ \matrix{ n \cr m \cr} \right\}\;} \right\|_{\,h} \quad {\bf I}_{\,h} + {\bf E}_{\,h} = \;\left\| {\;\left( \matrix{ 1 \cr n - m \cr} \right)\;} \right\|_{\,h} \cr & \overline {\bf X} = transpose({\bf X}) \cr}

After that the determinant follows easily, since the matrices other than the diagonal ones have unitary determinant $$\bbox[lightyellow] { \left| {\,{\bf M}_{\,h} (a)\,} \right| = \left( {\prod\limits_{0\, \le \,n\, \le \;h} {{{\left( {2\,\left( {n + a} \right)} \right)^{\,\underline {\,a} } } \over {2^{\,n + 2a} \left( {n + a} \right)^{\,\underline {\,a} } }}} } \right) = \left( {\prod\limits_{0\, \le \,n\, \le \;h} {{{\left( \matrix{ 2\,\left( {n + a} \right) \cr a \cr} \right)} \over {2^{\,n + 2a} \left( \matrix{ n + a \cr a \cr} \right)}}} } \right) \tag{2}}$$

Some notes concerning the inversion of identity (1), and further analysis you might possibly want perform on that. For the Binomial $${\bf B}_{\,h} ^{\,{\bf r}} = \;\left\| {\;r^{\,n - m} \left( \matrix{ n \cr m \cr} \right)\;} \right\|_{\,h} = \left( {r^n \circ {\bf I}_{\,h} } \right){\bf B}_{\,h} \;\left( {r^n \circ {\bf I}_{\,h} } \right)^{\, - \,{\bf 1}} \quad \;\left| {\;r \in R,C} \right.$$ where the second expression for $r=0$ is understood to be taken in the limit.
So $${\bf B}_{\,h} ^{\, - \,{\bf 1}} = \left( {\left( { - 1} \right)^n \circ {\bf I}_{\,h} } \right){\bf B}_{\,h} \;\left( {\left( { - 1} \right)^n \circ {\bf I}_{\,h} } \right)^{\, - \,{\bf 1}} = \left( {\left( { - 1} \right)^n \circ {\bf I}_{\,h} } \right){\bf B}_{\,h} \;\left( {\left( { - 1} \right)^n \circ {\bf I}_{\,h} } \right)$$ For the Stirling Numbers, 1st and 2nd kind are related by $${\bf St}_{{\bf 2}\,h} ^{\, - \,{\bf 1}} = \;\left\| {\;\left( { - 1} \right)^{\,n - m} \left[ \matrix{ n \cr m \cr} \right]\;} \right\|_{\,h} = \left( {\left( { - 1} \right)^n \circ {\bf I}_{\,h} } \right)\;{\bf St}_{{\bf 1}\,h} \;\left( {\left( { - 1} \right)^n \circ {\bf I}_{\,h} } \right)$$ ${\bf E}$ is the "shift", "first off-diagonal", .. matrix, i.e: $${\bf E}_{\,h} = \left\| {\;\left[ {1 = n - m} \right]\;} \right\|_{\,h} = \left\| {\;\left( \matrix{ 0 \cr n - m - 1 \cr} \right)\;} \right\|_{\,h}$$ (where $[P]$ is the Iverson bracket)

then \eqalign{ & {\bf E}_{\,h} ^{\,{\bf q}} = \left\| {\;\left[ {q = n - m} \right]\;} \right\|_{\,h} = \left\| {\;\left( \matrix{ 0 \cr n - m - q \cr} \right)\;} \right\|_{\,h} \quad \;\left| {\;0 \le q \in Z} \right. \cr & \left( {{\bf I}_{\,h} + {\bf E}_{\,h} } \right) = \left\| {\;\left[ {0 \le n - m \le 1} \right]\;} \right\|_{\,h} = \left\| {\;\left( \matrix{ 1 \cr n - m \cr} \right)\;} \right\|_{\,h} \cr & \left( {{\bf I}_{\,h} + {\bf E}_{\,h} } \right)^{\,{\bf r}} = \sum\limits_{0\, \le \,k\,\left( { \le \;h} \right)} {\left( \matrix{ r \cr k \cr} \right){\bf E}_{\,h} ^{\,{\bf k}} } = \left\| {\;\left( \matrix{ r \cr n - m \cr} \right)\;} \right\|_{\,h} \quad \;\left| {\;r \in R,C} \right. \cr}

and finally that ${\bf B}$ and ${\bf {I+E}}$ are tied by the similarity $${\bf B}_{\,h} \; = \left( {{\bf St}_{\,{\bf 2}\,h} \left( {n! \circ {\bf I}_{\,h} } \right)} \right)\left( {{\bf I}_{\,h} + {\bf E}_{\,h} } \right)\left( {{\bf St}_{\,{\bf 2}\,h} \left( {n! \circ {\bf I}_{\,h} } \right)} \right)^{{\bf - 1}}$$ and by a bunch of other relations, among which $$\left( {{\bf I}_{\,h} + {\bf E}_{\,h} } \right)^{\,{\bf - q}} \quad \left| {\;0 \le {\rm integer }q} \right.\quad = \left( {{\bf B}_{\,h} \left( {n^{\,\underline {\, - q\,} } \circ {\bf I}_{\,h} } \right)} \right)^{\,{\bf - 1}} \;\left( {\left( {n^{\,\underline {\, - q\,} } \circ {\bf I}_{\,h} } \right)\;\;{\bf B}_{\,h} } \right)$$

• @becko before posting, I tested both formulas for various values and are both ok. In particular for $a=1$ and $h=1$, the det. should in fact be $1/8$ and the last formula gives $2/(4 \cdot1) \cdot 4/(8 \cdot 2) = 1/8)$. – G Cab Jul 26 '17 at 11:50
• +1 Oh you are correct. I had a typo in the program I wrote to test this. Sorry :) ... This shows that the determinant is always positive, so the matrix is always invertible. – becko Jul 26 '17 at 11:59
• @becko: yes, for non-negative integer $a$ the matrix is always invertible, as can be seen from the determinant and from its expansion formula. – G Cab Jul 26 '17 at 12:58
• @becko: and clearly, id. (1) can be easily inverted to get the formula for $\bf{M^{-1}}$ – G Cab Jul 26 '17 at 13:09
• Yes, but you still have to invert $\mathbf{B}_h$, $\mathbf{St}_{2h}$ and $\mathbf{I}_h + \overline{\mathbf{E}_h}$, which I'm not sure how to do. In your notation, what does $(\mathbf{I}_h + \overline{\mathbf{E}_h})^\mathbf{a}$ mean? – becko Jul 26 '17 at 13:22