Matrice dans Mn(Z/2Z)

[Helidjah]

Bonsoir,

Je n'arrive pas à formaliser un problème.
On considère une matrice carré à coefficients dans Z/2Z. Quel est le nombre de permutations des colonnes de la matrice qui donne une matrice dont la diagonale ne possède pas de zéro ?
Plus particulièrement, existe-t-il une unique permutation des colonnes qui donne une telle matrice ?

Merci d'avance pour votre aide :we:

[barbu23]

si, ta matrice ne contient que des dans toutes les cases, à ce moment là, j'ai du mal à imaginer une permutation avec des zeros en diagonal ! :hum:
il faut au moins que la matrice contient un zero dans chaque colonne et dans chaque ligne aussi ! à ce moment là, c'est possible ! :happy3:

[Helidjah]

C'est bien ce que je me suis dis à première vue ..
Mais prends par exemple :

0 0 0 1 0 0
0 0 0 1 0 0
1 1 1 1 0 0
0 0 1 1 1 1
0 0 1 0 0 0
0 0 1 0 0 0

Ça m'étonnerait que celle-ci possède une telle permutation :hum:

[barbu23]

d'abord, tu travailles sur des matrices carrés c'est à dire de type et non de type comme tu fais toi ici pour ton choix de matrice ! trouve toi d'abord une autre, mais carré cette fois çi pour voir si elle admet une permutation comme ce que tu proposes ! :happy3:

[Helidjah]

Effectivement, je vais m'efforcer d'en trouver une carrée. Prenons par exemple celle de mon post précédent. :happy2:

[Helidjah]

En fait ma question vient d'un problème qu'il serait peut être préférable de considérer par une approche ensembliste :
On considère n ensembles finis d'entiers A, B, C, D, E.. Soit a un élément de A, b un élément de B.. Quel est le nombre d'ensemble {a, b, c, d, e ..} qui ne possède que des éléments différents ? Plus particulièrement, existe-t-il un unique ensemble qui vérifie cette propriété ?
Par exemple, si A={1,2,3}, B={1} et C={1}, il n'y a pas de solution.
Si A={1,2,3}, B={1,2}, C={1,2}, il y a exactement deux solutions : {a,b,c}={3,1,2} ou {3,2,1}.

N'hésitez pas à laisser un commentaire même si c'est une approche algorithmique [pour les pros du ML par exemple ;)]

[Doraki]

lol... j'ai pas souvenir de ce genre de problème donc j'imagine qu'un truc bourrin basique doit suffire genre choisir a dans A, puis choisir b dans B etc...
Si tu veux tu peux ne pas faire les choix dans l'odre et choisir en priorité dans les ensembles qui se retrouvent avec le moins d'éléments pas encore pris.
Si t'as une matrice carrée, tu peux aussi choisir en priorité dans les lignes / colonnes qui se retrouvent avec le moins de choix possible.

[Helidjah]

Ce n'est pas une mauvaise idée cette question de priorité.
Mais ça n'apporte rien (enfin si : un algorithme de tri supplémentaire) dans le cas où il n'y a pas de solution, ce qui est en l'occurrence le cas le plus fréquent (tu pouvais pas savoir).
Edit : en effet, la fréquence d'apparition des éléments dans un ensemble est la même pour tous les ensembles mais diffère largement suivant les éléments.

Normal que tu t'en souviennes pas, je suis encore sur les problèmes de noobs. Quoi qu'il en soit P283 -> Done.
Hehe