Konstruowanie nierównych macierzy binarnych

Próbuję skonstruować wszystkie nierówne macierze (lub jeśli chcesz) z elementami 0 lub 1. Operacją, która daje macierze równoważne, jest jednoczesna wymiana wiersza i i j ORAZ kolumny i i j. na przykład. dla $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}$

W końcu będę musiał również policzyć, ile macierzy równoważnych jest w każdej klasie, ale myślę, że twierdzenie Polyi może to zrobić. Na razie potrzebuję tylko algorytmicznego sposobu konstruowania jednej macierzy w każdej klasie nierówności. Jakieś pomysły?

algorithms combinatorics

— Heterotyczny
źródło

Istnieją co najmniej

z nich. To naprawdę duża liczba.

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

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

— Yuval Filmus,

@Yuval: To są naprawdę duże liczby i dla moich obliczeń naprawdę robi różnicę, jeśli są to

lub

. Uruchomienie może potrwać jeszcze tygodnie! To jest powód, dla którego próbuję wykorzystać wszystkie symetrie danego problemu. Nawiasem mówiąc, ten problem pochodzi z budowania modelu w teorii ciągów! :)

2^{48}

$2^{48}$

2^{52}

$2^{52}$

— Heterotic

Co zamierzasz zrobić z tymi wszystkimi matrycami? Gdzie zamierzasz je przechowywać? Jaka jest aplikacja

— Yuval Filmus

pomysł: czy nie jest to bardzo podobne do problemu izomorfizmu grafów? gdzie macierze są macierzami grafowymi? z wyjątkiem tych, które są symetryczne ... może uda się to jakoś wykorzystać, jest mnóstwo teorii na ten temat ...

— dniu

math.stackexchange.com/questions/924745/…

— orezvani

Poczyniłem pewne postępy w odpowiedzi na to pytanie. Piszę tutaj na wypadek, gdyby ktoś był zainteresowany, a także dlatego, że ta konstrukcja może być przydatna dla (ukierunkowanych) grafów.

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

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

Z moich prób i błędów wynika, że jeśli dwie macierze różnią się w tej parametryzacji, to należą one do różnych klas równoważności, więc aby zbudować reprezentanta w każdej klasie, po prostu skanujemy przestrzeń parametrów, jak opisano powyżej.

(Aktualizacja) Okazuje się, że ta parametryzacja działa dobrze dla n = 2, ale nie dla n = 3, ponieważ można to zobaczyć na podstawie obliczenia siły brutalnej. Nadal uważam, że zapewnia on pewien wgląd w strukturę odpowiedzi i zapraszam ludzi do próby modyfikacji lub rozszerzenia jej w celu uwzględnienia najbardziej ogólnego przypadku.

— Heterotyczny
źródło

1 \times 1

$1 \times 1$

2 \times 2

$2\times 2$

7 \times 7

$7 \times 7$

@DW: Rzeczywiście, jest to dowód, że ten warunek jest wystarczający, który niepokoi mnie i tego, z którym chciałbym trochę pomóc. Spróbuję to zweryfikować wyczerpująco w mniejszych przypadkach i zobaczę, co się stanie. Dzięki za radę! Niestety nie mam pojęcia, jak używać solvera SAT do szukania kontrprzykładów. Jeśli przypuszczenie dotyczy mniejszych macierzy, mógłbym zacząć się o nim uczyć ...

— Heterotic

Ma sens, Heterotyczny! Właściwie cofam moje zdanie na temat używania solvera SAT. Nie wiem też, jak używać solvera SAT do szukania kontrprzykładów (jest to trudniejsze niż początkowo myślałem) - więc proszę zignoruj tę część mojego komentarza. Przepraszam za to!

— DW

a_{i}

$a_i$

(1, 4)

$(1,4)$

(2, 3)

$(2,3)$

(1, 4)

$(1,4)$

(2, 4)

$(2,4)$ (wszystkie pozostałe wpisy 0 dla obu) nie są równoważne, ale mają tę samą parametryzację. (Oczywiście to natychmiast prowadzi do ulepszonej parametryzacji, która uwzględnia również kolumny.)

— FrankW

Heterotyczny, skoro już wiesz, że twoja odpowiedź nie działa, proponuję usunąć twoją odpowiedź, aby nie mylić innych ...

— DW