Page 215 - Advanced engineering mathematics

7.1 Matrices 195

v 2

v 1 v 3

v 6 v 4

v 5

FIGURE 7.1 A typical graph.

A walk of length n in a graph is a sequence v 1 ,v 2 ,··· ,v n+1 of points (not necessarily dif-
ferent), with each v j adjacent to v j+1 . Such a walk represents a possible path an atom might take
over n edges (perhaps some repeated) through various sites in the crystal. A v i − v j walk is one
that begins at v i and ends at v j .
Physicists and materials engineers are interested in the following question: given a crystal
with n sites v 1 ,v 2 ,··· ,v n , how many different walks of length k are there between two selected
sites?

Define the adjacency matrix A =[a ij ] of the graph to be the n × n matrix having

1 if v i is adjacent to v j in the graph
a ij =
0 if there is no line between v i and v j in the graph.

The graph of Figure 7.1 has the 6 × 6 adjacency matrix
⎛ ⎞
011100
101000
⎜ ⎟
⎜ ⎟
110100
⎜ ⎟
A = ⎜ ⎟ .
101011
⎜ ⎟
⎜ ⎟
⎝ 000101 ⎠
000110
The main diagonal elements are zero because there is no line between any v i and itself.
We claim that, if k be any positive integer, then the number of distinct v i −v j walks of length
k
k
k in the crystal is the i, j-element of A . The elements of A therefore answer the question posed.
To see why this is true, begin with k = 1. If i = j, there is a walk of length 1 between v i and
v j exactly when v i is adjacent to v j , and in this case a ij = 1.
We next show that, if the result is true for walks of length k, then it must be true for walks
of length k + 1. Consider how a v i − v j walk of length k + 1 is formed. First there must be a
v i − v r walk of length 1 from v i to some v r adjacent to v i ,followedbya v r − v j walk of length k
(Figure 7.2). Then

number of distinct v i − v j walks of length k + 1

= sum of the number of distinct v r − v j walks of length k,

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

October 14, 2010 14:23 THM/NEIL Page-195 27410_07_ch07_p187-246