Construction du graphe - Matrice des phyla

2. Matrice des phyla

Notations

On note dans la suite :

A = [ a_{i j} ] la matrice des degrés de connexité
B = [ b_{i j} ] la matrice des liens de filiation
δ_{i j} = 1 si i=j
δ_{i j} = 0 si i≠j (symboles de Kronecker)

a_{i j} se lit : « i est fils de j avec un poids a_{i j} »
b_{i j} se lit : « i est directement fils de j avec un poids b_{i j} »

2.1. matrices compatibles

(A,B) est un couple de matrices compatible si :

∑
k

b_{i k} a_{k j} =

∑
l

a_{i l} b_{l j} =

a_{i j} − δ_{i j}

qui signifie que, au δ_i j près :

le nombre de fois que i est fils de j est égal à la somme sur k du nombre de fois que k est fils de j, pondéré par le nombre de fois que i est directement fils de k ;
le nombre de fois que j est père de i est égal à la somme sur l du nombre de fois que l est père de i, pondéré par le nombre de fois que j est directement père de l.

Remarque :

Avant toute chose, il faut savoir si la notion est pertinente, c'est-à-dire s'il existe au moins un couple de matrices (A,B) qui vérifie la condition de compatibilité.

Il en existe. On peut prendre par exemple pour A la matrice identité et pour B la matrice nulle.

2.2. transformation directe

Soit T_{p q} la transformation :

T_{p q} :	α_{i j} = a_{i j} + a_{i p} a_{q j}
	β_{i j} = b_{i j} + δ_{i p} δ_{q j}

T_{p q} intuitivement rajoute l'arc « p est fils de q ».

Alors pour (A,B) compatible, T_{p q}(A,B) est compatible si a_{q p} = 0.

On remarque que la condition signifie très précisément :
« on reste compatible tant qu'on n'introduit pas de cycle. »

Calcul

∑ β_{i k} α_{k j}

= ∑ (b_{i k} + δ_{i p} δ_{q k}) (a_{k j} + a_{k p} a_{q j})

= ∑ b_{i k} a_{k j} + δ_{i p} (a_{q j} + a_{q p} a_{q j}) + ∑ b_{i k} a_{k p} a_{q j}

= (a_{i j} − δ_{i j}) + δ_{i p} a_{q j} + (a_{i p} − δ_{i p}) a_{q j}

= (a_{i j} + a_{i p} a_{q j}) − δ_{i j} = α_{i j} − δ_{i j}

∑ α_{i l} β_{l j}

= ∑ (a_{i l} + a_{i p} a_{q l}) (b_{l j} + δ_{l p} δ_{q j})

= ∑ a_{i l} b_{l j} + δ_{q j}(a_{i p} + a_{i p} a_{q p}) + ∑ a_{i p} a_{q l} b_{l j}

= (a_{i j} − δ_{i j}) + δ_{q j} a_{i p} + a_{i p} (a_{q j} − δ_{q j})

= (a_{i j} + a_{i p} a_{q j}) − δ_{i j} = α_{i j} − δ_{i j}

2.3. transformation inverse

Soit S_{p q} la transformation :

S_{p q} :	~a_{i j} = a_{i j} − a_{i p} a_{q j}
	~b_{i j} = b_{i j} − δ_{i p} δ_{q j}

S_{p q} intuitivement supprime l'arc « p est fils de q ».

Alors pour (A,B) compatible, S_{p q}(A,B) est compatible si a_{q p} = 0.

De plus, on a : S_{p q} T_{p q} (A,B) = (A,B).

Calcul

La compatibilité de S_{p q}(A,B) se démontre de la même façon que pour T_{p q}(A,B).

On calcule : S_{p q} T_{p q} (A,B) = (A,B).

~α_{i j}	= α_{i j} − α_{i p} α_{q j}
	= (a_{i j} + a_{i p} a_{q j}) − (a_{i p} + a_{i p} a_{q p}) (a_{q j} + a_{q p} a_{q j})
	= a_{i j} + a_{i p} a_{q j} − a_{i p} a_{q j} = a_{i j}

(sachant que (A,B) est compatible, on a : a_{q p} = 0)

2.4. commutativité

Soit (A,B) un couple de matrices compatible.

U_{p q} :	~a_{i j} = a_{i j} + x a_{i p} a_{q j}
	~b_{i j} = b_{i j} + x δ_{i p} δ_{q j}
V_{m n} :	~a_{i j} = a_{i j} + y a_{i m} a_{n j}
	~b_{i j} = b_{i j} + y δ_{i m} δ_{n j}

avec x et y = 1 ou −1.

Alors :

U_{p q} V_{m n} = V_{m n} U_{p q}

si les transformations préservent la compatibilité.

Calcul

On note :

U_{p q} (A) = [ Ua_{i j} ]	V_{m n} U_{p q} (A) = [ VUa_{i j} ]
V_{m n} (A) = [ Va_{i j} ]	U_{p q} V_{m n} (A) = [ UVa_{i j} ]

VUa_{i j}	= (Ua_{i j}) + y (Ua_{i m}) (Ua_{n j})
	= (a_{i j} + x a_{i p} a_{q j}) + y (a_{i m} + x a_{i p} a_{q m}) (a_{n j} + x a_{n p} a_{q j})
	= (a_{i j} + x a_{i p} a_{q j} + y a_{i m} a_{n j}) + xy (a_{i p} a_{q m} a_{n j} + a_{i m} a_{n p} a_{q j}) + x²y a_{n p} a_{q m} a_{i p} a_{q j}
UVa_{i j}	= (Va_{i j}) + x (Va_{i p}) (Va_{q j})
	= (a_{i j} + y a_{i m} a_{n j}) + x (a_{i p} + y a_{i m} a_{n p}) (a_{q j} + y a_{q m} a_{n j})
	= (a_{i j} + x a_{i p} a_{q j} + y a_{i m} a_{n j}) + xy (a_{i m} a_{n p} a_{q j} + a_{i p} a_{q m} a_{n j}) + xy² a_{n p} a_{q m} a_{i m} a_{n j}

Les termes croisés sont respectivement :

x²y a_{n p} a_{q m} a_{i p} a_{q j} et xy² a_{n p} a_{q m} a_{i m} a_{n j}

Ils sont nuls, puisque par compatibilité on a :

U_{p q} est compatible sur (A,B), donc :	a_{q p} = 0
V_{m n} est compatible sur U_{p q}(A,B), donc :	Ua_{n m} = 0 = a_{n m} + x a_{n p} a_{q m}
V_{m n} est compatible sur (A,B), donc :	a_{n m} = 0
U_{p q} est compatible sur V_{m n}(A,B), donc :	Va_{q p} = 0 = a_{q p} + y a_{q m} a_{n p}

ce qui montre deux fois que : a_{n p} a_{q m} = 0.

On remarque qu'ici la condition de compatibilité se traduit par le fait que dans le graphe :

p → q (concerne l'application de U_{p q})
m → n (concerne l'application de V_{m n})

on ne doit pas introduire de cycle : la condition a_{n p} a_{q m} = 0 signifie bien qu'on ne doit pas construire de cycle en deux étapes.

Note :

Avec trois transformations (p q,x) (m n,y) (r s,z), la commutativité imposerait :

a_{s r} + x a_{s p} a_{q r} + y a_{s m} a_{n r} + xy (a_{s m} a_{n p} a_{q r} + a_{s p} a_{q m} a_{n r}) + xy² a_{s m} a_{n p} a_{q m} a_{n r} = 0

Les paramètres étant quelconques, on en déduit :

(a)	a_{s r} = 0
(b)	a_{s p} a_{q r} = 0
(c)	a_{s m} a_{n r} = 0
(d)	a_{s m} a_{n p} a_{q r} = 0
(e)	a_{s p} a_{q m} a_{n r} = 0
(f)	a_{s m} a_{n p} a_{q m} a_{n r} = 0

On retrouve donc les conditions de formation d'un cycle en trois étapes – plus particulièrement dans les cas (d) et (e).

2.5. conclusion

Partant pour A de la matrice identité et pour B de la matrice nulle, qui forment un couple de matrices compatible, on conserve un couple de matrices compatible par application des transformations du type T_{p q} ou S_{m n}. De plus, la transformation S_{p q} est bien l'inverse de T_{p q}, et ceci même quand on ne l'applique pas immédiatement après la transformation T_{p q}, du fait de la commutativité des transformations sur des couples de matrices compatibles.

On peut ainsi dégager les deux propriétés :

l'ensemble des couples de matrices compatibles est non vide et stable par application des transformations directe ou inverse ;
l'effet de toute transformation directe appliquée sur un couple de matrices compatible peut être "annulé" par application de la transformation inverse, soit immédiatement après, soit après d'autres transformations.