A polynomial time spectral decomposition test for certain classes of inverse M-matrices
Jeffrey L. Stuart · Electronic Journal of Linear Algebra · 1998
The primary result in this paper is a set of O(n 3 ) time algorithms to determine whether a speci ed real, symmetric matrix is a memberof any of several closely related classes: the MMA-matrices; the inverse MMA-matrices; the strictly positive, positive de nite matrices whose eigenvectors form a Soules basis; and the strictly ultrametric matrices.When the class membership question is answered in the armative for an MMA-matrix or an inverse MMA-matrix, the algorithms also yield the complete spectral decomposition of the matrix in question.Additional results in this paper include an algorithmic test for when a matrix is a Soules matrix, and a construction for Soules bases.