# Characteristic polynomial

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 $$\N\times N\$$ ($$\N \ge 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^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]

• Dec 14 '17 at 12:42
• Related Dec 14 '17 at 12:44
• Can I output a polynomial? Dec 14 '17 at 12:50
• @alephalpha: Sure. Dec 14 '17 at 12:51
• May I output as [ 1.00000000e+00 -1.51000000e+02 1.12000000e+03], for instance? Dec 14 '17 at 13:17

# 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.

# 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!

# Pari/GP, 8 bytes

charpoly


Try it online!

# Pari/GP, 14 bytes

m->matdet(x-m)


Try it online!

• GP promotes x to a matrix of the appropriate dimension? Nice! Dec 15 '17 at 3:47

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. # 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 # 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]divk)=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

• One more byte here: c=z pure[1..]a. Dec 20 '17 at 2:54
• Damn, that's clever! Dec 20 '17 at 3:03
• Thanks! I just found 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, something similar should work on the other one too. Dec 20 '17 at 13:10 # Python 2 + numpy, 23 bytes from numpy import* poly  Try it online! # 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"  ## 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