Matrices Help Relationships
An Airline Problem
William A. McWorter Jr.
Consider the following problem.
Given n cities, it is desired to design a network of flights between the cities satisfying the following conditions. For each city there are direct flights to and from exactly the same number of other cities. Between any two cities there is exactly one flight with at most one stopover. For what values of n do such networks exist?
For n = 2, a solution is easy, one direct flight between the two cities. For
Let k denote the number of flights to and from a city. Here
There are no such networks for n = 6, 7, 8, and 9 cities, as we shall show. However, for n = 10 there is a solution which is realized by the so-called Petersen graph.
Again, you can check that all the conditions are satisfied. This graph has a high degree of symmetry (120 symmetries). It suffices to check the conditions for any one of the cities because of this symmetry. (To recognize the many symmetries of this graph, note that the same graph arises by taking as vertices all 2-element subsets of
With matrix theory we will show that there are only a small number of values for n for which there exists a network of flights between n cities satisfying the given conditions. Let A be the incidence matrix for the relationship "there is a direct flight between", with the rows and columns of A labelled by the cities. There is a 1 in a row labelled c and column labelled d if and only if there is a direct flight between c and d, zeros elsewhere. Then A is an n by n matrix of ones and zeros with the property that each row and column of A contains exactly k ones.
The integer powers of a square incidence matrix have a nice property in the context of networks. The entry in the i-th row, j-th column of Ad is the number of paths of length d from city i to city j. I haven't defined path in a network, but let's look at the solution for n = 5 cities.
A path is what you'd expect a path to be, the path followed by an airplane in this network. The length of the path is the number of stops. For example, the entry in row 1, column 1 of A2 is a 2, meaning that there are exactly two paths from city 2 to itself stopping somewhere else and finally stopping at city 2. These are 1 to 2 then 2 to 1 and 1 to 5 then 5 to 1. The entry in row 2, column 1 of A3 is 3, meaning that there are three paths from city 2 to city 1, namely, 2 to 1, 1 to 2, 2 to 1; 2 to 1, 1 to 5, 5 to 1; and 2 to 3, 3 to 2, 2 to 1. You may notice that it is easier to count these paths by multiplying matrices than counting the number of paths directly.
Now let's look at A2 in the general case of n cities, assuming the network exists for n cities. The condition that there are direct flights to exactly k other cities implies that the main diagonal entries of A2 are all equal to k. The condition that between any two cities there is exactly one flight with at most one stopover means that the off-diagonal entries of A2 are either 0 because there is a direct flight between the two cities, or 1 because there is a one-stopover flight between the two cities (look at the example A2 above for n = 5). The entries of matrix A hold the number of paths of length 1 between two cities. Hence the off-diagonal entries of A have a 1 where A2 has a zero and vice versa (again, look at the example above). Further, the main diagonal entries of A are all zero. Thus we can write
A2 + A - (k - 1)I = J
where I is the n by n identity matrix and J is the matrix of all ones.
Now we can take advantage of the concept of eigenvalues and eigenvectors of a square matrix. A nonzero vector v is an eigenvector of a square matrix M if Mv = λv, for some number λ. The number λ is called an eigenvalue and may be any number, including zero. Finding all the eigenvalues of a square matrix usually involves finding a determinant, but we won't need to do that here. Since all the row sums of A equal k, the vector
Av = kv (therefore, Adv = kdv, for every positive integer d)
nv = Jv = (A2 + A - (k - 1)I)v = A2v + Av - (k - 1)v = (k2 + k - (k - 1))v = (k2 + 1)v.
Since v is not the zero vector, it follows that
Now let u be any eigenvector of A with corresponding eigenvalue λ. Then Au = λu and
Ju = (A2 + A - (k - 1)I)u = (λ2 + λ - (k - 1))u.
Thus u is an eigenvector of J with eigenvalue
We're almost there. The sum of all the eigenvalues of A must equal the sum of the diagonal entries of A, which sum is 0. Hence
k + s(-1 + √4k - 3)/2 + t(-1 - √4k - 3)/2 = 0, or
(s - t)√4k - 3 = s + t - 2k = k2 - 2k.
Separate between two cases: s = t and s ≠ t. If
If s ≠ t, 4k - 3 is a complete square that divides the integer (k2-2k)2. There are only finitely many such k. Since (k2-2k)2 is congruent to 0 modulo 4k - 3, so is
- M. Aschbacher, The non-existence of rank three permutation groups of degree 3250 and subdegree 57, J. Algebra, 19 (1971), 538-540.
Copyright © 1996-2017 Alexander Bogomolny