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]
[ 1.00000000e+00 -1.51000000e+02 1.12000000e+03]
, misalnya?Jawaban:
SageMath , 3 byte
5 byte disimpan berkat @Mego
Cobalah online!
Mengambil
Matrix
input sebagai.fcp
singkatan f actorization dari c haracteristic p olynomial,yang lebih pendek dari builtin normal
charpoly
.sumber
Oktaf ,
164 byte@ BruteForce baru saja mengatakan kepada saya bahwa salah satu fungsi yang saya gunakan dalam solusi saya sebelumnya sebenarnya dapat melakukan seluruh pekerjaan:
Cobalah online!
16 Bytes: Solusi ini menghitung nilai eigen dari matriks input, dan kemudian mulai membangun polinomial dari akar yang diberikan.
Tapi tentu saja ada juga yang membosankan
(membutuhkan
symbolic
matriks tipe dalam Oktaf, tetapi bekerja dengan matriks yang biasa di MATLAB.)Cobalah online!
sumber
Pari / GP , 8 byte
Cobalah online!
Pari / GP , 14 byte
Cobalah online!
sumber
x
ke matriks dimensi yang sesuai? Bagus!R , 53 byte
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
adalah pustaka "PRACtical MAth" untuk R, dan memiliki beberapa fungsi praktis.sumber
Mathematica, 22 byte
-7 byte dari alephalpha
-3 byte dari Misha Lavrov
Cobalah online!
dan tentu saja...
Mathematica, 29 byte
Cobalah online!
kedua jawaban menghasilkan polinomial
sumber
Haskell ,
243 223222 byteCobalah 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:
Catatan: Saya mengambil ini langsung dari solusi ini
sumber
c=z pure[1..]a
.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.Python 2 + numpy , 23 byte
Cobalah online!
sumber
MATL , 4 byte
Cobalah online!
Ini hanyalah sebuah port jawaban oktaf flawr , sehingga mengembalikan koefisien dalam urutan menurun, yaitu,
[a_n, ..., a_1, a_0]
sumber
CJam (48 byte)
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.
sumber