Ingeniería inversa "bonitas" matrices a partir de los valores propios

Question

Antes de comenzar, debo señalar algunas similitudes con la pregunta: Construyendo matrices a partir de valores propios. Sin embargo, tengo un objetivo diferente.

La Configuración

Cuando se escriben problemas para un curso introductorio de álgebra lineal, una pregunta genérica sería

Encuentra los valores propios de $A= \begin{bmatrix} \dots \end{bmatrix}$.

Desde la perspectiva de un instructor, generalmente es deseable que el cálculo sea razonablemente sencillo (por ejemplo, no pedir a los estudiantes encontrar raíces de un quíntico irreducible). Además, el objetivo de la pregunta es si los estudiantes pueden encontrar correctamente el polinomio característico y resolver las raíces, en lugar de la capacidad de sumar cuidadosamente numerosas fracciones. Como tal, las matrices $A$ con entradas enteras son generalmente preferibles, quizás junto con una inclinación hacia entradas positivas que no sean demasiado grandes. Sin embargo, no queremos que el problema sea demasiado fácil. Por ejemplo, pedir a los estudiantes encontrar los valores propios de una matriz diagonal/triangular no hace una pregunta particularmente buena (a menos que específicamente sea una cuestión de reconocer esta propiedad).

Por lo tanto, probablemente sea mejor escribir tal pregunta comenzando con los valores propios y trabajando hacia atrás para generar una matriz $A$ con esos valores propios.

Estos pensamientos me llevan a una definición (admisiblemente vaga):

Una "matriz ingeniosa" $A$ debería

1. Tener un conjunto dado de valores propios $\{\lambda_1, \dots, \lambda_n\}$.

2. Contener solo enteros no nulos: $A = (a_{ij}) \in \{\mathbb{Z}\setminus\{0\}\}^{n \times n}$

Nota que nuestras condiciones requieren que los valores propios sean enteros algebraicos y que la lista de valores propios debe contener todos los conjugados de Galois.

Por ejemplo,

$$ D= \begin{bmatrix} 3 & 0 \\ 0 & 2 \end{bmatrix}, \quad T= \begin{bmatrix} 3 & 7 \\ 0 & 2 \end{bmatrix}, \quad \text{ y } A=\begin{bmatrix} 1 & 1 \\ -2 & 4 \end{bmatrix} $$ todas tienen los mismos valores propios, pero solo $A$ es una matriz "ingeniosa" para los valores propios $\{3,2\}$. De manera similar, $$A= \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}$$ es una matriz "ingeniosa" para los valores propios $\lambda_\pm = \frac{3 \pm \sqrt{5}}{2}$.

El Objetivo

Imagina que estás atrapado en una fábrica de libros de texto y necesitas escribir cientos de problemas de "calcular los valores propios". ¿Cómo te acercarías a tu tarea? Dado que estás eligiendo los valores propios al principio, también puedes controlar los polinomios característico y minimal de $A$, $\chi_A$ y $\mu_A$.

La forma en que visualizo que esto funcione es una función / algoritmo que brinde un mapeo (quizás no único)

$$\{\text{valores propios y min. o pol. característico} \} \longrightarrow \text{matriz ingeniosa}. $$

Un enfoque simple

1. Comienza con una lista de valores propios enteros.

2. Forma una matriz diagonal (o matriz de bloque de Jordan o matriz triangular superior) $M$ que tenga los valores propios deseados.

3. Construye una matriz $P$ realizando algunas operaciones de fila en la matriz identidad, sin reescalar filas ni agregar copias no enteras de filas. Según la regla de Cramer, $P^{-1}$ también tendrá entradas enteras.

4. Forma $A= P M P^{-1}$. Observa cómo lo hicimos. Sigue intentando con diferentes matrices $P$ hasta que algo funcione.

Un enfoque ligeramente más sofisticado.

Este enfoque tiene la ventaja de comenzar con el polinomio característico, lo que te permite generar matrices ingeniosas para valores propios que no necesariamente son enteros (a diferencia del enfoque anterior).

1. Elige un polinomio característico adecuado $\chi$ y un polinomio minimal $\mu$, cada uno con coeficientes enteros.

2. Construye una matriz $C$ que será la forma canónica racional de $A$ utilizando el polinomio característico y el polinomio minimal. Observa que $C$ tendrá entradas enteras.

3. Utiliza nuestro truco del algoritmo anterior: $A=P C P^{-1}$ donde $\det(P)= \pm 1$. Observa cómo lo hicimos. Sigue intentando con diferentes matrices $P$ hasta que algo funcione.

La Pregunta

¿Hay una mejor manera? Nota que ambos algoritmos están mal definidos: ¿cómo encontramos un $P$ que garantice que $A$ no tenga entradas nulas?

Como una extensión de este problema, supongamos que definimos una matriz super ingeniosa como una matriz ingeniosa que minimiza $f(A) = \max_{i,j} \{|a_{ij|} \}$ entre todas las matrices ingeniosas similares. ¿Cómo podríamos encontrar un minimizador (probablemente no único)? ¿Qué tal si minimizamos con respecto a $g(A) = \sum_{i,j} |a_{ij}|$ u otra norma apropiada en las entradas?

¿Y si decidimos que los números negativos son demasiado complicados y queremos $A=(a_{ij}) \in \mathbb{N}^{n\times n}$? ¿Qué condiciones impondría esto en los valores propios y nuestros algoritmos?

Editado para agregar:

Debo señalar que tales "matrices ingeniosas" realmente no son problemas agradables, fuera del caso $2 \times 2$. Por eso no las llamo "matrices agradables", sino "ingeniosas" como en "¡Oye! ¡Esta matriz desordenada de enteros tiene mis valores propios/pol. característico deseados! ¿No es eso ingenioso?" Estoy principalmente interesado en este problema como un constructo matemático; generar un problema ingenioso de álgebra lineal es solo una idea motivadora.

Para otra motivación, quizás más "realista", puedes reformular el problema como:

Dada una lista de $n$ valores propios adecuados, ¿es posible crear un grafo completo en $n$ vértices de modo que cada arista tenga un peso entero no nulo (posiblemente negativo) y la matriz de transición ponderada tenga los valores propios deseados? ¿Cuál es el grafo más "simple" de este tipo? ¿Cómo puedes construir algoritmicamente este grafo / matriz de transición ponderada?

Answer 1

Una posible solución se ve de la siguiente manera. La idea es comenzar con una matriz diagonal y luego alterar la matriz sin cambiar su polinomio característico.

Consideremos el siguiente ejemplo. Comenzamos con la matriz $$ \begin{pmatrix} 3 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{pmatrix} \,, $$ que obviamente tiene los valores propios $1$, $2$ y $3$. Su polinomio característico está dado por $$ \det \begin{pmatrix} 3 - t & 0 & 0\\ 0 & 1 - t & 0 \\ 0 & 0 & 2 - t \end{pmatrix} \,. $$ El determinante no cambia si agregamos un múltiplo de una fila de la matriz a otra fila. Por ejemplo, agreguemos dos veces la primera fila a la segunda fila. Obtenemos que $$ \det \begin{pmatrix} 3 - t & 0 & 0\\ 6 - 2t & 1 - t & 0 \\ 0 & 0 & 2 - t \end{pmatrix} $$ sigue siendo el mismo polinomio que antes. Sin embargo, el problema es que este no es el polinomio característico de la matriz donde $t=0$, porque la variable $t$ aparece en una entrada fuera de la diagonal. Podemos eliminar este $t$, agregando un múltiplo de una columna adecuada a otra columna. En este ejemplo, podemos agregar $(-2)$ veces la segunda columna a la primera. Obtenemos que $$ \det \begin{pmatrix} 3 - t & 0 & 0\\ 4 & 1 - t & 0 \\ 0 & 0 & 2 - t \end{pmatrix} $$ sigue siendo el mismo polinomio, y vemos que este es el polinomio característico de la matriz $$ \det \begin{pmatrix} 3 & 0 & 0\\ 4 & 1 & 0 \\ 0 & 0 & 2 \end{pmatrix} \,. $$ Este procedimiento se puede repetir hasta que se obtenga un resultado satisfactorio. En resumen, el procedimiento es

1. Elegir una matriz diagonal que tenga los valores propios deseados (de $\mathbb{Z}$) en la diagonal.
2. Elegir $i \neq j$, y $a \in \mathbb{Z}$.
3. Agregar $a$ veces la $j$-ésima fila a la $i$-ésima fila.
4. Agregar $-a$ veces la $i$-ésima columna a la $j$-ésima columna.
5. Repetir desde el paso 2. hasta estar satisfecho.

Este procedimiento funciona, siempre y cuando no todos los valores propios sean idénticos.

Convertí esta idea en un script de Python, que se puede encontrar en github. El script podría generar matrices que a veces tienen ceros en lugares aleatorios, sin embargo, esto podría corregirse utilizando una lógica de programa más sofisticada.