Matrices and Matroids for Systems Analysis

ISBN-13: 9783642039935 / Angielski / Miękka / 2009 / 483 str.

Kazuo Murota

Opis

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 last decade. 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." Andras Recski, Mathematical Reviews Clippings 2000m:93006

Spis treści

Preface I. Introduction to Structural Approach --- Overview of the Book 1 Structural Approach to Index of DAE 1.1 Index of differential-algebraic equations 1.2 Graph-theoretic structural approach 1.3 An embarrassing phenomenon 2 What Is Combinatorial Structure? 2.1 Two kinds of numbers 2.2 Descriptor form rather than standard form 2.3 Dimensional analysis 3 Mathematics on Mixed Polynomial Matrices 3.1 Formal definitions 3.2 Resolution of the index problem 3.3 Block-triangular decomposition II. Matrix, Graph and Matroid 4 Matrix 4.1 Polynomial and algebraic independence 4.2 Determinant 4.3 Rank, term-rank and generic-rank 4.4 Block-triangular forms 5 Graph 5.1 Directed graph and bipartite graph 5.2 Jordan-Holder-type theorem for submodular functions 5.3 Dulmage-Mendelsohn decomposition 5.4 Maximum flow and Menger-type linking 5.5 Minimum cost flow and weighted matching 6 Matroid 6.1 From matrix to matroid 6.2 Basic concepts 6.3 Examples 6.4 Basis exchange properties 6.5 Independent matching problem 6.6 Union 6.7 Bimatroid (linking system) III. Physical Observations for Mixed Matrix Formulation 7 Mixed Matrix for Modeling Two Kinds of Numbers 7.1 Two kinds of numbers 7.2 Mixed matrix and mixed polynomial matrix 8 Algebraic Implications of Dimensional Consistency 8.1 Introductory comments 8.2 Dimensioned matrix 8.3 Total unimodularity of dimensioned matrices 9 Physical Matrix 9.1 Physical matrix 9.2 Physical matrices in a dynamical system IV. Theory and Application of Mixed Matrices 10 Mixed Matrix and Layered Mixed Matrix 11 Rank of Mixed Matrices 11.1 Rank identities for LM-matrices 11.2 Rank identities for mixed matrices 11.3 Reduction to independent matching problems 11.4 Algorithms for the rank 11.4.1 Algorithm for LM-matrices 11.4.2 Algorithm for mixed matrices 12 Structural Solvability of Systems of Equations 12.1 Formulation of structural solvability 12.2 Graphical conditions for structural solvability 12.3 Matroidal conditions for structural solvability 13. Combinatorial Canonical Form of LM-matrices 13.1 LM-equivalence 13.2 Theorem of CCF 13.3 Construction of CCF 13.4 Algorithm for CCF 13.5 Decomposition of systems of equations by CCF 13.6 Application of CCF 13.7 CCF over rings 14 Irreducibility of LM-matrices 14.1 Theorems on LM-irreducibility 14.2 Proof of the irreducibility of determinant 15 Decomposition of Mixed Matrices 15.1 LU-decomposition of invertible mixed matrices 15.2 Block-triangularization of general mixed matrices 16 Related Decompositions 16.1 Partition as a matroid union 16.2 Multilayered matrix 16.3 Electrical network with admittance expression 17 Partitioned Matrix 17.1 Definitions 17.2 Existence of proper block-triangularization 17.3 Partial order among blocks 17.4 Generic partitioned matrix 18 Principal Structures of LM-matrices 18.1 Motivations 18.2 Principal structure of submodular systems 18.3 Principal structure of generic matrices 18.4 Vertical principal structure of LM-matrices 18.5 Horizontal principal structure of LM-matrices V. Polynomial Matrix and Valuated Matroid 19 Polynomial/Rational Matrix 19.1 Polynomial matrix and Smith form 19.2 Rational matrix and Smith-McMillan form at infinity 19.3 Matrix pencil and Kronecker form 20 Valuated Matroid 20.1 Introduction 20.2 Examples 20.3 Basic operations 20.4 Greedy algorithms 20.5 Valuated bimatroid 20.6 Induction through bipartite graphs 20.7 Characterizations 20.8 Further exchange properties 20.9 Valuated independent assignment problem 20.10 Optimality criteria 20.10.1 Potential criterion 20.10.2 Negative-cycle criterion 20.10.3 Proof of the optimality criteria 20.10.4 Extension to VIAP(k) 20.11 Application to triple matrix product 20.12 Cycle-canceling algorithms 20.12.1 Algorithms 20.12.2 Validity of the minimum-ratio cycle algorithm 20.13 Augmenting algorithms 20.13.1 Algorithms 20.13.2 Validity of the augmenting algorithm VI. Theory and Application of Mixed Polynomial Matrices 21 Descriptions of Dynamical Systems 21.1 Mixed polynomial mat

Blurb

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