Affine hull of a set of non-negative matrices with fixed row-sums

Question

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?

Answer 1

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

Answer 2

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.