Combinatorial Matrix Theory
Richard A. Brualdi
University of Wisconsin-Madison
38.1 Combinatorial Structure and Invariants
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, ...