Page 106 - Matrix Analysis & Applied Linear Algebra

100 Chapter 3 Matrix Algebra

For example, a very concise proof of the fact (2.3.5) stating that a system
of equations A m×n x n×1 = b m×1 is consistent if and only if b is a linear
combination of the columns in A is obtained by noting that the system is
consistent if and only if there exists a column s that satisfies

 
s 1
 s 2 
b = As =( A ∗1 A ∗2 ··· A ∗n )  .  = A ∗1 s 1 + A ∗2 s 2 + ··· + A ∗n s n .
.
 . 
s n
The following example illustrates a common situation in which matrix mul-
tiplication arises naturally.
Example 3.5.2
An airline serves five cities, say, A, B, C, D, and H, in which H is the “hub
city.” The various routes between the cities are indicated in Figure 3.5.1.

A B

H

C D

Figure 3.5.1
Suppose you wish to travel from city A to city B so that at least two connecting
flights are required to make the trip. Flights (A → H) and (H → B) provide the
minimal number of connections. However, if space on either of these two flights
is not available, you will have to make at least three flights. Several questions
arise. How many routes from city A to city B require exactly three connecting
flights? How many routes require no more than four flights—and so forth? Since
this particular network is small, these questions can be answered by “eyeballing”
the diagram, but the “eyeball method” won’t get you very far with the large
networks that occur in more practical situations. Let’s see how matrix algebra
can be applied. Begin by creating a connectivity matrix C =[c ij ] (also known
as an adjacency matrix) in which

1 if there is a flight from city i to city j,
c ij =
0 otherwise.