ABSTRACT
The combinatorial structure of a matrix generally refers to the locations of the nonzero entries of a matrix, or it might be used to refer to the locations of the zero entries. To study and take advantage of the combinatorial structure of a matrix, graphs are used as models. Associated with a matrix are several graphs that represent the combinatorial structure of a matrix in various ways. The type of graph (undirected graph, bipartite graph, digraph) used depends on the kind of matrices (symmetric, rectangular, square) being studied ([BR91], [Bru92], [BS04]). Conversely, associated with a graph, bipartite graph, or digraph are matrices that allow one to consider it as an algebraic object. These matrices — their algebraic properties — can often be used to obtain combinatorial information about a graph that is not otherwise obtainable. These are two of three general aspects of combinatorial matrix theory. A third aspect concerns intrinsic combinatorial properties of matrices viewed simply as an array of numbers.
