Eigenvectors of a tridiagonal stochastic matrix

Question

I'm looking for the eigenvectors of this matrix:

\begin{equation} \nonumber M = \frac{1}{N} \left( \begin{array}{ccccccccc} 0 & 1 &&&&&&&\\ N & 0 & 2&&&&&&& \\ &N-1 & 0 & 3&&&&&& \\ &&N-2 & 0& \ldots&&&&& \\ &&&\vdots & \ddots &&&&& \\ &&&&& 0 & N-2 && \\ &&&&&3 & 0 &N-1 & \\ &&&&&&2 & 0&N \\ &&&&&&& 1 &0 \\ \end{array} \right) \end{equation}

where only nonzero entries are shown.

This matrix has size $(N+1) \times (N+1)$. Its superdiagonal entries grow linearly from $1$ to $N$, and the subdiagonal entries decrease linearly from $N$ to $1$.

I have found something similar on the stack exchange but I can't see how to generalize it to this case: http://math.stackexchange.com/questions/495534/eigenvalues-of-a-tridiagonal-stochastic-matrix — Jennifer, Dec 24 '16 at 15:06
@kotomord What's the point of this bounty? As mentioned by J.M. in his comment, the eigenvectors are the columns of a Krawtchouk matrix. See e.g. sec. 4 of the Feinsilver and Kocik paper in one of his links. — user1551, Dec 26 '16 at 14:08
@J.M.isn'tamathematician Any interest to answer this bounty question? I think your inputs are invaluable. — user1551, Dec 27 '16 at 14:46
I've read your answer and J.M.'s comment, and now I'm clear about the problem. Thank you! — Jennifer, Dec 27 '16 at 14:48
In what sense is this matrix stochastic? It seems fully deterministic to me once $N$ is specified, so is $N$ a random variable? And then do you want the expectation of the largest eigenvalue over some distribution for $N$? — rajb245, Jan 01 '17 at 16:36

score 3 · Answer 1 · answered Jan 01 '17 at 19:45

Let $T$ be a tridiagonal matrix of order $m\times m$ such that the entries $T_{i+1,i}$ and $T_{i,i+1}$ are positive for all $i$. Let $p_r$ be the characteristic polynomial of the leading principal $r\times r$ submatrix of $T$ and set $p_0=1$. Then the polynomials $p_1,\ldots,p_m$ satisfy a three-term recurrence, and it follows that if $\theta$ is an eigenvalue of $T$, then the vector with entries \[ p_0(\theta),\ldots,p_{n-1}(\theta) \] is an eigenvector for $T$ with eigenvalue $\theta$. (All this works for any tridiagonal matrix $T$ such that $T_{i+1,i}T_{i,i+1}>0$ for all $i$. This is part of the theory of orthogonal polynomials.)

For your choice of $T$, the eigenvalues are the integers $n-2k$ for $k=0,\ldots,n$ and the polynomials $p_r$ are known as Krawtchouk polynomials. We have (following wikipedia for example) that \[ p_r(t) = \sum_{i=0}^r -1)^i \binom{t}{i} \binom{n-t}{r-i}. \]

The best reference I know for Krawtchouk polynomials is MacWilliams and Sloane's book on coding theory, I could not find anything really useful online.

With regards to online references, Krawtchouk polynomials do show up in the DLMF under the rubric of the Hahn class in the Askey scheme of OPs (sections 18.19-18.24) (Figure 18.21.1 shows their place in the Askey scheme). In particular, it includes a discussion of their asymptotic behavior in section 18.24 along with citations to relevant papers. — Semiclassical, Jan 01 '17 at 20:09
@Semiclassical: There is a fair bit of information out there, but I could not find something like a tutorial for someone starting from scratch. (Which surprises me.) — Chris Godsil, Jan 01 '17 at 23:40

Eigenvectors of a tridiagonal stochastic matrix

1 Answers1