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$
3
  • $\begingroup$ Do you want the row eigenvectors or the column ones? $\endgroup$ Jan 30, 2014 at 2:06
  • $\begingroup$ I'm interested in the regular right eigenvectors. $\endgroup$
    – MthQ
    Jan 30, 2014 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, 2014 at 4:20

4 Answers 4

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$
10
  • 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, 2014 at 5:57
  • $\begingroup$ This is great! Thank you so much, I would never have found this myself. $\endgroup$
    – MthQ
    Feb 2, 2014 at 12:25
  • $\begingroup$ you're welcome Thomas! I wouldn't have imagined either that it simplifies so prettily! $\endgroup$
    – Suvrit
    Feb 2, 2014 at 14:49
  • $\begingroup$ Why is it enough to find the eigenvalues of the square? $\endgroup$ Oct 27, 2014 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, 2014 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$
1
  • 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$ Jan 30, 2014 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$
4
  • 2
    $\begingroup$ How can you recover the eigenvectors of $J P^{-1}$ from those of $P^{-1}$? $\endgroup$ Jan 29, 2014 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, 2014 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, 2014 at 4:20
  • $\begingroup$ Very nice observations. I'm very curious to see your answer! $\endgroup$
    – MthQ
    Jan 30, 2014 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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