Matrices and Matroids for Systems Analysis (eBook)

Kazuo Murota (Autor)

eBook Download: PDF

2009 | 2000
XII, 483 Seiten
Springer Berlin (Verlag)
978-3-642-03994-2 (ISBN)

Infos

A matroid is an abstract mathematical structure that captures combinatorial properties of matrices. This book offers a unique introduction to matroid theory, emphasizing motivations from matrix theory and applications to systems analysis.

This book serves also as a comprehensive presentation of the theory and application of mixed matrices, developed primarily by the present author in the 1990's. A mixed matrix is a convenient mathematical tool for systems analysis, compatible with the physical observation that 'fixed constants' and 'system parameters' are to be distinguished in the description of engineering systems.

This book will be extremely useful to graduate students and researchers in engineering, mathematics and computer science.

From the reviews:

'...The book has been prepared very carefully, contains a lot of interesting results and is highly recommended for graduate and postgraduate students.'

András Recski, Mathematical Reviews Clippings 2000m:93006

Inhalt

Algorithms and Combinatorics 2
Preface 5
Contents 9
Introduction to Structural Approach --- Overview of the Book 13
Structural Approach to Index of DAE 13
Index of Differential-algebraic Equations 13
Graph-theoretic Structural Approach 15
An Embarrassing Phenomenon 19
What Is Combinatorial Structure? 22
Two Kinds of Numbers 23
Descriptor Form Rather than Standard Form 27
Dimensional Analysis 29
Mathematics on Mixed Polynomial Matrices 32
Formal Definitions 32
Resolution of the Index Problem 33
Block-triangular Decomposition 38
Matrix, Graph, and Matroid 42
Matrix 42
Polynomial and Algebraic Independence 42
Determinant 44
Rank, Term-rank and Generic-rank 47
Block-triangular Forms 51
Graph 54
Directed Graph and Bipartite Graph 54
Jordan--Hölder-type Theorem for Submodular Functions 59
Dulmage--Mendelsohn Decomposition 66
Maximum Flow and Menger-type Linking 76
Minimum Cost Flow and Weighted Matching 78
Matroid 82
From Matrix to Matroid 82
Basic Concepts 84
Examples 88
Basis Exchange Properties 89
Independent Matching Problem 95
Union 104
Bimatroid (Linking System) 108
Physical Observations for Mixed Matrix Formulation 117
Mixed Matrix for Modeling Two Kinds of Numbers 117
Two Kinds of Numbers 117
Mixed Matrix and Mixed Polynomial Matrix 126
Algebraic Implication of Dimensional Consistency 130
Introductory Comments 130
Dimensioned Matrix 131
Total Unimodularity of a Dimensioned Matrix 133
Physical Matrix 136
Physical Matrix 136
Physical Matrices in a Dynamical System 138
Theory and Application of Mixed Matrices 141
Mixed Matrix and Layered Mixed Matrix 141
Rank of Mixed Matrices 144
Rank Identities for LM-matrices 145
Rank Identities for Mixed Matrices 149
Reduction to Independent Matching Problems 152
Algorithms for the Rank 155
Structural Solvability of Systems of Equations 163
Formulation of Structural Solvability 163
Graphical Conditions for Structural Solvability 166
Matroidal Conditions for Structural Solvability 170
Combinatorial Canonical Form of LM-matrices 177
LM-equivalence 177
Theorem of CCF 182
Construction of CCF 185
Algorithm for CCF 191
Decomposition of Systems of Equations by CCF 197
Application of CCF 201
CCF over Rings 209
Irreducibility of LM-matrices 212
Theorems on LM-irreducibility 212
Proof of the Irreducibility of Determinant 215
Decomposition of Mixed Matrices 221
LU-decomposition of Invertible Mixed Matrices 222
Block-triangularization of General Mixed Matrices 225
Related Decompositions 231
Decomposition as Matroid Union 231
Multilayered Matrix 235
Electrical Network with Admittance Expression 238
Partitioned Matrix 240
Definitions 241
Existence of Proper Block-triangularization 245
Partial Order Among Blocks 248
Generic Partitioned Matrix 250
Principal Structures of LM-matrices 260
Motivations 260
Principal Structure of Submodular Systems 262
Principal Structure of Generic Matrices 264
Vertical Principal Structure of LM-matrices 267
Horizontal Principal Structure of LM-matrices 271
Polynomial Matrix and Valuated Matroid 280
Polynomial/Rational Matrix 280
Polynomial Matrix and Smith Form 280
Rational Matrix and Smith--McMillan Form at Infinity 281
Matrix Pencil and Kronecker Form 284
Valuated Matroid 289
Introduction 289
Examples 290
Basic Operations 291
Greedy Algorithms 294
Valuated Bimatroid 296
Induction Through Bipartite Graphs 299
Characterizations 304
Further Exchange Properties 309
Valuated Independent Assignment Problem 315
Optimality Criteria 317
Application to Triple Matrix Product 325
Cycle-canceling Algorithms 326
Augmenting Algorithms 334
Theory and Application of Mixed Polynomial Matrices 340
Descriptions of Dynamical Systems 340
Mixed Polynomial Matrix Descriptions 340
Relationship to Other Descriptions 341
Degree of Determinant of Mixed Polynomial Matrices 344
Introduction 344
Graph-theoretic Method 345
Basic Identities 346
Reduction to Valuated Independent Assignment 349
Duality Theorems 352
Algorithm 357
Smith Form of Mixed Polynomial Matrices 364
Expression of Invariant Factors 364
Proofs 372
Controllability of Dynamical Systems 373
Controllability 373
Structural Controllability 374
Mixed Polynomial Matrix Formulation 381
Algorithm 384
Examples 388
Fixed Modes of Decentralized Systems 393
Fixed Modes 393
Structurally Fixed Modes 396
Mixed Polynomial Matrix Formulation 399
Algorithm 404
Examples 407
Further Topics 412
Combinatorial Relaxation Algorithm 412
Outline of the Algorithm 412
Test for Upper-tightness 416
Transformation Towards Upper-tightness 422
Algorithm Description 426
Combinatorial System Theory 427
Definition of Combinatorial Dynamical Systems 428
Power Products 429
Eigensets and Recurrent Sets 431
Controllability of Combinatorial Dynamical Systems 435
Mixed Skew-symmetric Matrix 440
Introduction 440
Skew-symmetric Matrix 442
Delta-matroid 447
Rank of Mixed Skew-symmetric Matrices 453
Electrical Network Containing Gyrators 455
References 462
Notation Table 478
Index 478

Produkt-Details

• Erscheint lt. Verlag: 27.10.2009
• Reihe/Serie: Algorithms and Combinatorics
• Reihe/Serie: Algorithms and Combinatorics
• Zusatzinfo: XII, 483 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
• Themenwelt: Naturwissenschaften ► Chemie
• Themenwelt: Technik
• Schlagworte: Algebra • algorithm • algorithms • Analysis • combinatorics • Diskrete Mathematik • Graph • Matching • matrices • matrix theory • Matrizentheorie • Matroids • Modeling • Node • Systemanalyse • Systems Theory • Theorie der Matroide
• ISBN-10: 3-642-03994-4 / 3642039944
• ISBN-13: 978-3-642-03994-2 / 9783642039942