L’échange en cascade pour valider motifs et règles

 Des tableaux aux matrices

Dans toute cette partie, ce qu’on appelle matrice117 est un tableau à n lignes et p colonnes de valeurs 0 ou 1, n et p étant deux nombres entiers supérieurs à 1. On appelle marges de la matrice la colonne (colonne marginale) des totaux de chaque ligne et la ligne (ligne marginale) des totaux de chaque colonne. Le total général s’écrit à l’intersection de la ligne et de la colonne marginales. On appelle sommes marginales les nombres contenus dans les marges. Les marges 117Dans tout ce chapitre, on dira matrice au lieu de matrice booléenne dans la mesure où toutes les matrices de ce chapitre sont booléennes.

Premières dénitions ne font pas partie de la matrice

Voici dans le tableau 1 un exemple de matrice pour n=4 et p=3. Elle correspond à un tableau sujets×propriétés de 3 propriétés A, B, C et 4 sujets s1, s2, s3, s4. La matrice est le tableau de 12 valeurs situé au milieu et entouré d’un double trait. La colonne marginale est à droite et contient les totaux des lignes, la ligne marginale est en bas et contient les totaux des colonnes, et la dernière case en bas à droite contient le total général, donc le nombre de valeurs égales à 1 de la matrice. Sujet A B C Total s1 0 1 1 2 s2 1 0 0 1 s3 1 1 1 3 s4 1 0 1 2 Total 3 2 3 8 Tab. 6.1  Un tableau de 3 propriétés et 4 sujets, la matrice associée et ses marges 6.3 Premières dénitions Dénition 6.3.1. Matrices S-équivalentes. On dit que deux matrices sont S-équivalentes si elles ont mêmes sommes marginales. Par exemple, les matrices du tableau 2 sont S-équivalentes à celles du tableau 1. ab. 

Propriété 6.3.1.

La S-équivalence est une relation d’équivalence. Cette relation dénie dans l’ensemble des matrices est réexive, symétrique, transitive . Preuve. La preuve découle immédiatement de la dénition. Ayant obtenu une relation d’équivalence, il convient maintenant de nous donner les moyens de trouver la classe d’équivalence de chaque matrice. Par exemple la classe d’équivalence de la matrice du tableau 1 contient 5 matrices qui sont la matrice d’origine et les quatre matrices du tableau 2. Dans le paragraphe suivant, nous allons dénir une classe de transformations permettant de passer d’une matrice à une matrice S-équivalente, et établir qu’avec ces transformations nous générons bien tous les éléments de la classe d’équivalence d’une matrice. Puis nous en donnerons une expression plus simple du point de vue algorithmique qui nous permettra d’engendrer un grand nombre de ces matrices selon une répartition proche du hasard. 153 Chapitre 6. L’échange en cascade pour valider motifs et règles

Transformations opérant sur la classe d’équivalence d’une matrice

Une transformation simple : l’échange rectangulaire

Si dans une matrice, on échange un 0 et un 1 d’une ligne, donc les valeurs sur deux colonnes, la somme sur les lignes ne change pas, mais la somme sur les 2 colonnes concernées change. Toutefois, si sur une autre ligne, on peut faire l’échange inverse sur les colonnes, les sommes sur ces colonnes redeviennent les sommes initiales. Cela signie qu’on peut dessiner un rectangle dans la matrice pour lequel deux sommets consécutifs ont deux valeurs distinctes 0 et 1. Nous appelons « échange rectangulaire » la transformation qui consiste à changer ces 4 valeurs en leurs compléments à 1. Dénition 6.4.1. Échange rectangulaire A étant une matrice, i1 et i2 deux valeurs distinctes de I = {0, 1, …, n−1} et j1 et j2 deux valeurs distinctes de J = {0, 1, …, p − 1} telles que A(i1, j1) = A(i2, j2) = 1 − A(i1, j2) = 1 − A(i2, j1) on appelle échange rectangulaire E(i1,i2),(j1,j2) la transformation de A en B qui échange les 4 valeurs à l’intersection des deux lignes et des deux colonnes : B(i, j) = ½ 1 − A(i, j) si (i, j) ∈ {(i1, j1),(i1, j2),(i2, j1),(i2, j2)} A(i, j) si (i, j) ∈ I × J − {(i1, j1),(i1, j2),(i2, j1),(i2, j2)} Par exemple, prenons comme matrice A la matrice du tableau 1. On a I = {0, 1, 2, 3}, J = {0, 1, 2}. On peut dessiner sur cette matrice 3 rectangles pour lesquels les valeurs 0 et 1 alternent. Cela nous donne les échanges rectangulaires E(0,1),(0,1), E(0,1),(0,2) et E(0,3),(0,1). Les 3 premières matrices du tableau 2 sont les résultats des transformations correspondantes de la matrice A. Colonnes Colonnes 0 1 2 0 1 2 Ligne 0 0 1 1 1 1 0 Ligne 1 1 0 0 0 0 1 Ligne 2 1 1 1 1 1 1 Ligne 3 1 0 1 1 0 1 Tab. 6.3  Passage de la matrice A à la matrice B par l’échange rectangulaire E(0,1),(0,2) Détaillons le deuxième de ces échanges E(0,1),(0,2). Le premier couple (0,1) indique qu’on prend les lignes 0 et 1, qui sont les deux premières lignes. Le second couple (0,2) indique qu’on prend la première et la dernière colonne. On considère ainsi les quatre valeurs 0, 1, 0, 1 indiquées en gras dans la matrice de gauche du tableau 3, leurs coordonnées respectives (0,0), (0,2), (1,0), (1,2) formant un rectangle. Lors de la transformation, chacune de ces quatre valeurs est remplacée par son complément à 1, pour former la matrice à droite du tableau 3, les autres restant inchangées. Propriété 6.4.1. La transformée B d’une matrice A par un échange rectangulaire est une matrice S-équivalente. Preuve. Soit E un échange rectangulaire opérant sur les deux lignes d’indices i1 et i2 et sur les deux colonnes d’indices j1 et j2. 154 6.4. Transformations opérant sur la classe d’équivalence d’une matrice 1. Montrons d’abord que les sommes des lignes n’ont pas changé lors de la transformation E.  Pour chaque indice i diérent de i1 et i2, la ligne n’a pas changé, donc la somme de ses valeurs non plus.  Dans la ligne d’indice i1, deux termes ont changé, ce sont les termes des colonnes j1 et j2. Si l’échange a pu avoir lieu, c’est que l’un de ces 2 termes avait pour valeur 0 et l’autre pour valeur 1 avant l’échange. Leur somme était donc 1 avant l’échange. Après l’échange le terme de valeur 1 a pris comme nouvelle valeur 0, et inversement pour l’autre terme. Leur somme est toujours 1. La somme totale de la ligne i1 n’a donc pas changé.  On ferait le même raisonnement pour la ligne i2. On a ainsi montré que les sommes des lignes de la matrice avant et après l’échange rectangulaire sont identiques. 2. On montrerait de la même façon que les sommes des colonnes ne changent pas non plus lors de la transformation. La matrice B est donc S-équivalente à la matrice A. Les échanges de zéros et de uns selon un rectangle permettent, nous venons de le voir, de garder les marges inchangées. Ce ne sont pas les seuls, les échanges pouvant aussi se faire en cascade. En eet, une fois deux valeurs 0 et 1 échangées sur une ligne, on a vu précédemment que les sommes sur les deux colonnes avaient changé et devaient être rétablies. Dans l’échange rectangulaire, on utilise une deuxième ligne avec ces mêmes colonnes. Mais on peut très bien utiliser pour cela une troisième colonne et deux autres lignes. On rétablira la somme de la première colonne à l’aide de la deuxième ligne et de la troisième colonne, et la somme de la deuxième colonne à l’aide de la troisième ligne et de la troisième colonne. Du coup la troisième colonne, ayant été modiée deux fois, aura sa somme inchangée. Et on peut procéder ainsi de façon plus générale avec q colonnes et q lignes. 6.4.2 Une transformation plus complexe : l’échange en cascade Comme pour l’échange rectangulaire, l’échange en cascade ne peut se faire sur une matrice que si les valeurs 0 et 1 de la matrice sur les lignes et colonnes considérées se succèdent correctement. C’est cette disposition particulière que nous appelons « suite diagonale ».

Dénition 6.4.2. Suite diagonale

On appelle suite diagonale d’une matrice A un triplet (I, J, val) où I = (i1, i2, …, iq) est une suite ordonnée d’indices de lignes, J = (j1, j2, …, jr) une suite ordonnée d’indices de colonnes, val une valeur égale à 0 ou 1, tels qu’on ait la suite d’égalités suivante : A(i1, j1) = val A(i1, j2) = 1 − val A(i2, j2) = val A(i2, j3) = 1 − val … A(iq, jr) = val A(iq, j1) = 1 − val La suite I n’a pas d’éléments répétés, pas plus que la suite J. Ce sont toutes deux des suites d’indices distincts. Propriété 6.4.2. Dans une suite diagonale (I,J,val), les suites d’indices I et J ont le même nombre d’éléments. Ce nombre est appelé longueur de la suite. Preuve. Cela vient du fait que la suite s’écrit avec des égalités doubles A(ik, jk) = val et A(ik, jk+1) = 1 − val, où les valeurs de k se succèdent de 1 en 1 modulo q (ou r) donc on a q = r. 155 Chapitre 6. L’échange en cascade pour valider motifs et règles Une suite diagonale a donc une longueur comprise entre 2 et min(n,p), n et p étant les dimensions de la matrice. On l’a appelée suite diagonale car si on réordonne les lignes et les colonnes de la matrice selon les deux ensembles d’indices, on obtient une bande de largeur 2 sur la diagonale de la matrice. Et les extrémités de cette bande se recollent selon un tore. Dénition 6.4.3. Échange en cascade On appelle échange en cascade sur une matrice A la transformation associée à une suite diagonale sur A qui change toutes les valeurs de A concernées par la suite diagonale. On appelle longueur de l’échange en cascade la longueur de la suite diagonale associée. Propriété 6.4.3. Échange en cascade de longueur 2 C’est un échange rectangulaire. Preuve. La preuve est immédiate : Quand la longueur de la suite est 2, il n’y a plus que 4 équations qui sont : A(i1, j1) = val A(i1, j2) = 1 − val A(i2, j2) = val A(i2, j1) = 1 − val la suite diagonale se réduit à un rectangle où les valeurs des sommets alternent, donc l’échange en cascade associé est l’échange rectangulaire E(i1,i2),(j1,j2) . Par exemple, la matrice du tableau 1 ne peut contenir que des suites diagonales de longueur 2 ou 3.