Multiplicities and Minimal Widths for (0, 1)-Matrices

Abstract

In a previous paper (1) the notion of the α-width ∈_A(α) of a (0, 1)-matrix A was introduced, and a formula for the minimal α-width taken over the class of all (0, 1)-matrices having the same row and column sums as A, was obtained. The main tool in arriving at this formula was a block decomposition theorem (1, Theorem 2.1; repeated below as Theorem 2.1) that established the existence, in the class generated by A, of certain matrices having a simple block structure. The block decomposition theorem does not itself directly involve the notion of minimal α-width, but rather centres around a related class concept, that of multiplicity. We review both of these notions in § 2, together with some other pertinent definitions and results.