Special Ultrametric Matrices and Graphs

Special ultrametric matrices are, in a sense, extremal matrices in the boundary of the set of ultrametric matrices introduced by Martinez, Michon, and San Martin [ SIAM J. Matrix Anal. Appl., 15 (1994), pp. 98--106]. We show a simple construction of these matrices, if of order n, from nonnegatively edge-weighted trees on n vertices, or, equivalently, from nonnegatively edge-weighted paths. A general ultrametric matrix is then the sum of a nonnegative diagonal matrix and a special ultrametric matrix, with certain conditions fulfilled. The rank of a special ultrametric matrix is also recognized and it is shown that its Moore--Penrose inverse is a generalized diagonally dominant M-matrix. Some results on the nonsymmetric case are included.