13
\$\begingroup\$

The characteristic polynomial of a square matrix A is defined as the polynomial pA(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 xN is 1 (see test cases)
  • you don't need to handle invalid inputs

Testcases

Coefficients are given in decreasing order (ie. xN,xN-1,...,x2,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]
\$\endgroup\$
  • \$\begingroup\$ Related. Related. \$\endgroup\$ – ბიმო Dec 14 '17 at 12:42
  • \$\begingroup\$ Related \$\endgroup\$ – Peter Taylor Dec 14 '17 at 12:44
  • 1
    \$\begingroup\$ Can I output a polynomial? \$\endgroup\$ – alephalpha Dec 14 '17 at 12:50
  • 1
    \$\begingroup\$ @alephalpha: Sure. \$\endgroup\$ – ბიმო Dec 14 '17 at 12:51
  • \$\begingroup\$ May I output as [ 1.00000000e+00 -1.51000000e+02 1.12000000e+03], for instance? \$\endgroup\$ – Mr. Xcoder Dec 14 '17 at 13:17
11
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

Pari/GP, 8 bytes

charpoly

Try it online!


Pari/GP, 14 bytes

m->matdet(x-m)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ GP promotes x to a matrix of the appropriate dimension? Nice! \$\endgroup\$ – Charles Dec 15 '17 at 3:47
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ One more byte here: c=z pure[1..]a. \$\endgroup\$ – Ørjan Johansen Dec 20 '17 at 2:54
  • \$\begingroup\$ Damn, that's clever! \$\endgroup\$ – ბიმო Dec 20 '17 at 3:03
  • \$\begingroup\$ 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. \$\endgroup\$ – Ørjan Johansen Dec 20 '17 at 13:10
3
\$\begingroup\$

Python 2 + numpy, 23 bytes

from numpy import*
poly

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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"
\$\endgroup\$
1
\$\begingroup\$

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)
]}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.