Hispanopedia Wiki
Articulo de referencia

Forma normal de Smith

En matemáticas , la forma normal de Smith (a veces abreviada como SNF [ 1 ] ) es una forma normal que se puede definir para cualquier matriz (no necesariamente cuadrada ) con en...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , la forma normal de Smith (a veces abreviada como SNF [ 1 ] ) es una forma normal que se puede definir para cualquier matriz (no necesariamente cuadrada ) con entradas en un dominio ideal principal (DIP). La forma normal de Smith de una matriz es diagonal y se puede obtener a partir de la matriz original multiplicándola por la izquierda y por la derecha por matrices cuadradas invertibles . En particular, los enteros son un DIP, por lo que siempre se puede calcular la forma normal de Smith de una matriz entera . La forma normal de Smith es muy útil para trabajar con módulos finitamente generados sobre un DIP, y en particular para deducir la estructura de un cociente de un módulo libre . Recibe su nombre del matemático irlandés Henry John Stephen Smith . [ 2 ] [ 3 ]

Definición

DejarA{\displaystyle A}ser distinto de cerometro×norte{\displaystyle m\times n}matriz sobre un dominio ideal principalR{\displaystyle R}. Existen invertiblesmetro×metro{\displaystyle m\times m}ynorte×norte{\displaystyle n\times n}-matricesS,T{\displaystyle S,T}(con entradas enR{\displaystyle R}, ydet(S),det(T){\displaystyle \det(S),\det(T)}unidades enR{\displaystyle R}) de tal manera que el productoSAT{\displaystyle SAT}es

(α100⋯0⋯00α2000⋱⋮⋮⋮αr0⋯0⋯0⋮⋮⋮0⋯0⋯0).{\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αi{\displaystyle \alpha _{i}}satisfacerαi∣αi+1{\displaystyle \alpha _{i}\mid \alpha _{i+1}}a pesar de1≤i<r{\displaystyle 1\leq i<r}Esta es la forma normal de Smith de la matriz.A{\displaystyle A}Los elementosαi{\displaystyle \alpha _{i}}son únicos salvo multiplicación por una unidad y se denominan divisores elementales , invariantes o factores invariantes . Se pueden calcular (salvo multiplicación por una unidad) como

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

dóndedi(A){\displaystyle d_{i}(A)}(llamado divisor del i -ésimo determinante ) es igual al máximo común divisor de los determinantes de todosi×i{\displaystyle i\times i}menores de la matrizA{\displaystyle A}yd0(A):=1{\displaystyle d_{0}(A):=1}.

Ejemplo  : Para un2×2{\displaystyle 2\times 2}matriz,SnorteF(a  bdo  d)=diagramo(d1,d2/d1){\displaystyle {\rm {SNF}}{a~~b \choose c~~d}={\rm {diag}}(d_{1},d_{2}/d_{1})}cond1=mcd(a,b,do,d){\displaystyle d_{1}=\gcd(a,b,c,d)}yd2=|ad−bdo|{\displaystyle d_{2}=|ad-bc|}.

Algoritmo

El primer objetivo es encontrar matrices cuadradas invertibles.S{\displaystyle S}yT{\displaystyle T}de tal manera que el productoSAT{\displaystyle SAT}es 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 forma normal de Smith. Dicho de forma más abstracta, el objetivo es demostrar que, pensando enA{\displaystyle A}como un mapa deRnorte{\displaystyle R^{n}}(el libreR{\displaystyle R}-módulo de rangonorte{\displaystyle n}) aRmetro{\displaystyle R^{m}}(el libreR{\displaystyle R}-módulo de rangometro{\displaystyle m}), existen isomorfismosS:Rmetro→Rmetro{\displaystyle S:R^{m}\to R^{m}}yT:Rnorte→Rnorte{\displaystyle T:R^{n}\to R^{n}}de tal manera queS⋅A⋅T{\displaystyle S\cdot A\cdot T}tiene la forma simple de una matriz diagonal. Las matricesS{\displaystyle S}yT{\displaystyle T}se pueden encontrar comenzando con matrices identidad del tamaño apropiado y modificándolasS{\displaystyle S}cada vez que se realiza una operación de fila enA{\displaystyle A}en el algoritmo por la operación de columna correspondiente (por ejemplo, si filai{\displaystyle i}se agrega a la filaj{\displaystyle j}deA{\displaystyle A}, luego columnaj{\displaystyle j}debe restarse de la columnai{\displaystyle i}deS{\displaystyle S}para mantener el producto invariante), y modificando de manera similarT{\displaystyle T}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 preserva la invarianteA′=S′⋅A⋅T′{\displaystyle A'=S'\cdot A\cdot T'}dóndeA′,S′,T′{\displaystyle A',S',T'}denotan valores actuales yA{\displaystyle A}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 queS{\displaystyle S}yT{\displaystyle T}siguen siendo matrices invertibles.

Paraa∈R∖{0}{\displaystyle a\in R\setminus \{0\}}, escribirδ(a){\displaystyle \delta (a)}para el número de factores primos dea{\displaystyle a}(estos existen y son únicos ya que cualquier PID es también un dominio de factorización único ). En particular,R{\displaystyle R}También es un dominio de Bézout , por lo que es un dominio de mcd y el mcd de cualesquiera dos elementos.a,b∈R{\displaystyle a,b\in R}Satisface la identidad de Bézoutmcd(a,b)=ado+bd{\displaystyle \gcd(a,b)=ac+bd}para algunosdo,d∈R{\displaystyle c,d\in R}.

Para convertir una matriz a la forma normal de Smith, se puede aplicar repetidamente lo siguiente, donde el índicet{\displaystyle t}va de 1 ametro{\displaystyle m}.

Paso I: Elegir un punto de inflexión

Elegirjt{\displaystyle j_{t}}ser el índice de columna más pequeño deA{\displaystyle A}con una entrada distinta de cero, iniciando la búsqueda en el índice de columnajt−1+1{\displaystyle j_{t-1}+1}sit>1{\displaystyle t>1}.

Deseamos tenerat,jt≠0{\displaystyle a_{t,j_{t}}\neq 0}; si este es el caso, este paso está completo; de lo contrario, por suposición, hay algúnk{\displaystyle k}conak,jt≠0{\displaystyle a_{k,j_{t}}\neq 0}y podemos intercambiar filast{\displaystyle t}yk{\displaystyle k}, obteniendo asíat,jt≠0{\displaystyle a_{t,j_{t}}\neq 0}.

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

Paso II: Mejorar el pivote

Si existe una entrada en la posición ( k , jt ) tal queat,jt∤ak,jt{\displaystyle a_{t,j_{t}}\nmid a_{k,j_{t}}}, entonces, dejandoβ=mcd(at,jt,ak,jt){\displaystyle \beta =\gcd \left(a_{t,j_{t}},a_{k,j_{t}}\right)}, sabemos por la propiedad de Bézout que existen σ, τ en R tales que

at,jt⋅σ+ak,jt⋅τ=β.{\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 L apropiada , se puede lograr que la fila t del producto matricial sea la suma de σ veces la fila original t y τ veces 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 permanezcan sin cambios. Explícitamente, si σ y τ satisfacen la ecuación anterior, entonces paraα=at,jt/β{\displaystyle \alpha =a_{t,j_{t}}/\beta }yγ=ak,jt/β{\displaystyle \gamma =a_{k,j_{t}}/\beta }(qué divisiones son posibles por la definición de β) uno tiene

σ⋅α+τ⋅γ=1,{\displaystyle \sigma \cdot \alpha +\tau \cdot \gamma =1,}

para que la matriz

L0=(στ−γα){\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 ajustandoL0{\displaystyle L_{0}}en 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 , jt ) (y debido a nuestra elección de α y γ también tiene una entrada 0 en la posición ( k , jt ) , que es útil aunque no esencial para el algoritmo). Esta nueva entrada β divide la entradaat,jt{\displaystyle a_{t,j_{t}}}eso ya estaba allí antes, y por eso en particularδ(β)<δ(at,jt){\displaystyle \delta (\beta )<\delta (a_{t,j_{t}})}; por lo tanto, la repetición de estos pasos debe terminar eventualmente. Se obtiene una matriz que tiene una entrada en la posición ( t , j t ) que divide todas las entradas en la columna 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 que se encuentra en la posición ( t , j t ), sean cero. Esto se puede conseguir mediante la multiplicación por la izquierda con una matriz apropiada. Sin embargo, para que la matriz sea completamente diagonal, también necesitamos eliminar las entradas no nulas en la fila de la posición ( t , j t ). Esto se puede lograr repitiendo los pasos del Paso II para las columnas en lugar de las filas, y utilizando la multiplicación por la derecha por la transpuesta de la matriz L obtenida . En general, esto hará que las entradas cero de la aplicación previa del Paso III vuelvan a ser no nulas.

Sin embargo, observe que cada aplicación del Paso II, ya sea para filas o columnas, debe continuar reduciendo el valor deδ(at,jt){\displaystyle \delta (a_{t,j_{t}})}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.

En este punto, solo es necesario diagonalizar el bloque de A situado a la derecha de ( t , jt ) , y conceptualmente el algoritmo puede aplicarse recursivamente, tratando este bloque como una matriz independiente. En otras palabras, podemos incrementar t en uno y volver al paso I.

Paso final

Aplicando los pasos descritos anteriormente a las columnas no nulas restantes de la matriz resultante (si las hay), obtenemos unametro×norte{\displaystyle m\times n}-matriz con índices de columnaj1<…<jr{\displaystyle j_{1}<\ldots <j_{r}}dónder≤min(metro,norte){\displaystyle r\leq \min(m,n)}. Las entradas de la matriz(l,jl){\displaystyle (l,j_{l})}son distintos de cero, y todas las demás entradas son cero.

Ahora podemos mover las columnas nulas de esta matriz hacia la derecha, de modo que las entradas distintas de cero estén en las posiciones(i,i){\displaystyle (i,i)}para1≤i≤r{\displaystyle 1\leq i\leq r}. En resumen, conjuntoαi{\displaystyle \alpha _{i}}para el elemento en la posición(i,i){\displaystyle (i,i)}.

Es posible que no se cumpla la condición de divisibilidad de las entradas diagonales. Para cualquier índicei<r{\displaystyle i<r}para quéαi∤αi+1{\displaystyle \alpha _{i}\nmid \alpha _{i+1}}Este defecto se puede corregir mediante operaciones en filas y columnas.i{\displaystyle i}yi+1{\displaystyle i+1}solamente: primero agregue la columnai+1{\displaystyle i+1}a la columnai{\displaystyle i}para obtener una entradaαi+1{\displaystyle \alpha _{i+1}}en la columna i sin alterar la entradaαi{\displaystyle \alpha _{i}}en posición(i,i){\displaystyle (i,i)}y luego aplicar una operación de fila para hacer la entrada en la posición(i,i){\displaystyle (i,i)}igual aβ=mcd(αi,αi+1){\displaystyle \beta =\gcd(\alpha _{i},\alpha _{i+1})}como en el Paso  II; finalmente proceda como en el Paso  III para diagonalizar la matriz nuevamente. Dado que la nueva entrada en la posición(i+1,i+1){\displaystyle (i+1,i+1)}es una combinación lineal del originalαi,αi+1{\displaystyle \alpha _{i},\alpha _{i+1}}, es divisible por β.

El valorδ(α1)+⋯+δ(αr){\displaystyle \delta (\alpha _{1})+\cdots +\delta (\alpha _{r})}no cambia por la operación anterior (es δ del determinante del superiorr×r{\displaystyle r\times r}submatriz), de donde esa operación disminuye (al mover los factores primos a la derecha) el valor de

∑j=1r(r−j)δ(αj).{\displaystyle \sum _{j=1}^{r}(r-j)\delta (\alpha _{j}).}

Así que 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α1∣α2∣⋯∣αr{\displaystyle \alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}}como se desee.

Dado que todas las manipulaciones de filas y columnas involucradas en el proceso son invertibles, esto demuestra que existen invertibles.metro×metro{\displaystyle m\times m}ynorte×norte{\displaystyle n\times n}-matrices S, T de modo que el producto SAT satisfaga la definición de una forma normal de Smith. En particular, esto demuestra que la forma normal de Smith existe, lo cual se asumió sin demostración en la definició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 de dicho complejo son finitamente generados . Por ejemplo, en topología , se puede utilizar para calcular la homología de un complejo simplicial finito o complejo CW sobre los enteros, ya que las aplicaciones de frontera en dicho complejo son simplemente matrices de enteros. También se puede utilizar para determinar los factores invariantes que aparecen en el teorema de estructura para módulos finitamente generados sobre un dominio ideal principal , que incluye el teorema fundamental de los grupos abelianos finitamente generados .

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 . [ 4 ]

Ejemplo

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

(244−661210416){\displaystyle {\begin{pmatrix}2&4&4\\-6&6&12\\10&4&16\end{pmatrix}}}

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

→(200−6182410−16−4)→(200018240−16−4){\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}}}
→(20002200−16−4)→(200022000156){\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}}}
→(20002000156){\displaystyle \to {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}

Entonces, la forma normal de Smith es

(20002000156){\displaystyle {\begin{pmatrix}2&0&0\\0&2&0\\0&0&156\end{pmatrix}}}

y los factores invariantes son 2, 2 y 156.

Complejidad en tiempo de ejecución

La forma normal de Smith de una matriz A de N por N se puede calcular en tiempoO(‖A‖registro⁡‖A‖norte4registro⁡norte){\displaystyle O(\|A\|\log \|A\|N^{4}\log N)}. [ 5 ] Si la matriz es dispersa , el cálculo suele ser mucho más rápido.

Semejanza

La forma normal de Smith se puede utilizar para determinar si las matrices con entradas sobre un campo común son o no compatibles.K{\displaystyle K}son similares . Específicamente, dos matrices A y B son similares si y solo si las matrices características son similares.incógnitaI−A{\displaystyle xI-A}yincógnitaI−B{\displaystyle xI-B}tienen la misma forma normal de Smith (trabajando en el PID)K[incógnita]{\displaystyle K[x]}).

Por ejemplo, con

A=[1201],Centro de enfermería especializada(incógnitaI−A)=[100(incógnita−1)2]B=[3−41−1],Centro de enfermería especializada(incógnitaI−B)=[100(incógnita−1)2]do=[1012],Centro de enfermería especializada(incógnitaI−do)=[100(incógnita−1)(incógnita−2)].{\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.

Véase también

  • Un ejemplo animado del cálculo de la forma normal de Smith .
  • NumberTheory.org
  • "SmithDecomposition" . Sitio web de Wolfram Alpha .[ 6 ]

Referencias

  1. ↑ Stanley, Richard P. (2016). "Forma normal de Smith en combinatoria" . Journal of Combinatorial Theory . Serie A. 144 : 476–495 . arXiv : 1602.00166 . doi : 10.1016/j.jcta.2016.06.013 . S2CID 14400632 . 
  2. ↑ Lazebnik, F. (1996). Sobre sistemas de ecuaciones diofánticas lineales. Mathematics Magazine, 69(4), 261-266.
  3. ↑ Smith, HJS (1861). XV. Sobre sistemas de ecuaciones lineales indeterminadas y congruencias. Philosophical transactions of the royal society of london, (151), 293-326.
  4. ↑ Maciejowski, Jan M. (1989). Diseño de retroalimentación multivariable . Wokingham, Inglaterra: Addison-Wesley. ISBN 0201182432OCLC 19456124 .​ 
  5. ↑ "Tiempo de cálculo de la forma normal de Smith en Maple" . MathOverflow . Consultado el 5 de abril de 2024 .
  6. ↑ Wolfram Research (2015). "SmithDecomposition" . Recuperado el 6 de marzo de 2025. Proporciona la descomposición en forma normal de Smith de una matriz entera m .SmithDecomposition[m]
  • 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 . S2CID 110730515 .  Reimpreso (pp. 367–409 ) en The Collected Mathematical Papers of Henry John Stephen Smith , Vol. I , editado por JWL Glaisher . Oxford: Clarendon Press (1894), xcv + 603 pp.
  • KR Matthews, Forma normal de Smith . MP274: Álgebra lineal, Apuntes de clase, Universidad de Queensland, 1991.
Obtenido de " https://en.wikipedia.org/w/index.php?title=Smith_normal_form&oldid=1342016821 "