Construyendo matrices binarias no equivalentes

Estoy tratando de construir todas las matrices equivalentes (o si lo desea) con los elementos 0 o 1. La operación que da matrices equivalentes es el intercambio simultáneo de la fila i y j Y la columna i y j. p.ej. 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, también necesitaré contar cuántas matrices equivalentes hay dentro de cada clase, pero creo que el teorema de conteo de Polya puede hacer eso. Por ahora solo necesito una forma algorítmica de construir una matriz en cada clase de desigualdad. ¿Algunas ideas?

algorithms combinatorics Heterótica
fuente

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

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

2^{48}

$2^{48}$

2^{52}

$2^{52}$

¿Qué piensas hacer con todas estas matrices? ¿Dónde los vas a guardar? ¿Cuál es la aplicación?

Yuval Filmus

idea: ¿no es esto muy similar al problema del isomorfismo gráfico? donde las matrices son matrices de borde de gráfico? excepto que son simétricos ... tal vez se puede aprovechar de alguna manera, hay toneladas de teoría sobre eso ...

vzn

math.stackexchange.com/questions/924745/…

orezvani

He hecho algunos progresos para responder esta pregunta. Estoy publicando aquí en caso de que alguien más esté interesado y también porque esta construcción podría tener alguna utilidad para los gráficos (dirigidos).

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

Según mis pruebas y errores, parece que si dos matrices son diferentes en esta parametrización, entonces pertenecen a diferentes clases de equivalencia, por lo que para construir un representante en cada clase simplemente escaneamos a través del espacio de parámetros como se describió anteriormente.

(Actualización) Resulta que esta parametrización funciona bien para n = 2 pero no para n = 3, como puede verse por un cálculo de fuerza bruta. Sigo pensando que proporciona información sobre la estructura de la respuesta e invito a las personas a intentar modificarla / ampliarla para cubrir el caso más general.

Heterótica
fuente

Sería sorprendente e interesante si esto funcionara. No veo ninguna razón obvia por la que esto sea suficiente (es decir, por qué estamos garantizados de que si dos matrices tienen los mismos parámetros, estarán en la misma clase de equivalencia). Sin alguna prueba, soy escéptico. Como punto de partida, podría intentar verificar esta conjetura en matrices más pequeñas (

1 \times 1

$1 \times 1$

2 \times 2

$2\times 2$

7 \times 7

$7 \times 7$

@DW: De hecho, es la prueba de que esta condición es suficiente que me preocupa y con la que me gustaría recibir ayuda. Intentaré verificarlo exhaustivamente para los casos más pequeños y ver qué pasa. ¡Gracias por el consejo! Desafortunadamente, no tengo idea de cómo usar un solucionador SAT para buscar contraejemplos. Si la conjetura es válida para las matrices más pequeñas, podría comenzar a aprender sobre ella ...

Heterotic

¡Tiene sentido, heterótico! En realidad, retiro mi declaración sobre el uso de un solucionador SAT. Tampoco sé cómo usar un solucionador SAT para buscar contraejemplos (es más difícil de lo que pensé al principio), así que ignore esa parte de mi comentario. ¡Lo siento por eso!

Hay matrices inequívocas con la misma parametrización. Tenga en cuenta que al cambiar el

para contar los 1 en las columnas, también obtiene una parametrización que es invariante bajo la operación de equivalencia. De esto podemos concluir que las matrices con 1 en

a_{i}

$a_i$

(1, 4)

$(1,4)$

(2, 3)

$(2,3)$

(1, 4)

$(1,4)$

(2, 4)

$(2,4)$ (todas las entradas restantes 0 para ambos) no son equivalentes pero tienen la misma parametrización. (Por supuesto, esto lleva inmediatamente a una parametrización mejorada que también tiene en cuenta las columnas).

FrankW

Heterótico, ahora que sabe que su respuesta no funciona, le sugiero que elimine su respuesta para que no confunda a los demás ...

Construyendo matrices binarias no equivalentes

Respuestas: