Closed form expression for a matrix with elementwise combinatorial sums

Question

Suppose I have an $N \times N$ matrix of the form $M_{ij} = \sum_{k=0}^{N-i}\sum_{l=0}^{N-j}\frac{1}{2^{k+l+1}}\binom{k+l}{l}$. From numerical experiments, I've noticed that $\det(M)$ appears to be a power of $\frac{1}{2}$ (specifically, $\det(M) = \frac {1}{2^{N^2}}$. How to derive this?), and that $M^{-1}$ has all integer entries. Is there a name for a matrix like $M$, and is there a simple expression for its entries (or its inverse)?

Answer 1

It will be easier if we first rewrite and re-index your matrix to be $A_n = [a_{ij}]_{0 \hspace{0.75pt} \leq \hspace{1pt} i, \,j\hspace{1pt} \leq \hspace{0.75pt}n-1}$, where $$ a_{ij} = \sum_{k=0}^{i}\sum_{\ell=0}^{j} \frac{1}{2^{k+\ell + 1}} \binom{k+\ell}{\ell}. $$

---

Lemma. Suppose $A = [a_{ij}]$ and $B = [b_{\hspace{0.6pt}k\ell}]$ are $n \times n$ matrices such that $\sum_{k=0}^{i}\sum_{\ell=0}^{j} b_{\hspace{0.6pt}k\ell} = a_{ij}$. Then $\det(A) = \det(B)$.

Proof. Consider the $n \times n$ matrices $P = [p_{\hspace{0.6pt}ij}]$ and $Q = [q_{\hspace{0.7pt}ij}]$ whose matrix elements are given by $$ p_{\hspace{0.6pt}ij} = \begin{cases} 1 &\text{if}& i \geq j \\ 0 &\text{if}& i < j \end{cases}; \quad q_{\hspace{0.7pt}ij} = \begin{cases} 1 &\text{if}& i \leq j \\ 0 &\text{if}& i > j \end{cases}; $$ Then $PAQ = B$, since $$ \sum_{k=0}^{n}\sum_{\ell=0}^{n}p_{\hspace{0.7pt}ik}\hspace{0.6pt}b_{k\ell}\hspace{0.7pt}q_{\hspace{0.6pt}\ell j} = \sum_{k=0}^{i}\sum_{\ell=0}^{j} b_{k\ell} = a_{\hspace{0.35pt}ij}. $$ Therefore, $\det(A) = \det(PBQ) = \det(P)\det(B)\det(Q) = \det(B)$.

---

It suffices to determine the determinant of the matrix $B_n = [b_{k\ell}]_{0 \hspace{0.75pt} \leq \hspace{1pt} k, \,\ell\hspace{1pt} \leq \hspace{0.75pt}n-1}$, given by $b_{k\ell} = \frac{1}{2^{k+\ell+1}} \binom{k+\ell}{\ell}.$ Since $b_{k\ell} = \frac{1}{2} (\frac{1}{2})^{k}(\frac{1}{2})^{\ell} \binom{k+\ell}{\ell}$, we must have $$ \det(B_n) = \frac{1}{2^n} \cdot \prod_{k=0}^{n-1} \frac{1}{2^{k}} \cdot \prod_{\ell = 0}^{n-1} \cdot \frac{1}{2^{k}} \det(C_n) = \frac{1}{2^{n^2}} \det(C_n). $$ where $C_n = [c_{k\ell}]_{0 \hspace{0.75pt} \leq \hspace{1pt} k, \,\ell\hspace{1pt} \leq \hspace{0.75pt}n-1}$ is the $n\times n$ matrix given by $c_{k\ell} = \binom{k+\ell}{\ell}$. Consider the generating function

$$G(x) = (1-x)^{m-n-1} = \left(\sum_{\ell = 0}^{m} (-1)^\ell \binom{m}{\ell} x^\ell\right)\left(\sum_{\ell=0}^{\infty} \binom{n + \ell}{\ell} x^{\ell}\right).$$

Expanding both sides for $n < m$ and $n = m$ yields the identity

$$ \sum_{\ell=0}^{m} (-1)^{\ell} \binom{m}{\ell}\binom{n+\ell}{\ell} = \begin{cases} 0 &\text{if }& n < m \\ 1 &\text{if }& n = m \end{cases}. $$

In other words, one may write $$\sum_{\ell = 0}^{n-1} (-1)^\ell \binom{n-1}{\ell} c_{k\ell} = \delta_{k, n-1}.$$ It follows, after applying the corresponding elementary matrix operation and using the cofactor expansion, that $\det(C_n) = \det(C_{n-1}) = \cdots = \det(C_1) = 1$. Therefore,

$$\det(A_n) = \det(B_n) = \frac{1}{2^{n^2}}\det(C_n) = \frac{1}{2^{n^2}}.$$.