Matemática do ensino médio · Bovenbouw

30Matrizes e grafos

Uma matriz é uma tabela retangular de números, somada e multiplicada por regras concebidas para que a álgebra das matrizes represente a composição de transformações lineares. As matrizes resolvem sistemas lineares, governam sequências recorrentes acopladas e contam passeios em redes — a matemática por trás dos mecanismos de busca e dos algoritmos de caminho mínimo.

30.1 Álgebra das matrizes

Definição 30.1 (Matriz)

Uma matriz $m \times n$ é uma tabela de números reais com $m$ linhas e $n$ colunas: $A = (a_{ij})$ , em que $a_{ij}$ é a entrada da linha $i$ , coluna $j$ . Duas matrizes de mesmo tamanho são somadas entrada a entrada, e $\lambda A = (\lambda a_{ij})$ .

Definição 30.2 (Produto de matrizes)

Sejam $A$ de tamanho $m \times n$ e $B$ de tamanho $n \times p$ . O produto $AB$ é a matriz $m \times p$ cuja entrada $(i,j)$ é

(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}

(a regra “linha $i$ de $A$ vezes coluna $j$ de $B$ ”).

Exemplo 30.3

$\begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} 2 & 3\\ 4 & 7\end{pmatrix}$ , ao passo que $\begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} = \begin{pmatrix} 3 & 4\\ 4 & 6\end{pmatrix}$ : a multiplicação de matrizes não é comutativa.

Proposição 30.4 (Regras da álgebra das matrizes)

Sempre que os tamanhos tornem os produtos legítimos:

(AB)C = A(BC), \qquad A(B + C) = AB + AC, \qquad (A+B)C = AC + BC,

e a matriz identidade $I_n$ (uns na diagonal, zeros no resto) satisfaz $I_m A = A I_n = A$ para $A$ de tamanho $m \times n$ .

Demonstração. Todas são verificações entrada a entrada a partir da Definição 30.2; a associatividade, a única não trivial, resume-se a trocar duas somas finitas: $\bigl((AB)C\bigr)_{ij} = \sum_l \left(\sum_k a_{ik}b_{kl}\right) c_{lj} = \sum_k a_{ik} \left(\sum_l b_{kl} c_{lj}\right) = \bigl(A(BC)\bigr)_{ij}$ . ∎

Definição 30.5 (Inversa)

Uma matriz quadrada $A$ de tamanho $n$ é invertível se existe uma matriz $B$ com $AB = BA = I_n$ ; esse $B$ é então único e se escreve $A^{-1}$ .

Proposição 30.6 (Inversa de uma matriz $2\times2$ )

Sejam $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ e $\det A = ad - bc$ (o determinante). Então $A$ é invertível se, e somente se, $\det A \neq 0$ , e nesse caso

A^{-1} = \frac{1}{ad - bc}\begin{pmatrix} d & -b\\ -c & a\end{pmatrix}.

Demonstração. Um cálculo dá $A \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} = \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} A = (ad - bc) I_2$ ; se $ad - bc \neq 0$ , divida. Reciprocamente, se $ad - bc = 0$ , as colunas de $A$ são proporcionais, e o mesmo vale para as colunas de $AB$ qualquer que seja $B$ ; ora, as colunas de $I_2$ não são proporcionais, de modo que nenhum $B$ pode satisfazer $AB = I_2$ . ∎

Método 30.7 (Sistemas lineares)

O sistema $\begin{cases} ax + by = e\\ cx + dy = f \end{cases}$ é a equação matricial $AX = Y$ com $X = \begin{pmatrix} x \\ y\end{pmatrix}$ , $Y = \begin{pmatrix} e \\ f\end{pmatrix}$ . Se $\det A \neq 0$ , sua única solução é $X = A^{-1}Y$ . O mesmo formalismo trata $n$ equações a $n$ incógnitas.

30.2 Potências de matrizes e sequências recorrentes

Definição 30.8

Para uma matriz quadrada $A$ e $k \in \N$ , $A^k = A \times \dots \times A$ ( $k$ fatores), com $A^0 = I$ .

Método 30.9 (Casos diagonal-mais-nilpotente e diagonalizável)

Duas maneiras usuais de calcular $A^k$ :

Se $A = \lambda I + N$ com $N^2 = 0$ , o teorema binomial (válido aqui porque $I$ e $N$ comutam) se reduz a dois termos: $A^k = \lambda^k I + k \lambda^{k-1} N$ .
Se encontramos $P$ invertível com $A = PDP^{-1}$ e $D$ diagonal, então $A^k = P D^k P^{-1}$ , e $D^k$ se calcula entrada a entrada. (Encontrar tal $P$ de maneira sistemática é a teoria da diagonalização, desenvolvida na graduação; neste nível $P$ é dado.)

Exemplo 30.10 (Sequências acopladas)

Sejam $u_{n+1} = 3u_n + v_n$ e $v_{n+1} = u_n + 3v_n$ . Pondo $X_n = \begin{pmatrix} u_n\\ v_n \end{pmatrix}$ e $A = \begin{pmatrix} 3 & 1\\ 1 & 3\end{pmatrix}$ , obtemos $X_{n+1} = AX_n$ , logo $X_n = A^n X_0$ . As sequências auxiliares $s_n = u_n + v_n$ e $d_n = u_n - v_n$ satisfazem $s_{n+1} = 4s_n$ e $d_{n+1} = 2d_n$ , de modo que $s_n = 4^n s_0$ , $d_n = 2^n d_0$ e

u_n = \frac{4^n(u_0+v_0) + 2^n(u_0-v_0)}{2}, \qquad v_n = \frac{4^n(u_0+v_0) - 2^n(u_0-v_0)}{2}.

(Nos bastidores: $(1,1)$ e $(1,-1)$ são direções de autovetores de $A$ .)

30.3 Grafos e passeios

Definição 30.11 (Grafo, matriz de adjacência)

Um grafo é formado por vértices $1, 2, \dots, n$ e arestas ligando certos pares de vértices (pares ordenados, no caso de um grafo orientado). Sua matriz de adjacência é a matriz $M$ de tamanho $n \times n$ com $m_{ij} = 1$ se há uma aresta de $i$ para $j$ , e $0$ caso contrário. Um passeio de comprimento $k$ de $i$ a $j$ é uma sequência de $k$ arestas consecutivas que leva de $i$ a $j$ .

M = pmatrix 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 pmatrix Um grafo orientado e sua matriz de adjacência (): m_ij = 1 exatamente quando há uma aresta de i para j. — $M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ Um grafo orientado e sua matriz de adjacência (Exercício 30.6): $m_{ij} = 1$ exatamente quando há uma aresta de $i$ para $j$ .

Teorema 30.12 (Contagem de passeios)

O número de passeios de comprimento $k$ do vértice $i$ ao vértice $j$ é a entrada $(i,j)$ de $M^k$ .

Demonstração. Indução em $k$ . Para $k = 1$ , é a definição de $M$ . Suponha a afirmação verdadeira para $k$ . Um passeio de comprimento $k+1$ de $i$ a $j$ é um passeio de comprimento $k$ de $i$ até algum vértice $l$ , seguido de uma aresta de $l$ a $j$ ; pelos princípios aditivo e multiplicativo, seu número é

\sum_{l=1}^{n} \bigl(M^k\bigr)_{il}\, m_{lj} = \bigl(M^{k+1}\bigr)_{ij}. \qedhere

∎

Exemplo 30.13

Para o grafo triangular ( $3$ vértices, todos os pares ligados), $M = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0\end{pmatrix}$ e $M^2 = \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2\end{pmatrix}$ : de cada vértice há $2$ passeios de comprimento $2$ de volta a ele mesmo (por um ou outro vizinho) e $1$ até cada um dos outros vértices.

30.4 Exercícios

Exercício 30.1 ★

Sejam $A = \begin{pmatrix} 1 & 2\\ 0 & 1 \end{pmatrix}$ e $B = \begin{pmatrix} 2 & 0\\ 1 & 1 \end{pmatrix}$ . Calcule $A + B$ , $AB$ , $BA$ e $A^2$ .

Solução

Solução de Exercício 30.1.

A + B = \begin{pmatrix} 3 & 2\\ 1 & 2\end{pmatrix}, \quad AB = \begin{pmatrix} 4 & 2\\ 1 & 1\end{pmatrix}, \quad BA = \begin{pmatrix} 2 & 4\\ 1 & 3\end{pmatrix}, \quad A^2 = \begin{pmatrix} 1 & 4\\ 0 & 1\end{pmatrix}.

Observe que $AB \neq BA$ .

Exercício 30.2 ★

Determine se as matrizes seguintes são invertíveis e calcule as inversas quando existirem:

A = \begin{pmatrix} 2 & 5\\ 1 & 3\end{pmatrix}, \qquad B = \begin{pmatrix} 3 & 6\\ 2 & 4\end{pmatrix}.

Solução

Solução de Exercício 30.2.

$\det A = 6 - 5 = 1 \neq 0$ : $A^{-1} = \begin{pmatrix} 3 & -5\\ -1 & 2 \end{pmatrix}$ . $\det B = 12 - 12 = 0$ : $B$ não é invertível.

Exercício 30.3 ★

Resolva por inversão matricial o sistema $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 . \end{cases}$

Solução

Solução de Exercício 30.3.

O sistema é $AX = Y$ com $A$ como no Exercício 30.2 e $Y = \begin{pmatrix} 1\\ 2\end{pmatrix}$ :

X = A^{-1}Y = \begin{pmatrix} 3 & -5\\ -1 & 2\end{pmatrix} \begin{pmatrix} 1\\ 2\end{pmatrix} = \begin{pmatrix} -7\\ 3\end{pmatrix}: \qquad x = -7,\ y = 3 .

Exercício 30.4 ★★

Seja $A = \begin{pmatrix} 2 & 1\\ 0 & 2\end{pmatrix} = 2I + N$ com $N = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$ .

Verifique que $N^2 = 0$ e que $I$ e $N$ comutam.
Deduza $A^k$ para todo $k \in \N$ e confira a fórmula para $k=2$ por cálculo direto.

Solução

Solução de Exercício 30.4.

1. $N^2 = \begin{pmatrix} 0&1\\0&0\end{pmatrix} \begin{pmatrix} 0&1\\0&0\end{pmatrix} = 0$ , e $I$ comuta com toda matriz.

2. Como os dois termos comutam, o teorema binomial se aplica e todos os termos que contêm $N^2$ se anulam:

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N = \begin{pmatrix} 2^k & k\,2^{k-1}\\ 0 & 2^k \end{pmatrix}.

Verificação para $k = 2$ : $A^2 = \begin{pmatrix} 2&1\\0&2\end{pmatrix}^2 = \begin{pmatrix} 4&4\\0&4\end{pmatrix}$ , e a fórmula dá $2^2 = 4$ , $2 \times 2 = 4$ . ✓

Exercício 30.5 ★★

Sejam $A = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ e $F_n$ a sequência de Fibonacci ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ ). Mostre por indução que, para $n \geq 1$ ,

A^n = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix},

e deduza a identidade $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ . (Dica: os determinantes se multiplicam: $\det(MN) = \det M \det N$ , o que você pode verificar para matrizes $2\times2$ .)

Solução

Solução de Exercício 30.5.

Indução. Para $n = 1$ : $A^1 = \begin{pmatrix} 0&1\\1&1\end{pmatrix} = \begin{pmatrix} F_0 & F_1\\ F_1 & F_2\end{pmatrix}$ . Suponha a fórmula válida para $n$ ; então

A^{n+1} = A^n A = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} F_n & F_{n-1} + F_n\\ F_{n+1} & F_n + F_{n+1}\end{pmatrix} = \begin{pmatrix} F_n & F_{n+1}\\ F_{n+1} & F_{n+2}\end{pmatrix}.

Identidade. Para matrizes $2\times2$ , o desenvolvimento mostra que $\det(MN) = \det M \det N$ ; logo $\det(A^n) = (\det A)^n = (-1)^n$ , e $\det A^n = F_{n-1}F_{n+1} - F_n^2$ . (Esta é a identidade de Cassini.)

Exercício 30.6 ★★

Um grafo orientado sobre os vértices $\{1, 2, 3\}$ tem as arestas $1\to2$ , $2\to3$ , $3\to1$ e $1\to3$ .

Escreva a matriz de adjacência $M$ e calcule $M^2$ e $M^3$ .
Quantos passeios de comprimento $3$ vão de $1$ a $1$ ? Liste-os.

Solução

Solução de Exercício 30.6.

1. Ordenando os vértices $1, 2, 3$ :

M = \begin{pmatrix} 0&1&1\\ 0&0&1\\ 1&0&0\end{pmatrix}, \quad M^2 = \begin{pmatrix} 1&0&1\\ 1&0&0\\ 0&1&1\end{pmatrix}, \quad M^3 = \begin{pmatrix} 1&1&1\\ 1&0&1\\ 1&0&1 \end{pmatrix}.

2. $\bigl(M^3\bigr)_{11} = 1$ : exatamente um passeio fechado de comprimento $3$ no vértice $1$ , a saber $1 \to 2 \to 3 \to 1$ . (O passeio $1 \to 3 \to 1$ tem comprimento apenas $2$ , e $1 \to 3$ , depois $3\to1$ , depois $1\to3$ termina em $3$ .)

Exercício 30.7 ★★

Uma empresa de compartilhamento de carros movimenta veículos entre duas cidades $A$ e $B$ . A cada semana, $80\%$ dos carros em $A$ permanecem em $A$ e $20\%$ vão para $B$ ; $30\%$ dos carros em $B$ vão para $A$ e $70\%$ permanecem. Sejam $a_n, b_n$ as proporções da frota em cada cidade.

Escreva $X_{n+1} = MX_n$ com $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ e identifique $M$ .
Determine as proporções de equilíbrio (resolva $MX = X$ com $a + b = 1$ ).
Mostre que $c_n = a_n - 0.6$ satisfaz $c_{n+1} = 0.5\,c_n$ e conclua que a distribuição da frota converge para o equilíbrio.

Solução

Solução de Exercício 30.7.

1. $a_{n+1} = 0.8a_n + 0.3b_n$ , $b_{n+1} = 0.2a_n + 0.7b_n$ : $M = \begin{pmatrix} 0.8 & 0.3\\ 0.2 & 0.7\end{pmatrix}$ .

2. $MX = X$ dá $0.8a + 0.3b = a$ , isto é, $0.3b = 0.2a$ , logo $b = \frac23 a$ ; com $a + b = 1$ : $a = 0.6$ , $b = 0.4$ .

3. Usando $b_n = 1 - a_n$ : $a_{n+1} = 0.8a_n + 0.3(1 - a_n) = 0.5a_n + 0.3$ , de modo que

c_{n+1} = a_{n+1} - 0.6 = 0.5a_n + 0.3 - 0.6 = 0.5(a_n - 0.6) = 0.5\,c_n .

Assim, $c_n = 0.5^n c_0 \to 0$ : $a_n \to 0.6$ e $b_n \to 0.4$ , qualquer que seja a distribuição inicial.

Exercício 30.8 ★★★

Sejam $A = \begin{pmatrix} 3 & 1\\ 1 & 3 \end{pmatrix}$ , $P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}$ .

Calcule $P^{-1}$ , depois $D = P^{-1}AP$ , e verifique que $D$ é diagonal.
Deduza uma fórmula fechada para $A^n$ e compare com o Exemplo 30.10.

Solução

Solução de Exercício 30.8.

1. $\det P = -2$ , logo $P^{-1} = -\frac12\begin{pmatrix} -1 & -1\\ -1 & 1\end{pmatrix} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ . Então

AP = \begin{pmatrix} 4 & 2\\ 4 & -2 \end{pmatrix}, \qquad D = P^{-1}AP = \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} \begin{pmatrix} 4&2\\4&-2\end{pmatrix} = \begin{pmatrix} 4 & 0\\ 0 & 2\end{pmatrix}.

2. De $A = PDP^{-1}$ , uma indução imediata dá $A^n = PD^nP^{-1}$ com $D^n = \begin{pmatrix} 4^n & 0\\ 0 & 2^n\end{pmatrix}$ , logo

A^n = P D^n P^{-1} = \begin{pmatrix} 4^n & 2^n\\ 4^n & -2^n\end{pmatrix}\cdot \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} = \frac12\begin{pmatrix} 4^n + 2^n & 4^n - 2^n\\ 4^n - 2^n & 4^n + 2^n\end{pmatrix}.

Aplicar $A^n$ a $X_0 = \begin{pmatrix} u_0\\v_0\end{pmatrix}$ reproduz exatamente as fórmulas do Exemplo 30.10.

30.5 Problema: a matriz que conhece Fibonacci (e o tempo)

Problema 30.1

Problema de fim de semana — uma única matriz $2 \times 2$ carrega toda a sequência de Fibonacci, uma matriz de Markov prevê o tempo a longo prazo e um autovetor vale um bilhão de dólares

Uma matriz é uma máquina que come um estado e devolve o seguinte — e suas potências guardam, portanto, futuros inteiros. Este problema abre com a espantosa matriz cujas potências listam os números de Fibonacci (e demonstram suas identidades em uma linha cada), depois faz o tempo rodar como uma cadeia de Markov até seu regime estacionário e fecha com o autovetor sobre o qual se construiu um mecanismo de busca (Teorema 30.12, Método 30.9).

Parte I — Fluência.

Com $A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ e $B = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ : calcule $AB$ e $BA$ . Veredicto sobre a comutatividade?
Inverta $\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ (Proposição 30.6) e use a inversa para resolver $2x + y = 4$ , $5x + 3y = 7$ .
Seja $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : calcule $N^2$ e deduza que $(I + N)^n = I + nN$ para todo $n$ .
O grafo triangular (três vértices, todos os pares ligados): escreva sua matriz de adjacência $A$ , calcule $A^3$ e interprete as entradas da diagonal (Teorema 30.12).
Para $D = \begin{pmatrix} 2 & 0\\ 0 & \frac12 \end{pmatrix}$ : dê $D^n$ e seu comportamento quando $n \to \infty$ .

Parte II — A matriz de Fibonacci. Seja $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ e sejam $F_1 = F_2 = 1, F_3 = 2, \dots$ os números de Fibonacci do Problema 13.1.

Calcule $F^2$ , $F^3$ , $F^4$ e conjecture a forma geral de $F^n$ em termos dos números de Fibonacci.
Demonstre a conjectura $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$ por indução.
Tome os determinantes dos dois lados (o determinante de um produto é o produto dos determinantes — verifique para matrizes $2 \times 2$ se nunca viu isso): deduza a identidade de Cassini $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ — o motor do quadrado que some, demonstrado em uma linha.
De $F^{m+n} = F^m F^n$ , leia as entradas superiores direitas e obtenha a fórmula de adição

$F_{m+n} = F_{m+1} F_n + F_m F_{n-1} .$

Verifique-a para $m = n = 3$ .
Deduza da fórmula de adição (indução em $k$ ) que $F_n$ divide $F_{kn}$ , e confira em $F_3 \mid F_6$ e $F_3 \mid F_9$ .
Para calcular $F_{100}$ , não é preciso multiplicar $100$ matrizes: eleve ao quadrado repetidamente ( $F^2, F^4, F^8, \dots$ ) e combine. Quantas multiplicações de matrizes bastam, e que antigo truque de multiplicação do volume do ensino fundamental é este, promovido a matrizes?

Parte III — A máquina do tempo. Em certa cidade: depois de um dia de sol, o seguinte é de sol com probabilidade $0.8$ ; depois de um dia de chuva, é de sol com probabilidade $0.4$ . Codifique a distribuição do dia como uma coluna $\binom{p_{\text{sol}}}{p_{\text{chuva}}}$ e a evolução por

M = \begin{pmatrix} 0.8 & 0.4\\ 0.2 & 0.6 \end{pmatrix}.

Verifique que cada coluna de $M$ soma $1$ e diga por que toda máquina do tempo tem de ter essa propriedade.
Hoje faz sol. Calcule a previsão para amanhã e para depois de amanhã.
Encontre o regime estacionário: a distribuição $v$ com $Mv = v$ (e entradas somando $1$ ). Que fração dos dias é de sol a longo prazo?
Parta de um dia de chuva, $\binom01$ , e aplique $M$ quatro vezes, acompanhando a distância ao regime estacionário em cada passo. Por que fator a diferença encolhe a cada passo — e que tipo de convergência é esta?
PageRank em miniatura: três páginas, com os links $A \to B$ , $A \to C$ , $B \to C$ , $C \to A$ . Um navegante aleatório segue um link de saída escolhido ao acaso, uniformemente. Escreva a matriz de transição, encontre o regime estacionário e ordene as páginas.
Interprete a ordenação: por que $C$ pontua tão alto quanto $A$ apesar de receber links de menos páginas — o que o regime estacionário realmente mede? (O PageRank de verdade acrescenta um fator de amortecimento para becos sem saída e saltos; a ideia do autovetor é exatamente esta.)

Parte IV — Dividendos diagonais.

Duas grandezas acopladas obedecem a $u_{n+1} = 3u_n + v_n$ , $v_{n+1} = u_n + 3v_n$ , ou seja, à matriz $A$ do Exercício 30.8. Usando a diagonalização daquele exercício ( $D = \operatorname{diag}(4, 2)$ ), dê a fórmula fechada para $u_n$ quando $u_0 = 1$ , $v_0 = 0$ , e confira-a contra o cálculo direto para $n = 1, 2, 3$ .
Em uma ou duas frases: o que a diagonalização faz com um sistema acoplado — e em que sentido o regime estacionário de Markov da questão 14 é também uma história de autovetores?
Finale — as três faces da matriz neste fim de semana: contabilidade (sistemas e inversas), combinatória (passeios e links contados por potências) e evolução (Fibonacci, o tempo, a web — futuros lidos em direções próprias). Uma frase para cada, mais o ponteiro adiante: a álgebra linear dos volumes de graduação transforma cada uma dessas faces em uma teoria.

Solução

Solução de Problema 30.1.

1. $AB = \begin{pmatrix} 2 & 1\\ 4 & 3\end{pmatrix}$ e $BA = \begin{pmatrix} 3 & 4\\ 1 & 2\end{pmatrix}$ : a multiplicação de matrizes não é comutativa — $B$ troca as colunas quando está à direita e as linhas quando está à esquerda.

2. Determinante $6 - 5 = 1$ : inversa $\begin{pmatrix} 3 & -1\\ -5 & 2\end{pmatrix}$ . Aplicando-a a $\binom{4}{7}$ : $x = 12 - 7 = 5$ , $y = -20 + 14 = -6$ .

3. $N^2 = 0$ . Então $(I + N)^n = I + nN$ por indução: $(I + nN)(I + N) = I + (n+1)N + nN^2 = I + (n+1)N$ .

4. $A = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}$ , e $A^3$ tem entradas diagonais iguais a $2$ : de cada vértice partem exatamente dois passeios fechados de comprimento $3$ (o triângulo percorrido em um sentido ou no outro) — o teorema de contagem em ação.

5. $D^n = \begin{pmatrix} 2^n & 0\\ 0 & 2^{-n} \end{pmatrix}$ : uma direção explode, a outra morre — destinos diagonais são sequências geométricas independentes.

6. $F^2 = \begin{pmatrix} 2 & 1\\ 1 & 1\end{pmatrix}$ , $F^3 = \begin{pmatrix} 3 & 2\\ 2 & 1\end{pmatrix}$ , $F^4 = \begin{pmatrix} 5 & 3\\ 3 & 2\end{pmatrix}$ : Fibonacci por toda parte; a conjectura é a do enunciado.

7. Se $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\end{pmatrix}$ , então

F^{n+1} = F^n F = \begin{pmatrix} F_{n+1} + F_n & F_{n+1}\\ F_n + F_{n-1} & F_n \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1}\\ F_{n+1} & F_n \end{pmatrix} :

a hereditariedade; o caso inicial $n = 1$ é o próprio $F$ , com a convenção $F_0 = 0$ (que estende a recorrência para trás).

8. $\det F = -1$ , logo $\det(F^n) = (\det F)^n = (-1)^n$ ; e, diretamente, $\det(F^n) = F_{n+1}F_{n-1} - F_n^2$ : Cassini, em uma linha. (A regra do produto para determinantes $2 \times 2$ é um desenvolvimento agradável de cinco minutos.)

9. Canto superior direito de $F^m F^n$ : $F_{m+1}F_n + F_m F_{n-1}$ ; canto superior direito de $F^{m+n}$ : $F_{m+n}$ . Para $m = n = 3$ : $F_4 F_3 + F_3 F_2 = 3 \times 2 + 2 \times 1 = 8 = F_6$ .

10. Para $k = 1$ : trivial. Se $F_n \mid F_{kn}$ , a fórmula de adição com $m = kn$ dá $F_{(k+1)n} = F_{kn+1}F_n + F_{kn}F_{n-1}$ : os dois termos são múltiplos de $F_n$ . Logo $F_n \mid F_{kn}$ para todo $k$ : confira que $F_3 = 2$ divide $F_6 = 8$ e $F_9 = 34$ .

11. $F^{100} = F^{64} F^{32} F^4$ : sete elevações ao quadrado ( $F^2, F^4, \dots, F^{64}$ ) mais duas combinações — nove multiplicações em vez de noventa e nove. É o truque da tabela de dobros dos escribas egípcios, transposto dos números para as matrizes: escreva $100$ em binário e multiplique os dobros de que precisa.

12. $0.8 + 0.2 = 1$ e $0.4 + 0.6 = 1$ : amanhã terá algum tempo — cada coluna é uma distribuição de probabilidade completa, de modo que as probabilidades se conservam.

13. Amanhã: $\binom{0.8}{0.2}$ . Depois de amanhã: $M\binom{0.8}{0.2} = \binom{0.72}{0.28}$ .

14. $Mv = v$ com $v = \binom{s}{c}$ , $s + c = 1$ : $0.8s + 0.4c = s$ dá $0.4c = 0.2s$ , $s = 2c$ : $v = \binom{2/3}{1/3}$ . A longo prazo, dois dias em cada três são de sol — não importa como esteja hoje.

15. A partir de $\binom01$ : componentes de sol $0.4$ , $0.56$ , $0.624$ , $0.6496$ ; distâncias a $\frac23$ : $0.267$ , $0.107$ , $0.043$ , $0.017$ — cada passo multiplica a diferença por exatamente $0.4$ (o segundo autovalor da máquina): convergência geométrica para o regime estacionário.

16. Colunas (a partir de $A$ , $B$ , $C$ ): $P = \begin{pmatrix} 0 & 0 & 1\\ \frac12 & 0 & 0\\ \frac12 & 1 & 0\end{pmatrix}$ . Regime estacionário: $v_A = v_C$ , $v_B = \frac{v_A}{2}$ , $v_C = \frac{v_A}{2} + v_B$ ; somando $1$ : $v = \left(\frac25, \frac15, \frac25\right)$ . Ordenação: $A$ e $C$ empatam em primeiro, $B$ fica em último.

17. $C$ recebe todo o tráfego de $B$ e metade do de $A$ , e devolve tudo a $A$ : o regime estacionário mede onde o navegante passa o tempo, não quantos links apontam para a página — um link vindo de uma página popular pesa mais que vários vindos de páginas desertas. Essa ponderação recursiva é exatamente a ideia fundadora do Google; o amortecimento cuida das armadilhas e dos becos sem saída.

18. $A^n = P D^n P^{-1}$ dá $u_n = \frac{4^n + 2^n}{2}$ (e $v_n = \frac{4^n - 2^n}{2}$ ). Verificação: $u_1 = 3$ , $u_2 = 10$ , $u_3 = 36$ ; diretamente: $(1,0) \to (3,1) \to (10,6) \to (36, 28)$ : bate.

19. A diagonalização passa para coordenadas nas quais o sistema acoplado se desfaz em sequências geométricas independentes — cada autovalor corre sua própria corrida. O regime estacionário de Markov é o autovetor associado ao autovalor $1$ , e a taxa de convergência da questão 15 é o autovalor seguinte: a máquina do tempo era, desde o começo, uma história de autovetores.

20. Contabilidade: um sistema é uma única equação matricial, resolvida por uma única inversa. Combinatória: as potências da matriz de adjacência contam passeios, links, conexões. Evolução: as potências da máquina levam os estados a seus destinos, e as direções próprias (a direção áurea de Fibonacci, o regime estacionário do tempo, o vetor de ordenação da web) são esses destinos. A álgebra linear, nos volumes de graduação, é a ciência exatamente disso.