Le polynôme caractéristique d'une matrice carrée A est défini comme le polynôme p _A (x) = det ( I x- A ) où I est la matrice d'identité et det le déterminant . Notez que cette définition nous donne toujours un polynôme monique tel que la solution est unique.

Votre tâche pour ce défi est de calculer les coefficients du polynôme caractéristique pour une matrice à valeurs entières, pour cela, vous pouvez utiliser des éléments intégrés mais cela est déconseillé.

Règles

• l'entrée est une matrice entière NxN (N ≥ 1) dans n'importe quel format pratique
• votre programme / fonction affichera / renverra les coefficients dans un ordre croissant ou décroissant (veuillez préciser lequel)
• les coefficients sont normés de telle sorte que le coefficient de x ^N est 1 (voir cas de test)
• vous n'avez pas besoin de gérer des entrées invalides

Cas de test

Les coefficients sont donnés par ordre décroissant (c'est-à-dire x ^N , x ^N-1 , ..., x ² , 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]

SageMath , 3 octets

5 octets enregistrés grâce à @Mego

fcp

Essayez-le en ligne!

Prend une Matrixentrée.

fcpsupports pour f actorization du c haracteristic p olynomial,

qui est plus court que le builtin normal charpoly.

Octave , 16 4 octets

@BruteForce vient de me dire qu'une des fonctions que j'utilisais dans ma solution précédente peut en fait faire tout le travail:

poly

Essayez-le en ligne!

16 octets: cette solution calcule les valeurs propres de la matrice d'entrée, puis procède à la construction d'un polynôme à partir des racines données.

@(x)poly(eig(x))

Mais bien sûr, il y a aussi l'ennuyeux

charpoly

(nécessite une symbolicmatrice de type dans Octave, mais fonctionne avec les matrices habituelles dans MATLAB.)

Essayez-le en ligne!

Pari / GP , 8 octets

charpoly

Essayez-le en ligne!

Pari / GP , 14 octets

m->matdet(x-m)

Essayez-le en ligne!

R , 53 octets

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

Essayez-le en ligne!

Renvoie les coefficients dans l'ordre croissant; à savoir a_0, a_1, a_2, ..., a_n.

Calcule le polynôme en trouvant les valeurs propres de la matrice.

R + pracma , 16 octets

pracma::charpoly

pracma est la bibliothèque "PRACtical MAth" pour R, et possède plusieurs fonctions pratiques.

Mathematica, 22 octets

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

-7 octets d'alephalpha
-3 octets de Misha Lavrov

Essayez-le en ligne!

et ... bien sûr ...

Mathematica, 29 octets

#~CharacteristicPolynomial~x&

Essayez-le en ligne!

les deux réponses produisent un polynôme

Haskell , 243 223 222 octets

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

Essayez-le en ligne!

Merci à @ ØrjanJohansen de m'avoir aidé à jouer au golf!

Explication

Celui-ci utilise l' algorithme de Faddeev – LeVerrier pour calculer les coefficients. Voici une version non golfée avec des noms plus verbeux:

-- 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)

_{Remarque: je l'ai pris directement de cette solution}

Python 2 + numpy , 23 octets

from numpy import*
poly

Essayez-le en ligne!

MATL , 4 octets

1$Yn

Essayez-le en ligne!

Il s'agit simplement d'un port de réponse d'octave de flawr , il renvoie donc les coefficients dans l'ordre décroissant, c'est-à-dire[a_n, ..., a_1, a_0]

1$Yn          # 1 input Yn is "poly"

CJam (48 octets)

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

Suite de tests en ligne

Dissection

Ceci est assez similaire à ma réponse au déterminant d'une matrice entière . Il a quelques ajustements parce que les signes sont différents et parce que nous voulons garder tous les coefficients plutôt que le dernier.

{[              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)
]}