Polinom karakteristik

13

The polinomial karakteristik dari matriks persegi A didefinisikan sebagai polinomial p A (x) = det ( I x A ) di mana saya adalah matriks identitas dan det yang determinan . Perhatikan bahwa definisi ini selalu memberi kita polinomial monik sehingga solusinya unik.

Tugas Anda untuk tantangan ini adalah menghitung koefisien polinomial karakteristik untuk matriks bernilai integer, untuk ini Anda dapat menggunakan built-in tetapi tidak disarankan.

Aturan

  • input adalah matriks integer NxN (N ≥ 1) dalam format apa pun yang nyaman
  • program / fungsi Anda akan menampilkan / mengembalikan koefisien dalam urutan naik atau turun (sebutkan)
  • koefisien dinormalkan sedemikian sehingga koefisien x N adalah 1 (lihat kasus uji)
  • Anda tidak perlu menangani input yang tidak valid

Testcases

Koefisien diberikan dalam urutan menurun (mis. 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]
ბიმო
sumber
Terkait . Terkait .
ბიმო
Terkait
Peter Taylor
1
Bisakah saya membuat polinomial?
alephalpha
1
@alephalpha: Tentu.
ბიმო
Bolehkah saya menampilkan [ 1.00000000e+00 -1.51000000e+02 1.12000000e+03], misalnya?
Tn. Xcoder

Jawaban:

11

SageMath , 3 byte

5 byte disimpan berkat @Mego

fcp

Cobalah online!

Mengambil Matrixinput sebagai.

fcpsingkatan f actorization dari c haracteristic p olynomial,

yang lebih pendek dari builtin normal charpoly.

Uriel
sumber
9

Oktaf , 16 4 byte

@ BruteForce baru saja mengatakan kepada saya bahwa salah satu fungsi yang saya gunakan dalam solusi saya sebelumnya sebenarnya dapat melakukan seluruh pekerjaan:

poly

Cobalah online!

16 Bytes: Solusi ini menghitung nilai eigen dari matriks input, dan kemudian mulai membangun polinomial dari akar yang diberikan.

@(x)poly(eig(x))

Tapi tentu saja ada juga yang membosankan

charpoly

(membutuhkan symbolicmatriks tipe dalam Oktaf, tetapi bekerja dengan matriks yang biasa di MATLAB.)

Cobalah online!

cacat
sumber
6

R , 53 byte

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

Cobalah online!

Mengembalikan koefisien dalam urutan yang meningkat; yaitu a_0, a_1, a_2, ..., a_n,.

Menghitung jumlahnya banyak dengan menemukan nilai eigen dari matriks.

R + pracma , 16 byte

pracma::charpoly

pracma adalah pustaka "PRACtical MAth" untuk R, dan memiliki beberapa fungsi praktis.

Giuseppe
sumber
5

Mathematica, 22 byte

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

-7 byte dari alephalpha
-3 byte dari Misha Lavrov

Cobalah online!

dan tentu saja...

Mathematica, 29 byte

#~CharacteristicPolynomial~x&

Cobalah online!

kedua jawaban menghasilkan polinomial

J42161217
sumber
4

Haskell , 243 223 222 byte

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

Cobalah online!

Terima kasih kepada @ ØrjanJohansen karena membantu saya bermain golf ini!

Penjelasan

Ini menggunakan algoritma Faddeev-LeVerrier untuk menghitung koefisien. Berikut ini adalah versi yang tidak dikoleksi dengan lebih banyak nama verbose:

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

Catatan: Saya mengambil ini langsung dari solusi ini

ბიმო
sumber
1
Satu byte lebih lanjut di sini: c=z pure[1..]a.
Ørjan Johansen
Sial, itu pintar!
ბიმო
Terima kasih! Saya baru saja menemukan 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, sesuatu yang serupa harus bekerja pada yang lain juga.
Ørjan Johansen
3

MATL , 4 byte

1$Yn

Cobalah online!

Ini hanyalah sebuah port jawaban oktaf flawr , sehingga mengembalikan koefisien dalam urutan menurun, yaitu,[a_n, ..., a_1, a_0]

1$Yn          # 1 input Yn is "poly"
Giuseppe
sumber
1

CJam (48 byte)

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

Test suite online

Pembedahan

Ini sangat mirip dengan jawaban saya untuk Penentu matriks integer . Ini memiliki beberapa penyesuaian karena tanda-tanda berbeda, dan karena kami ingin menyimpan semua koefisien daripada hanya yang terakhir.

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