On joint realization of (0,1) matrices (Q1115506): Difference between revisions

Consider nonnegative integral vectors \(R=(r_ 1,...,r_ m)\), \(S=(s_ 1,...,s_ n)\), \(R'=(r'_ 1,...,r'_ m)\), \(S'=(s'_ 1,...,s'_ n)\). Denote by \({\mathcal A}(R,S)\) the class of (0,1) matrices with row sum vector R and column sum vector S. The three classes \({\mathcal A}(R,S)\), \({\mathcal A}(R',S')\), \({\mathcal A}(R+R',S+S')\) are called jointly realizable if there exist matrices A in \({\mathcal A}(R,S)\) and B in \({\mathcal A}(R',S')\) such that \(A+B\in {\mathcal A}(R+R',S+S')\). Suppose all these classes nonempty but not jointly realizable, then the existence of a matrix having one of the unavoidable configuration \[ \begin{pmatrix} 1 & 1 & \\ 1 & 0 & \\ 0 & 0 & \end{pmatrix},\quad \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} \] in the first two classes is shown. A similar theorem about unavoidable configurations in \({\mathcal A}(R+R',S+S')\) is proved. A slight generalization of Anstee's theorem by \textit{R. A. Brualdi} [ibid. 33, 159- 231 (1980; Zbl 0448.05047)], regarding joint realization of matrices with one of the classes having row sums differing by at most 1, is proved.