# 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 *network* exists satisfying the required conditions. 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 A^{d} 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 A^{2} 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 A^{3} 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 A^{2} 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 A^{2} 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 A^{2} 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 A^{2} 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 A^{2} 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

A^{2} + 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 M**v** = λ**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 **v** = (1, 1, ...)

A**v** = k**v** (therefore, A^{d}**v** = k^{d}**v**, for every positive integer d)

Thus,

n**v** = J**v** = (A^{2} + A - (k - 1)I)**v** = A^{2}**v** + A**v** - (k - 1)**v** = (k^{2} + k - (k - 1))**v** = (k^{2} + 1)**v**.

Since **v** is not the zero vector, it follows that ^{2} + 1,

Now let **u** be any eigenvector of A with corresponding eigenvalue λ. Then A**u** = λ**u** and

J**u** = (A^{2} + A - (k - 1)I)**u** = (λ^{2} + λ - (k - 1))**u**.

Thus **u** is an eigenvector of J with eigenvalue ^{2} + λ - (k - 1).**v** = (1, 1, 1, ...)^{2} + λ - (k - 1) = 0.^{2}.

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 = k^{2} - 2k.

Separate between two cases: s = t and s ≠ t. If ^{2} - 2k = 0,

If s ≠ t, 4k - 3 is a complete square that divides the integer (k^{2}-2k)^{2}. There are only finitely many such k. Since (k^{2}-2k)^{2} is congruent to 0 modulo 4k - 3, so is ^{4}(k^{2}-2k)^{2} = ((4k)^{2}-2(4)(4k))^{2}.^{2}-2(4)(3))^{2} = 225

### References

- M. Aschbacher,
*The non-existence of rank three permutation groups of degree 3250 and subdegree 57*,__J. Algebra__, 19 (1971), 538-540.

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

64845641 |