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

8Algebraic Graph Theory

We are at a turning point of the book. In this chapter, we will discover that associating a matrix with a graph is a powerful concept because we can make use of all the machinery of linear algebra and matrix computations. In the following chapter, we will see that if the associated matrix has special properties (primitivity or irreducibility) then much more can be said about the corresponding graph. In particular, for Google’s PageRank (see Chapter 10), one of the key points is to modify a graph to obtain a primitive matrix. For instance, we will soon learn the fact that a graph is bipartite is completely characterized by its spectrum, i.e. the set of eigenvalues of the associated matrix, or that the first coefficients of its characteristic polynomial have a combinatorial interpretation.

8.1. Prerequisites

We assume that the reader has a working knowledge of linear algebra. In this section, we fix notation and recap a few classical results that can be found in any textbook. In particular, matrices and row or column vectors will be denoted using boldface fonts. The set of m × n matrices with entries in the ring images will be denoted imagesm×n, i.e. m (respectively, n) is the number of rows (respectively, columns). The transpose of the matrix M will be denoted by M

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