ORTHOGONAL BASES THAT LEAD TO SYMMETRICAL NONNEGATIVE MATRICES

In a paper dating back to 1983, Soules constructs from a positive vect or x an orthogonal matrix R which has the property that for any nonneg ative diagonal matrix Lambda with nonincreasing diagonal entries, the matrix R Lambda R-T has all its entries nonnegative. Independently, Fi edler in 1988 showed that any symmetric irreducible nonsingular matrix whose powers are all M-matrices (and hence an MMA-matrix in the langu age of Friedland, Hershkowitz, and Schneider) must have an orthogonal matrix of eigenvectors (R) over tilde which has similar properties to those of R. Here, for a given positive n-vector x, we investigate the structure of all orthogonal matrices R for which, for any nonnegative diagonal matrix Lambda as above, the matrices R Lambda R-T are nonnega tive. Up to a permutation of its columns, each such R corresponds to a binary tree whose vertices are subsets of the set {1, 2,..., n} with the property that each vertex has either no successor or exactly two d isjoint successors. For such orthogonal matrices R and such nonsingula r diagonal matrices Lambda, we show that the set of matrices of the fo rm R Lambda R-T and the set of inverse MMA-matrices (i.e. matrices who se inverses are MMA-matrices) coincide. Using this result, we establis h a relation between strictly ultrametric matrices and inverse MMA-mat rices. Finally, we show that the QR factorization of R Lambda R-T, for certain such R's, has a special sign pattern. (C) 1998 Elsevier Scien ce Inc.