Centro de Informática · UFPE Álgebra Vetorial e LinearCIN0138 · 2026.2
Google Classroom

Aula 5 · 08/09 (ter) · Módulo 1 · laboratório

Propriedades elementares das matrizes II

Nesta aula você estuda as matrizes elementares, a fatoração LU, com e sem trocas de linhas, a matriz inversa e o método de Gauss-Jordan, a transposta, as matrizes simétricas e as matrizes de permutação. Quando a eliminação não precisa trocar linhas, a fatoração LU escreve uma matriz quadrada A como o produto de uma matriz triangular inferior L por uma matriz triangular superior U: A = LU. Na bancada, você escreve cada passo da eliminação como uma multiplicação por uma matriz elementar, monta L com os multiplicadores, calcula inversas com frações exatas, confere as regras (AB)T = BTAT e (AB)−1 = B−1A−1 para o produto de duas matrizes A e B e reordena as linhas e as colunas de uma tabela com permutações.

Eliminação com matrizes elementares

Cada passo da eliminação é uma multiplicação à esquerda: a matriz elementar do passo vezes a matriz antes do passo dá a matriz depois dele. A linha que muda aparece destacada, e o pivô, circulado. Os botões abaixo avançam e recuam os passos.

As linhas da matriz em ℝ3

Este quadro desenha as três linhas da matriz atual da eliminação como vetores de ℝ3 que partem da origem. Arraste o fundo da figura para girá-la.

Os fatores L e U

A matriz L começa igual à identidade, e cada multiplicador ℓij usado na eliminação é escrito na posição (i, j) de L. Ao lado está a matriz atual da eliminação, que no fim é a matriz triangular superior U. Abaixo, o produto das duas é comparado com a matriz A do painel. Quando há trocas de linhas, elas ficam acumuladas numa matriz de permutação P, e a comparação é com PA.

Por que guardar L, e não o produto E = E32E31E21?

Exemplos

A matriz A

As entradas podem ser inteiros, frações como 3/2 ou decimais como 0,5.

Opções da eliminação

As matrizes B e R

Escolha da permutação P

Cada opção define a matriz de permutação P pela ordem das linhas da tabela T no produto PT: com “2 3 1”, a primeira linha de PT é a linha 2 de T, a segunda é a linha 3, e a terceira é a linha 1.

Em dimensão n

Fatoração LU e permutações com n grande

Para uma matriz A de tamanho n × n, escrever A como o produto de uma matriz triangular inferior L por uma matriz triangular superior U, A = LU, custa cerca de n3/3 operações, cada uma formada por uma multiplicação e uma subtração. Depois, cada lado direito b de um sistema com a matriz A custa cerca de n2 operações, nas substituições progressiva e regressiva. Quando A tem muitas entradas nulas, a eliminação pode tornar não nulas algumas posições em que A tem entrada nula. Essas posições formam o preenchimento, e o número delas depende da ordem das linhas e das colunas. Por fim, você multiplica um sinal x ∈ ℝn, isto é, um vetor de n valores, várias vezes seguidas por uma matriz de permutação P e descobre depois de quantas multiplicações o sinal volta a ser x.

L e U de uma matriz n × n

A
L
matriz atual (no fim, U)

Custo de muitos lados direitos

O sinal Pkx

Cada clique em Aplicar P multiplica o sinal pela matriz de permutação P. Depois de k multiplicações, o sinal original x passa a ser Pkx, mostrado com uma barra por posição. Cada barra tem a cor do ciclo da sua posição, desenhado no quadro Os ciclos de P, e as posições fixas ficam em cinza. O contorno mostra o sinal original x.

Os ciclos de P

Multiplicar o sinal por P leva o valor de cada posição para outra posição ou o mantém no lugar. Um ciclo de P é uma sequência de posições em que P leva o valor de cada posição para a seguinte e o valor da última para a primeira. Cada anel do quadro é um ciclo de P, com as posições numeradas quando há espaço. Os círculos coloridos são os valores do sinal, e cada multiplicação por P leva cada valor à posição seguinte do seu ciclo, no sentido das setas.

A matriz A e a eliminação

Custo dos lados direitos

Permutação P e sinal x

Conceitos da aula

Fatoração LU, inversa, transposta e permutações

Uma guia por conceito, cada um com a definição, um exemplo resolvido e o lugar da bancada em que ele aparece. A notação é a do livro-texto (seções 1.5 e 1.6).

Cada operação elementar sobre linhas pode ser feita por uma multiplicação de matrizes: basta multiplicar, à esquerda, pela matriz obtida da identidade com a mesma operação. Assim, a eliminação de Gauss passa a ser uma sequência de produtos de matrizes.

Matriz elementar

Definição

Uma matriz n × n é uma matriz elementar se ela é obtida da identidade I por uma única operação elementar sobre linhas. As usadas nesta aula são:

  • para i ≠ j e um escalar ℓ, a matriz Eij, obtida da identidade subtraindo da linha i o produto de ℓ pela linha j: ela é a identidade com −ℓ na posição (i, j);
  • para i ≠ j, a matriz Pij, obtida da identidade trocando as linhas i e j;
  • para um escalar μ ≠ 0, a matriz obtida da identidade multiplicando a linha i por μ, que é a identidade com μ na posição (i, i); ela é usada no método de Gauss-Jordan.

Teorema

Seja A uma matriz com n linhas, e considere uma matriz elementar n × n, obtida de I por uma operação elementar sobre linhas. O produto dessa matriz elementar por A, nessa ordem, é a matriz obtida de A pela mesma operação. Toda matriz elementar é invertível, e a sua inversa é a matriz elementar da operação que desfaz a primeira: Eij−1 é a identidade com +ℓ na posição (i, j), Pij−1 = Pij, e a inversa da matriz que multiplica a linha i por μ é a matriz que multiplica a linha i por 1/μ.

O teorema vale porque cada linha do produto de uma matriz por A é a combinação linear das linhas de A cujos coeficientes são as entradas da linha correspondente dessa matriz. Na linha i de Eij, essas entradas são 1 na posição i e −ℓ na posição j, e as outras linhas de Eij são linhas da identidade. Por isso, a linha i de EijA é a linha i de A menos o produto de ℓ pela linha j de A, e as outras linhas não mudam.

Na eliminação, o escalar ℓ de Eij é o multiplicador ℓij: a entrada a eliminar dividida pelo pivô. Atenção ao sinal: o multiplicador é ℓij, mas a entrada (i, j) de Eij é −ℓij, porque a operação subtrai.

Um exemplo 3 × 3

Exemplo

A matriz do exemplo do livro é A = 2114−60−272. A primeira coluna tem o pivô 2 e, abaixo dele, a entrada 4. O multiplicador é ℓ21 = 4/2 = 2. A matriz elementar que subtrai da linha 2 o produto de 2 pela linha 1 e a sua inversa são

E21 = 100−210001,

E21−1 = 100210001.

No produto E21A, só a linha 2 muda:

(4, −6, 0) − 2·(2, 1, 1) = (0, −8, −2).

A inversa E21−1 soma à linha 2 o produto de 2 pela linha 1, o que desfaz a subtração: E21−1E21 = I, e por isso E21−1(E21A) = A.

Na bancada: no modo A = LU, o quadro Eliminação com matrizes elementares mostra, em cada passo, o produto da matriz elementar pela matriz antes do passo. No painel Opções da eliminação, ligue Eu preencho as matrizes elementares para digitar você mesmo a entrada fora da diagonal de cada matriz Eij. No modo Inversa, o exemplo Matriz elementar põe no painel A matriz A a matriz E21 deste exemplo, e o quadro Gauss-Jordan em [A | I] calcula a inversa dela.

Quando a eliminação de uma matriz quadrada A não precisa trocar linhas, desfazer os passos na ordem inversa escreve A como o produto de uma matriz triangular inferior L, que tem os multiplicadores abaixo da diagonal, por uma matriz triangular superior U, que é o resultado da eliminação.

A fatoração A = LU

Teorema

Seja A uma matriz n × n cuja eliminação de Gauss chega a uma matriz triangular superior U sem trocas de linhas. Seja L a matriz n × n triangular inferior que tem 1 em cada entrada da diagonal e, em cada entrada (i, j) com i > j, o multiplicador ℓij usado para zerar a posição (i, j), ou 0, se a eliminação encontrou essa posição já nula. Então A = LU. Quando as entradas da diagonal de U são todas não nulas, elas são os pivôs.

Para n = 3, a eliminação multiplica A, à esquerda, pelas matrizes elementares E21, E31 e E32, nessa ordem, e chega a U: E32E31E21A = U. Multiplicando os dois lados, à esquerda, por E32−1, depois por E31−1 e depois por E21−1, obtemos

A = E21−1E31−1E32−1U = LU.

Nesse produto, a entrada (i, j), para i > j, é exatamente o multiplicador ℓij. Para ver isso, calcule o produto aplicando à identidade as operações das inversas, da direita para a esquerda. Primeiro, E32−1 soma à linha 3 o produto de ℓ32 pela linha 2. Depois, E31−1 soma à linha 3 o produto de ℓ31 pela linha 1. Por fim, E21−1 soma à linha 2 o produto de ℓ21 pela linha 1. As linhas somadas, a linha 2 e a linha 1, ainda são linhas da identidade quando são usadas, e por isso cada multiplicador entra sozinho na sua posição. No produto E = E32E31E21, a ordem é a contrária: E32 subtrai da linha 3 o produto de ℓ32 pela linha 2 depois que E21 já mudou a linha 2. Por isso, a entrada (3, 1) de E é ℓ32ℓ21 − ℓ31, que envolve dois multiplicadores.

A igualdade A = LU também se lê linha por linha. Quando a linha j é usada como linha do pivô, ela já é a linha j de U. Por isso, a eliminação obtém a linha i de U subtraindo da linha i de A, para cada j < i, o produto de ℓij pela linha j de U. Logo, a linha i de A é a linha i de U somada a essas mesmas parcelas, e essa soma é a linha i de LU.

Um exemplo e o custo

Exemplo

Para a matriz A = 2114−60−272 do exemplo do livro, os multiplicadores são ℓ21 = 2, ℓ31 = −1 e ℓ32 = −1, e A = LU com

L = 100210−1−11,

U = 2110−8−2001.

Por exemplo, a linha 2 de A é 2 vezes a linha 1 de U mais a linha 2 de U:

2·(2, 1, 1) + (0, −8, −2) = (4, −6, 0).

Com A = LU, o sistema Ax = b se resolve em duas etapas. Primeiro, a substituição progressiva encontra, de cima para baixo, o vetor c tal que Lc = b. Depois, a substituição regressiva encontra, de baixo para cima, o vetor x tal que Ux = c. Esse x é a solução, pois Ax = L(Ux) = Lc = b. Para n grande, a fatoração custa cerca de n3/3 operações, cada uma formada por uma multiplicação e uma subtração, e as duas substituições custam cerca de n2 operações. Por isso, quando há muitos lados direitos b com a mesma matriz A, vale a pena fatorar A uma vez e fazer só as substituições para cada b.

Na bancada: no modo A = LU, escolha o Exemplo do livro e avance os passos do quadro Eliminação com matrizes elementares: no quadro Os fatores L e U, cada multiplicador é escrito em L, e a conferência mostra que L vezes a matriz atual é igual a A. Ligue Eu monto a matriz L, no painel Opções da eliminação, para digitar os multiplicadores. No fim desse quadro, abra a pergunta Por que guardar L, e não o produto E = E32E31E21? para comparar as duas matrizes. O custo para n grande está no quadro Custo de muitos lados direitos, na parte Em dimensão n.

Trocas de linhas: PA = LU

Teorema

Se A é uma matriz n × n invertível, existe uma matriz de permutação P tal que a eliminação de PA não precisa de trocas de linhas. Então PA = LU, com L e U como acima.

Quando aparece um zero na posição do pivô, a eliminação troca a linha do pivô por uma linha de baixo que tenha entrada não nula nessa coluna. Fazendo essas mesmas trocas antes de começar, isto é, multiplicando A, à esquerda, pela matriz de permutação P que as acumula, obtemos uma matriz PA cuja eliminação não precisa de trocas. A matriz P pode não ser única: no exemplo abaixo, a troca das linhas 1 e 3 também funciona.

Exemplo

Em A = 121243374, depois de zerar a primeira coluna, a linha 2 fica (0, 0, 1), e a linha 3, (0, 1, 1): há um zero na posição (2, 2), a do pivô. Trocando antes as linhas 2 e 3, com a matriz de permutação P = P23, a eliminação não precisa de trocas, e PA = LU com

L = 100310201,

U = 121011001.

Trocar duas linhas de A, junto com as entradas correspondentes do lado direito b, é trocar a ordem de duas equações de Ax = b, o que não muda as soluções.

Na bancada: no modo A = LU, o exemplo Pivô nulo mostra a troca de linhas durante a eliminação. No painel Opções da eliminação, o controle Troca de linhas antes da eliminação multiplica A, à esquerda, por uma matriz de permutação P0 antes de começar. Com uma boa escolha, a eliminação de P0A não precisa de trocas.

A inversa de uma matriz quadrada A, quando existe, se escreve A−1 e desfaz a multiplicação por A: se y = Ax, então x = A−1y. Nem toda matriz quadrada tem inversa.

Inversa de uma matriz

Definição

Uma matriz quadrada A, de tamanho n × n, é invertível se existe uma matriz B, também n × n, tal que AB = BA = I. Essa matriz B é a inversa de A e é denotada por A−1. Uma matriz quadrada que não é invertível é chamada de singular.

A inversa, quando existe, é única: se BA = I e AC = I, então B = B(AC) = (BA)C = C.

Teorema

Sejam A e B matrizes n × n invertíveis. Então:

  1. A−1 é invertível, e (A−1)−1 = A;
  2. AB é invertível, e (AB)−1 = B−1A−1;
  3. para todo b ∈ ℝn, o sistema Ax = b tem uma única solução, x = A−1b.

O item 1 vale porque as igualdades AA−1 = A−1A = I dizem também que A é a inversa de A−1. No item 2, a ordem se inverte porque, para desfazer a multiplicação por B seguida da multiplicação por A, é preciso desfazer primeiro a última: (AB)(B−1A−1) = A(BB−1)A−1 = AA−1 = I, e da mesma forma (B−1A−1)(AB) = I. No item 3, A−1b é solução, pois A(A−1b) = b, e é a única, pois Ax = b implica x = A−1Ax = A−1b.

A inversa de uma matriz 2 × 2

Teorema

A matriz A = abcd é invertível se, e somente se, ad − bc ≠ 0. Nesse caso,

A−1 = (1/(ad − bc))·d−b−ca.

Por quê: abcdd−b−ca = (ad − bc)I, e o mesmo vale com os fatores na outra ordem. Se ad − bc ≠ 0, basta dividir as duas igualdades por ad − bc. Se ad − bc = 0, o produto acima é a matriz nula. Se A tivesse inversa, multiplicar esse produto, à esquerda, por A−1 mostraria que a segunda matriz é nula, isto é, que a = b = c = d = 0. Então A seria a matriz nula, que não é invertível, uma contradição. O número ad − bc é o determinante de A. As Aulas 14 e 15 estudam o determinante de matrizes de qualquer tamanho.

Exemplo

Para A = 1234, temos ad − bc = 1·4 − 2·3 = −2 ≠ 0, e

A−1 = −(1/2)·4−2−31

= −213/2−1/2.

Confira: a primeira linha de AA−1 é (1·(−2) + 2·(3/2), 1·1 + 2·(−1/2)) = (1, 0). Já 1224 tem ad − bc = 4 − 4 = 0 e não é invertível: a segunda linha é o dobro da primeira.

Na bancada: as matrizes da bancada são 3 × 3, mas uma matriz 3 × 3 com uma matriz 2 × 2 no canto superior esquerdo permite conferir a fórmula. No modo Inversa, digite no painel A matriz A a matriz 120340001 e avance até o fim do quadro Gauss-Jordan em [A | I]: o bloco 2 × 2 do canto superior esquerdo da inversa é a inversa de 1234 dada pela fórmula. No quadro Conferência de uma inversa, digite uma matriz N e veja se o produto AN é a identidade I. No modo Transposta, com a matriz B do painel As matrizes B e R, o quadro Transposta e inversa de um produto compara (AB)−1 com B−1A−1 e com A−1B−1.

O método de Gauss-Jordan calcula a inversa de uma matriz quadrada A com operações elementares sobre linhas, aplicadas à matriz aumentada [A | I], que tem A à esquerda e a identidade I à direita.

O método

Definição

Seja A uma matriz n × n. O método de Gauss-Jordan começa com a matriz aumentada [A | I] e trata as colunas da metade esquerda uma de cada vez, da primeira à última. Em cada coluna, a posição do pivô fica na primeira linha que ainda não tem pivô, e o método aplica a [A | I] as operações elementares sobre linhas abaixo.

  1. Se a posição do pivô tem um zero, o método troca essa linha com uma linha de baixo que tenha entrada não nula na coluna. Se não há nenhuma, a coluna fica sem pivô, e o método passa à coluna seguinte.
  2. O método divide a linha do pivô pelo pivô, que passa a ser 1.
  3. O método subtrai de cada uma das outras linhas, acima e abaixo do pivô, o múltiplo da linha do pivô que zera a entrada dessa coluna.

Teorema

Ao fim do método de Gauss-Jordan:

  1. se a metade esquerda chega a I, a metade direita é A−1, isto é, [A | I] se transforma em [I | A−1];
  2. se alguma coluna fica sem pivô, A é singular.

Por que funciona. Cada operação do método é a multiplicação, à esquerda, por uma matriz elementar. Seja E o produto dessas matrizes elementares, com a do último passo à esquerda. Ao fim do método, a metade esquerda é EA, e a metade direita, que começou como I, é EI = E. Se a metade esquerda chega a I, então EA = I. Como E é um produto de matrizes elementares, que são invertíveis, E é invertível. Multiplicando EA = I, à esquerda, por E−1, obtemos A = E−1, e por isso AE = I. Logo E = A−1.

Um lado basta. Para matrizes quadradas, AN = I implica NA = I. De fato, suponha AN = I. Se alguma coluna de A ficasse sem pivô, a metade esquerda terminaria como uma matriz EA com uma linha nula, a de uma linha sem pivô. Então EAN = E também teria uma linha nula. Isso é impossível, porque E é invertível, e a linha correspondente de EE−1 = I seria nula. Logo a metade esquerda chega a I, E = A−1, e N = (EA)N = E(AN) = E = A−1. O mesmo argumento prova o item 2 do teorema: se alguma coluna fica sem pivô, nenhuma matriz N satisfaz AN = I, e A é singular.

Um exemplo 2 × 2

Exemplo

Para A = 2111, começamos com

[A | I] = 21101101.

Dividimos a linha 1 pelo pivô 2 e subtraímos a nova linha 1 da linha 2:

11/21/2001/2−1/21.

Dividimos a linha 2 pelo pivô 1/2 e subtraímos da linha 1 a metade da nova linha 2:

101−101−12.

A metade esquerda chegou a I, então A−1 = 1−1−12. A fórmula 2 × 2 dá o mesmo: ad − bc = 2 − 1 = 1.

Na bancada: no modo Inversa, o quadro Gauss-Jordan em [A | I] faz uma operação por passo, com frações exatas, e escreve a operação feita. O quadro O paralelepípedo das colunas desenha o paralelepípedo que tem como arestas, a partir da origem, as colunas da metade esquerda. No fim, quando a metade esquerda é I, ele é o cubo unitário. Com o exemplo Singular, uma coluna fica sem pivô, as colunas pertencem a um mesmo plano que passa pela origem, e o paralelepípedo tem volume 0.

A transposta de uma matriz tem como linhas as colunas dessa matriz. A transposta de um produto é o produto das transpostas na ordem inversa, como acontece com a inversa.

Transposta

Definição

Seja A uma matriz de tamanho m × n, com entrada aij na posição (i, j). A transposta de A é a matriz AT, de tamanho n × m, cuja entrada na posição (i, j), escrita (AT)ij, é aji, para i = 1, …, n e j = 1, …, m. Em palavras: a linha i de AT é a coluna i de A.

Teorema

Se A é m × n e B é n × p, então (AB)T = BTAT. Se A é quadrada e invertível, então AT é invertível e (AT)−1 = (A−1)T.

Por quê. Indique por bij a entrada (i, j) de B. A entrada (i, j) de (AB)T é a entrada (j, i) de AB, igual a aj1b1i + ⋯ + ajnbni. Essa soma é o produto da linha i de BT, de entradas b1i, …, bni, pela coluna j de AT, de entradas aj1, …, ajn. Logo, ela é a entrada (i, j) de BTAT. Para a inversa, transponha AA−1 = I e A−1A = I. Como IT = I, obtemos (A−1)TAT = I e AT(A−1)T = I, isto é, AT é invertível, e a sua inversa é (A−1)T.

Exemplo

Com A = 1234 e B = 0110, temos AB = 2143 e

(AB)T = 2413,

BTAT = 2413,

ATBT = 3142.

Com os fatores na mesma ordem, o resultado é outro: ATBT ≠ (AB)T.

Matrizes simétricas

Definição

Uma matriz quadrada S, com entrada sij na posição (i, j), é simétrica se ST = S, isto é, se sij = sji para quaisquer i e j.

Teorema

Para toda matriz R, de tamanho m × n, as matrizes RTR, de tamanho n × n, e RRT, de tamanho m × m, são simétricas.

Por quê. Pela regra da transposta de um produto e porque (RT)T = R, temos (RTR)T = RT(RT)T = RTR. O mesmo vale para RRT. Entrada por entrada: (RTR)ij é a soma dos produtos das entradas correspondentes das colunas i e j de R, e essa soma não muda quando i e j trocam de papel.

Seja S uma matriz simétrica n × n cuja eliminação chega a n pivôs não nulos sem trocas de linhas, com S = LU. Seja D a matriz diagonal que tem esses pivôs na diagonal. Então U = DLT e, por isso, S = LDLT. Em palavras: a linha i de U é o i-ésimo pivô vezes a coluna i de L, transposta. Para ver isso, divida cada linha de U pelo seu pivô. O resultado é uma matriz triangular superior V com 1 na diagonal, e S = LDV. Como S = ST = VTDLT, a matriz S tem duas fatorações como produto de uma matriz triangular inferior com 1 na diagonal, uma matriz diagonal e uma matriz triangular superior com 1 na diagonal. A seção 1.5 do livro-texto mostra que essa fatoração de uma matriz invertível é única. Logo V = LT, e U = DV = DLT.

Exemplo

Para R = 120110, de tamanho 3 × 2,

RTR = 2225,

RRT = 521210101.

A entrada (1, 2) de RTR é 1·2 + 0·1 + 1·0 = 2, a soma dos produtos das entradas correspondentes das colunas 1 e 2 de R; a entrada (2, 1) é a mesma soma.

Na bancada: no modo Transposta, o quadro Transposta de uma matriz gira a grade de cores em torno da diagonal: use o controle Rotação da grade em torno da diagonal ou o botão Transpor. O quadro Transposta e inversa de um produto compara (AB)T com BTAT e com ATBT. No quadro Matrizes simétricas RTR e RRT, mude R no painel As matrizes B e R e veja os dois produtos continuarem simétricos. O exemplo Simétrica, visto no modo A = LU, mostra que cada linha de U é o seu pivô vezes a coluna correspondente de L, transposta, isto é, U = DLT.

Uma matriz de permutação reordena as linhas de uma matriz, quando multiplica à esquerda, ou as colunas, quando multiplica à direita.

Matriz de permutação

Definição

Uma matriz de permutação n × n é uma matriz cujas linhas são as linhas da identidade I, em alguma ordem. Equivalentemente, ela tem exatamente uma entrada igual a 1 em cada linha e em cada coluna, e as demais entradas iguais a 0.

Teorema

Seja P uma matriz de permutação n × n.

  1. Se a linha i de P é a linha j de I, então a linha i de PA é a linha j de A, para toda matriz A com n linhas.
  2. Se a coluna j de P é a coluna i de I, então a coluna j de AP é a coluna i de A, para toda matriz A com n colunas.
  3. P é invertível, e P−1 = PT.
  4. O produto de duas matrizes de permutação n × n é uma matriz de permutação.

Itens 1, 2 e 4. A linha i de PA é a linha i de P vezes A. Se a linha i de P é a linha j de I, esse produto é a linha j de A, o que prova o item 1. O item 2 tem a mesma prova, com colunas. Para o item 4, seja Q outra matriz de permutação n × n. Pelo item 1, as linhas de PQ são as linhas de Q em outra ordem, logo são as linhas de I em outra ordem.

Por que P−1 = PT. A entrada (i, j) de PPT é o produto da linha i de P pela coluna j de PT, que é a linha j de P, transposta. As linhas de P são linhas diferentes da identidade, então esse produto vale 1 se i = j e 0 se i ≠ j: PPT = I. Da mesma forma, as colunas de P são colunas diferentes da identidade, e PTP = I.

Ciclos e ordem de uma permutação

Multiplicar um vetor x ∈ ℝn por P muda as posições das suas coordenadas. Se a linha i de P é a linha j de I, a coordenada i de Px é a coordenada j de x: a multiplicação leva o valor da posição j para a posição i. Dizemos que P leva a posição j à posição i.

Definição

Um ciclo de P, de tamanho q, é uma lista de q posições distintas j1, …, jq tal que P leva j1 a j2, j2 a j3, e assim por diante, até levar jq a j1. Uma posição que P leva a ela mesma forma um ciclo de tamanho 1. A ordem de uma matriz de permutação P é o menor inteiro k ≥ 1 tal que Pk = I.

Toda posição pertence a exatamente um ciclo. Partindo de uma posição e seguindo para onde P a leva, a lista de posições visitadas volta à posição de partida, porque há finitas posições e P leva posições diferentes a posições diferentes. A cada multiplicação por P, cada valor passa para a posição seguinte do seu ciclo. Num ciclo de tamanho q, os valores voltam às posições iniciais exatamente quando o número de multiplicações é múltiplo de q.

A ordem existe. As potências de P também são matrizes de permutação (item 4 do teorema), e há apenas n! matrizes de permutação n × n. Então duas das potências P, P2, …, Pn!+1 coincidem: Pk = Pk+h, com h ≥ 1. Multiplicando os dois lados por (P−1)k, obtemos Ph = I. Se os ciclos de P têm tamanhos q1, …, qt, então Pk = I exatamente quando k é múltiplo de todos esses tamanhos. Por isso, a ordem de P é o mínimo múltiplo comum desses tamanhos, mmc(q1, …, qt).

Exemplo

Para P = 010001100, as linhas de PA são as linhas 2, 3 e 1 de A, nessa ordem, para toda matriz A com 3 linhas, e

P(x1, x2, x3)T = (x2, x3, x1)T.

Assim, P leva a posição 2 à posição 1, a posição 3 à posição 2 e a posição 1 à posição 3: as três posições formam um único ciclo, de tamanho 3. Calculando,

P2 = 001100010,

que é PT. Logo P3 = P2P = PTP = I, a ordem de P é 3, e P−1 = P2 = PT.

Na bancada: no modo Permutações, escolha P no painel Escolha da permutação P e use os botões do quadro A tabela de lotes T: PT reordena as linhas (os lotes), e TP, as colunas (as etapas). O quadro A permutação P mostra P, PT e PPT = I. Na parte Em dimensão n, o campo Tamanhos dos ciclos monta uma permutação de até 24 posições, e o quadro Os ciclos de P desenha os seus ciclos.

Para pensar

Por que a diagonal da matriz L da fatoração A = LU só tem entradas iguais a 1?

Porque, sem trocas de linhas, cada passo da eliminação só subtrai de uma linha o produto de um escalar por uma linha acima dela, e nenhuma linha é multiplicada por um escalar. Por isso, cada matriz elementar Eij da eliminação tem i > j, e a sua inversa Eij−1 é triangular inferior com 1 na diagonal. A matriz L é o produto dessas inversas, e um produto de matrizes triangulares inferiores com 1 na diagonal também é triangular inferior com 1 na diagonal. Os pivôs ficam na diagonal da matriz triangular superior U. Se eles são todos não nulos, dividir cada linha de U pelo seu pivô dá uma matriz triangular superior V com 1 na diagonal. Com a matriz diagonal D que tem os pivôs na diagonal, vale U = DV e, portanto, A = LDV.

Se uma matriz A é simétrica e invertível, a inversa A−1 também é simétrica?

Sim. Como (A−1)T = (AT)−1, pelo teorema da guia Transposta e simetria, e AT = A, temos (A−1)T = A−1. Por exemplo, a matriz M do exemplo Canais de áudio é simétrica, e a inversa calculada no modo Inversa, 3/2−11/2−12−11/2−13/2, também é.

Uma matriz de permutação 5 × 5 pode ter ordem 6? E ordem 7?

Ordem 6, sim. Com um ciclo de tamanho 2 e outro de tamanho 3, que somam as 5 posições, os valores dos dois ciclos voltam juntos às posições iniciais, pela primeira vez, depois de mmc(2, 3) = 6 multiplicações pela matriz de permutação P. Ordem 7, não. A ordem, definida na guia Matrizes de permutação, é o mínimo múltiplo comum (mmc) dos tamanhos dos ciclos, e, como 7 é primo, 7 só divide esse mmc se algum ciclo tiver tamanho múltiplo de 7. Um ciclo assim tem pelo menos 7 posições, e a matriz só tem 5.