Soules vectors: applications in graph theory and the inverse eigenvalue problem

George Soules [1] introduced a set of vectors $r_1,...,r_N$ with the remarkable property that for any set of ordered numbers $\lambda_1\geq\dots\geq\lambda_N$, the matrix $\sum_n \lambda_nr_nr_n^T$ has nonnegative off-diagonal entries. Later, it was found [2] that there exists a whole class of such vectors - Soules vectors - which are intimately connected to binary rooted trees. In this talk I will describe the construction of Soules vectors starting from a binary rooted tree, and introduce some basic properties. I will also cover a number of applications: the inverse eigenvalue problem, equitable partitions in Laplacian matrices and the eigendecomposition of the Clauset-Moore-Newman hierarchical random graph model.

[1] Soules (1983), Constructing Symmetric Nonnegative Matrices
[2] Elsner, Nabben and Neumann (1998), Orthogonal bases that lead to symmetric nonnegative matrices