On the properties of interchange operations in classes of \((0,1)\)- matrices
type: Item
instance of: scholarly article
title: On the properties of interchange operations in classes of \((0,1)\)- matrices
zbMATH Open document ID: 0795.05094
DOI: 10.1007/BF01210228
author: V. E. Tarakanov
published in: Mathematical Notes
publication date: 1994-07-13T00:00:00Z
review text: 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 R…
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 567922
zbMATH Keywords: (0,1)-matrices
zbMATH Keywords: Ryser class
zbMATH Keywords: boundary rank
zbMATH Keywords: interchange operation
zbMATH Keywords: interchange matrices
MaRDI profile type: Publication
cites work: Matrices of zeros and ones with fixed row and column sum vectors
cites work: Combinatorial Properties of Matrices of Zeros and Ones
cites work: A theorem on flows in networks
full work available at URL: https://doi.org/10.1007/bf01210228
OpenAlex ID: W2064409923
description: scientific article; zbMATH DE number 567922