O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

9Perron–Frobenius Theory

Let A and B be two matrices with the same dimensions. Notation such as A ≥ 0, A > 0 or AB has to be understood component-wise. In this chapter, we are dealing with square matrices A ≥ 0, i.e. with non-negative entries. There is a rich theory about their spectra, eigenspaces and powers that turns out to be of particular interest when considering adjacency matrices of graphs. This theory also has many applications ranging from probability theory and Markov chains1 to dynamical systems (see, for instance, [BRI 02]). Perron’s theorem is at the core of Google’s PageRank algorithm discussed in the following chapter. For standard textbooks on matrix theory including discussions about Perron–Frobenius theory see, for instance, [HOR 13] or [SEN 06, GAN 59]. The reader will not find a proof of Perron’s theorem in this book.

9.1. Primitive graphs and Perron’s theorem

We will start with a quite specific property (more restrictive than strong connectedness) that has an important asymptotic consequence expressed by relation [9.3].

Let t ≥ 1 be an integer. A matrix Aimagest×t with non-negative entries is primitive if there exists an integer N such that AN is positive, i.e. all the entries in AN are positive. Primitive matrices have strong properties known as Perron–Frobenius2 theory.

DEFINITION 9.1.– A directed multigraph is primitive if its adjacency matrix is primitive. ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required