The critical exponent: a novel graph invariant

Abstract

A surprising result of FitzGerald and Horn (1977) shows that $A^{\circ \alpha }:=(a_{ij}^{\alpha })$ is positive semidefinite (p.s.d.) for every entrywise nonnegative $n\times n$ p.s.d. matrix $A=(a_{ij})$ if and only if $\alpha$ is a positive integer or $\alpha \ge n-2$. Given a graph $G$, we consider the refined problem of characterizing the set ${\mathcal{H}}_G$ of entrywise powers preserving positivity for matrices with a zero pattern encoded by $G$. Using algebraic and combinatorial methods, we study how the geometry of $G$ influences the set ${\mathcal{H}}_G$. Our treatment provides new and exciting connections between combinatorics and analysis, and leads us to introduce and compute a new graph invariant called the critical exponent.

12 pages, final version. This is an extended abstract of arXiv:1504.04069 in FPSAC 2017