Discussion :

[CosmoKnacki]

Bonjour, ça fait un bail que j'ai laché l'affaire avec ce genre de mathématiques, donc désolé d'avance si ce que je demande relève de la question de cours.

Soit A, l'ensemble des matrices carrées 9x9 à coefficients dans {0;1} tel que pour chaque colonne et pour chaque ligne la somme des coefficients est égale à 5.

Soit M la matrice de A suivante:


Est-il possible d'engendrer A (i.e. d'obtenir n'importe quel élément de A) à partir de cette seule matrice M à laquelle on appliquerait 2 matrices de permutations P et P' (l'une pour permuter les lignes, l'autre pour les colonnes)?

Autrement dit, peut-on écrire:


Si non, quel type de transformation(s) pourrait permettre d'engendrer A à partir de cet unique élément.

[dourouc05]

Tu pourras générer toutes les matrices avec exactement autant de zéros et de uns avec uniquement des permutations (une matrice suffit). Si tu te limites à un nombre de uns par ligne et par colonne, je pense que tu ne dois pas générer plus que des permutations (pour faire toutes les matrices 9x9, vu que tes colonnes forment une base orthogonale, tu peux effectuer des combinaisons linéaires jusqu'à générer n'importe quelle matrice 9x9, en utilisant des matrices de changement de base plutôt que de permutation). Plus clairement : je dirais qu'il suffit de permutations, mais je n'apporte pas de preuve formelle.

[tbc92]

Je ne suis pas d'accord.

A partir de la matrice de départ, je ne pense pas qu'on puisse arriver à celle-ci :
1 1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0 0
1 0 0 0 0 1 1 1 1
0 1 0 0 0 1 1 1 1
0 0 1 0 0 1 1 1 1
0 0 0 1 0 1 1 1 1
0 0 0 0 1 1 1 1 1
Disons le autrement.
A partir de cette matrice, on peut alterner lignes et colonnes autant qu'on veut, on aura toujours 5 colonnes et 4 lignes quelque part, avec des 1 aux 20 cases définies par ces 5 colonnes et 4 lignes.
Et dans la matrice proposée, on n'a pas cette configuration.

[anapurna]

Salut

une simple permutation devrais suffir du fait que le nombre de 0 et de 1 sont invariant
ce n'est que leur position qui differe de ligne en ligne
le premier 1 a la position x devient 0 et la valeur a la position (x+5) modulo 9 de vient 1
a chaque ligne x s'increment de 1

[tbc92]

Je reste très sceptique.

Dans ces questions, on parle souvent d'invariant.
Prenons tous les quadruplets de lignes, tous les quadruplets de colonnes, et pour chaque configuration, on calcule la somme des 16 valeurs obtenues.
Et on retient le maximum pour cette somme.
Et ce nombre, on va dire que c'est la signature de la grille.
Pour la grille que je propose, la signature est de 16. (en choisissant par exemple les 4 premières lignes et les 4 premières colonnes)
Pour la grille initiale, la signature est de 14 (lignes 1 à 4, colonnes 3 à 6)
Partant d'une grille quelconque, on peut faire des permutations de lignes et/ou de colonnes, cette signature ne change pas. La signature est un invariant.
Donc ces 2 grilles sont dans 2 familles différentes. Il n'y a aucune succession de permutations qui permet de passer d'une grille de signature 14 à une grille de signature 16.

Ici, la signature que je propose est loin d'être suffisante. On peut certainement avoir 2 grilles qui ont la même signature, et qui ne sont pas 'joignables' par une suite de permutations.

[CosmoKnacki]

Bien vu tbc92! En effet, la multiplication par une matrice inversible (comme le sont les matrices de permutation) conserve le rang de la matrice de départ. Comme celle que je propose est de rang 9 (9 vecteurs indépendants qui forment une base comme l'a souligné dourouc05), on ne peut donc pas produire par des permutations une matrice de rang 6 (à vue de nez) comme celle proposée par tbc92 à partir de celle-ci. Donc mon hypothèse de départ est fausse.

Peut-être que pour engendrer A uniquement avec des permutations, il faudrait disposer d'une matrice (respectant les contraintes) par rang possible. Reste à les trouver.

Merci à tous pour vos messages.

[anapurna]

salut

je ne comprend pas pourquoi veut tu absolument trouvé ta matrice
il dit bien qu'a partir de la matrice de base et de permutation
quelque soit les permutation celle-ci se verifira ..

On peut ajouter qu'il existe une symetrie dans cette matrice
donc quelque soit la permutation de ligne ou de colonne le resultat seras toujours le meme 5
la tu nous parle de changer les valeurs de la matrice originel
en creant des "doublon de colonne et de ligne" forcement cela ne fonctionne plus
ce n'est plus des permutation de ligne ou de colonne mais des permutation de cellule que tu dois generer pour y parvenir ...
Remarque que les suite de cellules de 1 ou de zero se trouve non continue avec ta matrice

[CosmoKnacki]

A partir de cette matrice, on peut alterner lignes et colonnes autant qu'on veut, on aura toujours 5 colonnes et 4 lignes quelque part...

Non pas forcément, regarde:

Code txt :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
0 0 0 0 0 0 1 0 0     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 1 0 0     0 0 1 0 0 1 1 1 1     0 0 0 0 0 0 1 0 0     1 0 1 1 0 1 0 0 1
0 0 0 0 1 0 0 0 0     1 1 1 1 1 0 0 0 0     1 0 0 0 0 0 0 0 0     1 0 0 0 0 1 1 1 1     1 0 0 0 0 0 0 0 0     1 1 1 0 0 1 0 0 1
0 0 0 1 0 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 0 0 1     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 0 0 1     0 1 0 1 1 0 1 1 0
1 0 0 0 0 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 1 0 0 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 1 0 0 0 0 0 0     0 1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 1 0  x  1 0 0 0 0 1 1 1 1  x  0 0 0 1 0 0 0 0 0  =  0 0 0 1 0 1 1 1 1  x  0 0 0 1 0 0 0 0 0  =  1 0 1 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1     0 1 0 0 0 1 1 1 1     0 0 0 0 0 1 0 0 0     0 0 0 0 1 1 1 1 1     0 0 0 0 0 1 0 0 0     1 0 1 0 0 1 1 0 1
0 1 0 0 0 0 0 0 0     0 0 1 0 0 1 1 1 1     0 0 0 0 1 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 0 0 1 0 0 0 0     0 1 0 1 1 0 1 1 0
0 0 0 0 0 1 0 0 0     0 0 0 1 0 1 1 1 1     0 1 0 0 0 0 0 0 0     0 1 0 0 0 1 1 1 1     0 1 0 0 0 0 0 0 0     1 0 1 0 0 1 0 1 1
0 0 1 0 0 0 0 0 0     0 0 0 0 1 1 1 1 1     0 0 0 0 0 0 0 1 0     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 0 1 0     0 1 0 1 1 0 1 1 0

On obtient quelque chose de relativement bien brouillé (sans les successions de uns de la matrice de départ), par contre il y a toujours 4 fois le même vecteur (colonnes 1,3,6,9) comme dans la matrice de départ (colonnes 6,7,8,9).

[tbc92]

Oui, c'est ce que je disais. Le 'paquet' avec 16 1 va toujours exister, quoi qu'on fasse.

[anapurna]

Non pas forcément, regarde:

Code txt :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
0 0 0 0 0 0 1 0 0     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 1 0 0     0 0 1 0 0 1 1 1 1     0 0 0 0 0 0 1 0 0     1 0 1 1 0 1 0 0 1
0 0 0 0 1 0 0 0 0     1 1 1 1 1 0 0 0 0     1 0 0 0 0 0 0 0 0     1 0 0 0 0 1 1 1 1     1 0 0 0 0 0 0 0 0     1 1 1 0 0 1 0 0 1
0 0 0 1 0 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 0 0 1     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 0 0 1     0 1 0 1 1 0 1 1 0
1 0 0 0 0 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 1 0 0 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 1 0 0 0 0 0 0     0 1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 1 0  x  1 0 0 0 0 1 1 1 1  x  0 0 0 1 0 0 0 0 0  =  0 0 0 1 0 1 1 1 1  x  0 0 0 1 0 0 0 0 0  =  1 0 1 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1     0 1 0 0 0 1 1 1 1     0 0 0 0 0 1 0 0 0     0 0 0 0 1 1 1 1 1     0 0 0 0 0 1 0 0 0     1 0 1 0 0 1 1 0 1
0 1 0 0 0 0 0 0 0     0 0 1 0 0 1 1 1 1     0 0 0 0 1 0 0 0 0     1 1 1 1 1 0 0 0 0     0 0 0 0 1 0 0 0 0     0 1 0 1 1 0 1 1 0
0 0 0 0 0 1 0 0 0     0 0 0 1 0 1 1 1 1     0 1 0 0 0 0 0 0 0     0 1 0 0 0 1 1 1 1     0 1 0 0 0 0 0 0 0     1 0 1 0 0 1 0 1 1
0 0 1 0 0 0 0 0 0     0 0 0 0 1 1 1 1 1     0 0 0 0 0 0 0 1 0     1 1 1 1 1 0 0 0 0     0 0 0 0 0 0 0 1 0     0 1 0 1 1 0 1 1 0

On obtient quelque chose de relativement bien brouillé (sans les successions de uns de la matrice de départ), par contre il y a toujours 4 fois le même vecteur (colonnes 1,3,6,9) comme dans la matrice de départ (colonnes 6,7,8,9).

salut tu as aussi 4 fois les memes Vecteurs (
lignes 2,3,7,8) comme dans la matrice de départ (Ligne 1,2,3,4)

en fait je ne sais pas pourquoi mais cela me fait penser au RuBik's Cube ... bien sur ce n'est qu'une face et c'est un carre de neuf par neuf
c'est peut etre juste la matrice et les permutation qui me donne l'impression de retrouver les meme principe

[tbc92]

Oui, on est dans la théorie des groupes si je ne m'abuse, on est exactement dans la même problématique que le Rubik's Cube.
A partir d'une position donnée, quelles sont toutes les positions qu'on peut atteindre (=Quelles sont toutes les positions qui sont dans la même classe d'équivalence, quelles sont toutes les positions qui ont la même signature)

Je parlais d'invariant ; si on recherche 'invariant Rubik's Cube', on trouve des documents très étoffés sur ce sujet.

[mathieu]

j'aime beaucoup les mathématiques, les formules et les algorithmes qui permettent d'aller vite. mais là je sèche un peu donc j'ai fait un code barbare qui calcule toutes les combinaisons
et comme ce code n'est pas optimisé, il est long. j'ai fini les calculs pour la taille 5 et les calculs pour la taille 7 devraient finir dimanche vers 10 h 00.

donc pour la taille 5, je suis parti de cette matrice :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
		[1 1 1 0 0]
		[0 1 1 1 0]
		[0 0 1 1 1]
		[1 0 0 1 1]
		[1 1 0 0 1]

et j'ai cherché à obtenir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
		[1 1 1 0 0]
		[1 1 1 0 0]
		[1 0 0 1 1]
		[0 1 0 1 1]
		[0 0 1 1 1]

il y a 5! = 120 matrices de permutations et donc mon code a testé 14 400 combinaisons et aucune n'arrive à ce but. et toutes les combinaisons donnent une matrice différente comme résultat.

en revanche en taille 3, il y a 6 matrices de permutations, 36 combinaisons et 6 de ces combinaisons donnent la matrice recherchée.
donc ces tests ne me permettent pas encore de prévoir ce qu'il se passera en taille 9.

une idée à creuser serait de calculer le nombre théorique de matrices différentes dans l'ensemble A.
on sait qu'il y a 9! matrices de permutations et donc (9!)² combinaisons. et donc si on trouve qu'il y a un plus grand nombre de matrices dans A, ça prouvera qu'on ne peut pas toutes les générer avec les permutations.

en fait je ne sais pas pourquoi mais cela me fait penser au RuBik's Cube ... bien sur ce n'est qu'une face et c'est un carre de neuf par neuf
c'est peut etre juste la matrice et les permutation qui me donne l'impression de retrouver les meme principe

avant de faire mon code d'attaque par force brute, j'avais fait une interface ou je définissais les 2 matrices de permutations en cliquant sur des boutons et j'ai aussi eu cette sensation

[CosmoKnacki]

salut tu as aussi 4 fois les memes Vecteurs (
lignes 2,3,7,8) comme dans la matrice de départ (Ligne 1,2,3,4)

Effectivement, et c'est normal je dirais, car la transposition d'une matrice (une rotation de 90°) ne change pas son rang (qui est bien 6, j'ai calculé). Autrement dit lorsque tu as 4 colonnes liées (ici elles sont mêmes carrément égales), tu as aussi 4 lignes qui le sont.

en fait je ne sais pas pourquoi mais cela me fait penser au RuBik's Cube ... bien sur ce n'est qu'une face et c'est un carre de neuf par neuf
c'est peut etre juste la matrice et les permutation qui me donne l'impression de retrouver les meme principe

Il y a de ça. Sauf qu'un Rubik's cube on peut le démonter, le dégommer à coups de marteau ou le faire fondre au four.