An interlacing theorem for matrices whose graph is a given tree

Abstract

Abstract Let A and B be (nn)-matrices. For an index set S ? {1, …, n}, denote by A(S) the principal submatrix that lies in the rows and columns indexed by S. Denote by S' the complement of S and define ?(A, B) = $$\mathop \sum \limits_S $$ det A(S) det B(S'), where the summation is over all subsets of {1, …, n} and, by convention, det A(Ø) = det B(Ø) = 1. C. R. Johnson conjectured that if A and B are Hermitian and A is positive semidefinite, then the polynomial ?(?A,-B) has only real roots. G. Rublein and R. B. Bapat proved that this is true for n ? 3. Bapat also proved this result for any n with the condition that both A and B are tridiagonal. In this paper, we generalize some little-known results concerning the characteristic polynomials and adjacency matrices of trees to matrices whose graph is a given tree and prove the conjecture for any n under the additional assumption that both A and B are matrices whose graph is a tree.