I am considering a Markov chain with $n$ states with a particularly nice structure. The transition matrix is as follows:
\begin{equation}\mathbf{P}=\begin{pmatrix}
0 & 0& \dots&0 & 0 &1\\
0 & 0& \dots&0 & \frac{1}{2}&\frac{1}{2}\\
\vdots& & & & & \vdots \\
0 &\frac{1}{n-1}& \dots&\frac{1}{n-1}&\frac{1}{n-1}&\frac{1}{n-1}\\
\frac{1}{n} &\frac{1}{n} &\dots&\frac{1}{n} &\frac{1}{n} &\frac{1}{n}
\end{pmatrix}
\end{equation}
I already deduced that the eigenvalues of the matrix are $\lambda_i=(-1)^{i-1}\frac{1}{i}$ for $1\leq i\leq n$. However, I feel that there should also exist closed-form expressions for the eigenvectors of this matrix. Any help in proving or disproving this feeling is appreciated. Thanks.
Eigenvectors of a Particular Transition Matrix
linear algebramarkov chainsmatrices
Best Answer
EDIT2. (5th Nov, 2014). Based on Darij's comments, am editing the answer to improve its clarity. The answer below shows how to get both eigenvalues and eigenvectors (my original answer was just for eigenvectors).
Eigenvalues
The key idea is to consider $P^{-1}$. Some (Markovian) guessing leads us to the following subdiagonal matrix: \begin{equation*} L_n := \begin{pmatrix} 0 &&&\\ -1 & 0 &&\\ 0& -2 & 0 &&\\ &&\ddots&\ddots\\ \dots& && 1-n & 0 \end{pmatrix}. \end{equation*} Compute now the matrix exponential $V=\exp(L_n)$, which is a lower-triangular matrix with the lower-triangle given by the binomial coefficients: \begin{equation*} V_{ij} = (-1)^{(i-j)}\binom{i-1}{j-1}. \end{equation*} A quick experiment shows that (something that can be verified by a moderately tedious induction): \begin{equation*} VP^{-1}V^{-1} = V\begin{pmatrix} &&&1-n & n\\ &&2-n & n-1&\\ &\dots&\dots&\\ -1& 2 &&&\\ 1&&&& \end{pmatrix}V^{-1} = \begin{pmatrix} 1 & * & \cdots &*\\ & -2 & * &* \\ &&\ddots&*\\ &&&(-1)^{n+1}n \end{pmatrix}, \end{equation*} which is upper triangular, so we can immediately read off the eigenvalues of $P^{-1}$ (and hence $P$).
Eigenvectors
Although $V$ does not diagonalize $P^{-1}$, we observe that it turns $P^{-2}$ into the bidiagonal matrix: \begin{equation*} B := VP^{-2}V^{-1} = \begin{pmatrix} 1 & -2(n-1)\\ & 4 & -3(n-2)\\ &&9 & -4(n-3)&\\ &&&\ddots & \ddots\\ \\ &&&&(n-1)^2 & -n(1)\\ &&&&& n^2 \end{pmatrix}. \end{equation*}
If we succeed in diagonalizing $B$ in closed-form, then we are done. Suppose, $SBS^{-1}=\Lambda$, then we obtain ($\Lambda$ can be read off of the diagonal): \begin{equation*} S^{-1}\Lambda S = VP^{-2}V^{-1} \implies SVP^{-2}V^{-1}S^{-1} = \Lambda = \text{Diag}([i^2]_{i=1}^n), \end{equation*} which shows that $SV$ diagonalizes $P^{-2}$, completing the answer.
Technical Lemma
It remains to find $S$. This reduces to the system of equations: \begin{equation*} SB = \Lambda S\quad\leftrightarrow\quad B^TS^T=S^T\Lambda. \end{equation*} I prefer to solve the latter formulation. Let us write $U := S^T$. Consider the $j$th eigenvalue $\lambda_j=j^2$; denote the corresponding column of $U$ by $u$. Then, the equation to solve is \begin{equation*} \begin{split} B^Tu = j^2u,\qquad \implies & u_1 = j^2u_1\\ -(k+1)(n-k)u_k + (k+1)^2u_{k+1} = j^2u_{k+1}. \end{split} \end{equation*} Examining these equations, we see that $U$ is a lower-triangular matrix, with $1$s on its diagonal (which comes from the equation with $k+1=j$). The subsequent values are nonzero. Solving the recurrences for a few different choices of $j$, we can guess the general solution with some help from Mathematica: \begin{equation*} u_k = \frac{(j+1)_{k-j}(n-k+1)_{k-j}}{(2j+1)_{k-j}(k-j)!},\qquad k \ge j. \end{equation*}