Suppose $$Q = \{q_{ij}\}$$ with $\sum\limits_j q_{ij} = 1,\quad |q_{ij}|\leq1$ is the transition matrix of a Markov chain. Then how to find the square root of $Q,$ namely $$R^2 = Q.$$ One way I used is using the Taylor expansion of $\sqrt{x},$ since every entry of $Q$ is smaller than $1,$ then $Q^n$ should be convergent. But is there any better way to computer the square root of a matrix?

  • $\begingroup$ It's not "the" square root, but rather "a" square root: in general, a matrix has a lot of square roots. Maybe, you want the square root to be a stochastic matrix as well, then it is a different story. In any case, you should try to use the Jordan decomposition. $\endgroup$ – zhoraster Jul 17 '17 at 6:36
  • $\begingroup$ @zhoraster It's a deterministic matrix. But even for the Jordan form, it's not easy to obtain the square root. $\endgroup$ – A.Oreo Jul 17 '17 at 6:49
  • $\begingroup$ By a stochastic matrix, I mean a one having non-negative entries and row sum 1. A transition matrix, if you like. For a Jordan matrix, it is rather straightforward to compute a square root. $\endgroup$ – zhoraster Jul 17 '17 at 6:53
  • $\begingroup$ @zhoraster That's my matrix. $\endgroup$ – A.Oreo Jul 17 '17 at 6:58
  • $\begingroup$ What's "that's" your matrix? Concerning the Taylor expansion, note that there is no Taylor expansion of $\sqrt{x}$ at zero. If you expand around another point, this is quite tricky. $\endgroup$ – zhoraster Jul 17 '17 at 7:01

The problem of finding a stochastic square root to a stochastic matrix (where again, a "stochastic" matrix is just a "transition" matrix; all matrices here are deterministic) is very non-trivial. Here is a paper on that very problem (this paper talks about finding $p$th roots, but finding square roots isn't all that much easier than the general case).

Notably, fact 4.1 says that there exist some transition matrices that have no square roots of any kind, let alone those that happen to be transition matrices themselves. For instance, $$ A = \pmatrix{0&1&0\\0&0&1\\0&0&1} $$


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.