4
$\begingroup$

Given a rank $2r$ matrix $M\in\Bbb Q^{n\times n}$ can we find two matrices $M_+\in\Bbb Q_{\geq0}^{n\times n}$ and $M_-\in\Bbb Q_{\geq0}^{n\times n}$ each of rank $r$ such that $M=M_+-M_-$ holds?

Though $M=AB$ where $A,B'\in\Bbb Q^{n\times 2r}$ are rank $2r$ and we can rewrite this as $$M=(A_+B'_++A_-B'_-)-(A_+B'_-+A_-B'_+)$$ where $A_+,A_-,B'_+,B'_-\in\Bbb Q_{\geq0}^{n\times 2r}$ holds it is unclear even $$rank(A_+B'_++A_-B'_-)=rank(A_+B'_-+A_-B'_+)=2r$$ holds while I seek $M_+-M_-$ as rank $r$ which is minimum possible.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

No, you can't always find two such matrices.

Let $n \gt 2$. Choose a $2$-dimensional subspace $V$ of $\mathbb{Q}^n$ that does not intersect the positive orthant except at $\vec 0$. Let $M$ be a matrix whose columns span $V$. Any decomposition of $M$ into $M_+ - M_-$, with each of these of rank $1$ and in $\mathbb{Q}^{n\times n}_{\ge 0}$ would produce a basis for $V$ consisting of vectors from the positive orthant, which by construction was impossible. In fact, we can't decompose $M$ as a difference of rank-$1$ matrices if we require even one of them to be all-nonnegative.

Example: $ \begin{pmatrix} -2 & 1 & 1 \newline 1 & -2 & 1 \newline 1 & 1 & -2 \end{pmatrix}$ has a column space consisting of vectors of sum $0$, which does not intersect the positive orthant except at $\vec{0}$ so it can't be decomposed this way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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