The Brualdi-Li Conjecture

Introduction

Round robin tournaments are tournaments in which each participant plays every other participant exactly once. The outcome of each encounter is a win for one player and a loss for the other. Draws are not allowed. Usually such tournaments are organized so as to produce a ranking of the participants from the strongest to the weakest.

Sometimes if a statistician wants to arrive at a ranking they will invent a round robin tournament precisely for that purpose. For example if it was desired to have a ranking of NHL goalies, it might be counterproductive to ask an expert for a ranking outright because of the complexity of the problem. It might be more productive to ask an expert (or perhaps a panel of experts with an odd number of members) whether goalie A is stronger than goalie B. This is a more clear cut issue and we could take the opinion of the expert or the majority decision in case of a panel. This could be done for every pair of goalies and the results would form a round robin tournament. This data would then be analyzed to produce a ranking.

Unfortunately, there is no completely foolproof way of doing this. Different criteria for analyzing tournaments can yield different rankings.

The results of a round robin tournament can be coded into a tournament matrix which is a square matrix with as many rows (or columns) as there are participants. The (j,k) entry of this matrix would be 1 if participant j prevails over participant k and 0 otherwise. The diagonal entries are always set to 0.

Two examples of tournament matrices are

\pmatrix{0 & 1 & 1\cr 0 & 0 & 1\cr 0 & 0 & 0\cr} \qquad\mbox{and}\qquad \pmatrix{0 & 1 & 0\cr 0 & 0 & 1\cr 1 & 0 & 0\cr}

In the first example player 1 beats players 2 and 3 and player 2 beats player 3. This is the tournament result that one would expect from the ranking player 1 is better than player 2 is better than player 3. The second example is the famous scissors, paper, stone tournament where the scissors beat the paper, the paper beats the stone and the stone blunts the scissors. So the first tournament supports a clear ranking, while the second is completely inconclusive.

So quite aside from the question of actually finding a ranking based on tournament results, it would be useful to have some measure of the inconsistency inherent in the results. One way of doing this is by means of the Perron root of the matrix. It is a well established fact that every square matrix with nonnegative entries has a greatest nonnegative eigenvalue and that eigenvalue has a nonnegative eigenvector. This largest eigenvalue is called the Perron root. The Perron root of the first matrix is zero and in fact all the eigenvalues of that matrix are zero. The Perron root of the second (scissors, paper, stone) matrix is 1. The feeling is that the larger the Perron root, the more the tournament is inconsistent with any specific ranking.

It is natural to ask which tournaments are most inconsistent with a ranking? Which tournament matrices of a given size have the greatest possible Perron root? If the number of participants is odd, then the number of encounters each player has is even (since they play everyone except themselves) and it is possible as in the case of scissors, paper, stone that they win exactly half of their encounters. All such tournaments yield matrices with a Perron root of \frac{n-1}{2} where n is the number of participants and this is the greatest possible value.

When the number of participants n is even, then each participant has an odd number of encounters and it is not possible for any of them to win exactly half of their encounters. The nearest situation to that would be that half the participants win \frac{n-2}{2} encounters and the other half win \frac{n}{2}. But when one examines such cases, one finds that the Perron root is not always the same. It depends on the specific configuration.

In 1983 Richard Brualdi and Li Qiao proposed a specific pattern which they conjectured attained the greatest possible Perron root. For n=10, this pattern is

\pmatrix{0&1&1&1&1&0&0&0&0&0\cr 0&0&1&1&1&1&0&0&0&0\cr 0&0&0&1&1&1&1&0&0&0\cr 0&0&0&0&1&1&1&1&0&0\cr 0&0&0&0&0&1&1&1&1&0\cr 1&0&0&0&0&0&1&1&1&1\cr 1&1&0&0&0&0&0&1&1&1\cr 1&1&1&0&0&0&0&0&1&1\cr 1&1&1&1&0&0&0&0&0&1\cr 1&1&1&1&1&0&0&0&0&0\cr }
and it generalizes to other even values of n in a fairly obvious way. I succeeded in verifying this conjecture in 2011. My article entitled "Solution of the Conjecture of Brualdi and Li" has been accepted for publication in Linear Algebra and its Applications. Although I am by no means an expert in this field, I have the impression that the method of attack is one that had not been seriously considered previously.

Characteristic Polynomials

This method of attack uses the characteristic polynomial. For the Brualdi-Li matrices, this had been previously worked out by Hemasinha et al. [1]. We give some complementary material, not included in the article but which may still be of interest to those who work in the field. We work with adjusted tournament matrices A which have the form A = 2T + I where T is a standard n \times n tournament matrix and where I denotes the identity matrix. They have diagonal entries equal to 1, off-diagonal entries in \{0,2\} and satisfy A + A' = 2J where J denotes the matrix in which every entry is 1. We also work with skew-symmetric tournament matrices S of the form S = A - J = T - T'. They are skew-symmetric with off-diagonal entries in \{-1,1\}. A routine calculation gives

\det(I - \mu A) = \det(I - \mu S) - \mu e'{\rm Adj}(I - \mu S)e
where e denotes the vector of ones. Some additional trickery now gives
\det(I - \mu A) = (1 - n\mu) \det(I - \mu S) + \mu^3 s'{\rm Adj}(I - \mu S)s
where s=Se. The terms in this expression can be expanded. For example
\det(I - \mu S) = \sum_X \mu^{|X|} \det(S_X).
where the sum is taken over subsets X of \{1,2,\ldots,n\} with an even number of elements. The notation S_X denotes the principal submatrix of S formed by the corresponding set of rows and columns. The second term can be expanded by using
\mu s'{\rm Adj}(I - \mu S)s = \sum_Y \mu^{|Y|} \det\pmatrix{0 & s_Y'\cr -s_Y & S_{Y}\cr}
where the sum is taken over subsets Y of \{1,2,\ldots,n\} with an odd number of elements. The notation s_Y denotes the vector s cut on the corresponding set of rows.

A little linear algebra shows that the determinants

\det(S_X) \qquad \mbox{and} \qquad\det\pmatrix{0 & s_Y'\cr -s_Y & S_{Y}\cr}
appearing above are odd integer squares. What is more remarkable and quite easy to prove is that in the case where S = S_0 the skew tournament matrix derived from the Brualdi-Li matrix, then all these determinants are equal to 1. This underlines the extremal role played by the Brualdi-Li matrix. It also yields the Hemasinha et al. formula in the form
\det(I - \mu A_0) = (1 - n\mu) \sum_{k {\rm \scriptstyle\ even}} {n \choose k} \mu^k + \mu^2 \sum_{k {\rm \scriptstyle\ odd}} {n \choose k} \mu^k
where A_0 is the adjusted tournament matrix derived from the Brualdi-Li matrix.



[1] R. Hemasinha, James R. Weaver, S. J. Kirkland, J. L. Stuart, Properties of the Brualdi-Li tournament matrix, Linear Algebra and its Applications 361 (2003) 63-73.