Entrywise perturbation theory for diagonally dominant M-matrices with applications

This paper introduces a new perspective on the study of computational problems related to diagonally dominant M-matrices by establishing some new entrywise perturbation results. If a diagonally dominant M-matrix is perturbed in a way that each off-diagonal entry and its row sums (i.e. the quantities of diagonal dominance) have small relative errors, we show that its determinant, cofactors, each entry of the inverse and the smallest eigenvalue all have small relative errors. The error bounds are given and they do not depend on any condition number. Applying this result to the studies of electrical circuits and tail probabilities of a queue whose embedded Markov chains is of GI/M/1 type, we discuss the relative sensitivity of the operating speed of circuits and of the percentile of the queue length, respectively.