On Restricted Nonnegative Matrix Factorization
  Nonnegative matrix factorization (NMF) is the problem of decomposing a given
nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times
d$ matrix $W$ and a nonnegative $d \times m$ matrix $H$. Restricted NMF
requires in addition that the column spaces of $M$ and $W$ coincide. Finding
the minimal inner dimension $d$ is known to be NP-hard, both for NMF and
restricted NMF. We show that restricted NMF is closely related to a question
about the nature of minimal probabilistic automata, posed by Paz in his seminal
1971 textbook. We use this connection to answer Paz's question negatively, thus
falsifying a positive answer claimed in 1974. Furthermore, we investigate
whether a rational matrix $M$ always has a restricted NMF of minimal inner
dimension whose factors $W$ and $H$ are also rational. We show that this holds
for matrices $M$ of rank at most $3$ and we exhibit a rank-$4$ matrix for which
$W$ and $H$ require irrational entries.
