Decomposing a stochastic matrix into a product of stochastic matrices

1k Views Asked by At

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.