# Eigenvalues and eigenvectors of the matrix with entries $\dbinom{n+1}{2j-i}$ for $i, j = 1, 2, \ldots, n$

Let $n$ be a nonnegative integer, and let $B$ be the $n \times n$-matrix (over the rational numbers) whose $\left(i, j\right)$-th entry is $\dbinom{n+1}{2j-i}$ for all $i, j \in \left\{ 1, 2, \ldots, n \right\}$.

For example, if $n = 5$, then $$B = \left(\begin{array}{rrrrr} 6 & 20 & 6 & 0 & 0 \\ 1 & 15 & 15 & 1 & 0 \\ 0 & 6 & 20 & 6 & 0 \\ 0 & 1 & 15 & 15 & 1 \\ 0 & 0 & 6 & 20 & 6 \end{array}\right) .$$

Question 1. Prove that the eigenvalues of $B$ are $2^1, 2^2, \ldots, 2^n$. (I know how to do this -- I'll write up the answer soon -- but there might be other approaches too.)

Question 2. Find a left eigenvector for each of these eigenvalues. What I know is that the row vector $v$ whose $i$-th entry is $\left(-1\right)^{i-1} \dbinom{n-1}{i-1}$ (for $i \in \left\{1,2,\ldots,n\right\}$) is a left eigenvector for eigenvalue $2^1$ (that is, $v B = 2 v$). But the other left eigenvectors are a mystery to me.

Question 3. Find a right eigenvector for each of these eigenvalues. For example, it appears to me that the column vector $w$ whose $i$-th entry is $\left(-1\right)^{i-1} / \dbinom{n-1}{i-1}$ (for $i \in \left\{1,2,\ldots,n\right\}$) is a right eigenvector for eigenvalue $2^1$ (that is, $B w = 2 w$). This (if correct) boils down to the identity $$\sum_{k=1}^n \left(-1\right)^{k-1} \left(k-1\right)! \left(n-k\right)! \dbinom{n+1}{2k-i} = 2 \left(-1\right)^{i-1} \left(i-1\right)! \left(n-i\right)!$$ for all $i \in \left\{1,2,\ldots,n\right\}$. Note that the entries of $w$ are the reciprocals to the corresponding entries of $v$ ! Needless to say, this pattern doesn't persist, but maybe there are subtler patterns.

I am going to put up an answer to Question 1 soon, as a stepping stone for the proof of https://math.stackexchange.com/questions/2886392 , but this shouldn't keep you from adding your ideas or answers.

• There is some connection with mathoverflow.net/questions/258284/… – Johann Cigler Aug 19 '18 at 12:51
• @JohannCigler: Thank you! This is noticeably simpler than my proof. – darij grinberg Aug 19 '18 at 12:52
• The right eigenvectors seem to be of this form. Fit a degree $n-1$ polynomial $p$ that takes the value $(-1)^{i-1}/{n-1\choose i-1}$ at $i$. Then the $i$th coordinate of the eigenvector corresponding to $2^{k+1}$ is $p^{(k)}(i)$. – MTyson Aug 19 '18 at 20:34
• Also, please, see math.stackexchange.com/questions/2884380/… – DVD Aug 19 '18 at 20:35
• It seems also that the Vandermonde matrix $V(1,2,\dots,n)$ upper-triangularizes $B$, but I do not see the pattern in the resulting matrix's entries. – MTyson Aug 20 '18 at 1:56

Here is a proof for your identity in Question 3: define the functions $$F(n,k):=\frac{\left(-1\right)^{k-i} \left(k-1\right)! \left(n-k\right)!} {2\left(i-1\right)! \left(n-i\right)!} \dbinom{n+1}{2k-i}$$ and $$G(n,k):=-\frac{F(n,k)\,(n-k+1)(2k-i-1)(2k-i)}{(n+1)(n+2-2k+i)(n-i+1)}$$. Then it is routine (e.g. using symbolic softwares) to check that $$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k).$$ If you sum both sides over all integers $k$ (bearing in mind the binomials have finite support), the RHS vanishes. Thus $\sum_kF(n,k)$ is a constant. A simple check for say $n=1$ shows $\sum_kF(n,k)=1$ and this is what you desire to achieve.

The above method is known as the Wilf-Zeilberger method of proof.

This is an update to confirm darij grinberg's claim in the comments: $WU=BW$.

Define the two new functions ($i, j$ are suppressed) $$F(n,k)=\binom{i-1}{k-1}2^{n+1-2j+k}\binom{n+1-j}{j-k}$$ and $$FF(n,k)=\binom{n+1}{2k-i}\binom{k-1}{j-1}.$$ Then there exist two companion functions $G(n,k)$ and $GG(n,k)$ such that $$(i-2j+n+3)F(n+2,k)+(-2i+4j-3n-7)F(n+1,k)+(2n+4-2j)F(n,k)=G(n,k+1)-G(n,k)$$ and $$(i-2j+n+3)FF(n+2,k)+(-2i+4j-3n-7)FF(n+1,k)+(2n+4-2j)FF(n,k)=GG(n,k+1)-GG(n,k).$$ As usual, sum over all integers $k$ to obtain that both $f(n)=\sum_kF(n,k)$ and $ff(n)=\sum_kFF(n,k)$ satisfy the same recurrence $$(i-2j+n+3)f(n+2)+(-2i+4j-3n-7)f(n+1)+(2n+4-2j)f(n)=0,$$ $$(i-2j+n+3)ff(n+2)+(-2i+4j-3n-7)ff(n+1)+(2n+4-2j)ff(n)=0.$$ After checking at two initial values, say $n=1$ and $n=2$, it follows that $f(n)=ff(n)$. That completes the proof.

• (1) Could it be that $F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$ should be $F(n+1,k)-F(n,k)=G(n,k)-G(n,k+1)$ instead? (2) Am I right in assuming that you set $F\left(n,k\right) = 0$ if $n < k$ or $n < i$ ? – darij grinberg Aug 19 '18 at 16:51
• You are right on both counts: (1) I've modified $G(n,k)$ with a minus sign; (2) my comment "compact support" was addressing the convention you pointed out. – T. Amdeberhan Aug 20 '18 at 14:58

The left eigenvectors seem to be related to the Euler polynomials.

For fixed $1\le k\le n$, if the left eigenvector for the eigenvalue $2^k$ is denoted $(v_1,\dots,v_n)$ and normalized to $v_1=1$, then it appears that $$\frac{\sum_{i=1}^n v_ix^i}{(1-x)^{n+1}}=x+2^kx^2+3^kx^3+\cdots$$ which allows to find the $v_i$ recursively, keeping $k$ and increasing $n$.
For $k=n$, $\sum_{i=1}^n v_ix^{i-1}$ is the $n$th Euler polynomial.