Konstruktion inäquivalenter binärer Matrizen

Ich versuche, mit den Elementen 0 oder 1 alle inequivalenten Matrizen (oder wenn Sie es wünschen) zu konstruieren. Die Operation, die äquivalente Matrizen ergibt, ist der gleichzeitige Austausch der i- und j-Reihe UND der i- und j-Spalte . z.B. für $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}$

Irgendwann muss ich auch zählen, wie viele äquivalente Matrizen es in jeder Klasse gibt, aber ich denke, dass Polyas Zählsatz das kann. Im Moment brauche ich nur eine mathematische Methode, um eine Matrix in jeder Ungleichwertigkeitsklasse zu konstruieren. Irgendwelche Ideen?

algorithms combinatorics Heterotisch
quelle

Es gibt mindestens davon. Das ist eine sehr große Zahl.

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

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

Yuval Filmus

@Yuval: Das sind in der Tat große Zahlen, und für meine Berechnung ist es wirklich ein Unterschied, ob es oder . Es könnte noch Wochen dauern, bis es läuft! Aus diesem Grund versuche ich, alle Symmetrien des vorliegenden Problems zu nutzen. Abgesehen davon stammt dieses Problem aus der Modellbildung in der Stringtheorie! :)

2^{48}

$2^{48}$

2^{52}

$2^{52}$

Heterotic

Was haben Sie mit all diesen Matrizen vor? Wo wirst du sie aufbewahren? Was ist die Anwendung?

Yuval Filmus

Idee: Ist das nicht sehr ähnlich zum Graph-Isomorphismus-Problem? Wo sind Matrizen Graphkantenmatrizen? außer diese sind symmetrisch ... vielleicht kann man sie irgendwie nutzen, da

steckt jede Menge

math.stackexchange.com/questions/924745/…

orezvani

Antworten:

Ich habe einige Fortschritte bei der Beantwortung dieser Frage gemacht. Ich poste hier, falls jemand anderes interessiert ist und auch, weil diese Konstruktion für (gerichtete) Graphen von Nutzen sein könnte.

Zählen Sie die Anzahl der Einsen in jeder Zeile. Sei die Anzahl der Zeilen mit null Einsen, die Anzahl der Zeilen mit einer Eins usw. bis zu die die Anzahl der Zeilen mit acht Einsen ist. Offensichtlich ist . Die vorgeschlagene Parametrisierung, zu der ich nach Versuch und Irrtum gekommen bin, ist: wobei T die Spur der Matrix ist und S wenn die Matrix symmetrisch ist und andernfalls. T läuft von bis $a_0$ $a_1$ $a_8$ $\sum a_i=8$

({ein}_{1}, \dots, {ein}_{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$

Aus meinen Versuchen und Fehlern geht hervor, dass zwei Matrizen, die sich in dieser Parametrisierung unterscheiden, zu verschiedenen Äquivalenzklassen gehören. Um in jeder Klasse einen Repräsentanten zu erstellen, scannen wir einfach den oben beschriebenen Parameterraum durch.

(Update) Es stellt sich heraus, dass diese Parametrisierung für n = 2, jedoch nicht für n = 3, gut funktioniert, wie eine Brute-Force-Berechnung zeigt. Ich denke immer noch, dass es einen Einblick in die Struktur der Antwort gibt, und ich fordere die Leute auf, zu versuchen, sie zu ändern / zu erweitern, um den allgemeinsten Fall abzudecken.

Heterotisch
quelle

1 \times 1

$1 \times 1$

2 \times 2

$2\times 2$

7 \times 7

$7 \times 7$

@DW: In der Tat ist es der Beweis, dass dieser Zustand ausreicht, der mich und denjenigen, bei dem ich Hilfe haben möchte, beunruhigt. Ich werde versuchen, es für die kleineren Fälle gründlich zu überprüfen und zu sehen, was passiert. Danke für den Hinweis! Leider habe ich keine Ahnung, wie ich mit einem SAT-Solver nach Gegenbeispielen suchen soll. Wenn die Vermutung für die kleineren Matrizen gilt, könnte ich anfangen, etwas darüber zu lernen ...

Heterotic

Sinnvoll, heterotisch! Eigentlich nehme ich meine Aussage über die Verwendung eines SAT-Lösers zurück. Ich weiß auch nicht, wie ich mit einem SAT-Solver nach Gegenbeispielen suchen soll (es ist schwieriger als ich zuerst dachte). Ignorieren Sie diesen Teil meines Kommentars. Das tut mir leid!

a_{i}

$a_i$

(1, 4)

$(1,4)$

(2, 3)

$(2,3)$

(1, 4)

$(1,4)$

(2, 4)

$(2,4)$ (Alle verbleibenden Einträge 0 für beide) sind nicht äquivalent, haben jedoch die gleiche Parametrisierung. (Dies führt natürlich sofort zu einer verbesserten Parametrisierung, die auch die Spalten berücksichtigt.)

FrankW

Heterotisch, jetzt, da Sie wissen, dass Ihre Antwort nicht funktioniert, würde ich vorschlagen, Ihre Antwort zu löschen, damit andere nicht verwirrt werden ...