Laurent asked on my blog:
Given n players, arrange a competition in which, in each match, two teams of k players play each other. We require that any two players are on the same team in a fixed number s of matches and on opposite teams in t matches, though t is not required to be the same as s. Furthermore, we want to play the minimum possible number of matches. How many matches do we need to schedule?
He put it under “About”, which probably nobody reads.
He gave the following example for n=4 and k=2, where three
matches are required:
|1,2 v 3,4|
|1,3 v 2,4|
|1,4 v 2,3|
Clearly the problem is a non-problem unless n ≥ 2k. In this post, I will address the case n = 2k.
A Hadamard matrix is a square matrix H of order n with entries +1 and −1 satisfying the equation HHT = nI (or equivalently HTH = nI). It is known that the order of a Hadamard matrix is 1, 2, or a multiple of 4; the Hadamard conjecture asserts that, for every number n which is divisible by 4, there is a Hadamard matrix of order n. The smallest multiple of 4 for which no Hadamard matrix is currently known is 668.
Hadamard defined these matrices in terms of a determinant problem: they maximise the determinant of a matrix all of whose entries have magnitude at most 1. They come up in many geometric and combinatorial situations. For example, if we take a cube with side length 2 and centre at the origin in Euclidean space of n dimensions, when can we select n vertices forming an orthogonal basis for the space? Such vectors must be the rows of a Hadamard matrix, and conversely. Sylvester called them anallagmatic pavements, clearly motivated by geometric ideas. (Sylvester was a genius at weird terminology; we saw his “synthematic totals” before.) For much more information see the Wikipedia article on Hadamard matrices.
Now the Hadamard conjecture would solve our problem for the case n = 2k:
- If k is even, then the number of matches is at least n−1, with equality if and only if there is a Hadamard matrix of order n.
- If k is odd and k>1, then the number of matches is at least 2(n−1); equality holds if there is a Hadamard matrix of order 2n.
Note that the second part does not say “if and only if”; I don’t know whether the converse is true. But in any case, the truth of the Hadamard conjecture would resolve the question.
I will sketch the proof of this result here. Let m be the number of matches. Since every player participates in all the matches, we have s+t = m. Fix attention on a particular player. In the m matches, he plays with each of the other n−1 players s times, so (2k−1)s = (k−1)m. Since the greatest common divisor of k−1 and 2k−1 is 1, we see that 2k−1 divides m, so clearly m ≥ n−1.
Now suppose that equality holds. Then s = k−1 and t = k. Number the players from 1 to n, and write each match as a row vector of length n with entries +1 (for one team) and −1 (for the other). Stack up these rows to form a matrix, and put a row with all entries +1 on top.
I claim that this matrix H is a Hadamard matrix. For if we take any two columns, they agree in the first row (which is all +1s) and in k−1 further rows, and disagree in k rows; so their inner product is 0. This means that all the off-diagonal entries of HTH are zero, so that HTH = nI.
By our remarks on Hadamard matrices, for k > 1, this is only possible if k is even.
Conversely, if we have a Hadamard matrix of order n = 2k, we can change signs of columns to make the top row consist entirely of +1s. The orthogonality of rows now says that each further row contains k +1s and k −1s, so we use these rows to describe the schedule of matches. Orthogonality of columns now shows that the conditions on pairs of players are satisfied.
Now suppose that k is odd and k > 1. Then m is a multiple of n−1, and is not n−1; so it is at least 2(n−1).
Suppose that a Hadamard matrix of order 2n exists. As before, change signs of columns to make the first row consist of +1s; then every further row has n +1s. Order the columns so that the +1s in the second row occur in positions 1,2,…,n. Now delete the last n columns and the first two rows of the matrix. What is left has k +1s and k −1s in each row, so it describes a schedule of matches; and as before, it is easy to see by looking at columns that the condition on pairs of players is true.
Last week one of my colleagues suggested to me that the Axiom of Choice is not “discrete mathematics”. I answered that it is, and gave the following illustration. Without using AC, it is possible to show that if AC holds for any family of 2-element sets, then it holds for any family of 4-element sets.
The proof is as follows. Consider the scheme for 4 players given above. They play 2 against 2 in all possible combinations. The Axiom of Choice for 2-element sets says that we can choose a winner for each of these matches. Now it is easy to see that, whatever the results, either one player is on the winning side in every match, or one player is on the losing side in every match; this is the player chosen from the set of 4.