Abstract:
Support theory is a methodology for bounding eigenvalues and generalized eigenvalues of matrices and matrix pencils; such bounds have been stated both in algebraic terms, and in combinatorial terms based on embeddings of the underlying graphs of the matrices. In this paper, we present a theorem that demonstrates the connection between these various bounding techniques, and also suggests a possible approach to generating approximate inverses for preconditioning. The theorem shows, given matrices A = U D_A U^* and B = V D_B V^* (where D_A and D_$ are invertible Hermitian matrices, and U and V are not necessarily square), that it is possible to define a matrix W such that W^* D_B^{-1} W D_A has the same nonzero eigenvalues counting multiplicity as B^+ A. In the special case that U is the orthogonal projector onto the range space of B and D_A = I (and hence that A = U U^* = U^2 = U), then W^* D_B^{-1} W = B^+. This suggests that finding an approximation to W might lead to an approximate inverse that can be used in preconditioning. We also describe how this theorem generalizes the idea of graph embeddings in an algebraic sense.