Polinomio característico

13

El polinomio característico de una matriz cuadrada A se define como el polinomio p A (x) = det ( I x- A ) donde I es la matriz de identidad y det el determinante . Tenga en cuenta que esta definición siempre nos da un polinomio monico tal que la solución es única.

Su tarea para este desafío es calcular los coeficientes del polinomio característico para una matriz con valores enteros, para esto puede usar incorporados pero no se recomienda.

Reglas

  • la entrada es una matriz entera NxN (N ≥ 1) en cualquier formato conveniente
  • su programa / función generará / devolverá los coeficientes en orden creciente o decreciente (especifique cuál)
  • los coeficientes están normados de tal manera que el coeficiente de x N es 1 (ver casos de prueba)
  • no necesita manejar entradas inválidas

Casos de prueba

Los coeficientes se dan en orden decreciente (es decir, x N , x N-1 , ..., x 2 , x, 1):

[0] -> [1 0]
[1] -> [1 -1]
[1 1; 0 1] -> [1 -2 1]
[80 80; 57 71] -> [1 -151 1120] 
[1 2 0; 2 -3 5; 0 1 1] -> [1 1 -14 12]
[4 2 1 3; 4 -3 9 0; -1 1 0 3; 20 -4 5 20] -> [1 -21 -83 559 -1987]
[0 5 0 12 -3 -6; 6 3 7 16 4 2; 4 0 5 1 13 -2; 12 10 12 -2 1 -6; 16 13 12 -4 7 10; 6 17 0 3 3 -1] -> [1 -12 -484 3249 -7065 -836601 -44200]
[1 0 0 1 0 0 0; 1 1 0 0 1 0 1; 1 1 0 1 1 0 0; 1 1 0 1 1 0 0; 1 1 0 1 1 1 1; 1 1 1 0 1 1 1; 0 1 0 0 0 0 1] -> [1 -6 10 -6 3 -2 0 0]
ბიმო
fuente
Relacionados . Relacionados .
ბიმო
Relacionado
Peter Taylor
1
¿Puedo generar un polinomio?
alephalpha
1
@alephalpha: Claro.
ბიმო
¿Puedo mostrar como [ 1.00000000e+00 -1.51000000e+02 1.12000000e+03], por ejemplo?
Sr. Xcoder

Respuestas:

11

SageMath , 3 bytes

5 bytes guardados gracias a @Mego

fcp

Pruébalo en línea!

Toma un Matrixcomo entrada.

fcprepresenta f actorization de la c haracteristic p olynomial,

que es más corto que el incorporado normal charpoly.

Uriel
fuente
9

Octava , 16 4 bytes

@BruteForce acaba de decirme que una de las funciones que estaba usando en mi solución anterior puede hacer todo el trabajo:

poly

Pruébalo en línea!

16 bytes: esta solución calcula los valores propios de la matriz de entrada y luego continúa construyendo un polinomio a partir de las raíces dadas.

@(x)poly(eig(x))

Pero, por supuesto, también está lo aburrido.

charpoly

(necesita una symbolicmatriz de tipo en Octave, pero funciona con las matrices habituales en MATLAB).

Pruébalo en línea!

falla
fuente
6

R , 53 bytes

function(m){for(i in eigen(m)$va)T=c(0,T)-c(T,0)*i
T}

Pruébalo en línea!

Devuelve los coeficientes en orden creciente; es decir, a_0, a_1, a_2, ..., a_n.

Calcula el polinomio al encontrar los valores propios de la matriz.

R + pracma , 16 bytes

pracma::charpoly

pracma es la biblioteca de "Matemáticas prácticas" para R, y tiene bastantes funciones útiles.

Giuseppe
fuente
5

Mathematica, 22 bytes

Det[MatrixExp[0#]x-#]&

-7 bytes de alephalpha
-3 bytes de Misha Lavrov

Pruébalo en línea!

y por supuesto...

Mathematica, 29 bytes

#~CharacteristicPolynomial~x&

Pruébalo en línea!

ambas respuestas generan un polinomio

J42161217
fuente
4

Haskell , 243 223 222 bytes

s=sum
(&)=zip
z=zipWith
a#b=[[s$z(*)x y|y<-foldr(z(:))([]<$b)b]|x<-a]
f a|let c=z pure[1..]a;g(u,d)k|m<-[z(+)a b|(a,b)<-a#u&[[s[d|x==y]|y<-c]|x<-c]]=(m,-s[s[b|(n,b)<-c&a,n==m]|(a,m)<-a#m&c]`div`k)=snd<$>scanl g(0<$c<$c,1)c

Pruébalo en línea!

¡Gracias a @ ØrjanJohansen por ayudarme a jugar golf!

Explicación

Esto utiliza el algoritmo Faddeev – LeVerrier para calcular los coeficientes. Aquí hay una versión sin golf con nombres más detallados:

-- Transpose a matrix/list
transpose b = foldr (zipWith(:)) (replicate (length b) []) b

-- Matrix-matrix multiplication
(#) :: [[Int]] -> [[Int]] -> [[Int]]
a # b = [[sum $ zipWith (*) x y | y <- transpose b]|x<-a]


-- Faddeev-LeVerrier algorithm
faddeevLeVerrier :: [[Int]] -> [Int]
faddeevLeVerrier a = snd <$> scanl go (zero,1) [1..n]
  where n = length a
        zero = replicate n (replicate n 0)
        trace m = sum [sum [b|(n,b)<-zip [1..n] a,n==m]|(m,a)<-zip [1..n] m]
        diag d = [[sum[d|x==y]|y<-[1..n]]|x<-[1..n]]
        add as bs = [[x+y | (x,y) <- zip a b] | (b,a) <- zip as bs]
        go (u,d) k = (m, -trace (a#m) `div` k)
          where m = add (diag d) (a#u)

Nota: Tomé esto directamente de esta solución

ბიმო
fuente
1
Un byte más aquí: c=z pure[1..]a.
Ørjan Johansen
Maldición, eso es inteligente!
ბიმო
¡Gracias! Acabo de encontrar f a|let c=z pure[0..]a;g(u,d)k|m<-[z(+)a b|(a,b)<-a#u&[[s[d|x==y]|y<-c]|x<-c]]=(m,-s[a#m!!n!!n|n<-c]`div`(k+1))=snd<$>scanl g(0<$c<$c,1)c, algo similar debería funcionar en el otro también.
Ørjan Johansen
1

CJam (48 bytes)

{[1\:A_,{1$_,,.=1b\~/A@zf{\f.*1fb}1$Aff*..+}/;]}

Conjunto de pruebas en línea

Disección

Esto es bastante similar a mi respuesta al Determinante de una matriz entera . Tiene algunos ajustes porque los signos son diferentes y porque queremos mantener todos los coeficientes en lugar de solo el último.

{[              e# Start a block which will return an array
  1\            e#   Push the leading coefficient under the input
  :A            e#   Store the input matrix in A
  _,            e#   Take the length of a copy
  {             e#     for i = 0 to n-1
                e#       Stack: ... AM_{i+1} i
    1$_,,.=1b   e#       Calculate tr(AM_{i+1})
    \~/         e#       Divide by -(i+1)
    A@          e#       Push a copy of A, bring AM_{i+1} to the top
    zf{\f.*1fb} e#       Matrix multiplication
    1$          e#       Get a copy of the coefficient
    Aff*        e#       Multiply by A
    ..+         e#       Matrix addition
  }/
  ;             e#   Pop AM_{n+1} (which incidentally is 0)
]}
Peter Taylor
fuente