When Inverses of Stochastic Matrices Are Also Stochastic – Linear Algebra

inverselinear algebramatricesstochastic-matrices

A stochastic matrix, with elements $\in[0,1]$ and rows summing to 1 are known to have one eigenvalue 1 (stationary distribution) and the rest of lower magnitude. However I don't know about many results regarding their inverses.

  1. In which cases is it possible to find another stochastic matrix being the inverse to the first?
  2. If we can not find an inverse fulfilling the requirements, can we find some "pseudo" inverse?
  3. Can we "expand" the probability space to find a larger space where it is possible to find a matrix ?

EDIT: The closest I have come so far is to expand the space to double number of states and allowing elements > 1. Let us call the $N\times N$ probability transition matrix $\bf P$, then assuming $\bf P$ nonsingular we can calculate ${\bf P}^{-1}$, build the new matrices :

$${\bf P_e = P \otimes I}_2\hspace{1cm}{\bf P_{ie}} = |{\bf P}^{-1}|\otimes ({{\bf 1}_2{\bf 1}_2}^T-{\bf I}_2)^{(1-\text{sgn}({\bf P}))\otimes {\bf I}_2}$$

Where the $|\cdot|$ and power are scalar wise operations.

If we do this then of course $\bf P_{ie}P_e \neq I\hspace{1cm}\bf P_{e}P_{ie} \neq I$, but that is because we are not finished yet!

If we now turn each $2\times2$ block $\bf A$ into a scalar by the following calculation: $[1,0] {\bf A} [1,-1]^T$

And systematically apply to all blocks:

$$\cases{({\bf I}_N \otimes [1,0])({\bf P_{ie}P_e})({\bf I}_N \otimes [1,-1]^T)\\
({\bf I}_N \otimes [1,0])({\bf P_{e}P_{ie}})({\bf I}_N \otimes [1,-1]^T)}$$

  1. Now we do indeed get identities!
  2. Row sums of $\bf P_{ie}$ equals 1 if we treat every second bin as $-1$ (as the construction above does).
  3. But how to interpret the elements of $\bf {P_{ie}}$ which can be >1 ?

Furthermore $\sum_j |({\bf P_{ie}})_{ij}|$ seems to be a measure of the confusion, it goes to $\infty$ as ${\bf P} \to \frac{1}{N^2}{{\bf 1}_N} {{\bf 1}_N}^T$ which is indeed the maximally confusing distribution as we lose all information except the mean values ( all other eigenvalues except stationary distribution will be 0 ).

Best Answer

The only stochastic matrices with a stochastic inverse are the permutation matrices. If $A$ and $B$ are stochastic, then all entries of $AB$ are non-negative. The only way $(AB)_{ij}$ can be zero is if the "support" of row $i$ of $A$ and column $j$ of $B$ are disjoint. So if $AB=I$ we need row $1$ of $A$ to be orthogonal to columns $2,\ldots,n$ of $B$. As these columns must be linearly independent, then row $1$ of $A$ can only have one non-zero entry. Continuing, all rows of $A$ have only one nonzero entry etc.

Related Question