14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want the row eigenvectors or the column ones? $\endgroup$ – Benjamin Steinberg Jan 30 '14 at 2:06
  • $\begingroup$ I'm interested in the regular right eigenvectors. $\endgroup$ – MthQ Jan 30 '14 at 7:07
  • $\begingroup$ One more thing that I noticed, that you might be interested in: the $ij$ entry of $PP^T$ is $1/\max(i,j)$, which means $PP^T$ is a very special semidefinite matrix. $\endgroup$ – Suvrit Feb 4 '14 at 4:20
12
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Here is a link to Matlab code that you can use to verify the above stuff: dropbox.com/s/3mqwaj55f727twu/evecsThomas.m $\endgroup$ – Suvrit Feb 1 '14 at 5:57
  • $\begingroup$ This is great! Thank you so much, I would never have found this myself. $\endgroup$ – MthQ Feb 2 '14 at 12:25
  • $\begingroup$ you're welcome Thomas! I wouldn't have imagined either that it simplifies so prettily! $\endgroup$ – Suvrit Feb 2 '14 at 14:49
  • $\begingroup$ Why is it enough to find the eigenvalues of the square? $\endgroup$ – darij grinberg Oct 27 '14 at 21:30
  • $\begingroup$ @darijgrinberg: Say $SX^2S^{-1}=D$ for some matrix $X$, then $SXS^{-1}SXS^{-1}=D$ which implies $SPS^{-1}=\sqrt{D}$, so.... $\endgroup$ – Suvrit Oct 27 '14 at 21:39
9
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Fix $n$ and look at the $j$th entry of the eigenvector for $1/d$. It appears to be a polynomial of degree $d-1$ in $j$. $\endgroup$ – David E Speyer Jan 30 '14 at 2:05
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ How can you recover the eigenvectors of $J P^{-1}$ from those of $P^{-1}$? $\endgroup$ – David E Speyer Jan 29 '14 at 18:24
  • $\begingroup$ sorry, I wrote too fast; all I meant was that it seems relatively easy to get eigenvectors of $JP^{-1}$ in closed form, and the closed form we get there can suggest what eigenvectors of $P^{-1}$ might look like. However, I don't know if this is possible. $\endgroup$ – Suvrit Jan 29 '14 at 19:39
  • $\begingroup$ I think I managed to obtain closed form eigenvectors for $P^{-1}$. Will upload this stuff once I get a chance to type it in! $\endgroup$ – Suvrit Jan 30 '14 at 4:20
  • $\begingroup$ Very nice observations. I'm very curious to see your answer! $\endgroup$ – MthQ Jan 30 '14 at 7:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.