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