Catatan penting : Karena tantangan ini hanya berlaku untuk matriks kuadrat, setiap kali saya menggunakan istilah "matriks", diasumsikan bahwa saya mengacu pada matriks kuadrat. Saya meninggalkan deskripsi "persegi" demi singkatnya.
Latar Belakang
Banyak operasi yang berhubungan dengan matriks, seperti menghitung determinan, menyelesaikan sistem linier, atau memperluas fungsi bernilai skalar ke matriks menjadi lebih mudah dengan menggunakan matriks diagonal (elemen yang elemen-elemennya tidak berada pada diagonal utama adalah 0) yang serupa ke matriks asli (artinya, untuk matriks input A
dan matriks diagonal D
, ada beberapa matriks yang dapat dibalik P
sehingga D = P^(-1) * A * P
; juga, D
dan A
berbagi beberapa sifat penting, seperti nilai eigen, determinan, dan jejak). Untuk matriks dengan nilai eigen yang berbeda (akar ke polinomial karakteristik matriks, diberikan oleh penyelesaian det(A-λI) = 0
untuk λ
, di mana I
matriks identitas dengan dimensi yang sama A
), diagonalisasi sederhana:D
adalah matriks dengan nilai eigen pada diagonal utama, dan P
merupakan matriks yang dibentuk dari vektor eigen yang sesuai dengan nilai eigen tersebut (dalam urutan yang sama). Proses ini disebut komposisi eigend .
Namun, matriks dengan nilai eigen berulang tidak dapat didiagonalisasi dengan cara ini. Untungnya, bentuk normal Jordan dari matriks apa pun dapat dihitung dengan mudah, dan tidak jauh lebih sulit untuk dikerjakan daripada matriks diagonal biasa. Ini juga memiliki properti bagus, jika nilai eigen unik, maka dekomposisi Jordan identik dengan komposisi eigend.
Dekomposisi Jordan menjelaskan
Untuk matriks kuadrat A
dengan nilai eigen semuanya memiliki kelipatan geometris 1, proses dekomposisi Jordan dapat digambarkan sebagai berikut:
- Membiarkan
λ = {λ_1, λ_2, ... λ_n}
menjadi daftar nilai eigen dariA
, dengan multiplisitas, dengan nilai eigen berulang muncul secara berurutan. - Buat matriks diagonal
J
yang unsur-unsurnya adalah unsur-unsurλ
, dalam urutan yang sama. - Untuk setiap nilai eigen dengan multiplisitas lebih besar dari 1, letakkan a
1
di sebelah kanan setiap pengulangan nilai eigen di diagonal utamaJ
, kecuali yang terakhir.
Matriks yang dihasilkan J
adalah bentuk normal Jordan dari A
(bisa ada beberapa bentuk normal Jordan untuk matriks yang diberikan, tergantung pada urutan nilai eigen).
Contoh yang berhasil
Membiarkan A
menjadi matriks berikut:
Nilai eigen dari A
, dengan multiplisitas, adalah λ = {1, 2, 4, 4}
. Dengan menempatkan ini ke dalam matriks diagonal, kami mendapatkan hasil ini:
Selanjutnya, kami menempatkan 1
s di sebelah kanan semua kecuali satu dari masing-masing nilai eigen yang diulang. Karena 4
satu-satunya nilai eigen yang diulang, kami menempatkan satu di 1
sebelah 4 pertama:
Ini adalah bentuk normal Jordan A
(sebuah matriks tunggal berpotensi memiliki beberapa bentuk normal Jordan yang valid, tapi saya membahas detail itu untuk tujuan penjelasan).
Tugas
Diberikan matriks persegi A
sebagai input, menghasilkan bentuk normal Jordan valid A
.
- Input dan output mungkin dalam format yang wajar (array 2D / daftar / apa pun, daftar / array / apa pun dari vektor kolom atau baris, tipe data matriks bawaan, dll.).
- Elemen dan nilai eigen dari
A
akan selalu menjadi bilangan bulat dalam rentang tersebut[-200, 200]
. - Demi kesederhanaan, semua nilai eigen akan memiliki kelipatan geometris 1 (dan dengan demikian proses di atas berlaku).
A
paling banyak akan menjadi matriks 10x10 dan setidaknya matriks 2x2.- Builtin yang menghitung nilai eigen dan / atau vektor eigen atau melakukan eigendekomposisi, dekomposisi Jordan, atau segala jenis dekomposisi / diagonalisasi lainnya tidak diperbolehkan. Aritmatika matriks, inversi matriks, dan matriks bawaan lainnya diizinkan.
Uji kasus
[[1, 0], [0, 1]] -> [[1, 1], [0, 1]]
[[3, 0], [0, 3]] -> [[1, 1], [0, 1]]
[[4, 2, 2], [1, 2, 2],[0, 3, 3]] -> [[6, 0, 0], [0, 3, 0], [0, 0, 0]]
[[42, 48, 40, 64, 64], [41, 47, 31, 58, 42], [-55, -47, -27, -74, -46], [-46, -58, -46, -70, -68], [30, 20, 12, 34, 18]] -> [[10, 0, 0, 0, 0], [0, -18, 0, 0, 0], [0, 0, 6, 1, 0], [0, 0, 0, 6, 1], [0, 0, 0, 0, 6]]
Last@JordanDecomposition@#&
? Atau itu curang?Sage, 79 byte
Cobalah online
Karena tidak ada orang lain yang memposting solusi, saya mungkin lebih baik memposting.
A.charpoly.roots()
menghitung akar (dan multiplisitas aljabar) dari polinomial karakteristikA
(alias nilai eigen dan multiplisitas).jordan_block
membangun blok Jordan dari akar yang diberikan dan banyaknya.block_diagonal_matrix
membentuk matriks dengan blok Jordan pada diagonal, yang persis definisi bentuk normal Jordan.sumber
J ,
7871 byteCobalah online!
Dua bagian yang menantang dari tugas ini, mendapatkan nilai eigen dan melakukan diagonalisasi, akhirnya mengambil jumlah byte yang sama. Ini tidak diizinkan oleh aturan tetapi jika ada yang penasaran, J memiliki builtin untuk dekomposisi QR (
128!:0
) serta addon LAPACK yang dapat digunakan untuk menemukan nilai eigen.Penjelasan (Sudah kedaluwarsa)
Ada dua bagian utama dari kata kerja ini: menemukan nilai eigen dan melakukan diagonalisasi. Pertama, untuk menemukan nilai eigen, akar polinomial karakteristik untuk matriks input harus ditemukan. Menggunakan matriks input yang sama dari contoh,
Polinomial karakteristik untuk matriks M dapat ditemukan menggunakan | M - λI | = 0 di mana saya adalah matriks identitas dengan dimensi yang sama seperti M . Ekspresi M - λI dapat dimodelkan dalam J dengan meninju setiap elemen dalam M dengan -1 jika berada pada diagonal yang lain, jika tidak, 0. Setiap kotak mewakili polinomial dalam bentuk koefisien.
Namun penentu dalam J adalah
-/ .*
, yang beroperasi pada angka, bukan polinomial kotak. Alih-alih multiplikasi, produk polinomial diperlukan yang dapat ditemukan menggunakan konvolusi ([:+//.*/
). Pengurangan dilipat masih digunakan, dan kedua kata kerja ini perlu beroperasi di dalam kotak sehingga di bawah (&.
) unbox (>
) digunakan.Ini adalah koefisien dari polinomial karakteristik. Akar dapat ditemukan menggunakan
p.
yang mengubah representasi polinomial antara koefisien dan bentuk akar.Akar adalah
[4, 4, 2, 1]
dan mereka adalah nilai eigen dari M .Kedua, diagonalisasi harus dilakukan. Setiap pasangan nilai kontinu diuji untuk kesetaraan.
Nol ditambahkan dan nilai-nilai tersebut dikelompokkan bersama dengan nilai eigen.
Kemudian setiap baris diisi dengan panjang yang sama dengan jumlah nilai eigen untuk membentuk matriks persegi.
Akhirnya setiap baris bergeser ke kanan dengan nilai jatuh di sebelah kanan dan nol didorong di sebelah kiri. Baris pertama digeser nol kali, yang kedua sekali, yang ketiga dua kali, dan seterusnya.
Output adalah dekomposisi Jordan dari M .
sumber
Oktaf , 60 byte
Cobalah online!
Port solusi Mathematica saya .
sumber
MATL , 29 byte, tidak bersaing
Cobalah online!
Ini adalah pengajuan MATL pertama saya jadi pasti ada perbaikan. Saya menghabiskan beberapa waktu untuk mempelajarinya dan hanya pada akhirnya saya ingat bahwa ini mungkin tidak akan berhasil menggunakan MATL dari 7 Mei 2016. Cukup yakin, saya memeriksa komitmen kedua dari belakang hingga hari itu dan itu tidak berjalan.
Saya ingin menggunakan
diag
tetapi tampaknya MATL hanya mendukung versi argumen tunggal. Argumen kedua akan diperlukan untuk menempatkan nilai di sepanjang superdiagonal (atau diagonal lainnya untuk masalah yang berbeda).sumber