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

Odpowiedzi:

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!

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 ...