Das charakteristische Polynom einer quadratischen Matrix A wird als Polynom definiert P _A (x) = det ( I x- A ) wobei I die ist Identitätsmatrix und det die Determinante . Beachten Sie, dass diese Definition immer ein monisches Polynom ergibt, sodass die Lösung eindeutig ist.

Ihre Aufgabe für diese Herausforderung ist es, die Koeffizienten des charakteristischen Polynoms für eine ganzzahlige Matrix zu berechnen. Hierzu können Sie integrierte Funktionen verwenden, aber davon wird abgeraten.

Regeln

• Die Eingabe ist eine NxN (N ≥ 1) Ganzzahlmatrix in einem beliebigen geeigneten Format
• Ihr Programm / Ihre Funktion gibt die Koeffizienten entweder in aufsteigender oder absteigender Reihenfolge aus / zurück (bitte spezifizieren Sie welche)
• die Koeffizienten werden so normiert, dass der Koeffizient von x ^N 1 ist (siehe Testfälle)
• Sie müssen keine ungültigen Eingaben verarbeiten

Testfälle

Die Koeffizienten sind in absteigender Reihenfolge angegeben (dh 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 Bytes

5 Bytes gespart dank @Mego

fcp

Probieren Sie es online!

Nimmt ein Matrixals Eingabe.

fcpsteht für f actorization des c haracteristic p olynomial,

Das ist kürzer als die normalen eingebauten charpoly.

Oktave , 16 4 Bytes

@BruteForce hat mir gerade gesagt, dass eine der Funktionen, die ich in meiner vorherigen Lösung verwendet habe, tatsächlich die gesamte Arbeit erledigen kann:

poly

Probieren Sie es online!

16 Bytes: Diese Lösung berechnet die Eigenwerte der Eingangsmatrix und baut dann aus den gegebenen Wurzeln ein Polynom auf.

@(x)poly(eig(x))

Aber es ist natürlich auch langweilig

charpoly

(Benötigt eine symbolicTypmatrix in Octave, funktioniert aber mit den üblichen Matrizen in MATLAB.)

Probieren Sie es online!

Pari / GP , 8 Bytes

charpoly

Probieren Sie es online!

Pari / GP , 14 Bytes

m->matdet(x-m)

Probieren Sie es online!

R , 53 Bytes

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

Probieren Sie es online!

Gibt die Koeffizienten in aufsteigender Reihenfolge zurück. dh a_0, a_1, a_2, ..., a_n.

Berechnet das Polynom durch Ermitteln der Eigenwerte der Matrix.

R + pracma , 16 Bytes

pracma::charpoly

pracma ist die "PRACtical MAth" -Bibliothek für R und verfügt über einige praktische Funktionen.

Mathematica, 22 Bytes

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

-7 Bytes von Alephalpha
-3 Bytes von Mischa Lawrow

Probieren Sie es online!

und natürlich...

Mathematica, 29 Bytes

#~CharacteristicPolynomial~x&

Probieren Sie es online!

Beide Antworten geben ein Polynom aus

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

Probieren Sie es online!

Vielen Dank an @ ØrjanJohansen, der mir beim Golfen geholfen hat!

Erläuterung

Dabei werden die Koeffizienten mit dem Faddeev-LeVerrier-Algorithmus berechnet. Hier ist eine ungolfed Version mit ausführlicheren Namen:

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

_{Hinweis: Ich habe dies direkt aus dieser Lösung übernommen}

Python 2 + Anzahl , 23 Bytes

from numpy import*
poly

Probieren Sie es online!

MATL , 4 Bytes

1$Yn

Probieren Sie es online!

Dies ist nur eine Portierung der Oktavantwort von flawr , daher werden die Koeffizienten in absteigender Reihenfolge zurückgegeben, dh[a_n, ..., a_1, a_0]

1$Yn          # 1 input Yn is "poly"

CJam (48 Bytes)

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

Online-Testsuite

Präparation

Dies ist meiner Antwort auf Determinante einer Ganzzahlmatrix ziemlich ähnlich . Es gibt einige Optimierungen, weil die Vorzeichen unterschiedlich sind und weil wir alle Koeffizienten behalten wollen und nicht nur den letzten.

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