Exercice 67

Idée. On traduit le tournoi en une égalité matricielle $M + {M}^{T} = J - I_{n}$, où $M$ est somme de $m$ matrices de rang $1$. Une matrice de rang petit a un gros noyau, dans lequel la forme $X \mapsto {X}^{T}(J - I_{n})X$ devrait être nulle, alors qu'elle y est strictement négative.

On note $b_{k}$ et $r_{k}$ les colonnes indicatrices de $B_{k}$ et $R_{k}$ ; alors $M_{k} = b_{k}{r_{k}}^{T}$. Pour $i \neq j$, les joueurs $i$ et $j$ se sont affrontés exactement une fois, l'un étant bleu et l'autre rouge, donc exactement un des coefficients $(i, j)$ et $(j, i)$ de $M$ vaut $1$, l'autre $0$. Les coefficients diagonaux de $M$ sont nuls, puisque les équipes sont disjointes. Ainsi $$M + {M}^{T} = J - I_{n}.$$ Supposons $m < n - 1$. Le système homogène ${r_{k}}^{T}X = 0$ pour $1 \leqslant k \leqslant m$, et ${U}^{T}X = 0$, où $U$ est la colonne de $1$, a $m + 1 < n$ équations et $n$ inconnues : il admet une solution $X \in \mathbb{R}^{n}$ non nulle (théorème 9). Alors $MX = \sum_{k} b_{k}({r_{k}}^{T}X) = 0$, donc $${X}^{T}(M + {M}^{T})X = 2\,{X}^{T}MX = 0.$$ Mais ${X}^{T}JX = ({U}^{T}X)^{2} = 0$, de sorte que ${X}^{T}(J - I_{n})X = -\sum_{i} x_{i}^{2} < 0$. C'est une contradiction, donc $m \geqslant n - 1$.

La valeur $n - 1$ est atteinte : au $k$-ième match, pour $1 \leqslant k \leqslant n - 1$, le joueur $k$ seul en bleu affronte les joueurs $k + 1$, …, $n$ en rouge. Deux joueurs $i < j$ se rencontrent alors au match $i$ et à lui seul. $$\boxed{m_{\min} = n - 1}$$ Remarque. Graham et Pollak ont établi ce résultat en 1971 pour décomposer un graphe complet en graphes bipartis complets ; la seule preuve connue passe par l'algèbre linéaire.