Wichtiger Hinweis : Da diese Herausforderung nur für quadratische Matrizen gilt, wird jedes Mal, wenn ich den Begriff "Matrix" verwende, davon ausgegangen, dass ich mich auf eine quadratische Matrix beziehe. Ich lasse die "quadratische" Beschreibung der Kürze halber weg.

Hintergrund

Viele matrixbezogene Operationen, wie das Berechnen der Determinante, das Lösen eines linearen Systems oder das Erweitern von skalarwertigen Funktionen auf Matrizen, werden durch die Verwendung einer Diagonalmatrix (deren Elemente, die sich nicht auf der Hauptdiagonale befinden, 0 sind) vereinfacht auf die ursprüngliche Matrix (dh, für die Eingangsmatrix Aund der Diagonalmatrix Dgibt es einige invertierbare Matrix , Pso dass D = P^(-1) * A * P, auch, Dund Aeinige wichtige Eigenschaften teilen, wie Eigenwerte, Determinante und Spur). Für Matrizen mit unterschiedlichen Eigenwerten (die Wurzeln zu der charakteristischen Polynom der Matrix, durch die Lösung gegeben det(A-λI) = 0für die λ, in denen Idie Identitätsmatrix mit den gleichen Abmessungen wie A) ist Diagonalisierung einfach:Dist eine Matrix mit den Eigenwerten auf der Hauptdiagonale und Pist eine Matrix, die aus Eigenvektoren gebildet wird, die diesen Eigenwerten entsprechen (in derselben Reihenfolge). Diesen Vorgang nennt man eigendecomposition .

Matrizen mit wiederholten Eigenwerten können auf diese Weise jedoch nicht diagonalisiert werden. Glücklicherweise kann die jordanische Normalform jeder Matrix relativ einfach berechnet werden und ist nicht viel schwerer zu verarbeiten als eine reguläre Diagonalmatrix. Es hat auch die nette Eigenschaft, dass, wenn die Eigenwerte eindeutig sind, die Jordan-Zerlegung mit der eigendecomposition identisch ist.

Jordanien Zersetzung erklärt

Für eine quadratische Matrix, Aderen Eigenwerte alle eine geometrische Multiplizität von 1 haben, kann der Prozess der Jordanzerlegung folgendermaßen beschrieben werden:

1. Sei λ = {λ_1, λ_2, ... λ_n}die Liste von Eigenwerten Amit Multiplizität, wobei wiederholte Eigenwerte nacheinander auftreten.
2. Erstellen Sie eine Diagonalmatrix, Jderen Elemente die Elemente von λin derselben Reihenfolge sind.
3. Platzieren Sie für jeden Eigenwert mit einer Multiplizität größer als 1 a 1rechts von jeder Wiederholung des Eigenwerts in der Hauptdiagonale von J, mit Ausnahme der letzten.

Die resultierende Matrix Jist eine Jordan-Normalform von A(für eine gegebene Matrix kann es abhängig von der Reihenfolge der Eigenwerte mehrere Jordan-Normalformen geben).

Ein gelungenes Beispiel

Sei Adie folgende Matrix:

Die Eigenwerte von Amit Multiplizität sind λ = {1, 2, 4, 4}. Wenn wir diese in eine diagonale Matrix einfügen, erhalten wir das folgende Ergebnis:

Als nächstes platzieren wir 1s rechts von allen bis auf einen der wiederholten Eigenwerte. Da dies 4der einzige wiederholte Eigenwert ist, setzen wir eine einzelne 1neben die erste 4:

Dies ist eine jordanische Normalform von A(eine einzelne Matrix kann möglicherweise mehrere gültige jordanische Normalformen haben, aber ich beschreibe dieses Detail zur Erläuterung).

Die Aufgabe

Bei einer quadratischen Matrix Aals Eingabe wird eine gültige jordanische Normalform von ausgegeben A.

• Die Eingabe und Ausgabe kann in jedem vernünftigen Format erfolgen (2D-Array / Liste / was auch immer, Liste / Array / was auch immer von Spalten- oder Zeilenvektoren, ein eingebauter Matrixdatentyp usw.).
• Die Elemente und Eigenwerte von Awerden immer ganze Zahlen im Bereich sein [-200, 200].
• Der Einfachheit halber haben alle Eigenwerte eine geometrische Multiplizität von 1 (und somit gilt der obige Prozess).
• A wird höchstens eine 10x10-Matrix und mindestens eine 2x2-Matrix sein.
• Builtins, die Eigenwerte und / oder Eigenvektoren berechnen oder eine Neukomposition, Jordan-Dekomposition oder eine andere Art von Dekomposition / Diagonalisierung durchführen, sind nicht zulässig. Matrixarithmetik, Matrixinversion und andere eingebaute Matrizen sind zulässig.

Testfälle

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

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

Ich habe gerade das eingebaute Symbol gefunden, mit dem die Nullen DiagonalMatrixund Einsen einfach entlang der Superdiagonale platziert werden können.

Verwendung

Salbei, 79 Bytes

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

Probieren Sie es online aus

Da sonst niemand Lösungen veröffentlicht, kann ich genauso gut eine veröffentlichen.

A.charpoly.roots()berechnet die Wurzeln (und algebraischen Multiplizitäten) des charakteristischen Polynoms von A(auch bekannt als die Eigenwerte und Multiplizitäten). jordan_blockkonstruiert einen Jordan-Block aus der gegebenen Wurzel und Multiplizität. block_diagonal_matrixbildet mit den Jordan-Blöcken auf der Diagonale eine Matrix, die genau die Definition einer Jordan-Normalform ist.

J , 78 71 Bytes

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

Probieren Sie es online!

Die beiden herausfordernden Teile dieser Aufgabe, das Abrufen der Eigenwerte und das Durchführen der Diagonalisierung, dauern ungefähr die gleiche Anzahl von Bytes. Diese wurden von den Regeln nicht zugelassen, aber für den Fall, dass jemand neugierig ist, hat J sowohl integrierte QR-Zerlegungsfunktionen ( 128!:0) als auch LAPACK-Addons, mit denen sich Eigenwerte ermitteln lassen.

Erklärung (veraltet)

Dieses Verb besteht aus zwei Hauptteilen: Ermitteln der Eigenwerte und Durchführen der Diagonalisierung. Um die Eigenwerte zu finden, müssen zunächst die Wurzeln des charakteristischen Polynoms für die Eingangsmatrix gefunden werden. Verwenden Sie die gleiche Eingabematrix aus dem Beispiel,

   ] 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

Das charakteristische Polynom für eine Matrix M kann mit | ermittelt werden M - λI | = 0 wobei I die Identitätsmatrix mit den gleichen Dimensionen wie M ist . Der Ausdruck M - λI kann in J modelliert werden, indem jedes Element in M mit -1 umrahmt wird, wenn es sich auf der Diagonale befindet, andernfalls eine 0. Jedes Kästchen repräsentiert ein Polynom in Koeffizientenform.

   (],&.>[:-@=#\) 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│
└────┴────┴────┴────┘

Die Determinante in J ist -/ .* jedoch, dass mit Zahlen gearbeitet wird, nicht mit Box-Polynomen. Anstelle der Multiplikation wird das Polynomprodukt benötigt, das mit Convolution ( [:+//.*/) ermittelt werden kann. Gefaltete Subtraktion wird weiterhin verwendet, und diese beiden Verben müssen innerhalb von Feldern operieren, sodass unter ( &.) unbox ( >) verwendet wird.

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

Dies sind die Koeffizienten des charakteristischen Polynoms. Es können die Wurzeln ermittelt werden, mit p.denen die Darstellung eines Polynoms zwischen Koeffizienten und Wurzelform konvertiert wird.

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

Die Wurzeln sind [4, 4, 2, 1]und das sind die Eigenwerte von M .

Zweitens muss die Diagonalisierung durchgeführt werden. Jedes fortlaufende Wertepaar wird auf Gleichheit geprüft.

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

Eine Null wird angehängt und diese Werte werden zusammen mit den Eigenwerten koluminiert.

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

Dann wird jede Zeile auf die gleiche Länge wie die Anzahl der Eigenwerte aufgefüllt, um eine quadratische Matrix zu bilden.

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

Schließlich wird jede Zeile nach rechts verschoben, wobei rechts die Werte abfallen und links die Nullen eingefügt werden. Die erste Reihe wird nullmal verschoben, die zweite einmal, die dritte zweimal und so weiter.

   (-@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

Der Ausgang ist die Jordan - Zerlegung von M .

Oktave , 60 Bytes

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

Probieren Sie es online!

Ein Port meiner Mathematica- Lösung .

MATL , 29 Bytes, nicht konkurrierend

1$Yn1$ZQYotdUZS~0hXdF1hYSwXd+

Probieren Sie es online!

Dies ist meine erste MATL-Einreichung, daher muss es Verbesserungen geben. Ich verbrachte , während sie lernen und erst am Ende habe ich daran erinnern , dass dies nicht von Mai die MATL gearbeitet haben , unter Verwendung von 7, 2016. Sicher genug, überprüfte ich die vorletzte heraus begehen zu diesem Tag und es nicht laufen.

Ich hätte es gerne benutzt, diagaber es scheint, dass MATL nur die Version mit einem Argument unterstützt. Das zweite Argument wäre erforderlich, um Werte entlang der Superdiagonale (oder einer anderen Diagonale für verschiedene Probleme) zu platzieren.