Powers of a simple matrix and Catalan numbers

Question

Consider $m \times m$ anti-bidiagonal matrix $M$ defined as:

$$M_{ij} = \begin{cases} -1, & i+j=m\\ \,\,\ 1, & i+j=m+1\\ \,\,\, 0, & \text{otherwise} \end{cases}$$

Let $S_n$ stand for the sum of all elements of the $n$-th power of the matrix:

$$S_n=\sum_{ij}\left(M^n\right)_{ij}.$$

Prove that for integer $0 < k < m$:

1. $S_{2k}=C_{k-1}$, where $C_k$ is $k$-th Catalan number;

2. $S_{2k+1}=0$,

and, additionally,

3. $S_{2m+1}=(-1)^{m-1}$.

PS: In fact, the first equality holds much longer up to $k=2m$. Besides $S_{4m+2}=C_{2m}-1$.

Answer 1

Acknowledgement

The idea of the proof and especially the closed form (2) are due to darij grinberg.

Preliminaries

Let numbers $b^n_i$, where $n$ and $i$ are integer numbers ($n>0$), be given by recurrence relation: $$(1)\quad b^1_i=\delta_{0i}+\delta_{1i},\quad b^{n+1}_i= \begin{cases} b^n_i-b^n_{i-1},&n \text{ even }\\ b^n_i-b^n_{i+1}, &n \text{ odd } \end{cases}. $$

Then the following explicit expression applies: $$(2)\quad b^n_i=(-1)^{i}\left[ \binom{n-1}{\left\lfloor\frac{n-1}{2}\right\rfloor-i}- \binom{n-1}{\left\lfloor\frac{n+1}{2}\right\rfloor-i} \right]. $$

For $n=1$ the statement is obviously valid. Substituting (2) into right-hand side of (1) separately for odd and even $n$ one ends up with the same expression (2) upon replacement of $n$ with $n+1$.

The following observations are important: $$ \begin{align} &(2a)\quad b^n_0=0, \text{ for even } n;\\ &(2b)\quad b^n_1=C_{\frac{n-1}{2}}, \text{ for odd } n;\\ &(2c)\quad b^n_i=0,\text{ for } i>\left\lfloor\frac{n+1}{2}\right\rfloor. \end{align}$$

Proof of the claims

It is convenient to introduce besides matrix $M$ the antidiagonal matrix $\Gamma$:

$$\varGamma=\begin{cases} 1, &i+j=m+1\\ 0, &\text{otherwise} \end{cases},$$

and construct the matrices $L_n=\varGamma^n M\varGamma^{n-1}$ and ${\cal L}_n: \{{\cal L}_1=L_1;\ {\cal L}_n=L_n{\cal L}_{n-1}\}$.

$L_n$ is lower- or upper-bidiagonal matrix for odd and even $n$, respectively. The diagonal elements are $1$ and subdiagonal (or, respectively, superdiagonal) elements are $-1$. Note that due to identity $\varGamma^2=I$ the following equality holds: $$ {\cal L}_n=\varGamma^n M^n. $$ Thus the action of ${\cal L}_n$ on a vector is up to permutation of elements equivalent to action of $M^n$.

Consider now the vectors $u^{n}={\cal L}_n u$, where $u$ is $m$-dimensional "all-ones" vector. Then the following recurrence relation holds for any $i=1\dots m$ and any $n>0$: $$(3)\quad u^{1}_i=(L_1u)_i=\delta_{1i},\quad u^{n+1}_i=(L_{n+1}u^n)_i= \begin{cases} u^n_i-u^n_{i-1},&n \text{ even }\\ u^n_i-u^n_{i+1}, &n \text{ odd } \end{cases}, $$ with a convention $u^n_0=0$ and $u^n_{m+1}=0$.

Now observe strong resemblance of (3) and (1). The fact that $u^n_0\ne b^n_0$ for odd $n$ does not matter as $u^n_0$ enters the recursion only for even $n$. One concludes that $u^n_i=b^n_i$ for all $i=1\dots m$ as long as $b^{n-1}_{m+1}=0$ for even $n$, which fails firstly for $n=2m+2$. Thus: $$ \forall i=1\dots m, \forall n=1\dots (2m+1):\quad u^n_i=b^n_i. $$

The completion of the proof is easy. In fact: $$ (4)\quad S_n=uM^nu=u{\cal L}_nu=\sum_{i=1}^m u^{n}_i=\begin{cases} u^{n-1}_m,& n\text{ odd }\\ u^{n-1}_1,& n\text{ even } \end{cases}. $$

For $n\le2m+1$ the equation amounts to:

$$ \text{for odd } n:\quad S_n= b^{n-1}_m=\begin{cases} 0, &n<2m+1\\ (-1)^{m+1}, & n=2m+1 \end{cases}; $$ $$ \text{for even } n:\quad S_n=b^{n-1}_{1}=C_{\frac{n}{2}-1}. $$

Thus all three claims of the question are proved.

Concluding remark

One may wonder why the equality $S_{2k}=C_{k-1}$ holds for much higher values of $k$ (up to $2m$). The reason is seen from the equality (4). As the $u^n$-vector starts "corrupting" from the end, it requires additional $2m$ recursion steps till $u^n_1$ starts deviating from $b^n_1$. To be more specific the equality $u^n_i=b^n_i$ holds up to $n=2(2m-i)+1$.