Построение неэквивалентных двоичных матриц

Я пытаюсь построить все неэквивалентные матрицы (или если хотите) с элементами 0 или 1. Операция, которая дает эквивалентные матрицы, - это одновременный обмен строк i и j И столбцов i и j , например. для $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}$

В конце концов, мне также нужно будет подсчитать, сколько эквивалентных матриц существует в каждом классе, но я думаю, что теорема Поли о подсчете может это сделать. Сейчас мне просто нужен алгоритм построения одной матрицы в каждом классе неэквивалентности. Есть идеи?

algorithms combinatorics Гетеротическая
источник

Есть по крайней мере ,

из них. Это действительно большое количество.

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

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

Yuval Filmus

@Yuval: Это действительно большие числа, и для моего расчета действительно имеет значение, если это

или

. Это может занять несколько недель, чтобы бежать! Вот почему я пытаюсь использовать все симметрии рассматриваемой проблемы. Кроме того, эта проблема возникает из построения модели в теории струн! :)

2^{48}

$2^{48}$

2^{52}

$2^{52}$

Гетеротик

Что вы собираетесь делать со всеми этими матрицами? Где вы собираетесь их хранить? Какое приложение?

Юваль Фильмус

идея: разве это не очень похоже на проблему изоморфизма графов? где матрицы - это матрицы ребер графа? кроме тех, которые симметричны ... может быть, как-то можно использовать, на это есть тонны теории ...

vzn

math.stackexchange.com/questions/924745/…

orezvani

Ответы:

Я добился определенного прогресса в ответе на этот вопрос. Я публикую здесь, если кому-то еще это интересно, а также потому, что эта конструкция может быть полезна для (направленных) графов.

Подсчитайте количество единиц в каждом ряду. Пусть будет число строк с нулевыми 1s, число строк с одним 1 и так далее до , который является количество строк , которые имеют восемь 1s. Очевидно . Предлагаемая параметризация, к которой я пришел после проб и ошибок: где T - это след матрицы, и S равно если матрица симметрична, и противном случае. Т работает от до $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$

Из моих проб и ошибок похоже, что если две матрицы отличаются в этой параметризации, то они принадлежат разным классам эквивалентности, поэтому для создания представителя в каждом классе мы просто сканируем пространство параметров, как описано выше.

(Обновление) Оказывается, что эта параметризация работает нормально для n = 2, но не для n = 3, как это видно из расчета методом грубой силы. Я все еще думаю, что это дает некоторое представление о структуре ответа, и я приглашаю людей попытаться изменить / расширить его, чтобы охватить наиболее общий случай.

Гетеротическая
источник

1 \times 1

$1 \times 1$

2 \times 2

$2\times 2$

7 \times 7

$7 \times 7$

@DW: Действительно, это доказательство того, что это условие является достаточным, меня беспокоит и то, с чем я хотел бы помочь. Я постараюсь исчерпывающе проверить это для небольших случаев и посмотрю, что произойдет. Спасибо за совет! К сожалению, я не знаю, как использовать SAT-решатель для поиска контрпримеров. Если гипотеза верна для меньших матриц, я мог бы начать об этом

узнавать

Имеет смысл, Гетеротик! На самом деле, я забираю свое заявление об использовании SAT-решателя. Я не знаю, как использовать SAT-решатель для поиска контрпримеров (это сложнее, чем я думал вначале) - поэтому, пожалуйста, игнорируйте эту часть моего комментария. Прости за это!

a_{i}

$a_i$

(1, 4)

$(1,4)$

(2, 3)

$(2,3)$

(1, 4)

$(1,4)$

(2, 4)

$(2,4)$ (все остальные записи 0 для обоих) не эквивалентны, но имеют одинаковую параметризацию. (Конечно, это немедленно приводит к улучшенной параметризации, которая также учитывает столбцы.)

FrankW

Гетеро, теперь, когда ты знаешь, что твой ответ не работает, я бы предложил удалить твой ответ, чтобы он не смутил других ...