Ważna uwaga : ponieważ to wyzwanie dotyczy tylko macierzy kwadratowych, za każdym razem, gdy używam terminu „macierz”, zakłada się, że mam na myśli macierz kwadratową. Ze względu na zwięzłość pomijam opis „kwadratowy”.

tło

Wiele operacji związanych z macierzą, takich jak obliczanie wyznacznika, rozwiązywanie układu liniowego lub rozszerzanie funkcji o wartości skalarnej na macierze, jest łatwiejsze dzięki zastosowaniu macierzy diagonalnej (tej, której elementy nie znajdują się na głównej przekątnej wynoszą 0), która jest podobna do pierwotnej macierzy (co oznacza, że ​​dla macierzy wejściowej Ai macierzy diagonalnej Distnieje pewna macierz odwracalna Ptaka, że D = P^(-1) * A * P; także, Di Amają pewne ważne właściwości, takie jak wartości własne, wyznacznik i ślad). Do matryc z różnych wartości własnych (korzeniach do osnowy charakterystycznej wielomianu danym w trakcie rozwiązywania det(A-λI) = 0dla λgdzie Imacierz identyczności z tych samych wymiarach co A) diagonalizacja jest prostaDjest macierzą z wartościami własnymi na głównej przekątnej i Pjest macierzą utworzoną z wektorów własnych odpowiadających tym wartościom własnym (w tej samej kolejności). Ten proces nazywa się składem eigend .

Jednak matryc z powtarzanymi wartościami własnymi nie można diagonalizować w ten sposób. Na szczęście normalną postać Jordana dowolnej matrycy można dość łatwo obliczyć i nie jest to trudniejsze w użyciu niż zwykła macierz diagonalna. Ma także tę przyjemną właściwość, że jeśli wartości własne są unikalne, to rozkład Jordana jest identyczny z rozkładem eigend.

Wyjaśnienie rozkładu Jordana

W przypadku macierzy kwadratowej, Aktórej wszystkie wartości własne mają geometryczną krotność 1, proces rozkładu Jordana można opisać jako taki:

1. Niech λ = {λ_1, λ_2, ... λ_n}będzie lista wartości własnych A, z wielokrotnością, z powtarzającymi się wartościami własnymi pojawiającymi się kolejno.
2. Utwórz macierz diagonalną, Jktórej elementy są elementami λ, w tej samej kolejności.
3. Dla każdej wartości własnej o wielokrotności większej niż 1, umieść a 1po prawej stronie każdego z powtórzeń wartości własnej na głównej przekątnej J, z wyjątkiem ostatniej.

Powstała macierz Jjest postacią normalną Jordana A(dla danej macierzy może być wiele postaci normalnych Jordana, w zależności od kolejności wartości własnych).

Sprawdzony przykład

Niech Abędzie następująca macierz:

Wartości własne A, z wielością, są λ = {1, 2, 4, 4}. Umieszczając je w macierzy diagonalnej, otrzymujemy ten wynik:

Następnie umieszczamy 1s po prawej stronie wszystkich oprócz jednej z powtarzanych wartości własnych. Ponieważ 4jest to jedyna powtarzana wartość własna, umieszczamy singiel 1obok pierwszych 4:

Jest to normalna forma Jordana A(pojedyncza matryca może potencjalnie mieć kilka prawidłowych form Jordan, ale w celu wyjaśnienia omawiam te szczegóły).

Zadanie

Biorąc pod uwagę kwadratową macierz Ajako dane wejściowe, wypisz prawidłową normalną postać Jordana A.

• Dane wejściowe i wyjściowe mogą być w dowolnym rozsądnym formacie (tablica 2D / lista / cokolwiek, lista / tablica / cokolwiek z wektorów kolumn lub wierszy, wbudowany typ danych macierzy itp.).
• Elementami i wartościami własnymi Azawsze będą liczby całkowite z tego zakresu [-200, 200].
• Dla uproszczenia wszystkie wartości własne będą miały geometryczną krotność 1 (a zatem powyższy proces obowiązuje).
• A będzie co najwyżej macierzą 10x10 i co najmniej macierzą 2x2.
• Wbudowane funkcje, które obliczają wartości własne i / lub wektory własne lub wykonują skład eigend, rozkład Jordana lub inny rodzaj rozkładu / diagonalizacji, są niedozwolone. Dozwolone są arytmetyka macierzy, inwersja macierzy i inne wbudowane macierze.

Przypadki testowe

[[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]]

Mathematica, 140 139 105 bajtów

Total[DiagonalMatrix@@@{{#},{1-Sign[Differences@#^2],1}}]&@(x/.Solve[#~CharacteristicPolynomial~x==0,x])&

Właśnie znalazłem wbudowany, DiagonalMatrixktóry pozwala na łatwy sposób umieszczania zer i jedynek wzdłuż superdiagonalnej.

Stosowanie

Sage, 79 bajtów

lambda A:block_diagonal_matrix([jordan_block(*r)for r in A.charpoly().roots()])

Wypróbuj online

Ponieważ nikt inny nie publikuje rozwiązań, równie dobrze mogę napisać jedno.

A.charpoly.roots()oblicza pierwiastki (i algebraiczne krotności) charakterystycznego wielomianu A(czyli wartości własnych i krotności). jordan_blockkonstruuje blok Jordan z podanego pierwiastka i wielokrotności. block_diagonal_matrixtworzy matrycę z blokami Jordan na przekątnej, co jest dokładnie definicją normalnej postaci Jordana.

J , 78 71 bajtów

1(#\.|."_1#{."1],.2=/\,&_)@>@{[:p.@>[:-&.>/ .(+//.@(*/)&.>)],&.>[:-@=#\

Wypróbuj online!

Dwie wymagające części tego zadania, uzyskiwanie wartości własnych i przeprowadzanie diagonalizacji, ostatecznie kończą się tą samą liczbą bajtów. Zostały one niedozwolone przez reguły, ale jeśli ktoś jest ciekawy, J ma wbudowane funkcje dekompozycji QR ( 128!:0), a także dodatki LAPACK, których można użyć do znalezienia wartości własnych.

Wyjaśnienie (nieaktualne)

Czasownik składa się z dwóch głównych części: znajdowanie wartości własnych i przeprowadzanie przekątnej. Po pierwsze, aby znaleźć wartości własne, należy znaleźć korzenie charakterystycznego wielomianu dla macierzy wejściowej. Korzystając z tej samej matrycy wejściowej z przykładu,

   ] m =: _4 ]\ 5 4 2 1 0 1 _1 _1 _1 _1 3 0 1  1 _1 2
 5  4  2  1
 0  1 _1 _1
_1 _1  3  0
 1  1 _1  2

Charakterystyczny wielomian macierzy M można znaleźć za pomocą | M - λI | = 0, gdzie I jest macierzą jednostkową o tych samych wymiarach jak M . Wyrażenie M - λI można modelować w J, umieszczając w ramkach każdy element w M z -1, jeśli jest on na przekątnej, w przeciwnym razie 0. 0. Każde pole reprezentuje wielomian w postaci współczynnika.

   (],&.>[:-@=#\) m
┌────┬────┬────┬────┐
│5 _1│4 0 │2 0 │1 0 │
├────┼────┼────┼────┤
│0 0 │1 _1│_1 0│_1 0│
├────┼────┼────┼────┤
│_1 0│_1 0│3 _1│0 0 │
├────┼────┼────┼────┤
│1 0 │1 0 │_1 0│2 _1│
└────┴────┴────┴────┘

Wyznacznikiem w J jest -/ .*jednak to , że działa na liczbach, a nie na wielomianach w ramkach. Zamiast mnożenia potrzebny jest iloczyn wielomianowy, który można znaleźć za pomocą splotu ( [:+//.*/). Odejmowane jest odejmowanie &.złożone i oba te czasowniki muszą działać w polach, dlatego użyto under ( ) unbox ( >).

   ([:-&.>/ .(+//.@(*/)&.>)],&.>[:-@=#\) m0
┌───────────────┐
│32 _64 42 _11 1│
└───────────────┘

Są to współczynniki charakterystycznego wielomianu. Można znaleźć pierwiastki, p.które przekształcają reprezentację wielomianu między współczynnikami i formą pierwiastków.

   ([:p.@>[:-&.>/ .(+//.@(*/)&.>)],&.>[:-@=#\) m0
┌─┬───────┐
│1│4 4 2 1│
└─┴───────┘

Korzenie [4, 4, 2, 1]i są to wartości własne M .

Po drugie, należy przeprowadzić diagonalizację. Każda ciągła para wartości jest testowana pod kątem równości.

   (2=/\]) 4 4 2 1
1 0 0

Dołączane jest zero i wartości te są koluminizowane wraz z wartościami własnymi.

   (],.0,~2=/\]) 4 4 2 1
4 1
4 0
2 0
1 0

Następnie każdy rząd jest dopełniany do tej samej długości, co liczba wartości własnych, aby utworzyć macierz kwadratową.

   (#{."1],.0,~2=/\]) 4 4 2 1
4 1 0 0
4 0 0 0
2 0 0 0
1 0 0 0

Na koniec każdy wiersz jest przesuwany w prawo, a wartości spadają po prawej, a zera są przesuwane po lewej stronie. Pierwszy rząd jest przesunięty zero razy, drugi raz, trzeci dwa razy i tak dalej.

   (-@i.@#|.!.0"_1#{."1],.0,~2=/\]) 4 4 2 1
4 1 0 0
0 4 0 0
0 0 2 0
0 0 0 1

Wyjście jest Jordan rozkładu M .

Oktawa , 60 bajtów

@(a)diag(1-sign(diff(v=round(roots(poly(a)))).^2),1)+diag(v)

Wypróbuj online!

Port mojego rozwiązania Mathematica .

MATL , 29 bajtów, niekonkurujący

1$Yn1$ZQYotdUZS~0hXdF1hYSwXd+

Wypróbuj online!

To jest moje pierwsze zgłoszenie MATL, więc na pewno będą poprawki. Spędziłem trochę czasu na nauce i dopiero na końcu przypomniałem sobie, że może to nie zadziałało przy użyciu MATL-a od 7 maja 2016. Rzeczywiście, sprawdziłem przedostatnie zatwierdzenie tego dnia i nie zadziałało .

Chciałbym użyć, diagale wygląda na to, że MATL obsługuje tylko wersję z jednym argumentem. Drugi argument byłby potrzebny do umieszczenia wartości wzdłuż superdiagonalnej (lub innej przekątnej dla różnych problemów).