Eigenvectors of a tridiagonal stochastic matrix

373 Views Asked by At

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

1

There are 1 best solutions below

2
On

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.