Combinatorics of nonnegative matrices / V. N. Sachkov, V. E. Tarakanov ; translated by Valentin F. Kolchin.

Format:

Book

Author/Creator:

Sachkov, Vladimir Nikolaevich.

Contributor:

Tarakanov, V. E. (Valeriĭ Evgenʹevich)

Series:

Translations of mathematical monographs 0065-9282 ; v. 213.

Translations of mathematical monographs, 0065-9282 ; v. 213

Standardized Title:

Kombinatorika neotrit͡satelʹnykh matrit͡s. English

Language:

English

Russian

Subjects (All):

Non-negative matrices.

Combinatorial analysis.

Physical Description:

ix, 269 pages : illustrations ; 26 cm.

Place of Publication:

Providence, R.I. : American Mathematical Society, [2002]

Contents:

Chapter 1. Matrices and Configurations 1

1.2. Term rank. Arrangement of positive elements 9

1.3. Combinatorial theory of cyclic matrices 27

Chapter 2. Ryser Classes 45

2.1. A constructive description of Ryser classes 46

2.2. Invariant sets 58

2.3. Estimates of the term rank 69

Chapter 3. Nonnegative Matrices and Extremal Combinatorial Problems 83

3.1. Forbidden configurations 84

3.2. Covering problem 90

3.3. The van der Waerden-Egorychev-Falikman Theorem 106

Chapter 4. Asymptotic Methods in the Study of Nonnegative Matrices 117

4.1. Nonnegative matrices and graphs 118

4.2. Asymptotics of the number of primitive (0, 1)-matrices 131

4.3. Asymptotics of the permanent of a random (0, 1)-matrix 135

4.4. Random lattices and Boolean algebras 138

4.5. Coverings of sets and (0, 1)-matrices 143

4.6. Random coverings of sets 151

Chapter 5. Totally Indecomposable, Chainable, and Prime Matrices 159

5.1. Totally indecomposable and chainable matrices 161

5.2. Rectangular nonnegative matrices 170

5.3. Rectangular nonnegative chainable matrices 184

5.4. Extension of partial diagonals 192

5.5. Prime Boolean matrices 199

5.6. Prime nonnegative matrices 208

Chapter 6. Sequences of Nonnegative Matrices 213

6.1. Directed graphs of nonnegative matrices 215

6.2. Irreducible and primitive matrices 221

6.3. Tournament matrices 227

6.4. Associated operator 232

6.5. Sequences of powers of a nonnegative matrix 243

6.6. Ergodicity of sequences of nonnegative matrices 250.

Notes:

Includes bibliographical references (pages 263-266) and index.

ISBN:

082182788X

OCLC:

50004639