4
$\begingroup$

Why we do spectral decomposition of a Markov matrix, when a Markov matrix is not always symmetric?

$\endgroup$
2
$\begingroup$

This is all from here: http://cims.nyu.edu/~holmes/teaching/asa15/Lecture2.pdf TLDR: your still using the spectral decomposition theorem; you just have to find the right symmetric matrix.

Detailed Balance

Let $P$ be your (say 2x2) transition matrix. It isn't symmetric. Let $\pi$ be the (1x2) stationary distribution vector. If the detailed balance equations hold, your Markov chain is reversible and this means that
$$ \left( \begin{array}{cc} \pi_1 & 0 \\ 0 & \pi_2 \end{array} \right) P = P' \left( \begin{array}{cc} \pi_1 & 0 \\ 0 & \pi_2 \end{array} \right). $$

If we define $$ \Lambda = \left( \begin{array}{cc} \sqrt{\pi_1} & 0 \\ 0 & \sqrt{\pi_2} \end{array} \right), $$ then you can re-write the above equation as $$ \Lambda^2P = P'\Lambda^2. $$

Using the Spectral Decomposition Theorem

The link above claims $V = \Lambda P \Lambda^{-1}$ is symmetric. This can be verified using the previous formula, left multiplying both sides by by $\Lambda$ and right multiplying both sides by $\Lambda^{-1}$.

By the spectral decomposition theorem, $V$ is orthogonally diagonalizable. The link calls its eigenvectors $w_j$, and its eigenvalues $\lambda_j$ (for $j=1,2$ in this case). So $Vw_j = \lambda_j w_j$ and $w_j' V = w_j \lambda_j$. Plugging in the definition of $V$, we get $$ \Lambda P \Lambda^{-1} w_j = \lambda_j w_j $$ and $$ w_j' \Lambda P \Lambda^{-1} = w_j' \lambda_j. $$ Premultiplying the former by $\Lambda^{-1}$ and the latter by $\Lambda$ we can verify the claim that $P$ has left eigenvectors $\psi_j = \Lambda w_j$ and right eigenvectors $\phi_j = \Lambda^{-1} w_j$. These could be written in terms of matrices as

$$ \left( \begin{array}{c} \psi_1' \\ \psi_2' \end{array} \right) P = \left( \begin{array}{c} \psi_1' \\ \psi_2' \end{array} \right) \left( \begin{array}{cc} \lambda_1 & 0 \\ 0 & \lambda_2 \end{array} \right) $$

$$ P (\phi_1 \phi_2) = \left( \begin{array}{cc} \lambda_1 & 0 \\ 0 & \lambda_2 \end{array} \right)(\phi_1 \phi_2). $$ Using the fact that $w_i'w_j = 0$ for $i \neq j$ and $1$ otherwise we can show that \begin{align*} P &= (\phi_1 \phi_2) \left( \begin{array}{c} \psi_1' \\ \psi_2' \end{array} \right) P (\phi_1 \phi_2) \left( \begin{array}{c} \psi_1' \\ \psi_2' \end{array} \right) \\ &= (\phi_1 \phi_2) \left( \begin{array}{c} \psi_1' \\ \psi_2' \end{array} \right) \left( \begin{array}{cc} \lambda_1 & 0 \\ 0 & \lambda_2 \end{array} \right)(\phi_1 \phi_2) \left( \begin{array}{c} \psi_1' \\ \psi_2' \end{array} \right) \\ &= (\phi_1 \phi_2) \left( \begin{array}{c} \psi_1' \\ \psi_2' \end{array} \right) \sum_k \lambda_k \phi_k \psi_k' \\ &=\sum_n\phi_n\psi_n' \sum_k \lambda_k \phi_k \psi_k' \\ &= \sum_k \lambda_k \phi_k \psi_k' \phi_k \psi_k \\ &= \sum_k \lambda_k \phi_k \psi_k. \end{align*}

$\endgroup$
1
$\begingroup$

The goal is finding the stationary distribution of the states. As the other answer mentioned, symmetric is not the key. "diagonalizable" is more important. See this post

One related posts. Properties of spectral decomposition I think you will be clear if you read the accepted answer in this post.

In the particular example in the question, the properties of a symmetric matrix have been confused with those of a positive definite one, which explains the discrepancies noted.

In addition, I personally feel this paper is explaining eigenvalue and eigenvector and iterative methods in a intuitive way. Feel free to check

https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf

$\endgroup$

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.