¿Cómo encontrar un miembro canónico de una clase de equivalencia de matrices bajo intercambios de filas y columnas?

Question

Dos matrices son equivalentes si una puede transformarse en la otra mediante una secuencia de intercambios de filas y columnas.

Me gustaría disponer de un algoritmo computacionalmente eficiente que pueda transformar una matriz en una matriz canónica de intercambio equivalente (de modo que todos los miembros de una clase de equivalencia den el mismo resultado).

Primero he ordenado las filas y luego las columnas, utilizando la siguiente función de comparación:

Una lista (fila o columna) $a$ se considera mayor que una lista $b$ si cuando se ordena, $a$ viene antes que $b$ lexicográficamente, con los empates rotos por el orden lexicográfico de (sin clasificar) $a$ y $b$ .

Por ejemplo:

$\begin{matrix} 1 & 0 & 3 \\ 0 & 4 & 2 \\ 2 & 0 & 4 \end{matrix}$

se convierte en

$\begin{matrix} 2 & 0 & 4 \\ 0 & 4 & 2 \\ 1 & 0 & 3 \end{matrix}$

después de ordenar las filas y, a continuación

$\begin{matrix} 4 & 0 & 2 \\ 2 & 4 & 0 \\ 3 & 0 & 1 \end{matrix}$

después de ordenar las columnas.

Esto es bastante eficiente, pero no he sido capaz de averiguar si es correcto.

EDIT: Resulta que esto no funciona.

$\begin{matrix} 2 & 1 & 0 \\ 1 & 0 & 2 \end{matrix}$

se transforma en

$\begin{matrix} 2 & 0 & 1 \\ 1 & 2 & 0 \end{matrix}$

pero

$\begin{matrix} 2 & 1 & 0 \\ 0 & 2 & 1 \end{matrix}$

se transforma en

$\begin{matrix} 1 & 2 & 0 \\ 2 & 0 & 1 \end{matrix}$

aunque sean equivalentes.

Sin embargo, volver a ordenar las filas lo soluciona. ¿Es suficiente? ¿Tal vez iterar hasta alcanzar un estado estable?

Answer 1

La pregunta enlazada por David Speyer en un comentario tiene una respuesta que señala que esto es equivalente a encontrar una representación canónica de un grafo bipartito, ya que las matrices pueden verse como matrices de biadyacencia. No se sabe que este problema esté en P. Sin embargo, el nauty suele encontrar rápidamente un formulario de este tipo.

Answer 2

Determinar si dos matrices son equivalentes en intercambio es el problema del isomorfismo de grafos para grafos bipartitos, que es asintóticamente tan difícil como el problema del isomorfismo de grafos para grafos generales (es GI-completo). No se conoce ningún algoritmo con un tiempo de ejecución polinómico en el peor de los casos, pero hay algoritmos que empíricamente parecen ser eficientes en la mayoría de los grafos con los que es probable encontrarse en la práctica.

Pides algo más: un algoritmo para calcular un representante de la clase de equivalencia, es decir, una forma canónica del grafo. Esto es al menos tan difícil como el problema del isomorfismo del grafo, y potencialmente más difícil. Sin embargo, las herramientas existentes para el isomorfismo de grafos también suelen proporcionar una forma de hacerlo.