Page 107 - Matrix Analysis & Applied Linear Algebra

3.5 Matrix Multiplication 101

For the network depicted in Figure 3.5.1,

AB C D H
 
A 0 0 1 0 1
B  1 0 0 0 1 
 
C = C  0 0 0 1 1  .
 
D  0 1 0 0 1 
H 1 1 1 1 0
4
3
2
The matrix C together with its powers C , C , C ,... will provide all of the
information needed to analyze the network. To see how, notice that since c ik
is the number of direct routes from city i to city k, and since c kj is the
number of direct routes from city k to city j, it follows that c ik c kj must be
the number of 2-flight routes from city i to city j that have a connection at
2
city k. Consequently, the (i, j) -entry in the product C = CC is
5

2
[C ] ij = c ik c kj = the total number of 2-flight routes from city i to city j.
k=1
3
Similarly, the (i, j) -entry in the product C = CCC is

5

3
[C ] ij = c ik 1 k 1 k 2 k 2 j = number of 3-flight routes from city i to city j,
c
c
k 1 ,k 2 =1
and, in general,
5

n
[C ] ij = c ik 1 k 1 k 2 ··· c k n−2 k n−1 k n−1 j
c
c
k 1 ,k 2 ,···,k n−1 =1
is the total number of n -flight routes from city i to city j. Therefore, the total
number of routes from city i to city j that require no more than n flights
must be given by
2
3
n
n
3
2
[C] ij +[C ] ij +[C ] ij + ··· +[C ] ij =[C + C + C + ··· + C ] ij .
For our particular network,
11121 23225 8777 9
     
 7877
 11211   22235  9 
2
3
4

C = 12111 , C = 32225 , C = 7787 9 ,





21111 22325 7778 9
     
11114 55554 999920