Spectral radii of certain iteration matrices and cycle means of digraphs (Q1311313)

This paper is very technical and very innovative. Solving a linear system iteratively requires the spectral radius of the iteration matrix to be less than 1. Splitting the iterative work between several parallel processors that operate independently and unsynchronized, leads to questions about the spectral radius of each of the individual processor iteration matrices. It is shown here that the eigenvalues of products of matrices with just one cycle are determined by the cycle means of an auxiliary graph. This connection between the eigenvalues of matrix products and associated digraphs is very astounding and beautiful in its own right. It is used to determine sufficient conditions that insure spectral radius monotonicity with regard to lengths of cycles in the matrix factors and thus allows to find sufficient conditions that such an asynchronous iteration scheme will converge.