Construire des matrices binaires non équivalentes

J'essaie de construire toutes les matrices inéquivalentes (ou si vous le souhaitez) avec les éléments 0 ou 1. L'opération qui donne des matrices équivalentes est l'échange simultané de la ligne i et j ET de la colonne i et j. par exemple. pour $8\times 8$ $n\times n$ $1\leftrightarrow2$

(\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{array}) \sim (\begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array})

$\begin{equation} \left( \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{array} \right) \sim \left( \begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right) \end{equation}$

Finalement, je devrai également compter le nombre de matrices équivalentes dans chaque classe, mais je pense que le théorème de comptage de Polya peut le faire. Pour l'instant, j'ai juste besoin d'une manière algoritmique de construire une matrice dans chaque classe d'inégivalence. Des idées?

algorithms combinatorics Hétérotique
la source

Il y a au moins

d'entre eux. C'est un très grand nombre.

2^{64} / 8! \geq 2^{48}

$2^{64}/8! \geq 2^{48}$

Yuval Filmus

@Yuval: Ce sont en effet de grands nombres et pour mon calcul cela fait vraiment une différence si c'est

. Cela pourrait prendre des semaines de plus! C'est la raison pour laquelle j'essaie d'utiliser toutes les symétries du problème en question. Soit dit en passant, ce problème provient de la construction de modèles dans la théorie des cordes! :)

2^{48}

$2^{48}$

2^{52}

$2^{52}$

Heterotic

Que comptez-vous faire avec toutes ces matrices? Où allez-vous les stocker? Quelle est l'application?

Yuval Filmus

idée: n'est-ce pas très similaire au problème d'isomorphisme graphique? où les matrices sont des matrices de bord de graphe? sauf que ceux-ci sont symétriques ... peut-être peut-être exploité d'une manière ou d'une autre, il y a des tonnes de théorie à ce sujet ...

vzn

math.stackexchange.com/questions/924745/...

orezvani

Réponses:

J'ai fait quelques progrès pour répondre à cette question. Je poste ici au cas où quelqu'un d'autre serait intéressé et aussi parce que cette construction pourrait avoir une certaine utilité pour les graphiques (dirigés).

$a_0$ $a_1$ $a_8$ $\sum a_i=8$

({une}_{1}, \dots, {une}_{8}; T, S)

$(a_1,\cdots, a_8; T, S)$

1

$1$

0

$0$

0

$0$

\sum_{i = 1}^{8} a_{i} = 8 - a_{0}

$\sum_{i=1}^8 a_i=8-a_0$

D'après mes essais et erreurs, il semble que si deux matrices sont différentes dans cette paramétrisation, alors elles appartiennent à des classes d'équivalence différentes, donc pour construire un représentant dans chaque classe, nous parcourons simplement l'espace des paramètres comme décrit ci-dessus.

(Mise à jour) Il s'avère que cette paramétrisation fonctionne bien pour n = 2 mais pas pour n = 3 comme on peut le voir par un calcul de force brute. Je pense toujours que cela donne un aperçu de la structure de la réponse et j'invite les gens à essayer de la modifier / l'étendre pour couvrir le cas le plus général.

Hétérotique
la source

1 \times 1

$1 \times 1$

2 \times 2

$2\times 2$

7 \times 7

$7 \times 7$

@DW: En effet, c'est la preuve que cette condition est suffisante qui me trouble et celle avec laquelle je voudrais de l'aide. Je vais essayer de le vérifier de manière exhaustive pour les petits cas et voir ce qui se passe. Merci pour le conseil! Malheureusement, je ne sais pas comment utiliser un solveur SAT pour rechercher des contre-exemples. Si la conjecture est valable pour les petites matrices, je pourrais commencer à l'apprendre ...

Heterotic

C'est logique, hétérotique! En fait, je reprends ma déclaration sur l'utilisation d'un solveur SAT. Je ne sais pas non plus comment utiliser un solveur SAT pour rechercher des contre-exemples (c'est plus difficile que je ne le pensais au début) - veuillez donc ignorer cette partie de mon commentaire. Désolé pour ça!

a_{i}

$a_i$

(1, 4)

$(1,4)$

(2, 3)

$(2,3)$

(1, 4)

$(1,4)$

(2, 4)

$(2,4)$ (toutes les entrées restantes 0 pour les deux) ne sont pas équivalentes mais ont le même paramétrage. (Bien sûr, cela conduit immédiatement à une paramétrisation améliorée qui prend également en compte les colonnes.)

FrankW

Hétérotique, maintenant que vous savez que votre réponse ne fonctionne pas, je suggère de supprimer votre réponse pour ne pas dérouter les autres ...