Book contents
- Frontmatter
- Contents
- Editor's Statement
- Section Editor's Foreword
- Preface
- Chapter 1 The Theory of Permanents in the Historical Order of Development
- Chapter 2 Properties of Permanents
- Chapter 3 (0,1)-Matrices
- Chapter 4 Lower Bounds for Permanents
- Chapter 5 The van der Waerden Conjecture
- Chapter 6 Upper Bounds for Permanents
- Chapter 7 Evaluation of Permanents
- Chapter 8 More about Permanents
- Bibliography
- Index to Bibliography
- Index of Notation
- Index
Chapter 3 - (0,1)-Matrices
Published online by Cambridge University Press: 05 June 2013
- Frontmatter
- Contents
- Editor's Statement
- Section Editor's Foreword
- Preface
- Chapter 1 The Theory of Permanents in the Historical Order of Development
- Chapter 2 Properties of Permanents
- Chapter 3 (0,1)-Matrices
- Chapter 4 Lower Bounds for Permanents
- Chapter 5 The van der Waerden Conjecture
- Chapter 6 Upper Bounds for Permanents
- Chapter 7 Evaluation of Permanents
- Chapter 8 More about Permanents
- Bibliography
- Index to Bibliography
- Index of Notation
- Index
Summary
Incidence Matrices
Matrices all of whose entries are either 0 or 1—that is, (0, 1)-matrices—play an important part in linear algebra, combinatorics, and graph theory. In some of these applications it is at times preferable to consider 1 as the “all” element in a Boolean algebra, or the identity element in a field of two elements. In what follows, however, the symbol 1 will represent the positive integer 1, since we shall be mainly concerned with enumerations of systems of distinct representatives and with related problems in the theory of permanents.
Many problems in the theory of nonnegative matrices depend only on the distribution of zero entries. In such cases the relevant property of each entry is whether it is zero or nonzero, and the problem can be often simplified by substituting for the given matrix the (0, 1)-matrix with exactly the same zero pattern.
Definition 1.1. Two m×n matrices A=(aij) and B = (bij) are said to have the same zero pattern if aij = 0 implies bij = 0, and vice versa.
Suppose that A, B, C, and D are nonnegative n-square matrices, and that A has the same zero pattern as B, and C has the same zero pattern as D. Then clearly A + C has the same zero pattern as B + D, and AC has the same zero pattern as BC.
- Type
- Chapter
- Information
- Permanents , pp. 29 - 50Publisher: Cambridge University PressPrint publication year: 1984