Expansion in matrix-weighted graphs

Abstract A matrix-weighted graph is an undirected graph with a k × k symmetric positive semidefinite matrix assigned to each edge. Such graphs admit natural generalizations of the Laplacian and adjacency matrices, leading to a generalized notion of expansion. Extensions of some theorems about expansion hold for matrix-weighted graphs—in particular, an analogue of the expander mixing lemma and one half of a Cheeger-type inequality. These results lead to a definition of a matrix-weighted expander graph, and suggest the tantalizing possibility of families of matrix-weighted graphs with better-than-Ramanujan expansion.