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.

Bordered Matrices

The idea of bordering matrices can be taken a little further. We can define

\widetilde{S} = \pmatrix{0 & s'\cr -s & S\cr}
so that in general \widetilde{S} is a skew-symmetric matrix. It is not in general a skew-symmetric tournament matrix, but it is if the entries of s =Se are all ones or minus ones. This is the so-called almost regular case. Further we have \widetilde{S}\tilde{e} = 0, where \tilde{e} is the vector of n+1 ones. This says that if S is an almost regular skew tournament matrix, then \widetilde{S} is a regular skew tournament matrix of order n+1. The converse is also true.

We denote by A_0 and S_0 the adjusted and skew tournament matrices derived from the Brualdi-Li matrix. We also denote \mu_0 the reciprocal of the Perron root of A_0. Then the Brualdi-Li Conjecture amounts to showing that for a general adjusted tournament matrix A, we have \det(I - \mu A) > 0 for 0 \leq \mu < \mu_0, since otherwise there would be \mu in the range 0 \leq \mu < \mu_0 for which \det(I - \mu A) = 0 giving an eigenvalue \mu^{-1} exceeding the Perron root of A_0. The analogous situation then transfers to the corresponding regular tournament matrix T. This is not straightforward since in fact 1 - n\mu_0 < 0, so any proof along these lines would have to come to grips with cancellation between the odd and even terms introduced above.

Instead of considering \det(I - \mu A) > 0 for 0 \leq \mu < \mu_0 we can consider \displaystyle\frac{\det(I - \mu A)}{\det(I - \mu S)} > 0 for the same range, since the denominator is always positive for \mu real. It would indeed suffice to show

\frac{\det(I - \mu A)}{\det(I - \mu S)} \geq \frac{\det(I - \mu A_0)}{\det(I - \mu S_0)}\qquad{\rm for\ } 0 \leq \mu \leq \mu_0.
However, a calculation gives
\det(I - \mu A) = (1 - (n+1)\mu) \det(I - \mu S) + \mu \det(I - \mu \widetilde{S})
and so the Brualdi-Li Conjecture would follow from
\frac{\det(I - \mu \widetilde{S})}{\det(I - \mu S)} \geq \frac{\det(I - \mu \widetilde{S_0})}{\det(I - \mu S_0)}\qquad{\rm for\ } 0 \leq \mu \leq \mu_0.
While the Brualdi-Li Conjecture is now known to be true, this inequality remains open. A very closely related question is to show that if R is a regular skew tournament matrix of odd order n+1, then for 0 \leq \mu \leq \mu_0, the diagonal entries of (I - \mu R)^{-1} are bounded above by
\frac{\det(I - \mu S_0)}{\det(I - \mu \widetilde{S_0})} = \frac{(1 + \mu)^n + (1 - \mu)^n}{(1 + \mu)^{n+1} + (1 - \mu)^{n+1}}.
In fact, this may be true These are open questions.

The figure shows the possible diagonal entries of (I - \mu R)^{-1} as R ranges over all 7 \times 7 skew tournament matrices and as \mu ranges over 0 \leq \mu \leq 1. The function that dominates for small values of \mu is the second largest just to the left of \mu=1. It dominates all the others in the range 0 < \mu < \frac{1}{3}\sqrt{6\sqrt{3} - 9} > \mu_0 \approx 0\!\cdot\!1704. The largest function just to the left of \mu=1 comes from a non-regular 7 \times 7 skew tournament 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.