How to reorder matrix to its canonical form (Markov chain)?

Question

Is it possible to rearrange this matrix in its canonical form (link below)? I have searched numerous websites and videos and have only found answers for small matrices where you automatically get the identity matrix just by rearranging the rows. How can I do that here if the absorbing states are all even states?

The matrix I have is: $$ \begin{bmatrix} 1/6 & 1/6 & 1/6 & 0 & 1/6 & 0 & 1/6 & 0 & 1/6 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/6 & 0 & 1/6 & 1/6 & 1/6 & 0 & 1/6 & 0 & 1/6 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/6 & 0 & 1/6 & 0 & 1/6 & 1/6 & 1/6 & 0 & 1/6 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1/6 & 0 & 1/6 & 0 & 1/6 & 0 & 1/6 & 1/6 & 1/6 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1/6 & 0 & 1/6 & 0 & 1/6 & 0 & 1/6 & 0 & 1/6 & 1/6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$ The canonical form is the block matrix form $$ P = \left[\!\begin{array}{c|c}Q & R \\ \hline 0 & I\end{array}\!\right] $$

Answer 1

For this to make sense, you have to understand what you're doing when you're rearranging the rows and columns of the matrix, and why you're allowed to do it without getting a completely unrelated transition matrix.

The $(i,j)$ entry of a transition matrix tells you the probability of going from the $i^{\text{th}}$ state to the $j^{\text{th}}$ state. But deciding which state is the $1^{\text{st}}$ state, which is the $2^{\text{nd}}$ state, and so on - that's often arbitrary. So if you number the states of a Markov chain, you get a transition matrix; if you number them differently, you get a different transition matrix.

The canonical form of the transition matrix is simply the one where all absorbing states get numbered last. So how do we get there from here? We renumber the states. However, the number of a state tells us two things: which row it corresponds to, and which column. As a consequence, we are allowed to reorder the rows however we like, provided we reorder the columns in the same way.

In your case, you've identified the even-numbered states as the absorbing states. So the rearrangement you should apply is:

1. First, reorder the rows: put rows $1, 3, 5, 7, 9$ first, and rows $2, 4, 6, 8, 10$ after them.
2. Second, reorder the columns in the same way: put columns $1, 3, 5, 7, 9$ (of the matrix you got after step 1) first, and columns $2, 4, 6, 8, 10$ after them.