Forma normal de Smith

Em matemática, a forma normal de Smith (às vezes abreviada como SNF) é uma forma normal que pode ser definida para qualquer matriz (não necessariamente quadrada) com entradas em um domínio de ideais principais (DIP). A forma normal de Smith de uma matriz é diagonal e pode ser obtida da matriz original multiplicando à esquerda e à direita por matrizes invertíveis quadradas. Em particular, os inteiros são um DIP, então pode-se sempre calcular a forma normal de Smith de uma matriz de inteiros. A forma normal de Smith é muito útil para trabalhar com módulos finitamente gerados sobre um DIP e, em particular, para deduzir a estrutura de um quociente de um módulo livre. Recebe o nome do matemático irlandês Henry John Stephen Smith.

Definição

Seja $A$ uma matriz $m\times n$ não nula sobre um domínio de ideais principais $R$ . Existem matrizes invertíveis $m\times m$ e $n\times n$ $S,T$ (com entradas em $R$ , e $\det(S),\det(T)$ unidades em $R$ ) tais que o produto $SAT$ é

${\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}}.$

e os elementos diagonais $\alpha _{i}$ satisfazem $\alpha _{i}\mid \alpha _{i+1}$ para todo $1\leq i<r$ . Esta é a forma normal de Smith da matriz $A$ . Os elementos $\alpha _{i}$ são únicos a menos de multiplicação por uma unidade e são chamados de divisores elementares, invariantes ou fatores invariantes. Eles podem ser calculados (a menos de multiplicação por uma unidade) como

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

onde $d_{i}(A)$ (chamado i-ésimo divisor determinantal) é igual ao máximo divisor comum dos determinantes de todos os menores $i\times i$ da matriz $A$ e $d_{0}(A):=1$ .

Exemplo : Para uma matriz $2\times 2$ , ${\rm {SNF}}{a~~b \choose c~~d}={\rm {diag}}(d_{1},d_{2}/d_{1})$ com $d_{1}=\gcd(a,b,c,d)$ e $d_{2}=|ad-bc|$ .

Algoritmo

O primeiro objetivo é encontrar matrizes quadradas invertíveis $S$ e $T$ tais que o produto $SAT$ seja diagonal. Esta é a parte mais difícil do algoritmo. Uma vez alcançada a diagonalidade, torna-se relativamente fácil colocar a matriz na forma normal de Smith. Colocando de forma mais abstrata, o objetivo é mostrar que, pensando em $A$ como um mapa de $R^{n}$ (o $R$ -módulo livre de posto $n$ ) para $R^{m}$ (o $R$ -módulo livre de posto $m$ ), existem isomorfismos $S:R^{m}\to R^{m}$ e $T:R^{n}\to R^{n}$ tais que $S\cdot A\cdot T$ tem a forma simples de uma matriz diagonal. As matrizes $S$ e $T$ podem ser encontradas começando com matrizes identidade do tamanho apropriado e modificando $S$ cada vez que uma operação de linha é realizada sobre $A$ no algoritmo pela operação de coluna correspondente (por exemplo, se a linha $i$ é somada à linha $j$ de $A$ , então a coluna $j$ deve ser subtraída da coluna $i$ de $S$ para manter o produto invariante), e similarmente modificando $T$ para cada operação de coluna realizada. Como as operações de linha são multiplicações à esquerda e as operações de coluna são multiplicações à direita, isso preserva o invariante $A'=S'\cdot A\cdot T'$ onde $A',S',T'$ denotam os valores atuais e $A$ denota a matriz original; eventualmente as matrizes neste invariante se tornam diagonais. Apenas operações de linha e coluna invertíveis são realizadas, o que garante que $S$ e $T$ permaneçam matrizes invertíveis.

Para $a\in R\setminus \{0\}$ , escreva $\delta (a)$ para o número de fatores primos de $a$ (estes existem e são únicos, pois qualquer DIP é também um domínio de fatoração única). Em particular, $R$ é também um domínio de Bézout, então é um domínio de MDC e o mdc de quaisquer dois elementos $a,b\in R$ satisfaz uma identidade de Bézout $\gcd(a,b)=ac+bd$ para alguns $c,d\in R$ .

Para colocar uma matriz na forma normal de Smith, pode-se aplicar repetidamente o seguinte, onde o índice $t$ varia de 1 a $m$ .

Passo I: Escolhendo um pivô

Escolha $j_{t}$ como o menor índice de coluna de $A$ com uma entrada não nula, começando a busca no índice de coluna $j_{t-1}+1$ se $t>1$ .

Desejamos ter $a_{t,j_{t}}\neq 0$ ; se este for o caso, este passo está completo; caso contrário, há por hipótese algum $k$ com $a_{k,j_{t}}\neq 0$ , e podemos trocar as linhas $t$ e $k$ , obtendo assim $a_{t,j_{t}}\neq 0$ .

Nosso pivô escolhido está agora na posição $(t,j_{t})$ .

Passo II: Melhorando o pivô

Se há uma entrada na posição (k,j_t) tal que $a_{t,j_{t}}\nmid a_{k,j_{t}}$ , então, fazendo $\beta =\gcd \left(a_{t,j_{t}},a_{k,j_{t}}\right)$ , sabemos pela propriedade de Bézout que existem σ, τ em R tais que

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

Por multiplicação à esquerda com uma matriz invertível apropriada L, pode-se conseguir que a linha t do produto matricial seja a soma de σ vezes a linha t original e τ vezes a linha k original, que a linha k do produto seja outra combinação linear dessas linhas originais e que todas as outras linhas permaneçam inalteradas. Explicitamente, se σ e τ satisfazem a equação acima, então para $\alpha =a_{t,j_{t}}/\beta$ e $\gamma =a_{k,j_{t}}/\beta$ (cujas divisões são possíveis pela definição de β) tem-se

\sigma \cdot \alpha +\tau \cdot \gamma =1,

de modo que a matriz

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

é invertível, com inversa

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

Agora L pode ser obtida encaixando $L_{0}$ nas linhas e colunas t e k da matriz identidade. Por construção, a matriz obtida após multiplicação à esquerda por L tem entrada β na posição (t,j_t) (e, devido à nossa escolha de α e γ, também tem uma entrada 0 na posição (k,j_t), o que é útil embora não essencial para o algoritmo). Esta nova entrada β divide a entrada $a_{t,j_{t}}$ que estava lá antes, e assim em particular $\delta (\beta )<\delta (a_{t,j_{t}})$ ; portanto, repetir estes passos deve eventualmente terminar. Termina-se com uma matriz tendo uma entrada na posição (t,j_t) que divide todas as entradas na coluna j_t.

Passo III: Eliminando entradas

Finalmente, somando múltiplos apropriados da linha t, pode-se conseguir que todas as entradas na coluna j_t, exceto a da posição (t,j_t), sejam zero. Isso pode ser alcançado por multiplicação à esquerda com uma matriz apropriada. No entanto, para tornar a matriz totalmente diagonal, precisamos também eliminar entradas não nulas na linha da posição (t,j_t). Isso pode ser alcançado repetindo os passos do Passo II para colunas em vez de linhas, e usando multiplicação à direita pela transposta da matriz L obtida. Em geral, isso fará com que as entradas zero da aplicação anterior do Passo III se tornem não nulas novamente.

No entanto, observe que cada aplicação do Passo II para linhas ou colunas deve continuar a reduzir o valor de $\delta (a_{t,j_{t}})$ , e assim o processo deve eventualmente parar após algum número de iterações, levando a uma matriz onde a entrada na posição (t,j_t) é a única entrada não nula tanto em sua linha quanto em sua coluna.

Neste ponto, apenas o bloco de A abaixo e à direita de (t,j_t) precisa ser diagonalizado, e conceitualmente o algoritmo pode ser aplicado recursivamente, tratando este bloco como uma matriz separada. Em outras palavras, podemos incrementar t em um e voltar ao Passo I.

Passo final

Aplicando os passos descritos acima às colunas não nulas restantes da matriz resultante (se houver), obtemos uma matriz $m\times n$ com índices de coluna $j_{1}<\ldots <j_{r}$ onde $r\leq \min(m,n)$ . As entradas da matriz $(l,j_{l})$ são não nulas, e todas as outras entradas são zero.

Agora podemos mover as colunas nulas desta matriz para a direita, de modo que as entradas não nulas fiquem nas posições $(i,i)$ para $1\leq i\leq r$ . Abreviadamente, defina $\alpha _{i}$ como o elemento na posição $(i,i)$ .

A condição de divisibilidade das entradas diagonais pode não ser satisfeita. Para qualquer índice $i<r$ para o qual $\alpha _{i}\nmid \alpha _{i+1}$ , pode-se corrigir essa deficiência por operações apenas nas linhas e colunas $i$ e $i+1$ : primeiro some a coluna $i+1$ à coluna $i$ para obter uma entrada $\alpha _{i+1}$ na coluna i sem perturbar a entrada $\alpha _{i}$ na posição $(i,i)$ , e então aplique uma operação de linha para tornar a entrada na posição $(i,i)$ igual a $\beta =\gcd(\alpha _{i},\alpha _{i+1})$ como no Passo II; finalmente proceda como no Passo III para tornar a matriz diagonal novamente. Como a nova entrada na posição $(i+1,i+1)$ é uma combinação linear dos $\alpha _{i},\alpha _{i+1}$ originais, ela é divisível por β.

O valor $\delta (\alpha _{1})+\cdots +\delta (\alpha _{r})$ não muda pela operação acima (é δ do determinante da submatriz superior $r\times r$ ), de modo que essa operação diminui (movendo fatores primos para a direita) o valor de

\sum _{j=1}^{r}(r-j)\delta (\alpha _{j}).

Assim, após um número finito de aplicações desta operação, nenhuma aplicação adicional é possível, o que significa que obtivemos $\alpha _{1}\mid \alpha _{2}\mid \cdots \mid \alpha _{r}$ como desejado.

Como todas as manipulações de linha e coluna envolvidas no processo são invertíveis, isso mostra que existem matrizes invertíveis $m\times m$ e $n\times n$ S, T tais que o produto S A T satisfaz a definição de uma forma normal de Smith. Em particular, isso mostra que a forma normal de Smith existe, o que foi assumido sem prova na definição.

Aplicações

A forma normal de Smith é útil para calcular a homologia de um complexo de cadeias quando os módulos de cadeia do complexo de cadeias são finitamente gerados. Por exemplo, em topologia, pode ser usada para calcular a homologia de um complexo simplicial finito ou complexo CW sobre os inteiros, porque os mapas de fronteira em tal complexo são apenas matrizes de inteiros. Também pode ser usada para determinar os fatores invariantes que ocorrem no teorema da estrutura para módulos finitamente gerados sobre um domínio de ideais principais, que inclui o teorema fundamental dos grupos abelianos finitamente gerados.

A forma normal de Smith também é usada em teoria de controle para calcular zeros de transmissão e bloqueio de uma matriz de função de transferência.

Exemplo

Como exemplo, encontraremos a forma normal de Smith da seguinte matriz sobre os inteiros.

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

As seguintes matrizes são os passos intermediários à medida que o algoritmo é aplicado à matriz acima.

\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}}

\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}}

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

Portanto, a forma normal de Smith é

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

e os fatores invariantes são 2, 2 e 156.

Complexidade de tempo de execução

A forma normal de Smith de uma matriz N-por-N A pode ser calculada em tempo $O(\|A\|\log \|A\|N^{4}\log N)$ . Se a matriz for esparsa, o cálculo é tipicamente muito mais rápido.

Similaridade

A forma normal de Smith pode ser usada para determinar se matrizes com entradas sobre um corpo comum $K$ são semelhantes. Especificamente, duas matrizes A e B são semelhantes se e somente se as matrizes características $xI-A$ e $xI-B$ têm a mesma forma normal de Smith (trabalhando no DIP $K[x]$ ).

Por exemplo, com

{\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 e B são semelhantes porque as formas normais de Smith de suas matrizes características coincidem, mas não são semelhantes a C porque as formas normais de Smith das matrizes características não coincidem.

Ver também

Forma canônica
Equação diofantina
Divisores elementares
Fatores invariantes
Teorema da estrutura para módulos finitamente gerados sobre um domínio de ideais principais
Forma normal de Frobenius (também chamada de forma canônica racional)
Forma normal de Hermite
Decomposição em valores singulares

Referências

↑ Stanley, Richard P. (2016). «Smith normal form in combinatorics». Journal of Combinatorial Theory. Series A. 144: 476–495. arXiv:1602.00166. doi:10.1016/j.jcta.2016.06.013
↑ Lazebnik, F. (1996). On systems of linear diophantine equations. Mathematics Magazine, 69(4), 261-266.
↑ Smith, H. J. S. (1861). Xv. on systems of linear indeterminate equations and congruences. Philosophical transactions of the royal society of london, (151), 293-326.
↑ Maciejowski, Jan M. (1989). Multivariable feedback design. Wokingham, England: Addison-Wesley. ISBN 0201182432. OCLC 19456124
↑ «Computation time of Smith normal form in Maple». MathOverflow (em inglês). Consultado em 5 de abril de 2024

Bibliografia

Smith, Henry J. Stephen (1861). «On systems of linear indeterminate equations and congruences». Phil. Trans. R. Soc. Lond. 151 (1): 293–326. JSTOR 108738. doi:10.1098/rstl.1861.0016 Reimpresso (pp. 367–409) em The Collected Mathematical Papers of Henry John Stephen Smith, Vol. I, editado por J. W. L. Glaisher. Oxford: Clarendon Press (1894), xcv+603 pp.
K. R. Matthews, Smith normal form. MP274: Linear Algebra, Lecture Notes, University of Queensland, 1991.

Ligações externas

[1] Stanley, Richard P. (2016). «Smith normal form in combinatorics». Journal of Combinatorial Theory. Series A. 144: 476–495. arXiv:1602.00166. doi:10.1016/j.jcta.2016.06.013

[2] Lazebnik, F. (1996). On systems of linear diophantine equations. Mathematics Magazine, 69(4), 261-266.

[3] Smith, H. J. S. (1861). Xv. on systems of linear indeterminate equations and congruences. Philosophical transactions of the royal society of london, (151), 293-326.

[4] Maciejowski, Jan M. (1989). Multivariable feedback design. Wokingham, England: Addison-Wesley. ISBN 0201182432. OCLC 19456124

[5] «Computation time of Smith normal form in Maple». MathOverflow (em inglês). Consultado em 5 de abril de 2024