8.2 Benefits of the graph representation

Let’s talk about the concrete advantages that the graph representation offers. For one, the powers of the matrix correspond to walks in the graph. Say, for any let . Its square is denoted by , where the elements are defined by

(Note that the (2) in the superscript of a_i,j⁽²⁾ is not an exponent; this is just an index indicating that a_i,⁽²⁾ is the element of A².)

Figure 8.5 shows the elements of the square matrix and its graph: all possible two-step walks are accounted for in the sum defining the elements of A².

Figure 8.5: Powers of the matrix describe walks on its directed graph

There is much more to this connection; for instance, it gives us a deep insight into the structure of nonnegative matrices. To see how, let’s talk about the concept of strongly connected components.

8.2.1 The connectivity of graphs

Intuitively, we can think of connectivity as the ability to reach every node from the others. To formalize this...