Me he encontrado un interesante problema, basado en un proyecto que estoy trabajando en mi trabajo. Me gustaría compartir con ustedes y ver si alguien sabe si es conocido, o si alguien tiene alguna algoritmos o técnicas para acercarse a ella:
Deje $M$ $n \times n$ matriz cuadrada. Es suficiente con considerar el $M$ tener entradas de $0$ $1$ sólo y para ser bastante escasa.
Imaginemos que ese $M$ es de bloque-diagonal y que los bloques se $B_1, B_2, \cdots, B_k$, donde cada bloque de la matriz $B_i$ $m_i \times m_i$ matriz cuadrada. Definimos el "diagonality" de $M$ a ser el más pequeño de la suma de la $\sum_{i = 1}^k m_i^2$ podemos lograr
Tenemos que elegir el "más pequeño" valor ya que suelen tener alguna opción con el tamaño de la $B_i$'s. Un $2 \times 2$ matriz identidad, por ejemplo, puede ser considerada como uno $2 \times 2$ o dos cuadras $1 \times 1$ bloques, dando puntuaciones de $2^2 + 2^2 = 8$ $1^2 = 1$ respectivamente. Y así elegimos $1$ en este caso.
Así que una matriz diagonal siempre tendrá diagonality $n$, mientras que una matriz de todos los $1$'s tendrá un diagonality de $n^2$. El trivial triangular superior $2 \times 2$ matriz tendrán diagonality $4$. Etc.
Mi pregunta entonces es esta: a Partir de una matriz fija $M$, supongo que se me permite permutar las filas y las columnas a su antojo. Equivalentemente, se me permite pre - o post-multiplicar por cualquier permutación de la matriz. En hacer esto, ¿cómo iba yo a ir encontrando las permutaciones de las filas y/o columnas que minimizar el diagonality de la matriz resultante?
Por ejemplo, tomemos el $3 \times 3$ matriz
$$ \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $$
Esto comienza a tener diagonality $9$.
Podría permutar fila $1$ y la de la fila $2$ para obtener:
\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}
Y entonces puedo permutar columna de $1$ y la columna $2$ para obtener:
\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}
Y el resultado ahora ha diagonality $5$ en lugar de $9$.
Obviamente, el programa de instalación de aquí es mío, así que me imagino que si este tipo de cosas ha sido explorado, ha sido explorado en mayor generalidad. Me gustaría saber si alguien puede prestarme algunas visión de cómo se podría ir sobre la minimización de esta cantidad.
