Nota importante : debido a que este desafío solo se aplica a las matrices cuadradas, cada vez que uso el término "matriz", se supone que me refiero a una matriz cuadrada. Estoy dejando la descripción "cuadrada" por razones de brevedad.

Antecedentes

Muchas operaciones relacionadas con la matriz, como calcular el determinante, resolver un sistema lineal o extender funciones de valores escalares a las matrices, se hacen más fáciles al usar una matriz diagonal (una cuyos elementos que no están en la diagonal principal son 0) que es similar a la matriz original (es decir, para la matriz de entrada Ay la matriz diagonal D, existe una matriz invertible Ptal que D = P^(-1) * A * P; también, Dy Acomparte algunas propiedades importantes, como valores propios, determinantes y trazas). Para matrices con valores propios distintos (la raíz hasta polinomio característico de la matriz, dado por la resolución det(A-λI) = 0para λ, donde Ies la matriz de identidad con las mismas dimensiones que A), diagonalización es simple:Des una matriz con los valores propios en la diagonal principal, y Pes una matriz formada por vectores propios correspondientes a esos valores propios (en el mismo orden). Este proceso se llama descomposición propia .

Sin embargo, las matrices con valores propios repetidos no se pueden diagonalizar de esta manera. Afortunadamente, la forma normal de Jordan de cualquier matriz se puede calcular con bastante facilidad, y no es mucho más difícil de trabajar que una matriz diagonal regular. También tiene la buena propiedad de que, si los valores propios son únicos, entonces la descomposición de Jordan es idéntica a la descomposición propia.

Descomposición de Jordan explicada

Para una matriz cuadrada Acuyos valores propios tienen una multiplicidad geométrica de 1, el proceso de descomposición de Jordan se puede describir como tal:

1. Sea λ = {λ_1, λ_2, ... λ_n}la lista de valores propios de A, con multiplicidad, con valores propios repetidos que aparecen consecutivamente.
2. Cree una matriz diagonal Jcuyos elementos son los elementos de λ, en el mismo orden.
3. Para cada valor propio con multiplicidad mayor que 1, coloque a 1a la derecha de cada una de las repeticiones del valor propio en la diagonal principal de J, excepto el último.

La matriz resultante Jes una forma normal de Jordan A(puede haber múltiples formas normales de Jordan para una matriz dada, dependiendo del orden de los valores propios).

Un ejemplo trabajado

Sea Ala siguiente matriz:

Los valores propios de A, con multiplicidad, son λ = {1, 2, 4, 4}. Al ponerlos en una matriz diagonal, obtenemos este resultado:

A continuación, colocamos 1s a la derecha de todos menos uno de cada uno de los valores propios repetidos. Como 4es el único valor propio repetido, colocamos un solo al 1lado de los primeros 4:

Esta es una forma normal de Jordan A(una matriz simple puede tener varias formas normales de Jordan válidas, pero voy a pasar por alto ese detalle a efectos de explicación).

La tarea

Dada una matriz cuadrada Acomo entrada, genera una forma normal válida de Jordan de A.

• La entrada y la salida pueden estar en cualquier formato razonable (matriz 2D / lista / lo que sea, lista / matriz / lo que sea de vectores de columna o fila, un tipo de datos de matriz incorporado, etc.).
• Los elementos y valores propios de Asiempre serán enteros en el rango [-200, 200].
• En aras de la simplicidad, todos los valores propios tendrán una multiplicidad geométrica de 1 (y, por lo tanto, el proceso anterior se cumple).
• A como máximo será una matriz de 10x10 y al menos una matriz de 2x2.
• No se permiten las unidades integradas que calculan valores propios y / o vectores propios o realizan descomposición propia, descomposición de Jordan o cualquier otro tipo de descomposición / diagonalización. La aritmética de la matriz, la inversión de la matriz y otras matrices incorporadas están permitidas.

Casos de prueba

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

Acabo de encontrar el incorporado DiagonalMatrixque permite una manera fácil de colocar los 0 y 1 a lo largo del superdiagonal.

Uso

Sabio, 79 bytes

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

Pruébalo en línea

Como nadie más está publicando soluciones, podría seguir adelante y publicar una.

A.charpoly.roots()calcula las raíces (y las multiplicidades algebraicas) del polinomio característico de A(también conocido como los valores propios y las multiplicidades). jordan_blockconstruye un bloque Jordan a partir de la raíz y multiplicidad dadas. block_diagonal_matrixforma una matriz con los bloques de Jordan en la diagonal, que es exactamente la definición de una forma normal de Jordan.

J , 78 71 bytes

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

Pruébalo en línea!

Las dos partes desafiantes de esta tarea, obtener los valores propios y realizar la diagonalización, terminan teniendo aproximadamente el mismo número de bytes. Estas reglas no lo permitieron, pero en caso de que alguno sea curioso, J tiene incorporados para la descomposición QR ( 128!:0), así como complementos LAPACK que podrían usarse para encontrar valores propios.

Explicación (desactualizada)

Hay dos porciones principales de este verbo: encontrar los valores propios y realizar la diagonalización. Primero, para encontrar los valores propios, se deberán encontrar las raíces del polinomio característico de la matriz de entrada. Usando la misma matriz de entrada del ejemplo,

   ] 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

El polinomio característico para una matriz M se puede encontrar usando | M - λI | = 0 donde I es la matriz identidad con las mismas dimensiones que M . La expresión M - λI puede modelarse en J al encuadrar cada elemento en M con un -1 si está en la diagonal, de lo contrario, un 0. Cada cuadro representa un polinomio en forma de coeficiente.

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

-/ .*Sin embargo, el determinante en J es que opera en números, no en polinomios en caja. En lugar de multiplicar, se necesita el producto polinomial que se puede encontrar usando convolution ( [:+//.*/). La sustracción plegada todavía se usa, y ambos verbos necesitan operar dentro de cajas, por lo que se usa under ( &.) unbox ( >).

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

Estos son los coeficientes del polinomio característico. Las raíces se pueden encontrar usando p.que convierte la representación de un polinomio entre coeficientes y forma de raíces.

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

Las raíces son [4, 4, 2, 1]y esos son los valores propios de M .

En segundo lugar, se debe realizar la diagonalización. Cada par continuo de valores se prueba para la igualdad.

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

Se agrega un cero y esos valores se columinizan junto con los valores propios.

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

Luego, cada fila se rellena con la misma longitud que el número de valores propios para formar una matriz cuadrada.

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

Finalmente, cada fila se desplaza a la derecha con los valores que caen a la derecha y los ceros se presionan a la izquierda. La primera fila se desplaza cero veces, la segunda una vez, la tercera dos veces, y así sucesivamente.

   (-@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 salida es la descomposición de Jordan M .

Octava , 60 bytes

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

Pruébalo en línea!

Un puerto de mi solución de Mathematica .

MATL , 29 bytes, no competidor

1$Yn1$ZQYotdUZS~0hXdF1hYSwXd+

Pruébalo en línea!

Esta es mi primera presentación de MATL, por lo que seguramente habrá mejoras. Pasé un tiempo aprendiéndolo y solo al final recordé que esto podría no haber funcionado usando el MATL desde el 7 de mayo de 2016. Efectivamente, revisé el penúltimo compromiso de ese día y no funcionó.

Me hubiera gustado usar, diagpero parece que MATL solo admite la versión de argumento único. El segundo argumento sería necesario para colocar valores a lo largo de la superdiagonal (o cualquier otra diagonal para diferentes problemas).