9
$\begingroup$

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.

$\endgroup$

1 Answer 1

6
$\begingroup$

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) $$

$\endgroup$
8
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – G Cab
    Jul 26, 2017 at 11:50
  • $\begingroup$ +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. $\endgroup$
    – valle
    Jul 26, 2017 at 11:59
  • $\begingroup$ @becko: yes, for non-negative integer $a$ the matrix is always invertible, as can be seen from the determinant and from its expansion formula. $\endgroup$
    – G Cab
    Jul 26, 2017 at 12:58
  • $\begingroup$ @becko: and clearly, id. (1) can be easily inverted to get the formula for $\bf{M^{-1}}$ $\endgroup$
    – G Cab
    Jul 26, 2017 at 13:09
  • $\begingroup$ 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? $\endgroup$
    – valle
    Jul 26, 2017 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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