ABSTRACT
Historically, matrix theory and combinatorics have enjoyed a powerful, mutually beneficial relationship. The Inverse Eigenvalue Problem of a graph (IEP-G) is rooted in the 1960s work of Gantmacher, Krein, Parter and Fielder, but new concepts and techniques introduced in the last decade have advanced the subject significantly and catalyzed several mathematically rich lines of inquiry and application. The IEP-G dates back at least as far as F. Gantmacher and M. Krein’s work on tridiagonal matrices, and arguably even back to Stieltjes’ work on continued fractions. In many cases, a numerical linear algebra algorithm consists of a process to reduce the computation to one on a tridiagonal matrix followed by an optimized algorithm for tridiagonal matrices. Motivated by the work of Gantmacher and Krein, S. Parter initiated the study of the spectral properties of matrices whose zero-nonzero entries are “highly structured.”.
