Membangun matriks biner yang tidak setara

Saya mencoba untuk membangun semua matriks tidak seimbang (atau jika Anda mau) dengan elemen 0 atau 1. Operasi yang memberikan matriks setara adalah pertukaran simultan dari baris i dan j DAN kolom i dan j. misalnya. untuk $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}$

Akhirnya, saya juga perlu menghitung berapa banyak matriks setara yang ada dalam setiap kelas tetapi saya pikir teorema penghitungan Polya dapat melakukan itu. Untuk saat ini saya hanya perlu cara algoritmik membangun satu matriks di setiap kelas ketidaksetaraan. Ada ide?

algorithms combinatorics Heterotik
sumber

Setidaknya ada

di antaranya. Itu jumlah yang sangat besar.

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

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

Yuval Filmus

@ Yuval: Ini memang angka yang besar dan untuk perhitungan saya itu benar-benar membuat perbedaan jika

atau

. Butuh waktu berminggu-minggu lebih banyak untuk berlari! Inilah alasan saya mencoba menggunakan semua simetri masalah yang ada. Selain itu, masalah ini berasal dari pembuatan model di String Theory! :)

2^{48}

$2^{48}$

2^{52}

$2^{52}$

Heterotic

Apa yang ingin Anda lakukan dengan semua matriks ini? Di mana Anda akan menyimpannya? Apa aplikasinya?

Yuval Filmus

ide: bukankah ini sangat mirip dengan masalah isomorfisme grafik? di mana matriks adalah matriks tepi grafik? kecuali yang simetris ... mungkin dapat ditingkatkan, entah bagaimana, ada banyak teori tentang itu ...

vzn

math.stackexchange.com/questions/924745/…

orezvani

Jawaban:

Saya telah membuat beberapa kemajuan dalam menjawab pertanyaan ini. Saya memposting di sini kalau-kalau ada orang lain yang tertarik dan juga karena konstruksi ini mungkin memiliki beberapa kegunaan untuk grafik (diarahkan).

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

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

Dari percobaan dan kesalahan saya, terlihat bahwa jika dua matriks berbeda dalam parametriisasi ini maka mereka termasuk kelas ekivalensi yang berbeda, jadi untuk membangun perwakilan di setiap kelas kami hanya memindai melalui ruang parameter seperti dijelaskan di atas.

(Pembaruan) Ternyata parametrization ini berfungsi dengan baik untuk n = 2 tetapi tidak untuk n = 3 karena dapat dilihat dengan perhitungan brute force. Saya masih berpikir itu memberikan beberapa wawasan tentang struktur jawaban dan saya mengundang orang untuk mencoba dan memodifikasi / memperluasnya untuk mencakup kasus yang paling umum.

Heterotik
sumber

1 \times 1

$1 \times 1$

2 \times 2

$2\times 2$

7 \times 7

$7 \times 7$

@ WD: Memang itu adalah bukti bahwa kondisi ini cukup yang mengganggu saya dan yang ingin saya bantu. Saya akan mencoba memverifikasinya secara mendalam untuk kasus yang lebih kecil dan melihat apa yang terjadi. Terima kasih atas sarannya! Sayangnya, saya tidak tahu cara menggunakan pemecah SAT untuk mencari contoh tandingan. Jika dugaan, berlaku untuk matriks yang lebih kecil, saya mungkin mulai belajar tentang hal itu ...

Heterotic

Masuk akal, Heterotik! Sebenarnya, saya mengambil kembali pernyataan saya tentang menggunakan pemecah SAT. Saya tidak tahu cara menggunakan pemecah SAT untuk mencari contoh tandingan, (lebih sulit dari yang saya pikirkan pada awalnya) - jadi tolong abaikan bagian komentar saya itu. Maaf soal itu!

a_{i}

$a_i$

(1, 4)

$(1,4)$

(2, 3)

$(2,3)$

(1, 4)

$(1,4)$

(2, 4)

$(2,4)$ (semua entri yang tersisa 0 untuk keduanya) tidak setara tetapi memiliki parametrization yang sama. (Tentu saja ini segera mengarah pada peningkatan parametriisasi yang juga memperhitungkan kolom-kolom itu.)

FrankW

Heterotik, sekarang setelah Anda tahu jawaban Anda tidak berfungsi, saya sarankan menghapus jawaban Anda sehingga tidak membingungkan orang lain ...