Forma normal de Smith

Forma normal de matriz

En matemáticas, la forma normal de Smith (a veces abreviada SNF ^[1] ) 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 a partir 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 irlandés Henry John Stephen Smith .

Definición

Sea una matriz distinta de cero sobre un dominio ideal principal . Existen matrices invertibles y - (con coeficientes en ) tales que el producto es ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle R}$ ${\displaystyle m\times m}$ ${\displaystyle n\times n}$ ${\displaystyle S,T}$ ${\displaystyle R}$ ${\displaystyle SAT}$

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

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

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

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

Ejemplo: para una matriz, con y . ${\displaystyle 2\times 2}$ ${\displaystyle {\rm {SNF}}{a~~b \choose c~~d}={\rm {diag}}(d_{1},d_{2}/d_{1})}$ ${\displaystyle d_{1}=\gcd(a,b,c,d)}$ ${\displaystyle d_{2}=ad-bc}$

Algoritmo

El primer objetivo es encontrar matrices cuadradas invertibles y cuyo producto sea diagonal. Esta 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 manera más abstracta, el objetivo es mostrar que, pensando en un mapa desde (el módulo libre de rango ) hasta (el módulo libre de rango ), hay isomorfismos y cosas que tienen la forma simple de una matriz diagonal . Las matrices y se pueden encontrar comenzando con matrices identidad del tamaño apropiado y modificando cada vez que se realiza una operación de fila en el algoritmo por la operación de columna correspondiente (por ejemplo, si la fila se agrega a la fila de , entonces la columna debe restarse de la columna de para conservar la invariante del producto) y modificar 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. Sólo se realizan operaciones de filas y columnas 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}\to 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 también es un dominio de factorización único ). En particular, también es un dominio de Bézout , por lo que es un dominio mcd y el mcd de dos elementos cualesquiera satisface la identidad de Bézout . ${\displaystyle a\in R\setminus \{0\}}$ ${\displaystyle \delta (a)}$ ${\displaystyle a}$ ${\displaystyle R}$

Para poner una matriz en forma normal de Smith, se puede aplicar repetidamente lo siguiente, donde se realiza un bucle de 1 a . ${\displaystyle t}$ ${\displaystyle m}$

Paso I: elegir un pivote

Elija ser el índice de columna más pequeño 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, se supone que hay 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, dejando , sabemos por la propiedad de Bézout que existen σ, τ en R tales 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 , esa fila k del producto es otra combinación lineal de esas filas originales y que todas las demás filas no cambian. Explícitamente, si σ y τ satisfacen la ecuación anterior, entonces para y (qué divisiones son posibles según la definición de β) se 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 se puede obtener ajustando las filas y columnas t y k de la matriz identidad. Por construcción, la matriz obtenida después de multiplicar por la izquierda por L tiene una 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 había antes, y así en particular ; por lo tanto, repetir estos pasos eventualmente debe terminar. Se termina con una matriz que tiene una entrada en la posición ( _t , jt ) que divide todas las entradas en la _columna jt . ${\displaystyle L_{0}}$ ${\displaystyle a_{t,j_{t}}}$ ${\displaystyle \delta (\beta )<\delta (a_{t,j_{t}})}$

Paso III: Eliminación de entradas

Finalmente, sumando 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 que la matriz sea completamente diagonal, también debemos 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 transpuesta 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, ya sea para filas o columnas, debe continuar reduciendo el valor de y, por lo tanto, el proceso debe detenerse eventualmente después de un 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, sólo es necesario diagonalizar el bloque de A en la parte inferior derecha de ( t , j _t ) 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 las hay), 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 hacia la derecha, de modo que las entradas distintas de cero estén en posiciones para . Para abreviar, configúrelo para 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 columna a 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 diagonal. Dado que la nueva entrada en la posición es una combinación lineal de la 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 con la operación anterior (es δ del determinante de la submatriz superior), por lo que esa operación sí disminuye (al mover 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}(r-j)\delta (\alpha _{j}).}$

Entonces, después de un número finito de aplicaciones de esta operación, no es posible realizar más aplicaciones, lo que significa que hemos obtenido lo deseado. ${\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 y -S invertibles , T de modo que el producto SAT satisface la definición de forma normal de Smith. En particular, esto muestra que existe la forma normal de Smith, que se asumió sin pruebas 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 cadenas cuando los módulos de cadena del complejo de cadenas se generan de forma finita . Por ejemplo, en topología , se puede utilizar para calcular la homología de un complejo simplicial finito o complejo CW sobre números enteros, porque los mapas de límites en dicho complejo son solo matrices de números enteros. 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 teoría de control para calcular la transmisión y el bloqueo de ceros de una matriz de función de transferencia . ^[2]

Ejemplo

Como ejemplo, encontraremos la forma normal de Smith de la siguiente matriz sobre los números 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 se aplica el algoritmo 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.

Complejidad del tiempo de ejecución

La forma normal de Smith de una matriz A de N por N se puede calcular en el tiempo . ^[3] Si la matriz es escasa , el cálculo suele ser mucho más rápido. ${\displaystyle O(\|A\|\log \|A\|N^{4}\log N)}$

Semejanza

La forma normal de Smith se puede utilizar para determinar si las matrices con entradas en 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 tienen la misma forma normal de Smith (trabajando en el PID ). ${\displaystyle K}$ ${\displaystyle xI-A}$ ${\displaystyle xI-B}$ ${\displaystyle K[x]}$

Por ejemplo, con

${\displaystyle {\begin{aligned}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}}.\end{aligned}}}$

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
• Ecuación diofántica
• Divisores elementales
• Forma normal de Frobenius (también llamada forma canónica racional)
• Forma normal de Hermita
• factor invariante
• Teorema de estructura para módulos generados finitamente sobre un dominio ideal principal
• Valor singular de descomposición

Notas

1. Stanley, Richard P. (2016). "Forma normal de Smith en combinatoria". Revista de teoría combinatoria . Serie A. 144 : 476–495. arXiv : 1602.00166 . doi : 10.1016/j.jcta.2016.06.013 . S2CID  14400632.
2. Maciejowski, enero M. (1989). Diseño de retroalimentación multivariable . Wokingham, Inglaterra: Addison-Wesley. ISBN 0201182432. OCLC  19456124.
3. "Tiempo de cálculo de la forma normal de Smith en Maple". Desbordamiento matemático . Consultado el 5 de abril de 2024 .

Referencias

• Smith, Henry J. Stephen (1861). "Sobre sistemas de congruencias y ecuaciones lineales indeterminadas". Fil. Trans. R. Soc. Londres. 151 (1): 293–326. doi :10.1098/rstl.1861.0016. JSTOR  108738. S2CID  110730515.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.
• Forma normal de Smith en PlanetMath .
• Ejemplo de forma normal de Smith en PlanetMath .
• KR Matthews, forma normal de Smith. MP274: Álgebra lineal, Apuntes de conferencias, Universidad de Queensland, 1991.

enlaces externos

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