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