Casco afín de un conjunto de matrices no negativas con sumas de filas fijas

Question

Fijar cualquier matriz no negativa $M \in \mathbb{R}_{\geq 0}^{m \times n}$ que no contiene ninguna fila cero ni ninguna columna cero. Además, fijar cualquier vector positivo $r \in \mathbb{R}_{> 0}^m$ . En $nz(M) := \{(i,j) \ | \ M_{i,j} > 0\}$ el conjunto de índices de entradas no cero en $M$ y $\mathbf{1}$ el todo-uno-vector, definir el conjunto

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

de todas las matrices no negativas que tienen suma de filas $r$ que tengan al menos las entradas cero de $M$ es decir $M_{i,j} = 0 \Rightarrow A_{i,j} = 0$ . Este conjunto no es vacío, porque $diag(r) \cdot diag(M \mathbf{1})^{-1} M \in S_{r, W}$ .

Consideremos ahora el siguiente conjunto:

$$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}$$ que a diferencia de $S_{r, W}$ permite matrices arbitrarias bajo estas restricciones.

Es fácil ver que toda combinación afín de elementos de $S_{r, W}$ da algún elemento de $A_{r, W}$ por lo que el casco afín satisface $$aff(S_{r, W}) \subseteq A_{r, W}.$$

Supongo que incluso sostiene que $aff(S_{r, W}) \supseteq A_{r, W}$ .

Intenté demostrarlo construyendo una combinación afín de matrices no negativas explícitamente para cualquier elemento de $A_{r, W}$ pero fracasé en este enfoque.

Así pues, mi pregunta es cómo demostrarlo (si es que es cierto).

¿Es probable que exista un argumento más elegante, por ejemplo a partir de la teoría de los politopos convexos, o mediante alguna caracterización clara del casco afín?

Answer 1

En otras palabras, quieres representar cada matriz con sumas de fila dadas como una combinación afín de matrices no negativas con las mismas sumas de fila (y sin nuevas entradas distintas de cero). No veo por qué no. Digamos que esto es cierto para $m=1$ y luego induce en $m$ : represente su matriz $A$ como una combinación afín de matrices con la misma última fila que $A$ y elementos no negativos en primer $m-1$ filas. Esto es posible por proposición de inducción. A continuación, para cada una de las matrices en su representación cambiar sólo la última fila. Esto es $m=1$ caso.

Answer 2

(La primera parte es la misma que la respuesta de @Fedor; sólo he llevado a cabo su algoritmo). Cada fila $i$ puede escribirse como $a_i^{(1)}x_i^{(1)}+a_i^{(2)}x_i^{(2)}$ donde $x_i^{(1)},x_i^{(2)}$ son vectores fila no negativos de suma $r_i$ (formado escalando las entradas positivas y negativas de esa fila) y $a_i^{(1)}+a_i^{(2)}=1$ . Entonces toda la matriz es $$ \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] .$$ Este método utiliza hasta $2^m$ términos (algunos pueden ser 0).

Ahora demostraré que se necesitan muchos menos términos. Todos los términos menos uno tendrán un solo elemento distinto de cero en cada fila.

Considere $A\in A_{r,W}$ . Si no hay entradas negativas, hemos terminado. En caso contrario $a_{ij}$ sea cualquier entrada negativa. Tomemos ahora una matriz $B$ con una entrada distinta de cero en cada fila (en una posición en la que $A$ es distinto de cero), con las entradas proporcionales a $r$ y con la entrada distinta de cero en la fila $i$ siendo exactamente $-a_{ij}$ . Entonces $B$ es no negativo y tiene sumas de filas proporcionales a $r$ y además $A+B$ tiene sumas de filas proporcionales a $A$ y al menos una entrada negativa menos. Continúa así, eliminando al menos una entrada negativa cada vez, hasta que solo queden entradas positivas.

Mediante este proceso ha escrito $A$ como una combinación lineal de matrices no negativas con sumas de filas proporcionales a $r$ por lo que escalando esto da $A$ como una combinación afín de matrices no negativas con sumas de filas iguales a $r$ . El número de términos es como máximo igual al número de entradas negativas, más 1.

Añadido: Ahora creo que me he perdido la solución más sencilla. Formar matriz $A^-$ de $A$ poniendo todos los elementos positivos a 0 y negando los negativos. Formar matriz $A^+$ de $A$ poniendo todos los elementos negativos a 0. Ahora tenemos $A=A^+ - A^-$ y, por lo tanto $A=(A^++B)-(A^-+B)$ para cualquier $B$ . Creo que es elemental elegir no negativo $B$ para que $A^++B$ y, por lo tanto $A^-+B$ tiene sumas de filas proporcionales a $r$ . Por tanto, sólo se necesitan dos términos.