Cómo codificar matrices únicamente

Question

Dada una matriz cuadrada a $A=[a_{ij}]_{n \times n}$, una operación $swap(A, i, j)$ está definido para intercambiar la fila $i$ $j$ $A$ y hacer lo mismo con las columnas correspondientes. Por ejemplo, en el siguiente ejemplo, podemos ver el $swap(A, 1, 3)$:

$$A=\left[ \begin{array}{ccc} a & b & c \\ d & e & f \\ g & h & i \end{array} \right] ~~~~~\Rightarrow~~~~~ swap(A,1,3)=\left[ \begin{array}{ccc} i & h & g \\ f & e & d \\ c & b & a \end{array} \right]$$

Para una matriz de $A$, vamos a $swap^k(A)$ el conjunto de matrices producida por exactamente $k$ swaps. Por ejemplo, $B \in swap^3(A)$ significa que hay una secuencia de 3 swaps que puede convertir $A$ a $B$.

Una única codificación de $\phi$ de esta matriz es una función de $A$ tal forma que:

$$\phi(A)=\phi(B) ~~~~ \Leftrightarrow ~~~~ \exists k ~:~ B \in swap^k(A)$$

Para simplificar, podemos suponer que la matriz es simétrica y de sus elementos están en $\{0,1\}$. Me interesa saber si existen tales codificación para este caso de matrices o si hay una prueba de su no existencia.

Edit. ¿Cuál es la forma más eficiente de hacer esto?

Answer 1

Tal codificación existe y es finito. Si es o no es manejable es una pregunta mucho más difícil.

$\phi(A)$ puede ser definido para ser una codificación de la extensión de los intercambios de $A$:

$$\text{SwapSpan}(A) = \cup_{k=0}^{\infty} \text{swap}^k(A)$$ $$\phi(A) = \text{Encoding}(\text{SwapSpan}(A))$$

Desde allí se $n^2$ elementos de la matriz, hay un límite superior de $(n^2)!$ número de matrices en $\text{SwapSpan}(A)$. De forma explícita escribiendo la lista de las matrices de orden lexicográfico es válido canónica $\text{Encoding}$.

Tenga en cuenta que si $A \in \text{SwapSpan}(B)$ $\text{SwapSpan}(A) = \text{SwapSpan}(B)$ desde el fin de la swaps simplemente puede ser revertido.

El lapso también puede ser calculada, ya que una primera extensión de la búsqueda de todos los swaps está garantizado para terminar.

Si esto es o no es manejable depende de la potencia de cálculo y el tamaño de las matrices.

Answer 2

El problema de encontrar una forma canónica para ${0,1}$ simétrica de las matrices cuadradas uso simultáneo de fila y columna de los swaps es uno de los enfoques para la solución de la Gráfica de Isomorfismo Problema a través de la gráfica de canonización. Hay algoritmos que hacer este es el polinomio de media hora, el mejor $O$-la complejidad del algoritmo es todavía superpolynomial. Así, el paso 1 es canonizó matriz/gráfico.

Desde aquí, usted puede comprimir los datos para hacer uso eficiente del espacio. Si sus elementos se encontraban en ${0,1}$, entonces usted podría hacer un blob binario, listado de las filas en orden. Si usted tiene muy pocos $1$'s (o $0$'s, la verdad), se puede almacenar como una matriz dispersa (lista enlazada de elementos y sus posiciones en cada fila). O, si usted tiene cierta cantidad infinitesimal de tolerancia para el error, que podría llevar a su actual codificación y enviarlos a través de un algoritmo de hash (como MD5). Entonces, la igualdad de los valores hash indica la igualdad de la original matrices (modulo fila swaps) con una alta probabilidad. Esta comparación podría suceder en tiempo constante.

Answer 3

Usted puede codificar filas y columnas con multisymmetric funciones (un conjunto de generadores para las filas, y un conjunto de generadores para las columnas). Este papel es una buena fuente.

Por ejemplo, un 2-por-2 de la matriz $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ puede ser codificado como $$ (ad, a+d, ac, b+c). $$ Esto no significa que la mayoría de codificación eficiente, pero se debe hacer el trabajo.

[He hecho una edición porque me doy cuenta que no he entendido mal el problema.]