Construindo matrizes binárias inequívocas

Eu estou tentando construir todas as matrizes (ou se desejar) com elementos 0 ou 1. A operação que fornece matrizes equivalentes é a troca simultânea da linha iej e da coluna iej . por exemplo. para $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}$

Eventualmente, também precisarei contar quantas matrizes equivalentes existem em cada classe, mas acho que o teorema da contagem de Polya pode fazer isso. Por enquanto, só preciso de uma maneira algorítmica de construir uma matriz em cada classe de desigualdade. Alguma ideia?

algorithms combinatorics Heterótico
fonte

Existem pelo menos destes. É um número realmente grande.

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

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

Yuval Filmus

@Yuval: Esses números são realmente grandes e, para meu cálculo, realmente faz diferença se são

. Pode levar semanas mais para ser executado! É por isso que estou tentando usar todas as simetrias do problema em questão. Como um aparte, esse problema se origina da construção de modelos na Teoria das Cordas! :)

2^{48}

$2^{48}$

2^{52}

$2^{52}$

Heterotic

O que você pretende fazer com todas essas matrizes? Onde você vai guardá-los? Qual é a aplicação?

Yuval Filmus

idéia: isso não é muito semelhante ao problema de isomorfismo gráfico? onde matrizes são matrizes de arestas gráficas? exceto aqueles são simétricas ... talvez pode ser aproveitado de alguma forma, há toneladas de teoria sobre isso ...

vzn

math.stackexchange.com/questions/924745/…

orezvani

Respostas:

Fiz alguns progressos no sentido de responder a esta pergunta. Estou postando aqui caso alguém esteja interessado e também porque essa construção pode ter alguma utilidade para gráficos (direcionados).

Conte o número de 1s em cada linha. Deixe é o número de linhas com zero 1s, o número de linhas com um 1 e assim por diante até que é o número de linhas que têm oito 1s. Obviamente . A parametrização proposta a que cheguei após tentativa e erro é: que T é o traço da matriz e S é se a matriz é simétrica e caso contrário. T vai de a $a_0$ $a_1$ $a_8$ $\sum a_i=8$

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

Pelas minhas tentativas e erros, parece que, se duas matrizes são diferentes nessa parametrização, elas pertencem a diferentes classes de equivalência; portanto, para construir um representante em cada classe, apenas examinamos o espaço de parâmetros conforme descrito acima.

(Atualização) Acontece que essa parametrização funciona bem para n = 2, mas não para n = 3, como pode ser visto por um cálculo de força bruta. Ainda acho que ele fornece algumas dicas sobre a estrutura da resposta e convido as pessoas a tentar modificá-las / estendê-las para cobrir o caso mais geral.

Heterótico
fonte

1 \times 1

$1 \times 1$

2 \times 2

$2\times 2$

7 \times 7

$7 \times 7$

@ DW: Na verdade, é a prova de que essa condição é suficiente que me incomoda e que eu gostaria de alguma ajuda. Vou tentar verificar exaustivamente os casos menores e ver o que acontece. Obrigado pelo conselho! Infelizmente, não tenho idéia de como usar um solucionador SAT para procurar contra-exemplos. Se a conjectura, vale para as matrizes menores, eu poderia começar a aprender sobre isso ...

Heterótica

Faz sentido, heterótico! Na verdade, retiro minha declaração sobre o uso de um solucionador SAT. Também não sei como usar um solucionador SAT para procurar contra-exemplos (é mais difícil do que eu pensava a princípio) - então, por favor, ignore essa parte do meu comentário. Me desculpe por isso!

a_{i}

$a_i$

(1, 4)

$(1,4)$

(2, 3)

$(2,3)$

(1, 4)

$(1,4)$

(2, 4)

$(2,4)$ (todas as entradas restantes 0 para ambos) não são equivalentes, mas têm a mesma parametrização. (Claro que isso imediatamente leva a uma parametrização melhorada que também leva as colunas em conta.)

FrankW

Heterótico, agora que você sabe que sua resposta não funciona, sugiro que a exclua para que não confunda os outros ...