Remarque importante : Étant donné que ce défi ne s'applique qu'aux matrices carrées, chaque fois que j'utilise le terme «matrice», on suppose que je fais référence à une matrice carrée. Je laisse la description «carré» par souci de concision.

Contexte

De nombreuses opérations liées aux matrices, telles que le calcul du déterminant, la résolution d'un système linéaire ou l'extension des fonctions à valeurs scalaires aux matrices sont rendues plus faciles en utilisant une matrice diagonale (une dont les éléments qui ne sont pas sur la diagonale principale sont 0) qui est similaire à la matrice d'origine (c'est-à-dire, pour la matrice d'entrée Aet la matrice diagonale D, il existe une matrice inversible Ptelle que D = P^(-1) * A * P; également, Det Apartagent certaines propriétés importantes, comme les valeurs propres, le déterminant et la trace). Pour les matrices avec des valeurs propres distinctes (les racines du polynôme caractéristique de la matrice, donné en résolvant det(A-λI) = 0pour λ, où Iest la matrice d'identité avec les mêmes dimensions que A), la diagonalisation est simple:Dest une matrice avec les valeurs propres sur la diagonale principale, et Pest une matrice formée de vecteurs propres correspondant à ces valeurs propres (dans le même ordre). Ce processus est appelé eigendecomposition .

Cependant, les matrices avec des valeurs propres répétées ne peuvent pas être diagonalisées de cette manière. Heureusement, la forme normale de Jordan de n'importe quelle matrice peut être calculée assez facilement et n'est pas beaucoup plus difficile à travailler qu'une matrice diagonale régulière. Il a également la belle propriété que, si les valeurs propres sont uniques, la décomposition de Jordan est identique à la composition propre.

Décomposition de la Jordanie expliquée

Pour une matrice carrée Adont les valeurs propres ont toutes une multiplicité géométrique de 1, le processus de décomposition de Jordan peut être décrit comme tel:

1. Soit λ = {λ_1, λ_2, ... λ_n}la liste des valeurs propres de A, avec multiplicité, avec des valeurs propres répétées apparaissant consécutivement.
2. Créez une matrice diagonale Jdont les éléments sont les éléments de λ, dans le même ordre.
3. Pour chaque valeur propre avec une multiplicité supérieure à 1, placez a 1à droite de chacune des répétitions de la valeur propre dans la diagonale principale de J, sauf la dernière.

La matrice résultante Jest une forme normale de Jordan de A(il peut y avoir plusieurs formes normales de Jordan pour une matrice donnée, selon l'ordre des valeurs propres).

Un exemple concret

Soit Ala matrice suivante:

Les valeurs propres de A, avec multiplicité, sont λ = {1, 2, 4, 4}. En les mettant dans une matrice diagonale, nous obtenons ce résultat:

Ensuite, nous plaçons 1s à droite de toutes les valeurs propres répétées sauf une. Puisque 4c'est la seule valeur propre répétée, nous plaçons un simple à 1côté du premier 4:

Il s'agit d'une forme normale de Jordan A(une matrice unique peut potentiellement avoir plusieurs formes normales de Jordan valides, mais je passe sous silence ce détail à des fins d'explication).

La tâche

Étant donné une matrice carrée Aen entrée, affichez une forme normale de Jordan valide A.

• L'entrée et la sortie peuvent être dans n'importe quel format raisonnable (tableau 2D / liste / peu importe, liste / tableau / quoi que ce soit des vecteurs de colonne ou de ligne, un type de données de matrice intégré, etc.).
• Les éléments et valeurs propres de Aseront toujours des entiers dans la plage [-200, 200].
• Par souci de simplicité, toutes les valeurs propres auront une multiplicité géométrique de 1 (et donc le processus ci-dessus est valable).
• A sera au plus une matrice 10x10 et au moins une matrice 2x2.
• Les chaînes intégrées qui calculent des valeurs propres et / ou des vecteurs propres ou effectuent une décomposition par eigend, une décomposition de Jordan ou tout autre type de décomposition / diagonalisation ne sont pas autorisées. L'arithmétique matricielle, l'inversion matricielle et d'autres fonctions intégrées matricielles sont autorisées.

Cas de test

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

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

Je viens de trouver la fonction intégrée DiagonalMatrixqui permet de placer facilement les 0 et les 1 le long de la superdiagonale.

Usage

Sauge, 79 octets

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

Essayez-le en ligne

Puisque personne d'autre ne publie de solutions, je ferais aussi bien d'aller de l'avant et d'en poster une.

A.charpoly.roots()calcule les racines (et les multiplicités algébriques) du polynôme caractéristique de A(alias les valeurs propres et les multiplicités). jordan_blockconstruit un bloc de Jordan à partir de la racine et de la multiplicité données. block_diagonal_matrixforme une matrice avec les blocs de Jordan sur la diagonale, ce qui est exactement la définition d'une forme normale de Jordan.

J , 78 71 octets

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

Essayez-le en ligne!

Les deux parties difficiles de cette tâche, obtenir les valeurs propres et effectuer la diagonalisation, finissant toutes les deux par prendre le même nombre d'octets. Ceux-ci étaient interdits par les règles, mais au cas où certains seraient curieux, J a intégré des fonctions de décomposition QR (128!:0 ) ainsi que des addons LAPACK qui pourraient être utilisés pour trouver des valeurs propres.

Explication (obsolète)

Il y a deux parties principales à ce verbe: trouver les valeurs propres et effectuer la diagonalisation. Premièrement, afin de trouver les valeurs propres, les racines du polynôme caractéristique de la matrice d'entrée devront être trouvées. En utilisant la même matrice d'entrée de l'exemple,

   ] 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

Le polynôme caractéristique d'une matrice M peut être trouvé en utilisant | M - λI | = 0 où I est la matrice d'identité avec les mêmes dimensions que M . L'expression M - λI peut être modélisée en J en encadrant chaque élément de M avec un -1 s'il est sur la diagonale sinon un 0. Chaque boîte représente un polynôme sous forme de coefficient.

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

Le déterminant de J est -/ .*cependant celui qui opère sur des nombres, et non sur des polynômes encadrés. Au lieu de la multiplication, le produit polynomial est nécessaire qui peut être trouvé en utilisant convolution ( [:+//.*/). La soustraction pliée est toujours utilisée, et ces deux verbes doivent fonctionner dans des boîtes, donc sous ( &.) unbox ( >) est utilisé.

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

Ce sont les coefficients du polynôme caractéristique. Les racines peuvent être trouvées en utilisant p.ce qui convertit la représentation d'un polynôme entre les coefficients et la forme des racines.

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

Les racines sont [4, 4, 2, 1]et ce sont les valeurs propres de M .

Deuxièmement, la diagonalisation doit être effectuée. Chaque paire continue de valeurs est testée pour l'égalité.

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

Un zéro est ajouté et ces valeurs sont columinées avec les valeurs propres.

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

Ensuite, chaque ligne est complétée à la même longueur que le nombre de valeurs propres pour former une matrice carrée.

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

Enfin, chaque ligne est décalée vers la droite avec des valeurs tombant à droite et des zéros enfoncés à gauche. La première ligne est décalée de zéro fois, la deuxième une fois, la troisième deux fois, etc.

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

La sortie est la décomposition de Jordan M .

Octave , 60 octets

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

Essayez-le en ligne!

Un portage de ma solution Mathematica .

MATL , 29 octets, non concurrent

1$Yn1$ZQYotdUZS~0hXdF1hYSwXd+

Essayez-le en ligne!

Ceci est ma première soumission MATL donc il y a forcément des améliorations. J'ai passé un peu de temps à l'apprendre et ce n'est qu'à la fin que je me suis souvenu que cela n'avait peut-être pas fonctionné avec MATL à partir du 7 mai 2016. Effectivement, j'ai vérifié l'avant-dernier commit de ce jour et il n'a pas fonctionné.

J'aurais aimé utiliser diagmais il semble que MATL ne supporte que la version à argument unique. Le deuxième argument serait nécessaire pour placer des valeurs le long de la superdiagonale (ou de toute autre diagonale pour différents problèmes).