It is well-known that any square real matrix of small rank $k$ can be decomposed into a product of a skinny matrix with $k$ columns and a fat matrix with $k$ rows by means of an SVD. This question is about whether something similar can be said about stochastic matrices.

By a stochastic matrix I mean any matrix in $\mathbb{R}^{m \times n}$ with non-negative entries and which satisfies the condition $M1 = 1$, i.e. rows sum to one ($1$ denotes a column vector of ones). In particular, the matrix need not be square. Of course a non-square stochastic matrix does not correspond to any Markov chain, but we can still study such objects algebraically.

The question is this. Given a stochastic $n \times n$ matrix of rank $k < n$ (indeed typically $k \ll n$), is it always possible to factor it into a product of two stochastic matrices of sizes $n \times k$ and $k \times n$?

If not, is it possible to at least factor it into a product of two stochastic matrices of sizes $n \times l$ and $l \times n$, where $l = O(k)$?

Ideally, I would like a constructive answer, i.e. an efficient way of defining the factoring.

I suspect this question must have been studied before, so if there is a large body of literature already there, please just post a pointer to an introductory book / paper.

  • $\begingroup$ Do you agree that $A=PQ$, where $A,P$ and $Q$ are stochastic, if and only if the convex hull of the rows of $Q$ contains the rows of $A$? So your question is about the smallest number of vectors, with non negative entries whose sum is 1, such that the convex hull of these vectors contains the rows of $A$. It might be possible to give a counterexample for your first question, but I don't know how to do it. $\endgroup$ – Daniel Sep 9 '14 at 11:41
  • $\begingroup$ can I ask a related question, suppose you have such a decomposition, in which way you want to apply it? $\endgroup$ – maomao May 21 '15 at 22:18

Your Answer

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

Browse other questions tagged or ask your own question.