Proceedings of Symposia in Applied Mathematics
Volume 40, 1990
THE MANY FACETS OF
COMBINATORIAL MATRIX THEORY
Richard A. Brualdi
ABSTRACT. I take a very broad view of combinatorial matrix theory.
Combinatorial matrix theory is concerned with the use of matrix theory and
linear algebra in proving combinatorial theorems and in describing and
classifying combinatorial constructions, and it is also concerned with the use of
combinatorial ideas and reasoning in the finer analysis of matrices and with
intrinsic combinatorial properties of matrix arrays.
1. THE DETERMINANT. It should come as no surprise that combinatorial theory and matrix
theory could interact to form a subject called "combinatorial matrix theory". One of the first
matrix functions one studies is the determinant, and the determinant has a very combinatorial
definition: The determinant of an n by n matrix
(1.1) A = (a
y
: i=l,...,n;j = l,...,n)
is given by
n
(1.2) det A = 2 (sign n) JJ aijl(i)
where the summation is over all permutations % of {l,...,n}, and where sign K is +1 or
1 according as n is an even or odd permutation. We may impart even more combinatorial
spirit to the determinant through the use of directed graphs (or digraphs).
A digraph T of order n has a set of n vertices, usually taken to be the set {l,...,n},
and a set A of arcs where each arc is an ordered pair (i,j) of not necessarily distinct vertices.
The arcs of T can be regarded as a subset of the positions of the matrix (1.1). The entry a..
at the position (i,j) of A is the weight assigned by A to the ar£ (ij) of P. If a.. = 1 or
0 according as (i,j) is or is not an arc of T (i,j = l,...,n), then A is the adjacency matrix of
T. We may use these arc weights in order to assign weights to other objects associated
with r. However this may be done, we define the weight of a sgt of objects to be the sum of
the weights of the objects in the set.
This paper was written during a period in which the author was partially
supported by National Science Foundation Grant No. DMS—8521521.
© 1990 American Mathematical Society
0160-7634/90 $1.00 + $.25 per page
1
http://dx.doi.org/10.1090/psapm/040/1059482
Previous Page Next Page