Lemme de Lindström-Gessel-Viennot

Soit G un graphe orienté acyclique localement fini. Cela signifie que G ne contient aucun cycle orienté et que chaque sommet a un degré fini. On attribue un poids ${\displaystyle w_{e}}$ à chaque arête orientée e. Les poids des arêtes sont supposés appartenir à un anneau commutatif fixé. Pour chaque chemin orienté P entre deux sommets, on note ${\displaystyle w(P)}$ le produit des poids des arêtes du chemin. Pour deux sommets a et b, on note e(a, b) la somme ${\displaystyle e(a,b)=\sum _{P:a\to b}w(P)}$ qui porte sur tous les chemins de a à b. Cette somme est bien définie s'il n'y a qu'un nombre fini de chemins entre deux points quelconques ; cependant, même s'il y a un nombre infini de chemins, il peut arriver que la somme soit bien définie (par exemple lorsque tous les poids des arêtes sont des indéterminées deux à deux distinctes et que ${\displaystyle e(a,b)}$ est considéré comme une série formelle). En particulier, si l'on attribue le poids 1 à chaque arête, alors e(a, b) compte le nombre de chemins de a à b. Enfin, on fixe un ensemble de sommets « sources » ${\displaystyle A=\{a_{1},\ldots ,a_{n}\}}$ et un ensemble de sommets « buts » ${\displaystyle B=\{b_{1},\ldots ,b_{n}\}}$.

Dans ce contexte, on définit

${\displaystyle M=M_{G,w}(A,B)={\begin{pmatrix}e(a_{1},b_{1})&e(a_{1},b_{2})&\cdots &e(a_{1},b_{n})\\e(a_{2},b_{1})&e(a_{2},b_{2})&\cdots &e(a_{2},b_{n})\\\vdots &\vdots &\ddots &\vdots \\e(a_{n},b_{1})&e(a_{n},b_{2})&\cdots &e(a_{n},b_{n})\end{pmatrix}}}$.

Une n-liste de chemins sans intersection de A à B est la donnée d'une n-liste (P₁,..., P_n) de chemins de G qui a les propriétés suivantes :

• il existe une permutation ${\displaystyle \sigma }$ de ${\displaystyle \left\{1,2,...,n\right\}}$ telle que pour tout i, le chemin P_i soit un chemin allant de ${\displaystyle a_{i}}$ à ${\displaystyle b_{\sigma (i)}}$ ;
• pour toute paire d'indices ${\displaystyle i\neq j}$, les chemins P_i et P_j n'ont pas de sommet en commun (pas même des extrémités).

Pour une telle n-liste (P₁,..., P_n), on note ${\displaystyle \sigma (P)}$ la permutation de ${\displaystyle \sigma }$ définie par la première condition.

Le lemme de Lindström-Gessel-Viennot exprime alors que le déterminant de M est la somme alternée portant sur toutes les n-listes P = (P₁,..., P_n) de chemins non sécants de A à B :

${\displaystyle \det(M)=\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\operatorname {sign} (\sigma (P))\prod _{i=1}^{n}w(P_{i})}$

(où ${\displaystyle \operatorname {sign} (\sigma (P))}$ est la signature de ${\displaystyle \sigma (P)}$).

Autrement dit, le déterminant de M compte les poids de toutes les n-listes de chemins non sécants partant de A et se terminant en B, chacun affecté du signe de la permutation déterminée par le chemin ${\displaystyle P_{i}}$, qui conduit ${\displaystyle a_{i}}$ en ${\displaystyle b_{\sigma (i)}}$.

En particulier, si la seule permutation possible est l'identité (c'est-à-dire que toute n-liste de chemins non sécants de A à B envoie a_i sur b _i pour tout i) et que tous les poids sont égaux à 1, alors det(M) est exactement le nombre de n-listes de chemins non sécants partant de A et se terminant en B.

Avant de prouver le lemme de Lindström-Gessel-Viennot, on introduit quelques notations.

Étant donné deux n-listes de sommets de G, disons${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ et ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$, un n-chemin de ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ à${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ est une n-liste ${\displaystyle (P_{1},P_{2},\ldots ,P_{n})}$ de chemins dans G, où chaque ${\displaystyle P_{i}}$ mène de ${\displaystyle a_{i}}$ à ${\displaystyle b_{i}}$. Ce n-chemin est dit sans intersection si deux chemins ${\displaystyle P_{i}}$ et ${\displaystyle P_{j}}$ associés à des indices distincts ${\displaystyle i\neq j}$ n'ont aucun sommet en commun (y compris à leurs extrémités). Sinon, on l'appellera enchevêtré.

Étant donné un n-chemin ${\displaystyle P=(P_{1},P_{2},\ldots ,P_{n})}$, son poids ${\displaystyle w(P)}$ est défini comme le produit des poids ${\displaystyle w(P_{1})w(P_{2})\cdots w(P_{n})}$.

Un n-chemin tordu de ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ à ${\displaystyle (b_{1},b_{2},\ldots ,b_{n})}$ est un n-chemin ${\displaystyle P}$ de ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})}$ à ${\displaystyle \left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)}$ pour une permutation ${\displaystyle \sigma }$ convenable du groupe symétrique ${\displaystyle {\mathfrak {S}}_{n}}$. Cette permutation ${\displaystyle \sigma }$ sera appelé la torsion de ce n-chemin tordu et notée ${\displaystyle \sigma (P)}$. Ceci, bien sûr, généralise la notation ${\displaystyle \sigma (P)}$ utilisée ci-dessus.

En revenant à la définition de M, on peut développer det M comme une somme alternée indexée par les permutations ; on obtient ainsi

${\displaystyle {\begin{aligned}\det M&=\sum _{\sigma \in S_{n}}\operatorname {sign} (\sigma )\prod _{i=1}^{n}e(a_{i},b_{\sigma (i)})\\&=\sum _{\sigma \in S_{n}}\operatorname {sign} (\sigma )\prod _{i=1}^{n}\sum _{P_{i}:a_{i}\to b_{\sigma (i)}}w(P_{i})\\&=\sum _{\sigma \in S_{n}}\operatorname {sign} (\sigma )\sum \{w(P):P~{\text{un}}~n{\text{-chemin de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{\sigma (1)},b_{\sigma (2)},\ldots ,b_{\sigma (n)}\right)\}\\&=\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu sans intersection de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&\quad +\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu enchevêtré}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}\\&=\sum _{(P_{1},\ldots ,P_{n})\colon A\to B}\operatorname {sign} (\sigma (P))w(P)\\&\quad +\underbrace {\sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu enchevêtré de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}} _{=0\,?}.\\\end{aligned}}}$

Il s'agit donc de montrer que la somme des ${\displaystyle \operatorname {sign} (\sigma (P))w(P)}$ sur tous les n-chemins tordus enchevêtrés est nulle. Pour cela, on définit une involution qui fixe le poids et change la signature de la permutation associée sur l'ensemble ${\displaystyle {\mathcal {E}}}$ des n-chemins tordus enchevêtrés. Autrement dit, on construit une involution ${\displaystyle f:{\mathcal {E}}\longrightarrow {\mathcal {E}}}$ avec les propriétés ${\displaystyle w(f(P))=w(P)}$ et ${\displaystyle \operatorname {sign} (\sigma (f(P)))=-\operatorname {sign} (\sigma (P))}$ pour tout ${\displaystyle P\in {\mathcal {E}}}$. L'existence d'une telle involution montre que la somme qui reste,

${\displaystyle \sum \{\operatorname {sign} (\sigma (P))w(P):P~{\text{un}}~n{\text{-chemin tordu enchevêtré de}}~\left(a_{1},a_{2},\ldots ,a_{n}\right)~{\text{à}}~\left(b_{1},b_{2},...,b_{n}\right)\}=\sum _{P\in {\mathcal {E}}}\operatorname {sign} (\sigma (P))w(P)}$

est nulle, puisque ses termes s'éliminent deux à deux : le terme correspondant à chaque ${\displaystyle P\in {\mathcal {E}}}$ simplifie le terme correspondant à ${\displaystyle f(P)}$ (vu que les permutations associées à ${\displaystyle P}$ et ${\displaystyle f(P)}$ sont différentes, ${\displaystyle f}$ n'a pas de point fixe).

Construisons donc l'involution ${\displaystyle f}$. L'idée consiste à choisir deux chemins qui s'intersectent dans un n-chemin enchevêtré et à échanger leurs queues après leur point d'intersection. Dans un tel n-chemin, il y a en général plusieurs paires de chemins qui se croisent, qui peuvent d'ailleurs se croiser plusieurs fois ; il faut donc faire un choix judicieux. Soit ${\displaystyle P=\left(P_{1},P_{2},...,P_{n}\right)}$ un n-chemin tordu enchevêtré, on définit ${\displaystyle f(P)}$ de la façon suivante.

On dit qu'un sommet est encombré s'il appartient à au moins deux des chemins ${\displaystyle P_{1},P_{2},...,P_{n}}$. Du fait que le graphe est acyclique, cela équivaut à « apparaître au moins deux fois dans tous les chemins »^{[n 1]}. Comme P est enchevêtré, il possède au moins un sommet encombré. On choisit le plus petit indice ${\displaystyle i\in \{1,2,\ldots ,n\}}$ tel que ${\displaystyle P_{i}}$ contient un sommet encombré. Ensuite, on choisit le premier sommet encombré v sur ${\displaystyle P_{i}}$ (c'est-à-dire « rencontré en premier lors d'un voyage le long de ${\displaystyle P_{i}}$ »), et on choisit le plus grand j tel que v appartient à ${\displaystyle P_{j}}$. Comme ${\displaystyle v}$ est encombré, que le graphe est acyclique et que ${\displaystyle i}$ est minimal, on a ${\displaystyle j>i}$. On écrit les deux chemins ${\displaystyle P_{i}}$ et ${\displaystyle P_{j}}$ sous la forme

${\displaystyle {\begin{array}{rcl}P_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {\mathbf {u} _{\alpha }\to u_{\alpha +1}\ldots \to u_{r}=b_{\sigma (i)}} ^{{\text{queue de}}~P_{i}}\\P_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {\mathbf {v} _{\beta }\to v_{\beta +1}\ldots \to v_{s}=b_{\sigma (j)}} _{{\text{queue de}}~P_{j}}\\\end{array}}}$

où ${\displaystyle \sigma =\sigma (P)}$ et où ${\displaystyle \alpha }$ et ${\displaystyle \beta }$ sont tels que v soit le ${\displaystyle \alpha }$-ième sommet de ${\displaystyle P_{i}}$ et le ${\displaystyle \beta }$-ième sommet de ${\displaystyle P_{j}}$ (c'est-à-dire ${\displaystyle v=u_{\alpha }=v_{\beta }}$). On pose ${\displaystyle \alpha _{P}=\alpha }$ et ${\displaystyle \beta _{P}=\beta }$ et ${\displaystyle i_{P}=i}$ et ${\displaystyle j_{P}=j}$ . Le ${\displaystyle k}$-ième chemin de ${\displaystyle f(P)}$ est ${\displaystyle P_{k}}$ si ${\displaystyle k}$ est différent de ${\displaystyle i}$ et ${\displaystyle j}$ ; par ailleurs, les chemins ${\displaystyle P_{i}}$ et ${\displaystyle P_{j}}$ sont remplacés par les suivants :

${\displaystyle {\begin{array}{rcl}P'_{i}&\equiv &a_{i}=u_{0}\to u_{1}\to u_{2}\ldots u_{\alpha -1}\to \overbrace {v_{\beta _{P}}\to v_{\beta _{P}+1}\ldots \to v_{s}=b_{\sigma (j)}} ^{{\text{queue de}}~P_{j}}\\P'_{j}&\equiv &a_{j}=v_{0}\to v_{1}\to v_{2}\ldots v_{\beta -1}\to \underbrace {u_{\alpha _{P}}\to u_{\alpha _{P}+1}\ldots \to u_{r}=b_{\sigma (i)}} _{{\text{queue de}}~P_{i}}\\\end{array}}}$

Il est immédiat de voir que ${\displaystyle f(P)}$ est un n-chemin tordu enchevêtré. En revenant sur la construction, on constate que ${\displaystyle i_{f(P)}=i_{P}}$, ${\displaystyle j_{f(P)}=j_{P}}$, que ${\displaystyle \alpha _{f(P)}=\alpha _{P}}$ et ${\displaystyle \beta _{f(P)}=\beta _{P}}$, de sorte que pour calculer l'image de ${\displaystyle f(P)}$ par ${\displaystyle f}$, on échange à nouveau les queues de ${\displaystyle f(P)_{i},f(P)_{j}}$ en laissant les autres chemins intacts. On en déduit que ${\displaystyle f(f(P))=P}$ , c'est-à-dire que ${\displaystyle f}$ est une involution. Il reste à vérifier les propriétés d'anti-symétrie annoncées.

Par construction, la permutation ${\displaystyle \sigma (f(P))}$ coïncide avec ${\displaystyle \sigma =\sigma (P)}$ sauf qu'elle échange ${\displaystyle \sigma (i)}$ et ${\displaystyle \sigma (j)}$ – c'est-à-dire que ${\displaystyle \sigma (f(P))=(\sigma (i),\sigma (j))\sigma (P)}$ – ce qui entraîne que ${\displaystyle \operatorname {sign} (\sigma (f(P)))=-\operatorname {sign} (\sigma (P))}$. Pour montrer que ${\displaystyle w(f(P))=w(P)}$, on calcule d'abord, à cause de l'échange des queues :

${\displaystyle {\begin{aligned}w(P'_{i})w(P'_{j})&=\left(\prod _{t=0}^{\alpha -1}w(u_{t},u_{t+1})\cdot \prod _{t=\beta }^{s-1}w(v_{t},v_{t+1})\right)\cdot \left(\prod _{t=0}^{\beta -1}w(v_{t},v_{t+1})\cdot \prod _{t=\alpha }^{r-1}w(u_{t},u_{t+1})\right)\\&=\prod _{t=0}^{r-1}w(u_{t},u_{t+1})\cdot \prod _{t=0}^{s-1}w(v_{t},v_{t+1})\\&=w(P_{i})w(P_{j}).\end{aligned}}}$

Ainsi, on a

${\displaystyle w(f(P))=\prod _{k=1}^{n}w(f(P)_{k})=\prod _{k=1,~k\neq i,j}^{n}w(P_{k})\cdot w(P'_{i})w(P'_{j})=\prod _{k=1,~k\neq i,j}^{n}w(P_{k})\cdot w(P_{i})w(P_{j})=\prod _{k=1}^{n}w(P_{k})=w(P)}$ .

La construction de cette involution ayant les propriétés souhaitées termine la preuve du lemme de Lindström-Gessel-Viennot.

Remarque. On trouve des arguments semblables à celui-ci dans plusieurs sources, avec des variations concernant le choix des queues à échanger. C'est une version avec j le plus petit (différent de i) au lieu du plus grand qui apparaît dans (Gessel et Viennot 1989, démonstration du théorème 1).

Le premier exemple est assez trivial mais illustratif. Étant donné un entier n et n² éléments d'un anneau quelconque (ou indéterminées) ${\displaystyle m_{ij}}$ (${\displaystyle 1\leq i,j\leq n}$) on considère le graphe biparti complet ayant 2n sommets ${\displaystyle \{a_{1},\dots ,a_{n},b_{1},\dots ,b_{n}\}}$ et une arête de ${\displaystyle a_{i}}$ vers ${\displaystyle b_{j}}$ de poids ${\displaystyle m_{ij}}$ pour tout couple ${\displaystyle (i,j)}$. On prend naturellement ${\displaystyle A=\{a_{1},\dots ,a_{n}\}}$ et ${\displaystyle B=\{b_{1},\dots ,b_{n}\}}$ : il y a exactement un chemin de ${\displaystyle a_{i}}$ vers ${\displaystyle b_{j}}$ et son poids est ${\displaystyle m_{ij}}$. La matrice ${\displaystyle M}$ du lemme est donc simplement ${\displaystyle (m_{ij})_{1\leq i,j\leq n}}$. Un n-chemin sans intersection ${\displaystyle P=(P_{1},\dots ,P_{n})}$ est donné par la permutation ${\displaystyle \sigma }$ : le chemin ${\displaystyle P_{i}}$ est l'arête de ${\displaystyle a_{i}}$ à ${\displaystyle b_{\sigma (i)}}$ ; son poids est ${\displaystyle m_{i,\sigma (i)}}$ et le poids de ${\displaystyle P}$ est ${\displaystyle w(P)=m_{1,\sigma (1)}\cdots m_{n,\sigma (n)}}$. Ainsi, le lemme de Lindström-Gessel-Viennot s'écrit simplement

${\displaystyle \det M=\sum _{\sigma \in {\mathfrak {S}}_{n}}\operatorname {sign} (\sigma )\prod _{i=1}^{n}m_{i,\sigma (i)}}$,

ce qui le réduit à la définition du déterminant...

On peut utiliser le lemme de Lindström-Gessel-Viennot pour démontrer la formule de Binet-Cauchy, d'où l'on peut en particulier déduire la multiplicativité du déterminant.

On peut utiliser le lemme de Lindström-Gessel-Viennot pour démontrer l'équivalence de deux définitions différentes des polynômes de Schur. Étant donné une partition ${\displaystyle \lambda =\lambda _{1}\geq \cdots \geq \lambda _{r}>0}$ de n en r parts, le polynôme de Schur ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})}$ peut être indifféremment défini par les égalités :

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\sum _{T}w(T),}$

où la somme porte sur tous les tableaux de Young semi-standards T de forme λ (c'est-à-dire que l'on affecte un entier i de {1,..., n} à chaque case du diagramme de Young de T de sorte qu'une case soit inférieure ou égale à celle qui est à sa droite et strictement inférieure à celle qui est en dessous), et où le poids ${\displaystyle w(T)}$ d'un tableau T est défini comme le monôme obtenu comme le produit des x_i indexés par les coefficients i de T. Par exemple, le poids du tableau est ${\displaystyle x_{1}x_{3}x_{4}^{3}x_{5}x_{6}x_{7}}$ ;

• ${\displaystyle s_{\lambda }(x_{1},\ldots ,x_{n})=\det \left((h_{\lambda _{i}+j-i})_{1\leq i,j\leq r}\right),}$

où les h_i sont les polynômes symétriques homogènes complets (en) (et h_i vaut 0 si i est négatif). Par exemple, pour la partition (3,2,2,1), le déterminant correspondant est

${\displaystyle s_{(3,2,2,1)}={\begin{vmatrix}h_{3}&h_{4}&h_{5}&h_{6}\\h_{1}&h_{2}&h_{3}&h_{4}\\1&h_{1}&h_{2}&h_{3}\\0&0&1&h_{1}\end{vmatrix}}.}$

On montre l'équivalence entre ces deux définitions. On définit un graphe orienté : ses sommets sont les points de ${\displaystyle \mathbb {Z} ^{2}}$, ou plutôt ${\displaystyle \mathbb {N} \times \{1,\dots ,n\}}$ ; il y a une arête « est » de ${\displaystyle (i,j)}$ à ${\displaystyle (i+1,j)}$ de poids ${\displaystyle x_{i}}$ et, si ${\displaystyle j\leq n-1}$, une arête « nord » de ${\displaystyle (i,j)}$ à ${\displaystyle (i,j+1)}$ de poids ${\displaystyle 1}$.

À présent, on fixe une partition λ et on considère les r points de départ ${\displaystyle a_{i}=(r+1-i,1)}$ et les r points d'arrivée ${\displaystyle b_{j}=(\lambda _{j}+r+1-j,n)}$. Avec cette définition, les r-listes de chemins de A à B s'identifient aux tableaux de Young semi-standard de forme λ, et le poids d'une telle r-liste est la somme correspondante dans la première définition des polynômes de Schur. Par exemple, le tableau correspond au quadruplet de chemins suivant.

Par ailleurs, la matrice M est exactement la matrice écrite ci-dessus pour le graphe orienté introduit plus haut. Ceci montre l'équivalence requise. (Voir également (Sagan 2010, §4.5), ou la première preuve de (Stanley 1999, théorème 7.16.1), ou (Fulmek 2012, §3.3), ou (Martin 2012, §9.13), pour de légères variations sur cet argument.)

On peut citer, entre autres :

• le calcul de certains « déterminants binomiaux », la positivité de tous les mineurs de la matrice ${\displaystyle \left({\binom {i}{j}}\right)_{1\leq i,j}}$ et plusieurs formules analogues à la formule des équerres, cf. (Gessel et Viennot 1985) ;
• le calcul du nombre de partitions planes (en) contenues dans une boîte (résultat dû à Percy Alexander MacMahon), cf. (Gessel et Viennot 1989) ;
• les deux formules de Jacobi-Trudi (en), etc.