On the existence of sequences and matrices with prescribed partial sums of elements (Q1369346)

To simplify the description of this paper we shall use the following notation: If \(x_{1},\ldots ,x_{n}\) is an list of real numbers and \(V \subseteq \{1,\ldots ,n\}\), then \(x[V] := \sum_{i\in V}x_{i}\). The main tool of this paper is the following theorem (Theorem 2.7). Let \([\ell _{1},u_{1}],\ldots , [\ell _{p},u_{p}]; [r_{1},R_{1}],\ldots ,[r_{s},R_{s}]\); and \([c_{1},C_{1}],\ldots ,[c_{t},C_{t}]\) be lists of closed real intervals. Suppose that \(\{S_{1},\ldots ,S_{s}\}\) and \(\{T_{1},\ldots ,T_{t}\}\) are partitions of \(\{1,\ldots ,p\}\) such that \(|S_{i} \cap T_{j}|\leq 1\) for all \(i,j\). Then the following are equivalent: (i) there exist \(A_{1},\ldots ,A_{p}\) with \(\ell _{i} \leq A_{i} \leq u_{i}\) for \(i = 1,\ldots ,p\) such that \(r_{i} \leq A[S_{i}] \leq R_{i}\) and \(c_{j} \leq A[T_{j}] \leq C_{j}\) for all \(i,j\); (ii) for all \(\alpha \subseteq \{1,\ldots ,s\}\) and \(\beta \subseteq \{1,\ldots ,t\}\) we have \(\min(R[\alpha ]-c[\beta ],C[\beta ^{c}]-r[\alpha ^{c}]) \geq l[\gamma \backslash \delta ]-u[\delta \backslash \gamma ]\) where \(\beta ^{c}\) and \(\alpha ^{c}\) are the complementary sets, \(\gamma := \bigcup_{i\in \alpha }S_{i}\) and \(\delta := \bigcup_{j\in \beta }T_{j}\). The proof of this theorem is based on the Hoffman circulation theorem. This result is applied to obtain theorems about the existence of matrices for which various sign patterns or row and column sums are prescribed, and about square matrices A with given zero pattern where \(A + A^{T}\) is prescribed. The paper concludes with a section on Hadamard adjustments.