Deux morceaux, des zéros qui persistent

Récurrence sur $d$.

Initialisation. Pour $d=1$, $(A^1{)}_{ij}=a_{ij}=0$ : c'est l'hypothèse, il n'y a aucune arête de $P$ vers $Q$.

Hérédité. Supposons $(A^d{)}_{ik}=0$ pour tout $i\in P$ et tout $k\in Q$. Soient $i\in P$ et $j\in Q$ ; coupons la somme selon le paquet où vit l'intermédiaire : $$(A^{d+1}{)}_{ij}=\sum _k(A^d{)}_{ik}{a}_{kj}=\sum _{k\in P}(A^d{)}_{ik}{a}_{kj}+\sum _{k\in Q}(A^d{)}_{ik}{a}_{kj}.$$ Dans la première somme, $k\in P$ et $j\in Q$ donnent $a_{kj}=0$. Dans la seconde, $i\in P$ et $k\in Q$ donnent $(A^d{)}_{ik}=0$ par hypothèse de récurrence. Tous les termes sont nuls.

Le critère. Comme $(I_n{)}_{ij}=0$ pour $i\ne j$, le coefficient $(i,j)$ de $I_n+A+\cdots +A^{n-1}$ est nul : le critère déclare $G$ non connexe, ce qui est bien le cas.

Le point à retenir. Chacune des deux sommes s'annule pour une raison différente — l'une par l'hypothèse, l'autre par la récurrence. Un chemin qui devrait franchir une frontière inexistante n'existe pas, et le produit matriciel le sait.