---
title: "Matrizes e grafos"
book: "Matemática do ensino médio"
subject: math
language: pt
chapter: 30
exercises: 8
source: https://one-course.com/books/math/2/pt/chapter/30-matrizes-e-grafos
---

# Capítulo 30 — Matrizes e grafos

Uma [matriz](#def-g12-matrix-matrix) é uma tabela retangular de números, somada e multiplicada por regras concebidas para que a álgebra das [matrizes](#def-g12-matrix-matrix) represente a composição de transformações lineares. As [matrizes](#def-g12-matrix-matrix) resolvem [sistemas lineares](https://one-course.com/books/math/2/pt/chapter/7-equacoes-de-retas-e-sistemas-lineares#def-g10-lines-system), governam [sequências](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) recorrentes acopladas e contam passeios em redes — a matemática por trás dos mecanismos de busca e dos algoritmos de caminho [mínimo](https://one-course.com/books/math/2/pt/chapter/3-funcoes#def-g10-functions-extrema).

## 30.1 Álgebra das matrizes

**Definição 30.1 (Matriz).**

Uma *matriz $m \times n$* é uma tabela de [números reais](https://one-course.com/books/math/2/pt/chapter/1-numeros-e-conjuntos-numericos#def-g10-numbers-sets) 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](#def-g12-matrix-matrix) $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](#def-g12-matrix-matrix) 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](#def-g12-matrix-matrix) 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](#def-g12-matrix-product); 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](#def-g12-matrix-matrix) quadrada $A$ de tamanho $n$ é *invertível* se existe uma [matriz](#def-g12-matrix-matrix) $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×22\times22×2).**

Sejam $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ e $\det A = ad - bc$ (o *determinante*). Então $A$ é [invertível](#def-g12-matrix-inverse) 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](https://one-course.com/books/math/2/pt/chapter/2-algebra-equacoes-e-inequacoes#def-g10-algebra-equation) 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](https://one-course.com/books/math/2/pt/chapter/2-algebra-equacoes-e-inequacoes#def-g10-algebra-equation) a $n$ incógnitas.

## 30.2 Potências de matrizes e sequências recorrentes

**Definição 30.8.**

Para uma [matriz](#def-g12-matrix-matrix) 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](#def-g12-matrix-inverse) 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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) 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](#def-g12-matrix-matrix) $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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) 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.](https://one-course.com/images/onecourse/chapters/math-2/g12-matrix/fig-783722c7530e.svg)

*$M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ Um [grafo](#def-g12-matrix-graph) orientado e sua [matriz de adjacência](#def-g12-matrix-graph) ([Exercício 30.6](#exo-g12-matrix-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](#def-g12-matrix-graph) 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 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](#def-g12-matrix-matrix) seguintes são [invertíveis](#def-g12-matrix-inverse) 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 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](#def-g12-matrix-inverse).

**Exercício 30.3 ★.**

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

**Solução de Exercício 30.3.**

O sistema é $AX = Y$ com $A$ como no [Exercício 30.2](#exo-g12-matrix-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}$.

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

**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](#def-g12-matrix-matrix).

*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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) 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](https://one-course.com/books/math/2/pt/chapter/15-vetores-e-retas-no-plano#def-g11-vect-det) se multiplicam: $\det(MN) = \det M \det N$, o que você pode verificar para [matrizes](#def-g12-matrix-matrix) $2\times2$.)

**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](#def-g12-matrix-matrix) $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](#def-g12-matrix-graph) orientado sobre os vértices $\{1, 2, 3\}$ tem as arestas $1\to2$, $2\to3$, $3\to1$ e $1\to3$.

1. Escreva a [matriz de adjacência](#def-g12-matrix-graph) $M$ e calcule $M^2$ e $M^3$ .
2. Quantos passeios de comprimento $3$ vão de $1$ a $1$ ? Liste-os.

**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.

![](https://one-course.com/images/onecourse/chapters/math-2/g12-matrix/fig-8ee5ea63de42.svg)

1. Escreva $X_{n+1} = MX_n$ com $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ e identifique $M$ .
2. Determine as proporções de equilíbrio (resolva $MX = X$ com $a + b = 1$ ).
3. Mostre que $c_n = a_n - 0.6$ satisfaz $c_{n+1} = 0.5\,c_n$ e conclua que a [distribuição](https://one-course.com/books/math/2/pt/chapter/18-probabilidade-e-variaveis-aleatorias#def-g11-prob-rv) da frota [converge](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-limit) para o equilíbrio.

**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](https://one-course.com/books/math/2/pt/chapter/18-probabilidade-e-variaveis-aleatorias#def-g11-prob-rv) inicial.

**Exercício 30.8 ★★★.**

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

1. Calcule $P^{-1}$ , depois $D = P^{-1}AP$ , e verifique que $D$ é diagonal.
2. Deduza uma fórmula fechada para $A^n$ e compare com o [Exemplo 30.10](#ex-g12-matrix-coupled) .

**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](#ex-g12-matrix-coupled).

## 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](#def-g12-matrix-matrix) é 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](#def-g12-matrix-matrix) 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](#thm-g12-matrix-walks), [Método 30.9](#met-g12-matrix-powers)).

**Parte I — Fluência.**

1. 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?
2. Inverta $\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ ( [Proposição 30.6](#prop-g12-matrix-inverse2x2) ) e use a inversa para resolver $2x + y = 4$ , $5x + 3y = 7$ .
3. Seja $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : calcule $N^2$ e deduza que $(I + N)^n = I + nN$ para todo $n$ .
4. O [grafo](#def-g12-matrix-graph) triangular (três vértices, todos os pares ligados): escreva sua [matriz de adjacência](#def-g12-matrix-graph) $A$ , calcule $A^3$ e interprete as entradas da diagonal ( [Teorema 30.12](#thm-g12-matrix-walks) ).
5. Para $D = \begin{pmatrix} 2 & 0\\ 0 & \frac12  \end{pmatrix}$ : dê $D^n$ e seu comportamento quando $n \to \infty$ .

**Parte II — A [matriz](#def-g12-matrix-matrix) 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](https://one-course.com/books/math/2/pt/chapter/13-sequencias-um-primeiro-curso#pb-g11-seq-1).

6. Calcule $F^2$ , $F^3$ , $F^4$ e conjecture a forma geral de $F^n$ em termos dos números de Fibonacci.
7. Demonstre a conjectura $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}  \end{pmatrix}$ por indução.
8. Tome os [determinantes](https://one-course.com/books/math/2/pt/chapter/15-vetores-e-retas-no-plano#def-g11-vect-det) dos dois lados (o [determinante](https://one-course.com/books/math/2/pt/chapter/15-vetores-e-retas-no-plano#def-g11-vect-det) de um produto é o produto dos [determinantes](https://one-course.com/books/math/2/pt/chapter/15-vetores-e-retas-no-plano#def-g11-vect-det) — verifique para [matrizes](#def-g12-matrix-matrix) $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.
9. 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$.
10. Deduza da fórmula de adição (indução em $k$ ) que $F_n$ [divide](https://one-course.com/books/math/2/pt/chapter/29-aritmetica#def-g12-arith-divides) $F_{kn}$ , e confira em $F_3 \mid F_6$ e $F_3 \mid F_9$ .
11. Para calcular $F_{100}$ , não é preciso multiplicar $100$ [matrizes](#def-g12-matrix-matrix) : eleve ao quadrado repetidamente ( $F^2, F^4,  F^8, \dots$ ) e combine. Quantas multiplicações de [matrizes](#def-g12-matrix-matrix) bastam, e que antigo truque de multiplicação do volume do ensino fundamental é este, promovido a [matrizes](#def-g12-matrix-matrix) ?

**Parte III — A máquina do tempo.** Em certa cidade: depois de um dia de sol, o seguinte é de sol com [probabilidade](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) $0.8$; depois de um dia de chuva, é de sol com [probabilidade](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) $0.4$. Codifique a [distribuição](https://one-course.com/books/math/2/pt/chapter/18-probabilidade-e-variaveis-aleatorias#def-g11-prob-rv) 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}.
$$

12. Verifique que cada coluna de $M$ soma $1$ e diga por que toda máquina do tempo tem de ter essa propriedade.
13. Hoje faz sol. Calcule a previsão para amanhã e para depois de amanhã.
14. Encontre o *regime estacionário* : a [distribuição](https://one-course.com/books/math/2/pt/chapter/18-probabilidade-e-variaveis-aleatorias#def-g11-prob-rv) $v$ com $Mv = v$ (e entradas somando $1$ ). Que fração dos dias é de sol a longo prazo?
15. 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?
16. 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](#def-g12-matrix-matrix) de transição, encontre o regime estacionário e ordene as páginas.
17. 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.**

18. Duas grandezas acopladas obedecem a $u_{n+1} = 3u_n + v_n$ , $v_{n+1} = u_n + 3v_n$ , ou seja, à [matriz](#def-g12-matrix-matrix) $A$ do [Exercício 30.8](#exo-g12-matrix-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$ .
19. 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?
20. Finale — as três faces da [matriz](#def-g12-matrix-matrix) 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 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](#def-g12-matrix-matrix) não é comutativa — $B$ troca as colunas quando está à direita e as linhas quando está à esquerda.

**2.** [Determinante](https://one-course.com/books/math/2/pt/chapter/15-vetores-e-retas-no-plano#def-g11-vect-det) $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](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) 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](https://one-course.com/books/math/2/pt/chapter/15-vetores-e-retas-no-plano#def-g11-vect-det) $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](https://one-course.com/books/math/2/pt/chapter/29-aritmetica#def-g12-arith-divides) $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](#def-g12-matrix-matrix): 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](https://one-course.com/books/math/2/pt/chapter/18-probabilidade-e-variaveis-aleatorias#def-g11-prob-rv) de [probabilidade](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) completa, de modo que as [probabilidades](https://one-course.com/books/math/2/pt/chapter/9-probabilidade-e-amostragem#def-g10-proba-distribution) 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](https://one-course.com/books/math/2/pt/chapter/5-geometria-analitica#def-g10-coordgeom-system) nas quais o sistema acoplado se desfaz em [sequências](https://one-course.com/books/math/2/pt/chapter/20-sequencias#def-g12-seq-sequence) 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](https://one-course.com/books/math/2/pt/chapter/2-algebra-equacoes-e-inequacoes#def-g10-algebra-equation) matricial, resolvida por uma única inversa. Combinatória: as potências da [matriz de adjacência](#def-g12-matrix-graph) 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](https://one-course.com/books/math/2/pt/chapter/15-vetores-e-retas-no-plano#def-g11-vect-vector) de ordenação da web) são esses destinos. A álgebra linear, nos volumes de graduação, é a ciência exatamente disso.