Let $A\in\mathcal{M}_n(\mathbb{R})$ be a square matrix, and $N\geq n$. Is there a necessary (and possibly sufficient as well) condition (on $A,S,Q$) for the existence of a decomposition $$ A = QS $$ where $Q\in\mathcal{M}_{n,N}(\mathbb{R})$ is arbitrary, and $S\in\mathcal{M}_{N,n}(\mathbb{R})$ is stochastic (non-negative and each column summing to one)?
(Since I am trying to rule out a special kind of decomposition where no column of $S$ has a coefficient equal to one, I'd be happy for instance with a necessary condition being $S$ needs to have a 1 in at least one column)
If not, what about assuming further that (either or both)
- $A$ is invertible (with determinant $1$)?
- $A$ has integer coefficients?
I could not recall any result of this sort, and am at a loss on what keywords to look for in the literature (looking for "factorization stochastic matrix" lleads to a lot of papers on the dictionary problem, or NMF, which are not AFAIK what I am looking for).
Pick $S$ to be any non-identity stochastic invertible matrix.** Let $Q = AS^{-1}$. Then $A = QS$.
And that's why there isn't a name for this decomposition. :)
[BTW, this argument fails for dimension $1$, because there's only one stochastic matrix, the identity. But it works in all other dimensions.]
** One technique: pick $n$ random vectors $v_1, \ldots, v_n$ in the first octant; with probability $1$, they're linearly independent. Scale each so that the sum of its entries is one. They're still linearly independent. Now use these scaled vectors as the columns of your matrix.