Fix any non-negative matrix $M \in \mathbb{R}_{\geq 0}^{m \times n}$ that contains no zero-row and no zero-column. Further, fix any positive vector $r \in \mathbb{R}_{> 0}^m$. With $nz(M) := \{(i,j) \ | \ M_{i,j} > 0\}$ the index set of non-zero-entries in $M$, and $\mathbf{1}$ the all-ones-vector, define the set

$$S_{r, W} := \{A \in \mathbb{R}_{\geq 0}^{m \times n} \ | \ A \mathbf{1} = r, \ nz(A) \subseteq nz(M)\}$$

of all non-negative matrices that have row sum $r$ at that have at least the zero-entries of $M$, that is $M_{i,j} = 0 \Rightarrow A_{i,j} = 0$. This set is non-empty, because $diag(r) \cdot diag(M \mathbf{1})^{-1} M \in S_{r, W}$.

Now consider the following set:

$$A_{r, W} := \{A \in \mathbb{R}^{m \times n} \ | \ A \mathbf{1} = r, \ nz(A) \subseteq nz(M)\} \quad \supseteq \quad S_{r, W}$$ which in contrast to $S_{r, W}$ allows for arbitrary matrices under these constraints.

It is easy to see that every affine combination of elements from $S_{r, W}$ gives some element from $A_{r, W}$, hence, the affine hull satisfies $$aff(S_{r, W}) \subseteq A_{r, W}.$$

I suppose that it even holds that $aff(S_{r, W}) \supseteq A_{r, W}$.

I tried to prove this by constructing an affine combination of non-negative matrices explicitly for any element from $A_{r, W}$, but I failed on this approach.

So, my question is how to prove this (if it is true at all)?

Is there probably even a more elegant argument, for example from the theory of convex polytopes, or by some neat characterization of the affine hull?


(The first part of this is the same as @Fedor's answer; I just carried out his algorithm.) Each row $i$ can be written as $a_i^{(1)}x_i^{(1)}+a_i^{(2)}x_i^{(2)}$ where $x_i^{(1)},x_i^{(2)}$ are non-negative row vectors of sum $r_i$ (formed by scaling the positive and negative entries in that row) and $a_i^{(1)}+a_i^{(2)}=1$. Then the whole matrix is $$ \sum_{1\le j_1,\ldots,j_m\le 2} a_1^{(j_1)}\cdots a_m^{(j_m)}\left[\begin{matrix}x_1^{(j_1)} \\ \cdots \\ x_1^{(j_m)} \end{matrix}\right] .$$ That method uses up to $2^m$ terms (some might be 0).

Now I'll show that far fewer terms are needed. All terms but one will have a single nonzero element in each row.

Consider $A\in A_{r,W}$. If there are no negative entries we are finished. Otherwise let $a_{ij}$ be any negative entry. Now take a matrix $B$ with one nonzero entry in each row (in a position where $A$ is nonzero), with those entries proportional to $r$, and with the nonzero entry in row $i$ being exactly $-a_{ij}$. Then $B$ is nonnegative and has row sums proportional to $r$, and moreover $A+B$ has row sums proportional to $A$ and at least one fewer negative entries. Continue in this fashion, removing at least one negative entry at a time, until only positive entries remain.

By this process you have written $A$ as a linear combination of nonnegative matrices with row sums proportional to $r$, so by scaling this gives $A$ as an affine combination of nonnegative matrices with row sums equal to $r$. The number of terms is at most equal to the number of negative entries, plus 1.

Added: Now I think that I missed the simplest solution. Form matrix $A^-$ from $A$ by setting all positive elements to 0 and negating the negative elements. Form matrix $A^+$ from $A$ by setting all negative elements to 0. Now we have $A=A^+ - A^-$, and therefore $A=(A^++B)-(A^-+B)$ for any $B$. I think it is elementary to choose nonnegative $B$ so that $A^++B$, and therefore $A^-+B$, has row sums proportional to $r$. So only two terms are needed.

  • $\begingroup$ I selected your answer as the correct one because of your really straightforward second solution (although the induction is neater). I feel sorry to gave up too early on a similar construction! $\endgroup$ – cubic lettuce Nov 30 '15 at 17:10
  • $\begingroup$ @cubic: Thanks. Either I'm delusional today or only two terms are needed, see my addition. $\endgroup$ – Brendan McKay Dec 1 '15 at 0:21
  • $\begingroup$ Your mind is in best order! This is the simplest but neatest solution. I like that the row sums of $A^- + B$ are implied by $A = A^+ - A^-$ to be proportional to $r$, which automatically yields an affine combination. However, in hindsight, my question may be used as a homework exercise rather than being a research level problem, so I apologize for asking that on MO. The problem surely gets more involved if one generalizes to arbitrary linear equality constraints on the entries in $A$ rather than just row sums. $\endgroup$ – cubic lettuce Dec 1 '15 at 9:20

In other words, you want to represent each matrix with given row sums as an affine combination of non-negative matrices with the same row sums (and no new non-zero entries). I do not see why not. Say, this is true for $m=1$, then induct on $m$: represent your matrix $A$ as an affine combination of matrices with the same last row as $A$ and non-negative elements in first $m-1$ rows. This is possible by induction proposition. Then for each of matrices in your representation change only last row. This is $m=1$ case.


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.