Adjacency Matrices and Graphs
M2, Degrees of the Vertices, and Walks from a Matrix
Using powers of an Adjacency Matrix to Determine Connectedness
Adjacency Matrices and Digraphs, Sources and Sinks

Draw a graph associated with the adjacency matrix M. M=

 

a

b

c

d

e

a

0

1

1

0

0

b

1

0

1

1

0

c

1

1

0

1

1

d

0

1

1

0

0

e

0

0

1

0

0

M2 = M× M

0

1

1

0

0

 

 

X

0

1

1

0

0

 

 

=

2

1

1

2

1

1

0

1

1

0

1

0

1

1

0

1

3

2

1

1

1

1

0

1

1

1

1

0

1

1

1

2

4

1

0

0

1

1

0

0

0

1

1

0

0

2

1

1

2

1

0

0

1

0

0

0

0

1

0

0

1

1

0

1

1

The entries along the main diagonal of M2 indicate two pieces of information in this case:

  1. They represent the number of 2-walks of a vertex with itself.
  2. Since this original graph was simple, they represent the degree of each vertex.

There are three 2-walks from B to itself, namely, B-A-B, B-C-B, and B-D-B. In general, if M is the adjacency matrix of a graph G, Mn tells us the number of n-walks from one vertex to another, i.e. ci, j gives the number of n-walks from vi to vj.

If the union of any of the powers of matrix M contains all nonzero entries, then the matrix is connected. How far do we need to find powers to establish connectivity? Given n vertices, each vertex should be reachable from any other in a walk of length no more than n - 1. So for a 5 vertex graph M4 is as high as we need to calculate to determine connectivity.

Consider the disconnected graph (draw this graph) M =

 

a

b

c

d

e

a

0

1

1

0

0

b

1

0

1

0

0

c

1

1

0

0

1

d

0

0

0

0

0

e

0

0

1

0

0

M2 = M× M

0

1

1

0

0

 

 

X

0

1

1

0

0

 

 

=

2

1

1

0

1

1

0

1

0

0

1

0

1

0

0

1

2

1

0

1

1

1

0

0

1

1

1

0

0

1

1

1

3

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

0

0

1

1

0

0

1

M3 =

 

M4 =

2

3

4

0

1

 

 

 

7

6

6

0

4

3

2

4

0

1

6

7

6

0

4

4

4

2

0

3

6

6

11

0

2

0

0

0

0

0

0

0

0

0

0

1

1

3

0

0

4

4

2

0

3

Evaluating M Ú M2 Ú M3 Ú M4 we see there are no walks connecting D with any other vertices so the graph is clearly disconnected.

Notice the symmetry across the main diagonal in each of the matrices above. This is always the case for undirected graphs. The edge for vi, j is also an edge for vj, i. Such is not the case for the adjacency matrix associated with a digraph.

Directed Graphs
The indegree of a vertex v, indeg(v), is the number of arcs terminating at v. The outdegree, outdeg(v), is the number of arcs beginning at v. Consider the adjacency matrix matrix A is shown below. Draw a digraph represented by A.

 

A =

 

v1

v2

v3

od

v1

1

0

0

1

v2

1

1

2

4

v3

1

0

0

1

id

3

1

2

 

Note that we labeled an additional column, outdegree (od), and an additional row, indegree (id). These values are easily calculated as their respective row/column sums. A vertex with zero indegree is termed a source. One with zero outdegree is a sink.

Properties of Matrices
The identity matrix I has ones across its main diagonal and zeros elsewhere.
Matrix multiplication is associative but not commutative. So A(BC) = (AB)C, but AB¹ BA (unless we have the special case where AB=I and BA=I.)
Multiplication is only possible between compatible matrices: Am, k , Bk, n, in which case the resulting product has dimension m x n.
To compute a matrix product: Matrix product formula.
For any n x n matrix A, the powers of A are defined as follows:

  1. A0 = I
  2. An = AAn - 1 for all integers n ³ 1.

Note: labeling of the vertices affects the appearance of the associated adjacency matrix but not the isomorphically invariant properties of either the matrix or the graph. We will discuss this topic in more detail in the next section.