Smith forma normal

Em matemática , a forma normal de Smith é uma forma normal que é definida para quaisquer matrizes com entradas de um anel ideal principal . A forma normal de Smith de uma matriz é uma matriz diagonal , que é obtida a partir da matriz de saída multiplicando esquerda e direita por uma matriz quadrada regular cada. As entradas nesta matriz diagonal são chamadas de divisores elementares ou fatores invariantes da matriz de saída. A forma normal de Smith foi nomeada em homenagem ao matemático inglês Henry John Stephen Smith .

definição

Se houver uma matriz sobre um anel ideal principal que não seja igual à matriz zero , então uma matriz regular e uma matriz regular existem tais que ${\ displaystyle A}$${\ displaystyle (m \ vezes n)}$${\ displaystyle R}$${\ displaystyle (m \ vezes m)}$${\ displaystyle S}$${\ displaystyle (n \ vezes n)}$${\ displaystyle T}$

${\ displaystyle S \ cdot A \ cdot T = {\ begin {pmatrix} \ alpha _ {1} & 0 & \ cdots & \ cdots & \ cdots & 0 \\ 0 & \ ddots & \ ddots &&& \ vdots \\ \ vdots & \ ddots & \ alpha _ {r} & \ ddots && \ vdots \\\ vdots && \ ddots & 0 & \ ddots & \ vdots \\\ vdots &&& \ ddots & \ ddots & 0 \\ 0 & \ cdots & \ cdots & \ cdots & 0 & 0 \ end {pmatrix}}}$

se aplica. Para os elementos da diagonal principal se destina a para aplicar. Essa representação é chamada de forma normal de Smith da matriz . As entradas são claramente definidas, exceto para multiplicação por uma unidade e são chamadas de divisores elementares ou fatores invariantes da matriz. Os divisores elementares são completamente (exceto para multiplicação por uma unidade) ${\ displaystyle \ alpha _ {i} \ mid \ alpha _ {i + 1}}$${\ displaystyle i = 1, \ ldots, r-1}$${\ displaystyle A}$${\ displaystyle \ alpha _ {i}}$

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

onde o maior divisor comum de todos - é o menor da matriz . ${\ displaystyle d_ {i} (A)}$${\ displaystyle (i \ times i)}$${\ displaystyle A}$

algoritmo

A parte difícil em encontrar a Forma Normal de Smith é encontrar duas matrizes e, portanto, o produto é uma matriz diagonal. Para tal, a matriz é sucessivamente levada à diagonal, sendo efetuada a cada etapa a remodelação elementar de linha ou coluna . Ao mesmo tempo, as matrizes e partindo de matrizes padrão de tamanho apropriado são remodeladas sucessivamente. Nesse caso, em uma linha que forma a matriz está a matriz da direita, e em uma coluna que se forma multiplicada da esquerda com uma matriz elementar correspondente. O relacionamento então se aplica às matrizes modificadas em uma etapa${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S \ cdot A \ cdot T}$${\ displaystyle A}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle A ', S', T '}$

${\ displaystyle A '= S' \ cdot A \ cdot T '}$.

Apenas as operações de linha e coluna invertíveis são realizadas, de modo que e permaneçam regulares. A forma normal de Smith é então finalmente determinada com base na forma diagonal de . A fim de trazer uma matriz para a forma normal de Smith, as seguintes etapas são realizadas especificamente. ${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle A}$${\ displaystyle t = 1, \ ldots, m}$

Etapa 1: escolher o pivô

Seja o menor índice de coluna daquelas colunas de que tenham pelo menos uma entrada diferente de zero, pelo qual a pesquisa é iniciada por às . Agora é necessário que para o elemento diagonal ${\ displaystyle j_ {t}}$${\ displaystyle A}$${\ displaystyle t> 1}$${\ displaystyle j_ {t-1} +1}$

${\ displaystyle a_ {t, j_ {t}} \ neq 0}$

se aplica. Se não for esse o caso, existe um elemento de acordo com o pré-requisito . Agora as duas linhas e são trocadas por multiplicação com uma matriz de permutação , de forma que um elemento diferente de zero apareça na diagonal da coluna atual. Esse elemento é então chamado de elemento pivô . ${\ displaystyle a_ {k, j_ {t}} \ neq 0}$${\ displaystyle t}$${\ displaystyle k}$

Etapa 2: melhorar o pivô

Se agora houver uma entrada com , então seja ${\ displaystyle a_ {k, j_ {t}}}$${\ displaystyle a_ {t, j_ {t}} \ nmid a_ {k, j_ {t}}}$

${\ displaystyle \ beta = \ operatorname {ggT} \ left (a_ {t, j_ {t}}, a_ {k, j_ {t}} \ right)}$.

O maior divisor comum de dois elementos de um anel ideal principal pode ser representado pelo lema de Bézout . Então existem elementos que ${\ displaystyle \ sigma, \ tau \ in R}$

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

se aplica. Usando uma conversão de linha, a -fold da linha agora é adicionada à -fold da linha . Satisfaça e a equação acima, então se aplica a e (essas divisões são possíveis devido à definição de ) ${\ displaystyle \ sigma}$${\ displaystyle t}$${\ displaystyle \ tau}$${\ displaystyle k}$${\ displaystyle \ sigma}$${\ displaystyle \ tau}$${\ displaystyle \ alpha = a_ {t, j_ {t}} / \ beta}$${\ displaystyle \ gamma = a_ {k, j_ {t}} / \ beta}$${\ displaystyle \ beta}$

${\ displaystyle \ sigma \ cdot \ alpha + \ tau \ cdot \ gamma = 1}$.

O Matrix

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

é, portanto, regular com o inverso

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

Ao inserir as entradas da matriz nas linhas e colunas e em uma matriz de identidade, a matriz elementar é obtida . O produto tem então a entrada no ponto (e, devido à escolha de e no ponto, a entrada zero, o que é prático, mas não essencial para o algoritmo). Esta nova entrada compartilha a entrada anterior . Esta etapa é repetida até que não haja nenhuma melhora. Denota o número de fatores primos de um elemento , então se aplica após cada etapa ${\ displaystyle L_ {0}}$${\ displaystyle t}$${\ displaystyle k}$${\ displaystyle L}$${\ displaystyle L \ cdot A}$${\ displaystyle (t, j_ {t})}$${\ displaystyle \ beta}$${\ displaystyle \ alpha}$${\ displaystyle \ gamma}$${\ displaystyle (k, j_ {t})}$${\ displaystyle \ beta}$${\ displaystyle a_ {t, j_ {t}}}$${\ displaystyle \ delta (a)}$${\ displaystyle a}$

${\ displaystyle \ delta (\ beta) <\ delta (a_ {t, j_ {t}})}$,

portanto, o processo termina após um número finito de etapas. O resultado é uma matriz com uma entrada no ponto que divide todas as entradas na coluna . ${\ displaystyle (t, j_ {t})}$${\ displaystyle j_ {t}}$

Etapa 3: eliminação de entradas

Adicionando os múltiplos correspondentes da linha , todas as entradas na coluna fora da diagonal são agora definidas como zero. Isso também pode ser alcançado pela multiplicação à esquerda com matrizes elementares apropriadas. No entanto, para trazer a matriz para uma forma diagonal completa, as entradas diferentes de zero na linha também devem ser eliminadas. Isso pode ser obtido repetindo a etapa 2 para as colunas da matriz em combinação com as multiplicações corretas. No entanto, isso pode significar que zero entradas que foram geradas em uma aplicação anterior da etapa 3 tornam-se diferentes de zero novamente. ${\ displaystyle t}$${\ displaystyle j_ {t}}$${\ displaystyle t}$

Os ideais que são formados pelos elementos na posição , entretanto, criam uma cadeia ascendente , uma vez que as entradas de uma etapa posterior sempre compartilham as entradas de uma etapa anterior. Depois de haver o noetherian , os ideais se tornam estacionários após uma determinada etapa e não mudam mais. Isso significa que, finalmente, a entrada no ponto após a aplicação da etapa 2 divide todas as entradas diferentes de zero na mesma coluna e linha. Essas entradas podem então ser eliminadas, com as entradas zero já geradas sendo retidas. Agora, apenas o bloco deve ser diagonalizado da direita abaixo . O algoritmo é continuado com esta submatriz na etapa 1. ${\ displaystyle (t, j_ {t})}$${\ displaystyle R}$ ${\ displaystyle (t, j_ {t})}$${\ displaystyle A}$${\ displaystyle (t, j_ {t})}$${\ displaystyle t + 1}$

Etapa 4: normalização

A aplicação repetida dos passos 1 a 3 acabará levando a uma matriz na qual apenas as entradas para com não são zero. As colunas zero desta matriz agora são deslocadas para a direita, de modo que as entradas diferentes de zero estejam exatamente nas posições para . Essas entradas agora são indicadas por. ${\ displaystyle (m \ vezes n)}$${\ displaystyle (l, j_ {l})}$${\ displaystyle j_ {1} <\ ldots <j_ {r}}$${\ displaystyle r \ leq \ min (m, n)}$${\ displaystyle (i, i)}$${\ displaystyle i = 1, \ ldots, r}$${\ displaystyle \ alpha _ {i}}$

No entanto, o requisito de divisibilidade da forma normal de Smith para os elementos diagonais pode ainda não ser atendido. Se isso se aplica a um índice , isso pode ser remediado por meio de transformações de linha e coluna como segue. Primeiro, a coluna é adicionada à coluna para que uma entrada seja criada na coluna sem que a entrada diagonal seja alterada na posição . Agora, como na etapa 2, com uma transformação de linha, a entrada no ponto torna-se a mesma ${\ displaystyle \ alpha _ {i} \ nmid \ alpha _ {i + 1}}$${\ displaystyle i}$${\ displaystyle i + 1}$${\ displaystyle i}$${\ displaystyle \ alpha _ {i + 1}}$${\ displaystyle i}$${\ displaystyle \ alpha _ {i}}$${\ displaystyle (i, i)}$${\ displaystyle (i, i)}$

${\ displaystyle \ beta = \ operatorname {ggT} (\ alpha _ {i}, \ alpha _ {i + 1})}$

conjunto. Finalmente, como no passo 3, a matriz é diagonalizada novamente. Como a nova entrada é uma combinação linear das entradas originais e , deve ser divisível por . Esta operação não altera o valor (corresponde ao do determinante da submatriz superior ), mas diminui o valor de ${\ displaystyle (i + 1, i + 1)}$${\ displaystyle \ alpha _ {i}}$${\ displaystyle \ alpha _ {i + 1}}$${\ displaystyle \ beta}$${\ displaystyle \ delta (\ alpha _ {1}) + \ cdots + \ delta (\ alpha _ {r})}$${\ displaystyle \ delta}$${\ displaystyle (r \ times r)}$

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

deslocando os fatores primários para a direita. Portanto, após um número finito de aplicações, nenhuma outra operação é possível, o que significa que o resultado desejado foi alcançado. Visto que todas as transformações de linha e coluna neste processo são invertíveis, matrizes invertíveis devem existir de forma que produzam a forma normal de Smith. Em particular, isso significa que a forma normal de Smith sempre existe, o que foi assumido na definição sem evidências. ${\ displaystyle \ alpha _ {1} \ mid \ alpha _ {2} \ mid \ cdots \ mid \ alpha _ {r}}$${\ displaystyle S, T}$${\ displaystyle S \ cdot A \ cdot T}$

exemplo

Por exemplo, a forma Smith-Normal da matriz

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

calculado. As seguintes matrizes são as etapas intermediárias do algoritmo de Smith aplicado a esta matriz:

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

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

A última matriz representa então a forma normal de Smith de . Os fatores invariantes de são , portanto , e . ${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle 2}$${\ displaystyle 6}$${\ displaystyle 12}$

usar

A forma normal de Smith é útil para calcular a homologia de um complexo de cadeia quando seus módulos são gerados finitamente. Na topologia , a forma normal de Smith pode ser usada, por exemplo, para calcular a homologia de um complexo simplicial ou um complexo celular sobre os números inteiros, uma vez que os operadores de fronteira de tais complexos são representados por matrizes inteiras. Ele também pode ser usado para provar o teorema da estrutura para módulos gerados finitamente sobre um anel ideal principal .

A forma normal de Smith também pode ser usada para determinar se duas matrizes sobre o mesmo corpo são semelhantes entre si . Duas matrizes e são de fato semelhantes entre si, se e somente se suas matrizes características e têm a mesma forma normal Smith. Por exemplo, o seguinte se aplica às seguintes matrizes: ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle xI-A}$${\ displaystyle xI-B}$

${\ displaystyle {\ begin {align} A & {} = {\ begin {pmatrix} 1 & 2 \\ 0 & 1 \ end {pmatrix}}, && {\ mbox {SNF}} (xI-A) = { \ begin {pmatrix} 1 & 0 \\ 0 & (x-1) ^ {2} \ end {pmatrix}} \\ B & {} = {\ begin {pmatrix} 3 & -4 \\ 1 & -1 \ end {pmatrix}}, && {\ mbox {SNF}} (xI-B) = {\ begin {pmatrix} 1 & 0 \\ 0 & (x-1) ^ {2} \ end {pmatrix}} \ \ C & {} = {\ begin {pmatrix} 1 & 0 \\ 1 & 2 \ end {pmatrix}}, && {\ mbox {SNF}} (xI-C) = {\ begin {pmatrix} 1 & 0 \\ 0 & (x-1) (x-2) \ end {pmatriz}} \ end {alinhado}}}$

Portanto, e são semelhantes entre si porque as formas Smith-Normal de suas matrizes características são as mesmas, mas não são semelhantes porque as matrizes características são diferentes. ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$

Veja também

• Forma normal de Frobenius
• Jordan forma normal
• Decomposição de valor singular

literatura

• Henry J. Stephen Smith : Em sistemas de equações lineares indeterminadas e congruências . In: Phil. Trans. R. Soc. Lond. . 151, No. 1, 1861, pp. 293-326. doi : 10.1098 / rstl.1861.0016 . Reimpresso. JWL Glaisher (Ed.): The Collected Mathematical Papers of Henry John Stephen Smith , Vol. I. Clarendon Press, Oxford 1894, pp. 367-409, Textarchiv - Internet Archive
• KR Matthews: Forma normal de Smith . (PDF) In: MP274: Linear Algebra , Lecture Notes, University of Queensland, 1991.

Links da web

• Forma normal de Smith . In: PlanetMath . (Inglês)
• Exemplo de forma normal de Smith . In: PlanetMath . (Inglês)