Symmetrizable matrices, quotients, and the trace problem

• Published in: Linear algebra and its applications 2020-09, Vol.600, p.60-81
• Main Authors: McKee, James, Smyth, Chris
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; Eigenvalues; Equitable partitions; Integers; Linear algebra; Mathematical analysis; Matrix methods; Number theory; Partitions (mathematics); Quotients; Symmetrizable matrices; Trace problem
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2020.04.009

Symmetrizable matrices are those that are a real diagonal change of basis away from being symmetric. Restricting to matrices that have integer entries (symmetrizable integer matrices — SIMs) we enter the worlds of combinatorics and number theory. It is known that quotients of equitable partitions of graphs provide examples of SIMs (with all entries nonnegative). We note a converse result, that every SIM comes from a quotient of an equitable partition of a signed graph (in the nonnegative case, a graph). There is a beautiful well-known combinatorial description of SIMs, which leads to a necessary combinatorial/number-theoretic property of their symmetrizations. We show that this property in fact classifies the matrices that are symmetrizations of SIMs. We then turn to the trace problem for totally positive algebraic integers. The analogous problem for eigenvalues of positive definite integer symmetric matrices (ISMs) was recently solved. We extend this to SIMs, showing that if A is a connected positive definite n×n SIM, then tr(A)≥2n−1, and that if equality holds then A must in fact be symmetric. We explore the structure of minimal-trace examples, in both the symmetric and asymmetric cases.