4
$\begingroup$

This question is about extending a result on transportation polytopes from Brualdi regarding $m\times n$ matrices to the case when $m=\infty$.

Notation: Denote an $m\times n$ matrix by $A=[a_{i,j}]$, and consider sets $K\subset\lbrace 1,2,\ldots, m\rbrace$ and $J\subset \lbrace 1,2,\ldots, n\rbrace$. Define $$A[K,J):=[a_{i,j}:i\in K, j\in\lbrace 1,2,\ldots,n\rbrace-J].$$

Denote by $N(R,S)$ by the class of all $m\times n$ nonnegative matrices with row sum given by the positive vector $R=(r_1,\ldots, r_m)$ and column sum given by the positive vector $S=(s_1,\ldots, s_n)\,\,\,$ ($N(R,S)$ is called a transportation polytope).

The following theorem is from Brualdi's Combinatorial Matrix Classes:enter image description here

I am trying to construct an $\infty\times n$ matrix with $\sum_{m=1}^{\infty}r_m = \sum_{j=1}^ns_j=1.$ Will this theorem also hold when $m=\infty$? I tried extending the proof to the case $m=\infty$, but Brualdi's proof heavily relies on the fact that $m$ is finite.

Update: Here's what I have. Let $r_i', s_j'$ denote the row and column sums in the case $m=\infty$. For a particular example, I can apply this theorem to prove the existence a $m\times n$ matrix for all sufficiently large $m$, where the column sums will necessarily be less than $s_j'$ (let's say $s_j' \epsilon$, where $\epsilon$ tends to 1 as $m$ tends to $\infty$) and I am able to verify the inequality after we replace $m$ with infinity, but I am not sure if this implies the existence of the $\infty \times n$ matrix.

$\endgroup$
  • $\begingroup$ If I am understanding your question correctly (what is a pattern?), you are looking for a generalization of the infinite Hall marriage theorem. Maybe you can generalize one of its proofs? $\endgroup$ – darij grinberg Oct 18 '17 at 8:17
  • $\begingroup$ @ darij grinberg, it means that $A$ has $0$'s at entries $(i,j) $for which $W$ has a zero, and $A$ has a positive number at $(i,j)$ in locations for which $W$ has a $1$. @PeterTaylor I closed the other one. $\endgroup$ – The Substitute Oct 18 '17 at 8:26
  • $\begingroup$ but is $n$ finite? $\endgroup$ – Fedor Petrov Oct 18 '17 at 11:42
  • $\begingroup$ @FedorPetrov Yes. $\endgroup$ – The Substitute Oct 18 '17 at 17:30
  • $\begingroup$ Oh, then it isn't a generalization of infinite Hall. The condition that the sum of the $r_i$ equals the sum of the $s_j$ shows that only finitely many $r_i$ are nonzero; then, the whole thing follows from the finite version. $\endgroup$ – darij grinberg Oct 18 '17 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.