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.