Classements et cycles cachés

I — Incidence et orthogonalité

1. Si l’arête $e$ est orientée de $i$ vers $j$, sa colonne dans $B$ contient $-1$ en ligne $i$ et $+1$ en ligne $j$. Ainsi

$$(B^\top p)_e=p_j-p_i.$$

Pour $x\in\mathbb R^m$, la ligne $i$ de $B$ contient $+1$ pour les arêtes orientées vers $i$, $-1$ pour celles orientées à partir de $i$, et $0$ pour les autres. Donc

$$(Bx)_i =\sum_{e\,:\,e\text{ arrive en }i}x_e -\sum_{e\,:\,e\text{ part de }i}x_e.$$

2. Le vecteur

$$\mathbf1=(1,\ldots,1)^\top$$

vérifie $B^\top\mathbf1=0$, puisque chaque colonne de $B$ contient un coefficient $-1$ et un coefficient $+1$.

Réciproquement, soit $p\in\ker(B^\top)$. Pour toute arête orientée $i\to j$, la question 1 donne

$$p_j-p_i=0.$$

Deux sommets adjacents portent donc la même valeur. Le graphe étant connexe, deux sommets quelconques peuvent être reliés par un chemin ; toutes les coordonnées de $p$ sont égales. Par conséquent

$$\boxed{\ker(B^\top)=\operatorname{Vect}(\mathbf1).}$$

Ainsi

$$\operatorname{rg}B =\operatorname{rg}(B^\top) =n-1,$$

puis, par le théorème du rang appliqué à $B:\mathbb R^m\to\mathbb R^n$,

$$\boxed{\dim\ker B=m-n+1.}$$

3. Pour $p\in\mathbb R^n$ et $x\in\mathbb R^m$,

$$\langle B^\top p,x\rangle =(B^\top p)^\top x =p^\top Bx =\langle p,Bx\rangle.$$

Si $x\in\ker B$, alors ce produit scalaire est nul pour tout $p$. On obtient donc

$$\operatorname{Im}(B^\top)\perp\ker B.$$

D’autre part,

$$\dim\operatorname{Im}(B^\top)+\dim\ker B =(n-1)+(m-n+1)=m.$$

Les deux sous-espaces orthogonaux ont donc des dimensions dont la somme vaut $m$ :

$$\boxed{\mathbb R^m =\operatorname{Im}(B^\top) \mathbin{\overset\perp\oplus}\ker B.}$$

Par définition d’une somme directe, tout $x\in\mathbb R^m$ s’écrit d’une manière unique

$$x=g+c, \qquad g\in\operatorname{Im}(B^\top), \qquad c\in\ker B.$$

Si $g=B^\top p$, alors, pour tout $\lambda\in\mathbb R$,

$$B^\top(p+\lambda\mathbf1)=B^\top p.$$

Réciproquement, si $B^\top p=B^\top q$, alors

$$p-q\in\ker(B^\top)=\operatorname{Vect}(\mathbf1).$$

Ainsi tous les vecteurs donnant le même $g$ sont exactement

$$\boxed{p+\lambda\mathbf1,\qquad \lambda\in\mathbb R.}$$

II — Duels et meilleur score global

4. Appliquons la décomposition de la question 3 au vecteur $y$. Il existe un unique couple

$$g\in\operatorname{Im}(B^\top), \qquad c\in\ker B$$

tel que

$$y=g+c.$$

Choisissons $p_0$ tel que $g=B^\top p_0$. Pour tout $p\in\mathbb R^n$,

$$y-B^\top p =c+B^\top(p_0-p).$$

Les deux termes sont orthogonaux, donc

$$\|y-B^\top p\|^2 =\|c\|^2+\|B^\top(p_0-p)\|^2.$$

La quantité est minimale exactement lorsque

$$B^\top p=B^\top p_0=g.$$

D’après la question 3, tous les minimisateurs sont donc de la forme

$$\boxed{p_0+\lambda\mathbf1,\qquad \lambda\in\mathbb R.}$$

On peut aussi les caractériser par une équation matricielle. En effet, au minimum,

$$y-B^\top p\in\ker B,$$

donc

$$B(y-B^\top p)=0,$$

soit

$$\boxed{BB^\top p=By.}$$

Réciproquement, si cette équation est vérifiée, alors $y-B^\top p\in\ker B$ ; la décomposition orthogonale de la question 3 montre que $B^\top p$ est nécessairement la composante $g$ de $y$, donc $p$ est bien un minimisateur.

Enfin, parmi les vecteurs $p_0+\lambda\mathbf1$, la somme des coordonnées vaut

$$\sum_{i=1}^n(p_0)_i+n\lambda.$$

Il existe donc une unique valeur de $\lambda$ pour laquelle cette somme est nulle. Ainsi

$$\boxed{\text{il existe un unique minimisateur de somme nulle}.}$$

5. Par définition,

$$L=BB^\top,$$

donc

$$L^\top=L.$$

La matrice $L$ est symétrique. Pour tout $p\in\mathbb R^n$,

$$p^\top Lp =p^\top BB^\top p =\|B^\top p\|^2 \geqslant0.$$

La question 1 donne plus précisément

$$\boxed{p^\top Lp =\sum_{\{i,j\}\in E}(p_j-p_i)^2.}$$

Si $Lp=0$, alors

$$0=p^\top Lp=\|B^\top p\|^2,$$

donc $B^\top p=0$. La réciproque est immédiate. Par la question 2,

$$\boxed{\ker L=\operatorname{Vect}(\mathbf1).}$$

Pour les coefficients, $L_{ii}$ est le produit scalaire de la ligne $i$ de $B$ avec elle-même. Chaque arête incidente à $i$ y contribue pour $1$, donc

$$L_{ii}=\deg(i).$$

Si $i\neq j$ sont adjacents, l’unique colonne associée à l’arête $\{i,j\}$ contient un $-1$ et un $+1$ sur les lignes $i$ et $j$ ; elle contribue donc pour $-1$. S’ils ne sont pas adjacents, aucune colonne ne contribue aux deux lignes. Ainsi

$$\boxed{ L_{ij}=\begin{cases} \deg(i) & \text{si }i=j,\\ -1 & \text{si }i\neq j\text{ sont adjacents},\\ 0 & \text{sinon}. \end{cases}}$$

6. Soit $D$ la matrice diagonale de taille $m$ dont tous les coefficients diagonaux valent $1$, sauf celui associé à l’arête retournée, qui vaut $-1$. Après changement d’orientation,

$$B'=BD, \qquad y'=Dy.$$

Comme $D^\top=D$ et $D^2=I_m$,

$$B'^\top p=DB^\top p.$$

Par conséquent

$$y'-B'^\top p =D(y-B^\top p).$$

Or $D$ conserve la norme, donc

$$\|y'-B'^\top p\| =\|y-B^\top p\|$$

pour tout $p$. Les deux problèmes de minimisation ont donc exactement les mêmes minimisateurs et la même valeur minimale. En particulier, le minimisateur de somme nulle ne dépend pas du choix des orientations.

III — Un exemple complet à quatre objets

7. Dans l’ordre $12,13,14,23,24,34$,

$$B= \begin{pmatrix} -1&-1&-1&0&0&0\\ 1&0&0&-1&-1&0\\ 0&1&0&1&0&-1\\ 0&0&1&0&1&1 \end{pmatrix}.$$

On calcule

$$L=BB^\top= \begin{pmatrix} 3&-1&-1&-1\\ -1&3&-1&-1\\ -1&-1&3&-1\\ -1&-1&-1&3 \end{pmatrix} =4I_4-J,$$

où $J$ désigne la matrice dont tous les coefficients valent $1$.

Par ailleurs,

$$By=(-12,-4,4,12)^\top.$$

Le minimisateur recherché est de somme nulle. Sur l’hyperplan

$$p_1+p_2+p_3+p_4=0,$$

on a $Jp=0$, donc $Lp=4p$. L’équation de la question 4 devient

$$4p=By,$$

d’où

$$\boxed{p=(-3,-1,1,3)^\top.}$$

On en déduit

$$B^\top p=(2,4,6,2,4,2)^\top$$

et

$$\boxed{c=y-B^\top p=(1,-1,0,1,0,0)^\top.}$$

Ainsi

$$\|c\|^2=3,$$

tandis que

$$\|y\|^2=3^2+3^2+6^2+3^2+4^2+2^2=83.$$

Donc

$$\boxed{\frac{\|c\|^2}{\|y\|^2}=\frac3{83}.}$$

Le vecteur $c$ est non nul uniquement sur les arêtes $12$, $13$ et $23$. Sur $12$ et $23$, son signe est positif ; sur $13$, il est négatif. Avec les orientations $1\to2$, $1\to3$ et $2\to3$, ces signes correspondent au parcours

$$1\to2\to3\to1.$$

La partie des données que le meilleur score global n’explique pas est donc ici entièrement portée par le triangle $123$. Le rapport $3/83$ compare sa norme carrée à celle des données initiales.

IV — Triangles et cycles qui leur échappent

8. Considérons une colonne $c_k$ de $C$, associée à un triangle parcouru dans un sens fixé. À chacun des trois sommets du triangle, une arête du parcours arrive et une autre repart. Les deux contributions correspondantes se compensent dans $Bc_k$. Ainsi

$$Bc_k=0.$$

Ceci vaut pour toute colonne, donc

$$\boxed{BC=0.}$$

Par conséquent

$$\operatorname{Im}C\subset\ker B.$$

La question 3 donne

$$\operatorname{Im}(B^\top)\perp\ker B,$$

donc en particulier

$$\operatorname{Im}(B^\top)\perp\operatorname{Im}C.$$

Par définition,

$$H=\ker B\cap\ker(C^\top).$$

Or

$$\ker(C^\top)=(\operatorname{Im}C)^\perp.$$

Ainsi $H$ est exactement le sous-espace de $\ker B$ orthogonal à $\operatorname{Im}C$, d’où

$$\ker B =\operatorname{Im}C \mathbin{\overset\perp\oplus}H.$$

En combinant avec la question 3,

$$\boxed{ \mathbb R^m =\operatorname{Im}(B^\top) \mathbin{\overset\perp\oplus}\operatorname{Im}C \mathbin{\overset\perp\oplus}H.}$$

Enfin,

$$\dim H =\dim\ker B-\dim\operatorname{Im}C.$$

Comme $\dim\ker B=m-n+1$,

$$\boxed{\dim H=m-n+1-\operatorname{rg}C.}$$

9. Toujours dans l’ordre $12,13,14,23,24,34$,

$$c_{123}=(1,-1,0,1,0,0)^\top,$$ $$c_{124}=(1,0,-1,0,1,0)^\top,$$ $$c_{134}=(0,1,-1,0,0,1)^\top.$$

Ces trois vecteurs sont linéairement indépendants : dans une relation

$$\alpha c_{123}+\beta c_{124}+\gamma c_{134}=0,$$

la coordonnée $23$ impose $\alpha=0$, la coordonnée $24$ impose $\beta=0$, puis la coordonnée $34$ impose $\gamma=0$.

Ainsi

$$\operatorname{rg}C\geqslant3.$$

Mais $\operatorname{Im}C\subset\ker B$ et, pour $K_4$, $m=6$ et $n=4$, donc

$$\dim\ker B=6-4+1=3.$$

Par conséquent

$$\boxed{\operatorname{rg}C=3,\qquad \operatorname{Im}C=\ker B.}$$

La formule de la question 8 donne alors

$$\boxed{H=\{0\}.}$$

Le vecteur de la question 7 est exactement

$$c=(1,-1,0,1,0,0)^\top=c_{123}.$$

Il appartient donc entièrement à $\operatorname{Im}C$.

10. Dans l’ordre $12,23,34,14$, avec les orientations $1\to2$, $2\to3$, $3\to4$ et $1\to4$,

$$B= \begin{pmatrix} -1&0&0&-1\\ 1&-1&0&0\\ 0&1&-1&0\\ 0&0&1&1 \end{pmatrix}.$$

Ici $n=m=4$. Le graphe est connexe, donc

$$\dim\ker B=m-n+1=1.$$

Comme aucun triangle n’est sélectionné,

$$\operatorname{Im}C=\{0\},$$

et donc

$$H=\ker B.$$

Le vecteur

$$h=(1,1,1,-1)^\top$$

vérifie immédiatement $Bh=0$. Il est non nul et $\ker B$ est de dimension $1$, donc

$$\boxed{H=\operatorname{Vect}(h).}$$

Dans $K_4$, les vecteurs associés aux triangles sélectionnés engendrent tout $\ker B$, de sorte que $H=\{0\}$. Dans le carré sans diagonale, le cycle $1-2-3-4-1$ ne peut pas être obtenu à partir de triangles sélectionnés ; il subsiste donc dans $H$.

11. La question 8 fournit directement, pour tout $y\in\mathbb R^m$, une unique décomposition orthogonale

$$\boxed{y=g+t+h}$$

avec

$$g\in\operatorname{Im}(B^\top), \qquad t\in\operatorname{Im}C, \qquad h\in H.$$

Si $g=B^\top p$, tous les vecteurs $p$ donnant ce même $g$ diffèrent d’un multiple de $\mathbf1$. La condition

$$p_1+\cdots+p_n=0$$

sélectionne donc un unique $p$.

Si $t=C\alpha$ avec $\alpha\in\mathbb R^q$, alors $\alpha$ est unique exactement lorsque l’application linéaire

$$\alpha\longmapsto C\alpha$$

est injective, c’est-à-dire lorsque

$$\boxed{\ker C=\{0\}.}$$

Cela équivaut à dire que les colonnes de $C$ sont linéairement indépendantes, ou encore que

$$\boxed{\operatorname{rg}C=q.}$$

Dans le problème de classement :

• $g$ est la partie des comparaisons expliquée par des différences de scores globaux ;
• $t$ regroupe la partie expliquée par les triangles sélectionnés ;
• $h$ est la partie cyclique restante, orthogonale à tous ces triangles.

Sources

[SOURCE] L.-H. Lim — Hodge Laplacians on Graphs. Lien direct [SOURCE] Jiang, Lim, Yao et Ye — Statistical Ranking and Combinatorial Hodge Theory. Lien direct