On the properties of interchange operations in classes of \((0,1)\)- matrices (Q1326083)

We will study certain connections between (0,1)-matrices belonging to the same Ryser class. Let \(R\) and \(S\) be two vectors with nonnegative integer coordinates of dimensions \(m\) and \(n\), respectively. We use the notation \({\mathfrak A}^{m,n} (R,S)\) for the class of all \((0,1)\)-matrices with vector of row sums \(R\) and vector of column sums \(S\) (we will sometimes omit the indices \(m\) and \(n)\). These classes were introduced at the end of the 1950's by H. J. Ryser and D. A. Gale. They have been studied in detail in publications of Ryser, Falkerson, Haber, Brualdi and numerous other mathematicians. One of the fundamental combinatorial characteristics of a nonnegative matrix \(A\) is its boundary rank: the largest number of positive elements in a matrix such that no two of them appear in the same line, i.e., in one row or column. We denote the boundary rank of a matrix \(A\) by \(\rho (A)\). According to a familiar theorem of König, \(\rho (A)\) is equal to the smallest possible number of lines that cover all positive elements of the matrix \(A\). Suppose that we are given some set of ones in a \((0,1)\)-matrix. We say that these ones are independent if no two of them lie on the same line. If the boundary rank of a \((0,1)\)-matrix \(A\) is equal to \(\rho\), then we say that any \(\rho\) independent ones are basic. Consider the following two \(2 \times 2\) \((0,1)\)-matrices: \[ {\mathcal G} = {1 \;0 \choose 0 \;1}, \quad \overline {\mathcal G} = {0 \;1 \choose 1 \;0}. \] These matrices are used to define the interchange operation in a \((0,1)\)- matrix \(A\): Some submatrix in \(A\) of the form \({\mathcal G}\) is replaced by the submatrix \(\overline {\mathcal G}\), or, conversely, a submatrix of the form \(\overline {\mathcal G}\) in \(A\) is replaced by the submatrix \({\mathcal G}\). The matrices \({\mathcal G}\) and \(\overline {\mathcal G}\) are called interchange matrices. The interchange operation plays a very important role in the study of Ryser classes. When this operation is applied, a given matrix is carried into another matrix of the same class. Furthermore, as Ryser proved, any two matrices of the same class can be transformed into each other by some sequence of interchange operations. We will also establish other properties of the interchange operation, including a generalization of one of Ryser's results.