# Does this matrix have nonnegative entries?

All inequalities in this post are meant element-wise. Consider a stochastic $n \times n$ matrix $P$, i.e. $P \geq 0, P1 = 1$, where $1$ is a vector of ones. Consider a matrix $A$ of size $n \times m$, $A \geq 0$, whose span includes the row space of $P$. Therefore we have $AA^\dagger P^\top = P^\top$, where $\dagger$ denotes the Moore-Penrose pseudoinverse. Assume further that $A$ has independent columns and $m < n$.

Is it true that $A^\dagger P^\top A \geq 0$ ?

This question is a modification of this post, with an additional assumption on $A$.

Edit: I am also interested in the case where the structure of $A$ is additionally constrained as follows: The columns of $A$ contain a basis for the column space of $P^\top$, selected from the columns of $P^\top$, they can also contain other elementwise non-negative vectors.

## 1 Answer

No. My first try was $$P=\frac1{10}\pmatrix{1&9\\9&1}, \quad A=\pmatrix{1&5\\0&1}, \quad A^\dagger=\pmatrix{1&-5\\0&1} \quad A^\dagger P^TA=\frac1{10}\pmatrix{-44&-216\\9&46}\not\geq 0.$$ Now of course I ignored the $m<n$ diktat. Let me pay some lip service to that. $$P^T=\frac1{10}\pmatrix{1&9&5\\9&1&5\\0&0&0}, \quad A=\pmatrix{1&5\\0&1\\0&0}, \quad A^\dagger=\pmatrix{1&-5&0\\0&1&0}$$ and we still have $$A^\dagger P^TA=\frac1{10}\pmatrix{-44&-216\\9&46}\not\geq 0.$$

• Thank you for the excellent answer. I'm still unsure whether a counterexample can be found under the additional constraint (which I didn't include in the original question), that the columns of $A$ do not just contain a basis for the range of $P^\top$, but contain a basis which is a verbatim subset of the columns of $P^\top$. – ziutek Mar 8 '15 at 12:15
• @ziutek: You probably won't change the verdict by adding additional hypotheses, unless you have an idea that such hypotheses could possibly be useful in a proof. For the hypothesis you add now, I don't see how it could be useful. – Marc van Leeuwen Mar 8 '15 at 12:32