Smith forma normal - Smith normal form

En matemáticas, la forma normal de Smith (a veces abreviada SNF ) es una forma normal que se puede definir para cualquier matriz (no necesariamente cuadrada) con entradas en un dominio ideal principal (PID). La forma normal de Smith de una matriz es diagonal y se puede obtener de la matriz original multiplicando a la izquierda y a la derecha por matrices cuadradas invertibles . En particular, los números enteros son un PID, por lo que siempre se puede calcular la forma normal de Smith de una matriz de números enteros. La forma normal de Smith es muy útil para trabajar con módulos generados de forma finita sobre un PID y, en particular, para deducir la estructura de un cociente de un módulo libre . Lleva el nombre del matemático británico Henry John Stephen Smith .

Definición

Deje que A sea un no nulo m × n matriz sobre un dominio de ideales principales R . Existen matrices S, T invertibles y - tales que el producto SAT es ${\ Displaystyle m \ times m}$${\ Displaystyle n \ times n}$

${\ displaystyle {\ begin {pmatrix} \ alpha _ {1} & 0 & 0 && \ cdots && 0 \\ 0 & \ alpha _ {2} & 0 && \ cdots && 0 \\ 0 & 0 & \ ddots &&&&& 0 \\\ vdots &&& \ alpha _ {r} &&& \ vdots \\ &&&& 0 && \\ &&&&&& \ ddots & \\ 0 &&& \ cdots &&& 0 \ end {pmatrix}}.}$

y los elementos diagonales satisfacen . Esta es la forma normal de Smith de la matriz A . Los elementos son únicos hasta la multiplicación por una unidad y se denominan divisores elementales , invariantes o factores invariantes . Se pueden calcular (hasta multiplicar por una unidad) como ${\ Displaystyle \ alpha _ {i}}$${\ Displaystyle \ alpha _ {i} \ mid \ alpha _ {i + 1} \; \ forall \; 1 \ leq i <r}$${\ Displaystyle \ alpha _ {i}}$

${\ Displaystyle \ alpha _ {i} = {\ frac {d_ {i} (A)} {d_ {i-1} (A)}},}$

donde (llamado i -ésimo divisor determinante ) es igual al máximo común divisor de todos los menores de la matriz A y . ${\ Displaystyle d_ {i} (A)}$${\ Displaystyle i \ times i}$ ${\ Displaystyle d_ {0} (A): = 1}$

Algoritmo

El primer objetivo es encontrar matrices cuadradas invertibles y tales que el producto sea ​​diagonal. Ésta es la parte más difícil del algoritmo. Una vez que se logra la diagonalidad, resulta relativamente fácil poner la matriz en la forma normal de Smith. Dicho de un modo más abstracto, el objetivo es mostrar que, pensando en como mapa a (la libre - módulo de rango ) a (la libre - módulo de rango ), no son isomorfismos y de tal manera que tiene la forma simple de una matriz diagonal . Las matrices y se pueden encontrar comenzando con matrices de identidad del tamaño apropiado y modificando cada vez que se realiza una operación de fila en el algoritmo mediante la operación de columna correspondiente (por ejemplo, si la fila se agrega a la fila de , entonces la columna debe restar de la columna de para retener el producto invariante), y modificando de manera similar para cada operación de columna realizada. Dado que las operaciones de fila son multiplicaciones por la izquierda y las operaciones de columna son multiplicaciones por la derecha, esto conserva el invariante donde denota los valores actuales y denota la matriz original; eventualmente, las matrices en este invariante se vuelven diagonales. Solo se realizan operaciones de fila y columna invertibles, lo que garantiza que y sigan siendo matrices invertibles. ${\ Displaystyle S}$${\ Displaystyle T}$${\ displaystyle SAT}$${\ Displaystyle A}$${\ Displaystyle R ^ {n}}$${\ Displaystyle R}$${\ Displaystyle n}$${\ Displaystyle R ^ {m}}$${\ Displaystyle R}$${\ Displaystyle m}$${\ Displaystyle S: R ^ {m} \ to R ^ {m}}$${\ Displaystyle T: R ^ {n} \ a R ^ {n}}$${\ Displaystyle S \ cdot A \ cdot T}$${\ Displaystyle S}$${\ Displaystyle T}$${\ Displaystyle S}$${\ Displaystyle A}$${\ Displaystyle i}$${\ Displaystyle j}$${\ Displaystyle A}$${\ Displaystyle j}$${\ Displaystyle i}$${\ Displaystyle S}$${\ Displaystyle T}$${\ Displaystyle A '= S' \ cdot A \ cdot T '}$${\ Displaystyle A ', S', T '}$${\ Displaystyle A}$${\ Displaystyle S}$${\ Displaystyle T}$

Para , escriba el número de factores primos de (estos existen y son únicos, ya que cualquier PID es también un dominio de factorización único ). En particular, también es un dominio Bézout , por lo que es un dominio gcd y el gcd de dos elementos cualesquiera satisface la identidad de un Bézout . ${\ Displaystyle a \ in R \ setminus \ {0 \}}$${\ Displaystyle \ delta (a)}$${\ Displaystyle a}$${\ Displaystyle R}$

Para poner una matriz en la forma normal de Smith, se puede aplicar repetidamente lo siguiente, donde bucles de 1 a ' . ${\ Displaystyle t}$${\ Displaystyle m}$

Paso I: elegir un pivote

Elija ser el índice de columna más pequeño de con una entrada distinta de cero, comenzando la búsqueda en el índice de columna si . ${\ Displaystyle j_ {t}}$${\ Displaystyle A}$${\ Displaystyle j_ {t-1} +1}$${\ Displaystyle t> 1}$

Deseamos tener ; si este es el caso este paso está completo, de lo contrario hay por supuesto algunos con , y podemos intercambiar filas y , obteniendo así . ${\ Displaystyle a_ {t, j_ {t}} \ neq 0}$${\ Displaystyle k}$${\ Displaystyle a_ {k, j_ {t}} \ neq 0}$${\ Displaystyle t}$${\ Displaystyle k}$${\ Displaystyle a_ {t, j_ {t}} \ neq 0}$

Nuestro pivote elegido está ahora en posición . ${\ Displaystyle (t, j_ {t})}$

Paso II: mejorar el pivote

Si hay una entrada en la posición ( k , j _t ) tal que , entonces, sepamos por la propiedad de Bézout que existe σ, τ en R tal que ${\ Displaystyle a_ {t, j_ {t}} \ nmid a_ {k, j_ {t}}}$${\ Displaystyle \ beta = \ gcd \ left (a_ {t, j_ {t}}, a_ {k, j_ {t}} \ right)}$

${\ Displaystyle a_ {t, j_ {t}} \ cdot \ sigma + a_ {k, j_ {t}} \ cdot \ tau = \ beta.}$

Mediante la multiplicación por la izquierda con una matriz invertible apropiada L , se puede lograr que la fila t del producto de la matriz sea la suma de σ por la fila original t y τ por la fila original k , que la fila k del producto sea otra combinación lineal de esas filas originales, y que todas las demás filas no se modifican. Explícitamente, si σ y τ satisfacen la ecuación anterior, entonces para y (qué divisiones son posibles según la definición de β) uno tiene ${\ Displaystyle \ alpha = a_ {t, j_ {t}} / \ beta}$${\ Displaystyle \ gamma = a_ {k, j_ {t}} / \ beta}$

${\ Displaystyle \ sigma \ cdot \ alpha + \ tau \ cdot \ gamma = 1,}$

para que la matriz

${\ displaystyle L_ {0} = {\ begin {pmatrix} \ sigma & \ tau \\ - \ gamma & \ alpha \\\ end {pmatrix}}}$

es invertible, con inversa

${\ displaystyle {\ begin {pmatrix} \ alpha & - \ tau \\\ gamma & \ sigma \\\ end {pmatrix}}.}$

Ahora L puede obtenerse mediante la instalación en filas y columnas t y k de la matriz de identidad. Por construcción, la matriz obtenida después de multiplicar por la izquierda por L tiene la entrada β en la posición ( t , j _t ) (y debido a nuestra elección de α y γ también tiene una entrada 0 en la posición ( k , j _t ), lo cual es útil aunque no es esencial para el algoritmo). Esta nueva entrada β divide la entrada que estaba allí antes, y así en particular ; por lo tanto, la repetición de estos pasos debe terminar eventualmente. Uno termina con una matriz que tiene una entrada en la posición ( t , j _t ) que divide todas las entradas en la columna j _t . ${\ Displaystyle L_ {0}}$${\ Displaystyle a_ {t, j_ {t}}}$${\ Displaystyle \ delta (\ beta) <\ delta (a_ {t, j_ {t}})}$

Paso III: Eliminación de entradas

Finalmente, agregando los múltiplos apropiados de la fila t , se puede lograr que todas las entradas en la columna j _t excepto la de la posición ( t , j _t ) sean cero. Esto se puede lograr mediante la multiplicación por la izquierda con una matriz adecuada. Sin embargo, para hacer que la matriz sea completamente diagonal, también necesitamos eliminar las entradas distintas de cero en la fila de posición ( t , j _t ). Esto se puede lograr repitiendo los pasos del Paso II para columnas en lugar de filas, y usando la multiplicación de la derecha por la transposición de la matriz L obtenida . En general, esto dará como resultado que las entradas cero de la aplicación anterior del Paso III vuelvan a ser distintas de cero.

Sin embargo, observe que cada aplicación del Paso II para filas o columnas debe continuar reduciendo el valor de , por lo que el proceso debe eventualmente detenerse después de cierto número de iteraciones, lo que lleva a una matriz donde la entrada en la posición ( t , j _t ) es la única entrada distinta de cero tanto en su fila como en su columna. ${\ Displaystyle \ delta (a_ {t, j_ {t}})}$

En este punto, solo el bloque de A en la parte inferior derecha de ( t , j _t ) necesita diagonalizarse y, conceptualmente, el algoritmo se puede aplicar de forma recursiva, tratando este bloque como una matriz separada. En otras palabras, podemos incrementar t en uno y volver al paso I.

Último paso

Aplicando los pasos descritos anteriormente a las columnas restantes distintas de cero de la matriz resultante (si corresponde), obtenemos una -matriz con índices de columna donde . Las entradas de la matriz son distintas de cero y todas las demás entradas son cero. ${\ Displaystyle m \ times n}$${\ Displaystyle j_ {1} <\ ldots <j_ {r}}$${\ Displaystyle r \ leq \ min (m, n)}$${\ Displaystyle (l, j_ {l})}$

Ahora podemos mover las columnas nulas de esta matriz a la derecha, de modo que las entradas distintas de cero estén en posiciones para . Para abreviar, establezca el elemento en la posición . ${\ Displaystyle (i, i)}$${\ Displaystyle 1 \ leq i \ leq r}$${\ Displaystyle \ alpha _ {i}}$${\ Displaystyle (i, i)}$

Es posible que no se cumpla la condición de divisibilidad de las entradas diagonales. Para cualquier índice para el cual , se puede reparar esta deficiencia mediante operaciones en filas y columnas y solo: primero agregue una columna a la columna para obtener una entrada en la columna i sin alterar la entrada en la posición , y luego aplique una operación de fila para hacer la entrada en posición igual a la del Paso II; finalmente proceda como en el Paso III para volver a hacer la matriz en diagonal. Dado que la nueva entrada en la posición es una combinación lineal del original , es divisible por β. ${\ Displaystyle i <r}$${\ Displaystyle \ alpha _ {i} \ nmid \ alpha _ {i + 1}}$${\ Displaystyle i}$${\ Displaystyle i + 1}$${\ Displaystyle i + 1}$${\ Displaystyle i}$${\ Displaystyle \ alpha _ {i + 1}}$${\ Displaystyle \ alpha _ {i}}$${\ Displaystyle (i, i)}$${\ Displaystyle (i, i)}$${\ Displaystyle \ beta = \ gcd (\ alpha _ {i}, \ alpha _ {i + 1})}$${\ Displaystyle (i + 1, i + 1)}$${\ Displaystyle \ alpha _ {i}, \ alpha _ {i + 1}}$

El valor no cambia por la operación anterior (es δ del determinante de la submatriz superior ), por lo que esa operación sí disminuye (moviendo los factores primos hacia la derecha) el valor de ${\ Displaystyle \ delta (\ alpha _ {1}) + \ cdots + \ delta (\ alpha _ {r})}$${\ Displaystyle r \ times r}$

${\ Displaystyle \ sum _ {j = 1} ^ {r} (rj) \ delta (\ alpha _ {j}).}$

Entonces, después de un número finito de aplicaciones de esta operación, no es posible ninguna otra aplicación, lo que significa que hemos obtenido la deseada. ${\ Displaystyle \ alpha _ {1} \ mid \ alpha _ {2} \ mid \ cdots \ mid \ alpha _ {r}}$

Dado que todas las manipulaciones de filas y columnas involucradas en el proceso son invertibles, esto muestra que existen matrices S, T invertibles y -T de modo que el producto SAT satisface la definición de una forma normal de Smith. En particular, esto muestra que existe la forma normal de Smith, que se asumió sin prueba en la definición. ${\ Displaystyle m \ times m}$${\ Displaystyle n \ times n}$

Aplicaciones

La forma normal de Smith es útil para calcular la homología de un complejo de cadena cuando los módulos de cadena del complejo de cadena se generan de forma finita . Por ejemplo, en topología , se puede usar para calcular la homología de un complejo simplicial o complejo CW sobre los números enteros, porque los mapas de límites en tal complejo son simplemente matrices enteras. También se puede utilizar para determinar los factores invariantes que ocurren en el teorema de estructura para módulos generados finitamente sobre un dominio ideal principal , que incluye el teorema fundamental de grupos abelianos generados finitamente .

La forma normal de Smith también se utiliza en la teoría de control para calcular los ceros de transmisión y bloqueo de una matriz de función de transferencia .

Ejemplo

Como ejemplo, encontraremos la forma normal de Smith de la siguiente matriz sobre los enteros.

${\ displaystyle {\ begin {pmatrix} 2 & 4 & 4 \\ - 6 & 6 & 12 \\ 10 & 4 & 16 \ end {pmatrix}}}$

Las siguientes matrices son los pasos intermedios a medida que el algoritmo se aplica a la matriz anterior.

${\ displaystyle \ to {\ begin {pmatrix} 2 & 0 & 0 \\ - 6 & 18 & 24 \\ 10 & -16 & -4 \ end {pmatrix}} \ to {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 18 & 24 \\ 0 & -16 & -4 \ end {pmatrix}}}$

${\ displaystyle \ to {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 20 \\ 0 & -16 & -4 \ end {pmatrix}} \ to {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 20 \\ 0 & 0 & 156 \ end {pmatrix}}}$

${\ displaystyle \ to {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 156 \ end {pmatrix}}}$

Entonces la forma normal de Smith es

${\ displaystyle {\ begin {pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 156 \ end {pmatrix}}}$

y los factores invariantes son 2, 2 y 156.

Semejanza

La forma normal de Smith se puede utilizar para determinar si las matrices con entradas sobre un campo común son similares o no . Específicamente, dos matrices A y B son similares si y solo si las matrices características y tienen la misma forma normal de Smith. ${\ Displaystyle xI-A}$${\ Displaystyle xI-B}$

Por ejemplo, con

${\ displaystyle {\ begin {align} A & {} = {\ begin {bmatrix} 1 & 2 \\ 0 & 1 \ end {bmatrix}}, && {\ mbox {SNF}} (xI-A) = {\ begin {bmatrix} 1 & 0 \\ 0 & (x-1) ^ {2} \ end {bmatrix}} \\ B & {} = {\ begin {bmatrix} 3 & -4 \\ 1 & -1 \ end {bmatrix}}, && {\ mbox {SNF}} (xI-B) = {\ begin {bmatrix} 1 & 0 \\ 0 & (x-1) ^ {2} \ end {bmatrix}} \\ C & {} = {\ begin {bmatrix} 1 & 0 \\ 1 & 2 \ end {bmatrix}}, && {\ mbox {SNF}} (xI-C) = {\ begin {bmatrix} 1 & 0 \\ 0 & (x-1) (x-2) \ end {bmatrix}}. \ final {alineado}}}$

A y B son similares porque la forma normal de Smith de sus matrices características coincide, pero no son similares a C porque la forma normal de Smith de las matrices características no coincide.

Ver también

• Forma canónica
• Divisores elementales
• Forma normal de Frobenius (también llamada forma canónica racional)
• Forma normal de hermite
• Factor invariante
• Teorema de estructura para módulos generados finitamente sobre un dominio ideal principal

Notas

Referencias

• Smith, Henry J. Stephen (1861). "Sobre sistemas de ecuaciones lineales indeterminadas y congruencias". Phil. Trans. R. Soc. Lond. 151 (1): 293–326. doi : 10.1098 / rstl.1861.0016 . JSTOR   108738 . Reimpreso (págs. 367–409 ) en The Collected Mathematical Papers of Henry John Stephen Smith , vol. Yo , editado por JWL Glaisher . Oxford: Clarendon Press (1894), xcv +603 págs.
• Smith de forma normal en PlanetMath .
• Ejemplo de forma normal de Smith en PlanetMath .
• KR Matthews, Smith en forma normal . MP274: Álgebra lineal, Lecture Notes, Universidad de Queensland, 1991.

enlaces externos

• Un ejemplo animado de cálculo de la forma normal de Smith .