Potentials of random walks on trees

Abstract

In this article we characterize inverse M-matrices and potentials whose inverses are supported on trees. In the symmetric case we show they are a Hadamard product of tree ultrametric matrices, generalizing a result by Gantmacher and Krein [12] done for inverse tridiagonal matrices. We also provide an algorithm that recognizes when a positive matrix W has an inverse M-matrix supported on a tree. This algorithm has quadratic complexity. We also provide a formula to compute W-1, which can be implemented with a linear complexity. Finally, we also study some stability properties for Hadamard products and powers.