Characteristic polynomial

Question

The characteristic polynomial of a square matrix A is defined as the polynomial p_A(x) = det(Ix-A) where I is the identity matrix and det the determinant. Note that this definition always gives us a monic polynomial such that the solution is unique.

Your task for this challenge is to compute the coefficients of the characteristic polynomial for an integer valued matrix, for this you may use built-ins but it is discouraged.

Rules

• input is an NxN (N ≥ 1) integer matrix in any convenient format
• your program/function will output/return the coefficients in either increasing or decreasing order (please specify which)
• the coefficients are normed such that the coefficient of x^N is 1 (see test cases)
• you don't need to handle invalid inputs

Testcases

Coefficients are given in decreasing order (ie. 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]

Answer 1

SageMath, 3 bytes

5 bytes saved thanks to @Mego

fcp

Try it online!

Takes a Matrix as input.

fcp stands for factorization of the characteristic polynomial,

which is shorter than the normal builtin charpoly.

Answer 2

Octave, 16 4 bytes

@BruteForce just told me that one of the functions I was using in my previous solution can actually do the whole work:

poly

Try it online!

16 Bytes: This solution computes the eigenvalues of the input matrix, and then proceeds building a polynomial from the given roots.

@(x)poly(eig(x))

But of course there is also the boring

charpoly

(needs a symbolic type matrix in Octave, but works with the usual matrices in MATLAB.)

Try it online!

Answer 3

Pari/GP, 8 bytes

charpoly

Try it online!

---

Pari/GP, 14 bytes

m->matdet(x-m)

Try it online!

Answer 4

R, 53 bytes

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

Try it online!

Returns the coefficients in increasing order; i.e., a_0, a_1, a_2, ..., a_n.

Computes the polynomial by finding the eigenvalues of the matrix.

R + pracma, 16 bytes

pracma::charpoly

pracma is the "PRACtical MAth" library for R, and has quite a few handy functions.

Answer 5

Mathematica, 22 bytes

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

-7 bytes from alephalpha
-3 bytes from Misha Lavrov

Try it online!

and... of course...

Mathematica, 29 bytes

#~CharacteristicPolynomial~x&

Try it online!

both answers output a polynomial

Answer 6

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

Try it online!

Thanks to @ØrjanJohansen for helping me golf this!

Explanation

This uses the Faddeev–LeVerrier algorithm to compute the coefficients. Here's an ungolfed version with more verbose names:

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

_{Note: I took this straight from this solution}

Answer 7

Python 2 + numpy, 23 bytes

from numpy import*
poly

Try it online!

Answer 8

MATL, 4 bytes

1$Yn

Try it online!

This is merely a port of flawr's Octave answer, so it returns the coefficients in decreasing order, i.e., [a_n, ..., a_1, a_0]

1$Yn          # 1 input Yn is "poly"

Answer 9

CJam (48 bytes)

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

Online test suite

Dissection

This is quite similar to my answer to Determinant of an integer matrix. It has some tweaks because the signs are different, and because we want to keep all of the coefficients rather than just the last one.

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