COMBINATORIAL APPROACH TO MATRIX THEORY AND ITS APPLICATIONS
by Richard A. Brualdi and Dragos Cvetkovic
Preface
Matrix theory is a fundamental area of mathematics with application not
only to many branches of mathematics but also to science and engineering.
Its connections to many different branches of mathematics include: (i)
algebraic structures such as groups, fields and vector spaces, (ii)
combinatorics including graphs and other discrete structures, and (iii)
analysis including systems of linear differential equations and functions
of a matrix argument.
Generally, elementary (and some advanced) books on matrices ignore or only
touch on the combinatorial or graph-theoretical connections with matrices.
This is unfortunate in that these connections can be used to shed light on
the subject, and to clarify and deepen one's understanding. In fact, a
matrix and a (weighted) graph can each be regarded as different models of
the same mathematical concept.
Most researchers in matrix theory, and most users of its methods, are
aware of the importance of graphs in linear algebra. This can be seen from
the great number of papers in which graph-theoretic methods for solving
problems in linear algebra are used. Also, electrical engineers apply
these methods in practical work. But, in most instances, the graph is
considered as an auxiliary, but nonetheless very useful, tool for solving
important problems.
The present book differs from most other books on matrices in that the
combinatorial, primarily graph-theoretic, tools are put in the forefront
of the development of the theory. Graphs are used to explain and
illuminate basic matrix constructions, formulas, computations, ideas, and
results. Such an approach fosters a better understanding of many ideas of
matrix theory and, in some instances, contributes to easier descriptions
of them. The approach taken in this book should be of interest to
mathematicians, electrical engineers, and other specialists in sciences
such as chemistry and physics.
Each of us has written a previous book which is related to the present
book:
I. R.A. Brualdi, H.J.Ryser,
Combinatorial Matrix Theor}, Cambridge University Press, Cambridge, 1991;
reprinted 1992.
II. D. Cvetkovicc, Combinatorial Matrix
Theory, with Applications to Electrical Engineering, Chemistry and
Physics}, (in Serbian), Naucna knji-ga, Beograd, 1980; II edition
1987.
This joint book came about as a result of a proposal from the second-named
author (D.C.) to the first-named author (R.A.B.) to join in reworking and
translating (parts of) his book (II). While that book---mainly the
theoretical parts of it---has been used as a guide in preparing this book,
the material has been rewritten in a major way with some new organization
and with substantial new material added throughout. The stress in this
book is on the combinatorial aspects of the topics treated; other aspects
of the theory (e.g. algebraic and analytic) are described as much as
necessary for the book to be reasonably self-contained and to provide some
coherence. Some material which is rarely found in books at this level, for
example, Gersgorin's theorem and its extensions, Kronecker product of
matrices, and sign-nonsingular matrices and evaluation of the permanent,
is included in the book.
Thus our goal in writing this book is to increase one's understanding of
and intuition for the fundamentals of matrix theory, and its application
to science, with the aid of combinatorial/graph-theoretic tools. The book
is not written as a first course in linear algebra. It could be used in a
special course in matrix theory for students who know the basics of vector
spaces. More likely, this book could be used as a supplementary book for
courses in matrix theory (or linear algebra). It could also be used as a
book for an undergraduate seminar or as a book for self-study.
We now briefly describe the chapters of the book. In the first chapter we
review the basics and terminology of graph theory, elementary counting
formulas, fields, and vector spaces. It is expected that someone reading
this book has a previous acquaintence with vector spaces. In Chapter 2 the
algebra of matrices is explained, and the Konig digraph is introduced
and then used in understanding and carrying out basic matrix operations.
The short Chapter 3 is concerned with matrix powers and their description
in terms of another digraph associated with a matrix.
In Chapter 4 we introduce the Coates digraph of a matrix and use it to
give a graph-theoretic definition of the determinant. The fundamental
properties of determinants are established using the Coates digraph. These
include the Binet-Cauchy formula and the Laplace development of the
determinant along a row or column. The classical formula for the
determinant is also derived. Chapter 5 is concerned with matrix inverses
and a graph-theoretic interpretation is given. In Chapter 6 we develop the
elementary theory of solutions of systems of linear equations, including
Cramer's rule, and show how the Coates digraph can be used to solve a
linear system. Some brief mention is made of sparse matrices.
In Chapter 7 we study the eigenvalues, eigenvectors, and characteristic
polynomial of a matrix. We give a combinatorial argument for the classical
Cayley-Hamilton theorem and a very combinatorial proof of the Jordan
canonical form of a matrix. Chapter 8 is about nonnegative matrices and
their special properties that highly depend on their digraphs. We discuss,
but do not prove, the important properties of nonnegative matrices that
are part of the Perron-Frobenius theory. We also describe some basic
properties of graph spectra. There are three unrelated topics in Chapter
9, namely Kronecker products of matrices, eigenvalue inclusion regions,
and the permanent of a matrix and its connection with sign-nonsingular
matrices. In Chapter 10 we describe some applications in Electrical
Engineering, Physics, and Chemistry.
Our hope is that this book will be useful for both students, teachers, and
users of matrix theory.
Richard A. Brualdi
Dragoss Cvetkovic