ELA, Volume 3, pp. 129-141, August 1998, abstract.
A Polynomial Time Spectral Decomposition Test for
Certain Classes of Inverse M-Matrices
Jeffrey L. Stuart
The primary result in this paper is a set of O(n cube) time
algorithms to determine whether a specified real, symmetric
matrix is a member of any of several closely related classes:
the MMA-matrices; the inverse MMA-matrices; the strictly
positive, positive definite matrices whose eigenvectors form
a Soules basis; and the strictly ultrametric matrices.
When the class membership question is answered in the
affirmative 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.