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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .