Team games, 3

Recall the general problem:

Given n players, arrange a series of matches, each between two teams of k players, in such a way that every pair of players are on the same team in s matches and on opposite teams in t matches, and subject to this the number of matches is as small as possible.

The first post in the sequence treated the case n = 2k, and found a connection with Hadamard matrices. This time, I consider the next case n = 2k+1, and find a connection with another class of combinatorial matrices, namely conference matrices. These were first introduced by Belevich in the 1950s in connection with conference telephony. (I don’t know how the application works.)

The counting arguments introduced in the earlier chapters show that the smallest feasible solution has s = k−1, t = k, and the total number of matches is 2k+1; each player sits out one match. Since the numbers of players and matches are equal, it is not surprising that we can represent the schedule by a special kind of square matrix.

A conference matrix of order n is an n×n matrix C with diagonal entries 0 and off-diagonal entries ±1 which satisfies CC^T = (n−1)I. (This equation is equivalent to C^TC = (n−1)I.)

A few observations about conference matrices:

• Since the inverse of C is C^T/n, we also have C^TC = (n−1)I.
• Two rows (or columns) agree in n/2−1 places; so n is even.
• Changing the sign of any row or column does not affect the property of being a conference matrix.

From match schedules to conference matrices

If we represent the match schedule by a matrix S in which each row represents one game, with +1 and −1 assigned arbitrarily to the two teams and 0 to the player who sits out, we can order the rows so that the ith player sits out the ith game; thus, the diagonal entries are 0. We change notation so that the number of players and matches (the size of the matrix) is m, where m = 2k+1.

The conditions on our match schedule imply that S^TS = mI−J, where J is the all-one matrix. A small detour is required to arrange that also SS^T = mI−J.

From linear algebra we know that SS^T = mI−X, where X is a symmetric rank 1 matrix satisfying X² = mX. All entries of X are odd, and the diagonal entries are 1, so the sum of squares of the entries in each row is m. Hence all entries are ±1. Since X has rank 1, any row is plus or minus the first row. It follows easily that, changing the sign of some rows and the corresponding columns, we have X = J. These sign changes are achieved by changing signs of the corresponding rows of S; this doesn’t change the match schedule, since the positive and negative teams in each match were chosen arbitrarily. (Sorry if that was a bit brief!)

Now, if we add a new first row and column to S with all entries +1 except for the diagonal entry zero, it is easy to see that the resulting matrix C is a conference matrix of order n = m+1.

Conversely, given a conference matrix of order m+1, where m = 2k+1, change signs of rows and columns to ensure that all entries in the first row and column are +1 (apart from the diagonal); then deleting this row and column gives a match schedule.

About conference matrices

As we saw, we can assume that all entries in the first row and column (apart from their intersection) are +1. Then any row other than the first has n/2 entries +1 (including the first entry) and (n−2)/2 entries −1. Let C be such a matrix, and let S be the matrix obtained from C by deleting the first row and column (the matrix of the match schedule).

The basic result about conference matrices is:

If n is congruent to 2 (mod 4), then S is symmetric; if n is congruent to 0 mod 4 then S is skew-symmetric.

By slight abuse of language, we call a normalised conference matrix C symmetric or skew according as S is symmetric or skew (that is, according to the congruence on n (mod 4)). A “symmetric” conference matrix really is symmetric, while a “skew” conference matrix becomes really skew if we change the sign of the first column.

Symmetric conference matrices

Let C be a symmetric conference matrix. Let A be the matrix obtained from S by replacing +1 by 0 and −1 by 1. Then A is the adjacency matrix of a strongly regular graph of Paley type: that is, a graph with n−1 vertices in which every vertex has degree (n−2)/2, two adjacent vertices have (n−6)/4 common neighbours, and two non-adjacent vertices have (n−2)/4 common neighbours. The matrix S is called the Seidel adjacency matrix of the graph.

The complementary graph has the same properties.

Symmetric conference matrices are associated with other combinatorial objects, among them regular two-graphs, sets of equiangular lines in Euclidean space, switching classes of graphs. Note that the same conference matrix can give rise to many different strongly regular graphs by choosing a different row and column for the normalisation.

A theorem of van Lint and Seidel asserts that, if a symmetric conference matrix of order n exists, then n−1 is the sum of two squares. Thus there is no such matrix of order 22 or 34. They exist for all other orders up to 42 which are congruent to 2 (mod 4), and a complete classification of
these is known up to order 30.

In the excluded cases, we deduce that there is no match schedule of the kind we are looking for, having equally many players and matches, with k = 10 or 16. I don’t know what the smallest possible number of matches is in these cases (it must be a multiple of the number of players).

The simplest construction is that by Paley, in the case where n−1 is a prime power: the matrix S has rows and columns indexed by the finite field of order n 1, and the (i,j) entry is +1 if j−i is a non-zero square in the field, −1 if it is a non-square, and 0 if i=j.

In connection with conference telephony, the following parameter is considered. Let C be a symmetric matrix with 0 on the diagonal and ±1 elsewhere. Then the largest eigenvalue of C² is n−1, with equality if and only if C is a symmetric conference matrix. The minimum largest eigenvalue of C² (over all possible C) has been considered by Goethals, who showed that it is n, n+1 or n+2 if there is a symmetric conference matrix of order n+1, n+2, or n+3 respectively; the minimum is attained only by deleting 1, 2 or 3 rows and columns from such a conference matrix.

Skew conference matrices

Let C be a “skew conference matrix”. By changing the sign of the first column, we can ensure that C really is skew: that is, C^T = −C. Now it follows that (C+I)(C^T+I) = nI, so that H = C+I is a Hadamard matrix. (See the first post in this sequence.) By similar abuse of language, it is called a skew-Hadamard matrix: apart from the diagonal, it is skew. Conversely, if H is a skew-Hadamard matrix, then H−I is a skew conference matrix.

It is conjectured that skew-Hadamard matrices exist for every order divisible by 4. Many examples are known. The simplest are the Paley matrices, defined as in the symmetric case, but skew-symmetric because −1 is a non-square in the field of order q in this case.

If C is a skew conference matrix, then S is the adjacency matrix of a strongly regular tournament (also called a doubly regular tournament. (The term “tournament” here does not refer to our match scheduling problem. A skew matrix with zero diagonal and other entries ±1 records the results of a round-robin tournament in which every team plays against every other and draws are not possible: the (i,j) entry is +1 if team i beats team j, or −1 if team i loses to team j. We can represent this by a directed graph, with an arc from i to j if team i beats team j.)

A strongly regular tournament is a directed graph on m vertices in which every vertex has in-degree and out-degree (m−1)/2 (so that every pair of vertices is joined by an arc in one direction) and every pair of vertices have (m−3)/4 common in-neighbours (and the same number of out-neighbours). Again this is equivalent to the existence of a skew conference matrix of size n = m+1.

Note that if the results of a round robin were described by a strongly regular tournament, there would be no obvious way to decide who has won!