Isaac Newton Institute for Mathematical Sciences

Validated computation tool for Perron-Frobenius eigenvalue using graph theory

Author: K Nagatou (Kyushu)

Abstract

Any nonnegative matrix has a special eigenvalue, so called Perron-Frobenius eigenvalue, which plays an important role in dynamical systems. In this talk we present a numerical tool to compute rigorous (upper and lower) bounds of Perron-Frobenius eigenvalue of nonnegative matrices. Since a non-negative matrix corresponds to a directed graph, we make use of Tarjan's algorithm which founds all strongly connected components of a directed graph very efficiently. By applying Tarjan's algorithm to the directed graph which is derived from the original matrix, we decompose the matrix into (possibly small) irreducible components, and then enclose the aimed Perron-Frobenius eigenvalue. We show some numerical examples which demonstrate the efficiency of our tool.