main-content

## Über dieses Buch

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

## Inhaltsverzeichnis

### 1. Introduction to Structural Approach — Overview of the Book

Abstract
This chapter is a brief introduction to the central ideas of the combinatorial method of this book for the structural analysis of engineering systems. We explain the motivations and the general framework by referring, as a specific example, to the problem of computing the index of a system of differentialalgebraic equations (DAEs). In this approach, engineering systems are described by mixed polynomial matrices. A kind of dimensional analysis is also invoked. It is emphasized that relevant physical observations are crucial to successful mathematical modeling for structural analysis. Though the DAEindex problem is considered as an example, the methodology introduced here is more general in scope and is applied to other problems in subsequent chapters.
Kazuo Murota

### 2. Matrix, Graph, and Matroid

Abstract
This chapter lays the mathematical foundation for combinatorial methods of systems analysis. Combinatorial properties of numerical matrices can be stated and analyzed with the aid of matroid theory, whereas those of polynomial matrices are formulated in the language of valuated matroids in Chap. 5. Emphasis is laid also on the general decomposition principle based on submodularity, and accordingly the Dulmage–Mendelsohn decomposition, which serves as a fundamental tool for the generic-case analysis of matrices, is presented in a systematic manner.
Kazuo Murota

### 3. Physical Observations for Mixed Matrix Formulation

Abstract
The dual viewpoint from structural analysis and dimensional analysis, as previewed in §1.2, is explained in more detail. Firstly, two different kinds, “accurate” and “inaccurate,” are distinguished among numbers characterizing real-world systems, and secondly, algebraic implications of the principle of dimensional homogeneity are discussed. These observations lead to the concepts of “mixed matrices,” “mixed polynomial matrices,” and “physical matrices” as the mathematical models of matrices arising from real problems.
Kazuo Murota

### 4. Theory and Application of Mixed Matrices

Abstract
This chapter is devoted to a study on mixed matrices and layered mixed matrices using matroid-theoretic methods. Particular emphasis is laid on the combinatorial canonical form (CCF) of layered mixed matrices and related decompositions, which generalize the Dulmage–Mendelsohn decomposition. Applications to the structural solvability of systems of equations are also discussed.
Kazuo Murota

### 5. Polynomial Matrix and Valuated Matroid

Abstract
Matrices consisting of polynomials or rational functions play fundamental roles in various branches in engineering. Combinatorial properties of polynomial matrices are abstracted in the language of valuated matroids. This chapter is mostly devoted to an exposition of the theory of valuated matroids, whereas the first section describes a number of canonical forms of polynomial/rational matrices that are amenable to combinatorial methods of analysis to be explained in Chap. 6.
Kazuo Murota

### 6. Theory and Application of Mixed Polynomial Matrices

Abstract
This chapter is devoted to a study of the mathematical properties of mixed polynomial matrices with particular emphasis on applications to control theoretic problems. Mathematically, the analysis of mixed polynomial matrices relies heavily on the results in Chap. 4 and Chap. 5, in particular, the CCF of LM-matrices and the properties of valuated matroids.
Kazuo Murota

### 7. Further Topics

Abstract
This chapter introduces three supplementary, mutually independent, topics: the combinatorial relaxation algorithm, combinatorial system theory, and mixed skew-symmetric matrices.
Kazuo Murota

### Backmatter

Weitere Informationen