Eigenvectors of a particular transition matrix

Question

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.

Answer 1

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*}

Answer 2

Not a complete answer, but some further numerical observations.

We know that the eigenvector for $\lambda = 1$ is $(1,1,1,\ldots,1)$. David Speyer notes in a comment that experimentation with small $n$ suggests the following generalization: the eigenvector for $\lambda_i = (-1)^{i-1}/i$ has $j$-th coordinate a polynomial of degree $i-1$ in $j$. For each $i$ one can readily surmise a pattern, e.g. for $i=2$ it's a linear polynomial whose value at $j=1$ is $-2$ times the value at $j=n$.

Proceeding from the opposite direction, the eigenvector for $\lambda_n$ always has $j$-th coordinate $(-1)^j {n \choose j}$. More generally, it seems that the eigenvector for $\lambda_i$ has $j$-th coordinate a linear combination of the vectors $\left((-1)^j {k \choose j}\right)_{j=1}^n$ for $i \leq k \leq n$. Again for each value of $n-i$ one can surmise the pattern.

This suggests the following conjugations of ${\bf P}$ to a triangular matrix. Let $B$ be the matrix whose $(i,j)$ entry is $j \choose i$. Then $B {\bf P} B^{-1}$ is lower triangular with $\lambda_i$ on the diagonal. the other entries are predictable too; for instance, here's the $n=7$ case:

1     0    0    0    0     0    0

3   -1/2   0    0    0     0    0

5   -5/3  1/3   0    0     0    0

5   -5/2   1  -1/4   0     0    0

3    -2   6/5 -3/5  1/5    0    0

1   -5/6  2/3 -1/2  1/3  -1/6   0

1/7 -1/7  1/7 -1/7  1/7  -1/7  1/7

it was produced in gp with the commands

M(n) = matrix(n,n,i,j,if(i+j>n,1/i,0))
B(n) = matrix(n,n,i,j,binomial(j,i))
Binv(n) = matrix(n,n,i,j,(-1)^(i-j)*binomial(j,i))
MD(n) = B(n) * M(n) * Binv(n)
MD(7)

it's easier to see what's going on if we multiply the $i$th row by $i$ for each $i=1,\ldots,n$:

 1   0  0  0  0  0  0

 6  -1  0  0  0  0  0

15  -5  1  0  0  0  0

20 -10  4 -1  0  0  0

15 -10  6 -3  1  0  0

 6  -5  4 -3  2 -1  0

 1  -1  1 -1  1 -1  1

each column is $\pm$ a row of Pascal's triangle. Presumably this is not hard to prove in general, and establishes of the formula for $\lambda_i$ as well as the description of the eigenvectors for $i$ near $n$ for each value of $n-i$.

On the other hand, let $B'$ be the matrix whose $(i,j)$ entry is $(-1)^{i-j} {i-1 \choose j-1}$. Then Then $B' {\bf P} {B'}^{-1}$ is upper triangular with $\lambda_i$ on the diagonal. Here's the $n=7$ case after multiplying row $i$ by $i$:

1  6 15  20  15  6  1

0 -1 -5 -10 -10 -5 -1

0  0  1   4   6  4  1

0  0  0  -1  -3 -3 -1

0  0  0   0   1  2  1

0  0  0   0   0 -1 -1

0  0  0   0   0  0  1

This time the rows are $\pm$ rows of Pascal's triangle. Assuming that this too is straightforward to prove in general, it again establishes the formula for $\lambda_i$, and this time gives for each value of $i$ the formula for the $\lambda_i$ eigenvector as a polynomial of degree $i-1$.

Answer 3

I like to know what the answer to a problem is before I try to prove that it is right, so immediately I went to my computer and generated some data.

So for one thing, it looks like the eigenvectors have rational entries (when normalized so that their first entry is 1).

Furthermore, if you're a little creative and don't always write these rational numbers in lowest terms, it seems like you can express the denominators in the eigenvector associated to the eigenvalue 1/i (or -1/i) are a polynomial of degree (i-1) in n. For the 1 eigenvector (the perron-frobenius one, obviously) you get the constant function 1 (obviously). For the -1/2 eigenvector, for instance, the denominators are 2, 4, 6, 8, .... and for the 1/3 eigenvector, they appear to be the values of the polynomial 3/2(n-1)(n-2)

Edit: It looks like the correct denominator for the ith eigenvector in the n by n matrix is probably i/(i-1)! (n-1)(n-2)...(n-i+1) - that is, the eigenvectors are integer vectors, if this is their first coordinate.

Answer 4

I'll write out closed eigenvectors for a related matrix.

Let $J$ denote the "reverse-diagonal" matrix (i.e., $J_{i,n-i+1}=1$).

Then, consider the matrix $JP^{-1}$. This is seen to be \begin{equation*} JP^{-1} = \begin{pmatrix} 1 & &\\ -1 & 2 & \\ 0 & -2 & 3 & \\ \vdots & &\ddots & \ddots & \\ \dots & & & -(n-1) & n \end{pmatrix} \end{equation*}

This is very special bidiagonal matrix, whose eigenvectors are obtainable in closed form, though it is not clear if this helps towards getting eigenvectors of $P^{-1}$ (thanks to D. Speyer for catching this gaffe).

Here is an explicit diagonalization of $JP^{-1}$. It seems after some experimentation that $$VJP^{-1}V=\text{Diag}([1,2,\ldots,n]),$$ where $V=\exp(L_{n})$ and $L_n$ is the $n\times n$ lower triangular matrix that with entries $1,2,\ldots,n-1$ on its first lower-diagonal and zeros elsewhere (this is related to Pascal matrices and matrix exponentials)

Looking more into Pascal matrices, their generalizations etc., one should be able to figure out explicit eigenvectors also for $P^{-1}$ directly.