¿Cuál es la forma más rápida de encontrar el polinomio característico de una matriz?

Question

Encontrar el polinomio característico de una matriz de orden $n$ es una tarea tediosa y aburrida para $n > 2$ .

Lo sé:

• el coeficiente de $\lambda^n$ es $(-1)^n$ ,
• el coeficiente de $\lambda^{n-1}$ es $(-1)^{n-1}(a_{11} + a_{22} + \dots + a_{nn})$ ,
• el término constante es $\det{A}$ .

Al encontrar el coeficiente del término lineal $\lambda$ del polinomio característico de un $3\times 3$ se debe calcular el determinante de la matriz $A - \lambda I_n$ de todos modos. (Pero no hay que sumar todos los términos, sólo los lineales).

¿Alguien conoce una forma más rápida?

Answer 1

En una época menos ilustrada, en la que la gente tenía menos conocimientos sobre los entresijos del cálculo algorítmico de los valores propios, los métodos para generar los coeficientes del eigenpolinomio de una matriz estaban bastante extendidos. Uno de los métodos más destacados para calcular los coeficientes era un método atribuido tanto al francés Leverrier como al ruso Faddeev (que fue (co)autor de una de las referencias más antiguas sobre la práctica del álgebra lineal numérica).

El método de (Faddeev-)Leverrier es un método que requerirá hacer un número de multiplicaciones matriciales para generar los coeficientes del polinomio característico. Dejando que el $n\times n$ matriz $\mathbf A$ tienen el monic polinomio característico $(-1)^n \det(\mathbf A-\lambda\mathbf I)=\lambda^n+c_{n-1}\lambda^{n-1}+\cdots+c_0$ el algoritmo procede así:

$\mathbf C=\mathbf A;$
$\text{for }k=1,\dots,n$

$\text{if }k>1$
$\qquad \mathbf C=\mathbf A\cdot(\mathbf C+c_{n-k+1}\mathbf I);$

$c_{n-k}=-\dfrac{\mathrm{tr}(\mathbf C)}{k};$

$\text{end for}$

Si tu entorno informático puede multiplicar matrices, o tomar su traza (suma de los elementos diagonales, $\mathrm{tr}(\cdot)$ ), entonces se puede programar fácilmente a (Faddeev-)Leverrier. El método funciona bien en la aritmética exacta, o en el cálculo manual (suponiendo que se tiene la resistencia para multiplicar repetidamente matrices), pero es muy pobre en la aritmética inexacta, ya que el método tiende a magnificar en gran medida los errores de redondeo en la matriz, produciendo siempre coeficientes que se vuelven cada vez más inexactos a medida que avanza la iteración. Pero, para el simple $3\times 3$ caso previsto por el OP, esto debería funcionar bien.

Las personas interesadas en este método antiguo y retirado tal vez quieran ver este documento .

Answer 2

A mano, creo que el método de Ted Shifrin es el más rápido.

Por ordenador, evalúe $\det (\lambda \cdot \mathrm{Id}- A)$ para $n$ valores de $\lambda$ y encontrar el polinomio característico por interpolación de Lagrange.

Answer 3

Esto puede hacerte feliz o no. El coeficiente de $\lambda^{n-k}$ es $(-1)^{n-k}$ veces la suma de todos los principales $k\times k$ menores, es decir, los determinantes de todos los $k\times k$ submatrices construidas con las mismas filas y columnas. Tenga en cuenta que esto generaliza sus observaciones para $k=n$ y $k=1$ .

Answer 4

Puede utilizar el Teorema de Cayley-Hamilton que dice que la matriz $A$ es una raíz del polinomio mínimo, que divide al polinomio característico. De hecho, el polinomio mínimo tiene las mismas raíces que el característico, excepto que esas raíces pueden tener menor multiplicidad. En particular, si los valores propios de $A$ son distintos, entonces los dos polinomios son iguales.

Se calcula el $n=\dim$ poderes: $I, A, A^2, A^3,...,A^n$ y luego buscar los coeficientes $c_i$ tal que $A^n = c_{n-1}A^{n-1}+...+c_1A^1+c_0I$ entonces el polinomio mínimo es $\det(\lambda I - A) = P(X) = \lambda^n-c_{n-1}\lambda^{n-1}-...-c_1\lambda-c_0$ .

Por ejemplo, si $A=\begin{pmatrix} 0&1&0\\1&0&0\\0&0&2\end{pmatrix}$ entonces $A^2=\begin{pmatrix} 1&0&1\\0&1&0\\0&0&4\end{pmatrix}$ y $A^3=\begin{pmatrix} 0&1&0\\1&0&0\\0&0&8\end{pmatrix}$ ,

para que $A^2-I=\begin{pmatrix} 0&0&0\\0&0&0\\0&0&3\end{pmatrix}$ y $A^3-A=\begin{pmatrix} 0&0&0\\0&0&0\\0&0&6\end{pmatrix}$ Por lo tanto $A^3-A=2(A^2-I)$ y

el polinomio mínimo es $\lambda^3-\lambda-2(\lambda^2-1)=(\lambda^2-1)(\lambda-2)=(\lambda+1)(\lambda-1)(\lambda-2)$ . Al ser todas las raíces simples, el polinomio mínimo es también el polinomio característico, y $\chi_A(\lambda)=\det(\lambda I-A)=\lambda^3-2\lambda^2-\lambda+2$ .

La búsqueda de los coeficientes $c_i$ puede hacerse de forma sistemática, similar a la Método Gauss . Sin embargo, el sistema está sobredeterminado, con $n \times n$ ecuaciones, y suele ser más rápido de resolver de lo que se piensa, especialmente para las matrices que se encuentran en las tareas.

Los valores propios serán casi siempre distintos (por lo que la característica y los polinomios mínimos serán los mismos), excepto quizás para las matrices que se encuentran en la tarea. Para éstas, es mejor buscar la matriz de potencia $A^k, k \le n$ a medida que las calculas, y mira si son combinaciones lineales de las anteriores.

Por ejemplo, si $A=\begin{pmatrix} 0&1&1\\1&0&1\\1&1&0\end{pmatrix}$ entonces $A^2=\begin{pmatrix} 2&1&1\\1&2&1\\1&1&2\end{pmatrix}$ y $A^2=A+2I$ . Así que el polinomio mínimo es $\lambda^2-\lambda-2 = (\lambda+1)(\lambda-2)$ . Siendo el polinomio característico un polinomio de grado 3 con las mismas raíces, puede ser $(\lambda+1)^2(\lambda-2)$ o $(\lambda+1)(\lambda-2)^2$ . La multiplicidad $\nu_i$ de $(x-\lambda_i)$ en $\chi_A(x) = \prod (x-\lambda_i)^{\nu_i}$ es la dimensión del eigespacio asociado $E_{\lambda_i}=\ker (A-\lambda_i I)=\{x\mid Ax=\lambda_i x\}$ . En nuestro caso, $E_{-1} = \ker(A+I) = \ker \begin{pmatrix} 1&1&1\\1&1&1\\1&1&1\end{pmatrix}=2$ Así que $\chi_A(\lambda)=(\lambda+1)^2(\lambda-2)$ .

No sé si el método es menos tedioso, pero lo encuentro menos aburrido.

Answer 5

Creo que la forma más rápida conocida es la Algoritmo aleatorio Pernet-Storjohann con complejidad $O(n^\theta)$ , donde $\theta$ es un exponente admisible para la complejidad de la multiplicación de matrices en términos de operaciones de campo. Por otro lado, se sabe que la complejidad del producto de dos matrices está acotada por encima de la complejidad del polinomio característico, por lo que la complejidad Pernet-Storjohann es "aguda".