Mathematics Seminar - 09/24/26

Abstract: A zero-nonzero pattern matrix is a way to represent which entries of a matrix are zeros. A problem in combinatorial matrix theory is to study the minimum rank among all matrices that can come from these pattern matrices by substituting elements of some field for the nonzero entries of the pattern matrix. A lower bound on the minimum rank of a pattern matrix is its triangle number, the size of the largest upper triangular submatrix that can be obtained by permuting rows and columns. We show that whether this bound is tight for a particular pattern has somewhat surprising connections to the notion of an adjoint of a matroid.

The notion of a matroid is an abstraction of the concept of linear independence. Matroid theory also has connections to graph theory and lattice theory. Every matroid is associated with a lattice called its lattice of flats. Loosely speaking, an adjoint of a matroid M is a matroid M' into whose lattice of flats the lattice of flats of M can be embedded via an order-reversing injection.