Determinantes II

Permutação e sinal

Há n! permutações de {1, …, n}: são n escolhas para σ(1), n − 1 para σ(2), e assim por diante, até uma única escolha para σ(n).

Trocas e sinal. Trocar os valores de duas posições vizinhas de σ muda inv(σ) em exatamente uma unidade, porque só a ordem desse par muda. Trocar os valores das posições i e j, com i < j, equivale a 2(j − i) − 1 trocas de vizinhos, um número ímpar: j − i trocas levam o valor da posição i até a posição j, e mais j − i − 1 trocas levam o valor que estava na posição j até a posição i. Logo toda troca de dois valores de σ muda a paridade de inv(σ) e troca o sinal. Por isso, se σ se obtém da identidade (1, 2, …, n) com k trocas, então sgn(σ) = (−1)^k.

A matriz de permutação de σ se escreve P_σ: ela tem 1 nas casas (i, σ(i)), para i = 1, …, n, e 0 nas demais. As mesmas k trocas, feitas nas linhas da matriz identidade I, levam I a P_σ. Cada troca de linhas muda o sinal do determinante (Aula 14), logo det P_σ = (−1)^k = sgn(σ).

Torres que não se atacam

Num tabuleiro n × n, como no xadrez, duas torres se atacam quando estão na mesma linha ou na mesma coluna. Pôr n torres sem que nenhuma ataque outra é pôr uma torre em cada linha e em cada coluna. Chame de σ(i) a coluna da torre da linha i. Como as colunas das n torres são diferentes, σ é uma permutação, e cada permutação corresponde a uma única posição das torres. No tabuleiro, uma inversão é um par de torres em que a da linha de cima está numa coluna mais à direita.

Na bancada: no quadro Tabuleiro de A, com o modo Põe ou retira uma torre, clique numa casa de cada linha, em colunas diferentes. A leitura abaixo do tabuleiro mostra a permutação σ, o número de inversões e o sinal. O exemplo Reordenar 4 pacotes, do painel Exemplos, é a matriz de permutação de σ = (2, 4, 1, 3). Multiplicar por ela leva o vetor (x₁, x₂, x₃, x₄)^T, com os conteúdos de quatro pacotes, em (x₂, x₄, x₁, x₃)^T: a posição i recebe o pacote da posição σ(i).

A fórmula com n! termos

Por quê. A demonstração usa só as três propriedades da Aula 14.

1. A linha i de A é a soma de n linhas: para cada coluna j, a linha que tem a entrada a_ij na coluna j e 0 nas outras posições.
2. Pela linearidade em cada linha (propriedade 3 da Aula 14), aplicada a uma linha de cada vez, det A é a soma de nⁿ determinantes, um para cada escolha de uma coluna em cada linha. O determinante de uma escolha é o produto das n entradas escolhidas vezes o determinante da matriz que tem 1 nas casas escolhidas e 0 nas demais.
3. Se duas linhas escolhem a mesma coluna, essa matriz de zeros e uns tem duas linhas iguais, e o seu determinante é 0.
4. Restam as escolhas em que as n colunas são diferentes, isto é, as permutações σ, com a coluna σ(i) na linha i. Para elas, a matriz de zeros e uns é P_σ, e det P_σ = sgn(σ) (guia Permutações e sinal).

Reciprocamente, pode-se verificar que a função dada pela fórmula tem as três propriedades da Aula 14. Assim, a fórmula também mostra que o determinante existe.

• Para n = 2, as permutações (1, 2) e (2, 1) dão det A = a₁₁a₂₂ − a₁₂a₂₁. Com a = a₁₁, b = a₁₂, c = a₂₁ e d = a₂₂, essa é a fórmula ad − bc do determinante 2 × 2.
• Cada entrada a_ij aparece nos (n − 1)! termos das permutações com σ(i) = j, porque as outras n − 1 linhas recebem as n − 1 colunas restantes de (n − 1)! maneiras. Se a_ij = 0, todos esses termos são nulos.
• Seja A triangular superior e seja σ diferente da identidade. Como os valores σ(1), …, σ(n) somam 1 + 2 + ⋯ + n, existe uma posição i com σ(i) < i, e a entrada a_iσ(i), abaixo da diagonal, é nula. Logo só o termo da identidade pode ser não nulo, e det A = a₁₁a₂₂ ⋯ a_nn. Para A triangular inferior, o argumento é o mesmo, com σ(i) > i.

Os seis termos de uma matriz 3 × 3

Esses seis produtos, com esses sinais, são os da regra de Sarrus, que só vale para matrizes 3 × 3. Para uma matriz 4 × 4, a fórmula já tem 4! = 24 termos.

Na bancada: com o exemplo Seis termos, do painel Exemplos, o quadro Os n! termos lista esses seis termos, cada um com um minitabuleiro que mostra as suas torres. Clique num termo para ver as torres no quadro Tabuleiro de A. Com o modo Zera a entrada desse quadro, clique numa entrada e veja os 2! = 2 termos que a usam ficarem nulos.

Submatriz, menor e cofator

Por quê. Fixe a linha i. Em cada termo da fórmula das permutações, a torre da linha i está numa coluna j = σ(i).

1. Os termos com σ(i) = j têm o fator comum a_ij. Neles, as outras n − 1 torres ocupam uma casa em cada linha e em cada coluna de M_ij, e cada posição dessas torres aparece em exatamente um termo. Sem o fator a_ij e sem o sinal, esses termos são os produtos da fórmula de det M_ij.
2. As inversões de σ são de dois tipos: as que envolvem só as outras n − 1 torres, que são as inversões do termo correspondente de det M_ij, e as que envolvem a torre da casa (i, j). Para contar as do segundo tipo, seja s o número de torres acima da linha i e à direita da coluna j. Das i − 1 torres acima da linha i, as outras i − 1 − s estão à esquerda da coluna j. As j − 1 torres à esquerda da coluna j são essas i − 1 − s e mais j − i + s torres abaixo da linha i. A torre da casa (i, j) forma uma inversão com cada torre acima e à direita dela e com cada torre abaixo e à esquerda dela: são 2s + j − i inversões, um número com a mesma paridade que i + j.
3. Logo o sinal de cada termo com σ(i) = j é (−1)^i+j vezes o sinal do termo correspondente de det M_ij, e a soma desses termos é a_ij(−1)^i+j det M_ij = a_ijC_ij. Somando sobre j = 1, …, n, obtemos a expansão pela linha i.

A expansão por uma coluna de A é a expansão por uma linha de A^T, e det A^T = det A (Aula 14).

Os sinais e um exemplo

O sinal (−1)^i+j é + quando i + j é par e − quando i + j é ímpar. Assim, os sinais começam com + na casa (1, 1) e se alternam ao longo de cada linha e de cada coluna. Para n = 3:

Se a_ij = 0, a parcela a_ijC_ij é 0, e o cofator C_ij não precisa ser calculado. Por isso, cada entrada nula da linha ou da coluna escolhida dispensa o cálculo de um determinante (n − 1) × (n − 1), e convém expandir pela linha ou pela coluna com mais entradas nulas.

Na bancada: no quadro Expansão em cofatores, escolha a linha ou a coluna no controle Expandir por. Cada bloco mostra a entrada a_ij, a submatriz M_ij, o cofator C_ij e a parcela a_ijC_ij. Clique num bloco para ver a submatriz no quadro Tabuleiro de A, onde a linha i e a coluna j aparecem riscadas. Nesse quadro, as casas claras são as de sinal + e as escuras, as de sinal −. No quadro Os n! termos, os termos aparecem agrupados pela casa da torre na linha (ou na coluna) escolhida, e a soma de cada grupo é a parcela a_ijC_ij.

A inversa por cofatores

Por quê. A entrada (i, j) de AC^T é a_i1C_j1 + ⋯ + a_inC_jn.

• Para j = i, essa soma é a expansão de det A pela linha i.
• Para j ≠ i, troque a linha j de A por uma cópia da linha i. Os cofatores C_j1, …, C_jn não mudam, porque não dependem da linha j. A soma passa a ser a expansão, pela linha j, do determinante de uma matriz com duas linhas iguais, que é 0.

Com expansões por colunas, o mesmo argumento dá C^TA = (det A) I. Se det A ≠ 0, dividindo as duas igualdades por det A, obtemos A(C^T/det A) = (C^T/det A)A = I.

Dois exemplos

Para matrizes grandes, a eliminação de Gauss-Jordan (Aula 5) calcula a inversa com muito menos operações. A fórmula serve para estudar A⁻¹. Ela mostra, por exemplo, que, se A tem entradas inteiras e det A = ±1, então A⁻¹ também tem entradas inteiras (veja Para pensar).

Na bancada: no quadro Inversa por cofatores, a matriz da esquerda é C, e a da direita é A⁻¹. Clique numa entrada de A⁻¹: a leitura mostra de qual cofator ela vem, e o quadro Tabuleiro de A destaca a submatriz correspondente. A linha Conferência verifica que AC^T = (det A) I. Se det A = 0, só a matriz C aparece, e a linha Conferência mostra que AC^T é a matriz nula.

A regra de Cramer

Por quê.

1. Como det A ≠ 0, a matriz A é invertível (Aula 14), e x = A⁻¹b é a única solução.
2. Seja X_j a matriz identidade com a coluna j trocada por x. Multiplicar A por uma coluna da identidade dá a coluna de A na mesma posição, e Ax = b. Logo AX_j é A com a coluna j trocada por b, isto é, AX_j = B_j.
3. Na linha j de X_j, a única entrada que pode ser não nula é x_j, na diagonal. Expandindo por essa linha, det X_j = x_j.
4. Pela regra do produto (Aula 14), det B_j = det A · det X_j = det A · x_j. Basta dividir por det A.

Áreas com sinal

Para u, v ∈ ℝ², a matriz [u  v] tem colunas u e v. O determinante det [u  v] é a área com sinal do paralelogramo de lados u e v. O seu módulo é a área. O sinal é + quando a rotação de u para v, pelo menor ângulo, é no sentido anti-horário, e − quando é no sentido horário. Se u e v estão numa mesma reta que passa pela origem, a área com sinal é 0. Para u, v, w ∈ ℝ³, |det [u  v  w]| é o volume do paralelepípedo de arestas u, v e w. Para uma matriz A de tamanho n × n, com n > 3, |det A| é tomado como o volume n-dimensional do paralelepípedo gerado pelas colunas de A (Aula 14).

Seja A = [a₁  a₂] uma matriz 2 × 2 de colunas a₁ e a₂, com det A ≠ 0, seja b ∈ ℝ² e seja x a solução de Ax = b. A regra de Cramer diz que x₁ = det [b  a₂] / det [a₁  a₂], a razão entre as áreas com sinal dos paralelogramos de lados b, a₂ e de lados a₁, a₂. Isso também se vê diretamente. Como b = x₁a₁ + x₂a₂, a linearidade do determinante em cada coluna dá

pois a matriz [a₂  a₂] tem duas colunas iguais. Geometricamente, o paralelogramo de lados x₁a₁ e a₂ e o de lados b e a₂ têm a mesma base a₂ e a mesma altura, porque b − x₁a₁ = x₂a₂ é paralelo a a₂. Por isso, os dois têm a mesma área com sinal, x₁ det A.

Se det A = 0, uma das colunas é múltipla da outra, e o paralelogramo de lados a₁ e a₂ tem área nula. Nesse caso, a regra não se aplica. O sistema tem infinitas soluções se b pertence ao espaço das colunas de A, e nenhuma solução se b não pertence a ele.

Na bancada: no quadro Regra de Cramer no plano, arraste as pontas de a₁, a₂ e b, as colunas e o lado direito do sistema Ax = b do painel Sistema de Cramer. O paralelogramo cinza tem lados a₁ e a₂. O vermelho tem lados b e a₂, ou a₁ e b quando você escolhe x₂ no controle Incógnita. O quadro As contas de Cramer mostra det A, as matrizes B₁ e B₂ e a solução em frações exatas. Com o sistema Colunas paralelas, do painel Sistema de Cramer, det A = 0.

Quanto custa a fórmula

Para uma matriz A de tamanho n × n e invertível, a eliminação encontra n pivôs, e det A é o produto deles, com o sinal trocado se houve um número ímpar de trocas de linhas. Esse cálculo usa cerca de n³/3 multiplicações (Aula 14). A fórmula das permutações tem n! termos, cada um com n − 1 multiplicações. A expansão em cofatores, repetida até chegar a matrizes 1 × 1, também faz um número de operações da ordem de n! quando a matriz não tem entradas nulas.

Por isso, a fórmula das permutações serve para demonstrar propriedades e obter outras fórmulas, como a expansão em cofatores, a inversa por cofatores e a regra de Cramer. Para calcular o determinante de uma matriz grande, usa-se a eliminação.

Na bancada: na parte Em dimensão n, o quadro Quantos termos compara n! com n³ para n de 1 a 12, e o quadro Os n! termos de A mostra os 5040 termos de uma matriz 7 × 7, com o controle Ordem n em 7.

A tridiagonal −1, 2, −1

Por quê. Seja n ≥ 3, e expanda D_n pela linha 1 de T_n.

1. Na linha 1, só as entradas a₁₁ = 2 e a₁₂ = −1 são não nulas; logo D_n = 2C₁₁ − C₁₂.
2. A submatriz M₁₁ é T_n−1; logo C₁₁ = det M₁₁ = D_n−1.
3. A primeira coluna de M₁₂ tem uma só entrada não nula, −1, na primeira linha. Expandindo por essa coluna, det M₁₂ é −1 vezes o determinante da matriz que sobra ao retirar essa linha e essa coluna, que é T_n−2. Logo det M₁₂ = −D_n−2 e C₁₂ = −det M₁₂ = D_n−2.

Assim, D_n = 2D_n−1 − D_n−2. Por indução, se D_n−1 = n e D_n−2 = n − 1, então D_n = 2n − (n − 1) = n + 1.

Os termos não nulos. O termo de uma permutação σ na fórmula de det T_n é não nulo exatamente quando |σ(i) − i| ≤ 1 para todo i, porque as entradas não nulas de T_n são as da diagonal e as vizinhas dela. A troca das posições i e i + 1 se escreve i ↔ i + 1. Se i é a menor posição com σ(i) ≠ i, então σ(i) = i + 1 e σ(i + 1) = i. Repetindo o argumento a partir da posição i + 2, vemos que σ faz algumas trocas i ↔ i + 1, sem posição em comum, e mantém as outras posições fixas. Com k trocas, o sinal é (−1)^k, as n − 2k posições fixas dão o fator 2^n−2k, e cada troca dá o fator (−1)(−1) = 1. O termo vale (−1)^k 2^n−2k.

Para contar essas permutações, olhe a posição n. Ou ela fica fixa, e as posições 1, …, n − 1 formam uma permutação do mesmo tipo, ou ela troca com n − 1, e as posições 1, …, n − 2 formam uma permutação do mesmo tipo. Assim, o número dessas permutações para n é a soma dos números para n − 1 e para n − 2, com 1 permutação para n = 1 e 2 para n = 2. Os números de Fibonacci F₁, F₂, F₃, … começam com F₁ = F₂ = 1, e cada um dos seguintes é a soma dos dois anteriores: 1, 1, 2, 3, 5, 8, 13, … Logo o número de termos não nulos de T_n é F_n+1: para n = 6, são 13 dos 720 termos.

Na bancada: na parte Em dimensão n, escolha a família Tridiagonal no painel Família e ordem e mova o controle Ordem n. O quadro Os n! termos de A mostra em cor os F_n+1 termos não nulos, e o quadro A tridiagonal mostra D₁, …, D₁₂ sobre a reta n + 1.