1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – ziutek Mar 8 '15 at 12:15
  • $\begingroup$ @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. $\endgroup$ – Marc van Leeuwen Mar 8 '15 at 12:32

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.