Matemática universitária — Graduação 2 · Bachelor Year 2

3Redução de endomorfismos

Para entender um endomorfismo, procure as direções que ele apenas estica. Este capítulo constrói a maquinaria — autovalores, polinômios característico e minimal, o lema da decomposição em núcleos — e suas recompensas: critérios de diagonalização e de triangularização, Cayley–Hamilton, a decomposição de Dunford e o cálculo de potências e exponenciais de que o Capítulo 16 se alimentará. Em todo o capítulo, $E$ é um $K$ -espaço vetorial de dimensão finita ( $K = \R$ ou $\C$ ) e $u \in \mathcal{L}(E)$ , $n = \dim E$ .

3.1 Autovalores e autovetores

Definição 3.1

$\lambda \in K$ é um autovalor de $u$ quando $u(x) = \lambda x$ para algum $x \neq 0$ (um autovetor); o autoespaço é $E_\lambda(u) = \ker(u - \lambda\,\mathrm{id})$ . O conjunto dos autovalores é o espectro $\operatorname{Sp}(u)$ . Um subespaço $F$ é estável quando $u(F) \subseteq F$ ; os autoespaços são estáveis, e os subespaços estáveis permitem endomorfismos induzidos $u|_F$ .

Teorema 3.2 (Independência dos autoespaços)

Autovetores associados a autovalores dois a dois distintos formam uma família livre; equivalentemente, a soma dos autoespaços $E_{\lambda_1} + \dots + E_{\lambda_r}$ ( $\lambda_i$ distintos) é direta. Em particular, $u$ tem no máximo $n$ autovalores.

Demonstração. Por indução sobre $r$ . Suponha $x_1 + \dots + x_r = 0$ com $x_i \in E_{\lambda_i}$ , sendo o enunciado conhecido para $r - 1$ . Aplique $u$ e subtraia $\lambda_r$ vezes a relação:

\sum_{i=1}^{r-1} (\lambda_i - \lambda_r)\, x_i = 0 ,

logo, por indução, cada $(\lambda_i - \lambda_r)x_i = 0$ , isto é, $x_i = 0$ para $i < r$ , e então $x_r = 0$ . Somas diretas de espaços não nulos num espaço de dimensão $n$ têm no máximo $n$ parcelas. ∎

A matriz A = psmallmatrix2 & 1\\ 1 & 2 psmallmatrix agindo no plano: o vetor genérico e_1 é tirado de sua reta, mas as direções próprias v_1 = (1,1) e v_2 = (1,-1) são apenas esticadas — por 3 e por 1 (de modo que Av_2 = v_2: a imagem tracejada coincide com v_2). A diagonalização é a mudança para a base (v_1, v_2), na qual A se torna diag(3, 1). — A matriz $A = \left(\begin{smallmatrix}2 & 1\\ 1 & 2\end{smallmatrix}\right)$ agindo no plano: o vetor genérico $e_1$ é tirado de sua reta, mas as direções próprias $v_1 = (1,1)$ e $v_2 = (1,-1)$ são apenas esticadas — por $3$ e por $1$ (de modo que $Av_2 = v_2$ : a imagem tracejada coincide com $v_2$ ). A diagonalização é a mudança para a base $(v_1, v_2)$ , na qual $A$ se torna $\operatorname{diag}(3, 1)$ .

Definição 3.3 (Polinômio característico)

$\chi_u(X) = \det(X\,\mathrm{id} - u)$ — calculado em qualquer base como $\det(XI_n - A)$ , um polinômio mônico de grau $n$ , invariante por semelhança (Teorema 2.17). Suas raízes em $K$ são exatamente os autovalores ( $\lambda$ é autovalor $\iff u - \lambda\,\mathrm{id}$ não injetivo $\iff \chi_u(\lambda) = 0$ ), e

\chi_u(X) = X^n - (\operatorname{tr} u)\, X^{n-1} + \dots + (-1)^n \det u .

A multiplicidade algébrica $m_\lambda$ de um autovalor é sua multiplicidade como raiz de $\chi_u$ ; a multiplicidade geométrica é $\dim E_\lambda$ , e $1 \leq \dim E_\lambda \leq m_\lambda$ .

Demonstração dos fatos enunciados. As afirmações sobre os coeficientes: desenvolva $\det(XI - A)$ pela fórmula das permutações; a permutação identidade contribui com $\prod_i (X - a_{ii}) = X^n - (\sum a_{ii})X^{n-1} + \dots$ , e toda outra permutação fixa no máximo $n - 2$ posições diagonais, contribuindo com grau $\leq n - 2$ : os dois coeficientes de topo são os anunciados; $X = 0$ dá o termo constante $\det(-A) = (-1)^n\det A$ .

Geométrica $\leq$ algébrica: seja $d = \dim E_\lambda$ e complete uma base de $E_\lambda$ numa base de $E$ ; a matriz de $u$ é triangular superior por blocos com bloco superior esquerdo $\lambda I_d$ , logo $\chi_u(X) = (X - \lambda)^d\, \chi_{\text{(bloco inferior)}}(X)$ : a multiplicidade de $\lambda$ vale ao menos $d$ . ∎

Exemplo 3.4 (Mesmo $\chi$ , geometria diferente)

As matrizes

\begin{pmatrix}2 & 0\\ 0 & 2\end{pmatrix} \qquad\text{e}\qquad \begin{pmatrix}2 & 1\\ 0 & 2\end{pmatrix}

têm o mesmo polinômio característico $(X - 2)^2$ , o mesmo traço, o mesmo determinante, o mesmo espectro — e no entanto não são semelhantes: a primeira tem $E_2$ de dimensão $2$ (multiplicidade geométrica $2$ ), a segunda de dimensão $1$ . O polinômio característico enxerga apenas multiplicidades algébricas; as dimensões dos autoespaços são o invariante mais fino, e o polinômio minimal arbitra ( $X - 2$ contra $(X - 2)^2$ ). Moral para toda discussão de diagonalizabilidade: $\chi$ seleciona os candidatos, mas são os núcleos que depositam os votos.

Definição 3.5 (Diagonalizável, triangularizável)

$u$ é diagonalizável quando $E$ tem uma base de autovetores (matricialmente: semelhante a uma matriz diagonal); triangularizável quando sua matriz em alguma base é triangular superior.

Teorema 3.6 (Critérios de diagonalizabilidade)

As afirmações seguintes são equivalentes:

$u$ é diagonalizável;
$E = \bigoplus_{\lambda \in \operatorname{Sp} u} E_\lambda$ ;
$\chi_u$ se decompõe sobre $K$ e $\dim E_\lambda = m_\lambda$ para todo autovalor;
(suficiente, não necessária) $\chi_u$ tem $n$ raízes distintas em $K$ .

Demonstração. (1 $\iff$ 2): uma base de autovetores se separa em bases dos $E_\lambda$ e, reciprocamente, concatenar bases das parcelas diretas dá uma base de $E$ (o Teorema 3.2 torna a soma direta; a igualdade de dimensões faz dela o espaço todo).

(2 $\iff$ 3): na base diagonal, $\chi_u = \prod (X - \lambda)^{\dim E_\lambda}$ se decompõe com multiplicidades correspondentes. Reciprocamente, suponha que $\chi_u$ se decomponha com $\dim E_\lambda = m_\lambda$ em toda parte; então a soma direta dos autoespaços (direta pelo Teorema 3.2) tem dimensão

\sum_{\lambda}\dim E_\lambda = \sum_{\lambda} m_\lambda = \deg\chi_u = n ,

a igualdade do meio porque o grau de um polinômio que se decompõe é a soma das multiplicidades de suas raízes: a soma é todo o $E$ . Note onde cada hipótese trabalhou: a decomposição preencheu o grau, a igualdade das multiplicidades preencheu as dimensões.

(4 $\Rightarrow$ 1): $n$ autovalores distintos dão $n$ autovetores independentes (Teorema 3.2): uma base. ∎

Método 3.7 (Decidir a diagonalizabilidade)

Na prática, teste nesta ordem — cada etapa pode encerrar o serviço. (1) Um polinômio anulador com raízes simples e que se decompõe se apresenta sozinho ( $u^2 = \mathrm{id}$ , $u^2 = u$ , $u^k = \mathrm{id}$ )? Se sim: diagonalizável, sem cálculo algum (Corolário 3.17 adiante). (2) Calcule $\chi_u$ ; se ele tiver $n$ raízes distintas em $K$ : diagonalizável (Teorema 3.6 (4)). (3) Caso contrário, apenas para cada raiz múltipla $\lambda$ , compare $\dim\ker(u - \lambda\,\mathrm{id})$ com a multiplicidade $m_\lambda$ : qualquer déficit mata a diagonalizabilidade; a igualdade em toda parte a demonstra. Nunca calcule autoespaços de raízes simples (sua dimensão está forçada a ser $1$ ), e nunca triangularize só para decidir.

Exemplo 3.8 (A diagonalização posta a trabalhar)

$A = I + J = \left(\begin{smallmatrix}2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2\end{smallmatrix}\right)$ , com $J$ a matriz de uns: de $\operatorname{Sp}(J) = \{3, 0\}$ (Exemplo 2.19), $\operatorname{Sp}(A) = \{4, 1\}$ , com autoespaços $\R(1,1,1)$ e o plano $\{x + y + z = 0\}$ : dimensões $1 + 2 = 3$ , diagonalizável (Teorema 3.6 (2)). Potências sem nenhuma matriz de mudança de base: com $\Pi = J/3$ o projetor sobre $\R(1,1,1)$ ,

A = 4\,\Pi + 1\cdot(I - \Pi) \quad\Longrightarrow\quad A^k = 4^k\,\Pi + (I - \Pi) = \frac{4^k - 1}{3}\,J + I .

(Confira $k = 1$ : $\frac{4-1}3 J + I = A$ .) A lição final: quando os autoespaços estão visíveis, os projetores espectrais calculam potências mais depressa do que $PDP^{-1}$ jamais fará — e a fórmula exibe a dinâmica: $A^k$ cresce como $4^k$ ao longo de $(1,1,1)$ e fica parado no plano ortogonal.

Teorema 3.9 (Triangularização)

$u$ é triangularizável sobre $K$ se e somente se $\chi_u$ se decompõe sobre $K$ . Em particular, todo endomorfismo de um $\C$ -espaço vetorial é triangularizável.

Demonstração. ( $\Rightarrow$ ) O polinômio característico de uma matriz triangular é $\prod(X - t_{ii})$ : decompõe-se.

( $\Leftarrow$ ) Indução sobre $n$ . Como $\chi_u$ se decompõe, ele tem uma raiz $\lambda$ : escolha um autovetor $e_1$ . Numa base que começa por $e_1$ , a matriz é $\begin{pmatrix} \lambda & \ast\\ 0 & B\end{pmatrix}$ , e $\chi_u = (X - \lambda)\chi_B$ : $\chi_B$ também se decompõe. Pela hipótese de indução aplicada à matriz $(n-1) \times (n-1)$ $B$ , existe uma $Q$ invertível com $Q^{-1}BQ$ triangular superior; conjugar a matriz inteira por $\begin{pmatrix}1 & 0\\ 0 & Q\end{pmatrix}$ a triangulariza. ∎

Exemplo 3.10 (Triangularizando à mão)

$B = \begin{pmatrix}3 & -1\\ 1 & 1\end{pmatrix}$ : $\chi_B = X^2 - 4X + 4 = (X - 2)^2$ , e $\ker(B - 2I) = \ker\left(\begin{smallmatrix}1 & -1\\ 1 & -1\end{smallmatrix}\right)$ é a reta gerada por $e_1' = (1, 1)$ : um único autovalor, um autoespaço de dimensão um — não diagonalizável, mas triangularizável (Teorema 3.9). Complete a base com $e_2' = (1, 0)$ e calcule:

u(e_1') = (2, 2) = 2e_1', \qquad u(e_2') = (3, 1) = 1\cdot e_1' + 2\, e_2' ,

de modo que, na base $(e_1', e_2')$ , a matriz é $T = \left(\begin{smallmatrix}2 & 1\\ 0 & 2\end{smallmatrix}\right)$ . A lição final: a diagonal de $T$ estava forçada (as duas entradas têm de ser o autovalor duplo $2$ ); só a entrada do canto dependia da escolha de $e_2'$ , e reescalar $e_2'$ pode torná-la qualquer valor não nulo — o resistente “ $1$ ” é a sombra da parte nilpotente que Dunford vai isolar.

3.2 Polinômios de um endomorfismo

Definição 3.11

Para $P = \sum a_k X^k \in K[X]$ , ponha $P(u) = \sum a_k u^k \in \mathcal{L}(E)$ . A aplicação $P \mapsto P(u)$ é um morfismo de álgebras $K[X] \to \mathcal{L}(E)$ (Definição 1.33); seu núcleo $\{P : P(u) = 0\}$ é um ideal de $K[X]$ , não nulo (a família $(\mathrm{id}, u, \dots, u^{n^2})$ é ligada no $n^2$ de dimensão $\mathcal{L}(E)$ ), logo gerado por um único polinômio mônico $\mu_u$ : o polinômio minimal (Teorema 1.26).

Proposição 3.12

$P(u) = 0 \iff \mu_u \mid P$ ; os autovalores de $u$ são raízes de todo polinômio anulador, e as raízes de $\mu_u$ são exatamente os autovalores.
Se $F$ é estável, $\mu_{u|_F} \mid \mu_u$ .

Demonstração. (1) A divisibilidade é a definição de gerador. Se $u(x) = \lambda x$ , $x \neq 0$ , então $0 = P(u)(x) = P(\lambda)x$ , logo $P(\lambda) = 0$ : os autovalores são raízes dos anuladores, em particular de $\mu_u$ . Reciprocamente, se $\lambda$ é raiz, $\mu_u = (X - \lambda)Q$ com $Q(u) \neq 0$ (o grau de $\mu_u$ é mínimo): escolha $y$ com $Q(u)(y) \neq 0$ ; então $(u - \lambda)(Q(u)(y)) = \mu_u(u)(y) = 0$ exibe o autovetor $Q(u)(y)$ .

(2) $\mu_u(u|_F) = \mu_u(u)|_F = 0$ , e aplique (1) a $u|_F$ . ∎

Exemplo 3.13 (Polinômios minimais achados à mão)

O polinômio minimal se calcula testando graus sucessivos. Para a matriz de uns $J \in \mathcal{M}_3(\R)$ : $J \neq \lambda I$ (o grau $1$ está fora), e $J^2 = 3J$ , logo

\mu_J = X^2 - 3X = X(X - 3) :

grau $2$ , decompõe-se, raízes simples — $J$ é diagonalizável com espectro $\{0, 3\}$ (Corolário 3.17 adiante), confirmando Exemplo 2.19 sem um único determinante. Para a matriz de troca $A$ de Exemplo 3.15: $A \neq \pm I$ e $A^2 = I$ dão $\mu_A = X^2 - 1$ . Nos dois casos o padrão é o mesmo: adivinhe uma identidade de grau baixo a partir da estrutura (o posto um força $J^2 = (\operatorname{tr}J)\,J$ ; uma involução força $A^2 = I$ ) e depois verifique que nenhum divisor próprio anula. Os polinômios minimais são em geral achados, e não calculados a partir de $\chi$ .

Teorema 3.14 (Lema da decomposição em núcleos)

Se $P = P_1 P_2 \cdots P_r$ com os $P_i$ dois a dois coprimos, então

\ker P(u) = \ker P_1(u) \oplus \dots \oplus \ker P_r(u),

e as projeções sobre as parcelas são polinômios em $u$ .

Demonstração. Basta tratar o caso $r = 2$ e fazer indução. Bézout em $K[X]$ (Teorema 1.26): $U P_1 + V P_2 = 1$ , de modo que, para todo $x$ ,

x = \underbrace{U(u)P_1(u)(x)}_{=:\,x_2} + \underbrace{V(u)P_2(u)(x)}_{=:\,x_1}.

Se $x \in \ker P(u)$ : $P_2(u)(x_2) = U(u)\,P(u)(x) = 0$ (polinômios em $u$ comutam), logo $x_2 \in \ker P_2(u)$ e, simetricamente, $x_1 \in \ker P_1(u)$ : a soma preenche $\ker P(u)$ ; as duas parcelas ficam dentro de $\ker P(u)$ ( $P_i \mid P$ ). Diretividade: $x \in \ker P_1(u) \cap \ker P_2(u)$ dá $x = U(u)P_1(u)x + V(u)P_2(u)x = 0$ . As fórmulas para $x_1, x_2$ exibem as projeções como $V(u)P_2(u)$ e $U(u)P_1(u)$ . ∎

Exemplo 3.15 (O lema dos núcleos com projetores explícitos)

Seja $A = \left(\begin{smallmatrix}0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{smallmatrix}\right)$ (troca as duas primeiras coordenadas). Então $A^2 = I$ : o polinômio $X^2 - 1 = (X - 1)(X + 1)$ anula $A$ , seus fatores são coprimos e Bézout é explícito:

\frac{1}{2}(X + 1) - \frac12(X - 1) = 1 .

Seguindo a demonstração do Teorema 3.14, as projeções sobre $\ker(A - I)$ e $\ker(A + I)$ são os polinômios em $A$

\pi_+ = \frac{A + I}{2} = \frac12\begin{pmatrix} 1 & 1 & 0\\ 1 & 1 & 0\\ 0 & 0 & 2\end{pmatrix}, \qquad \pi_- = \frac{I - A}{2} = \frac12\begin{pmatrix} 1 & -1 & 0\\ -1 & 1 & 0\\ 0 & 0 & 0\end{pmatrix}.

Verificação: $\pi_+ + \pi_- = I$ , $\pi_+\pi_- = 0$ , $\pi_\pm^2 = \pi_\pm$ , e as imagens são o plano $\{x = y\}$ (vetores simétricos, autovalor $1$ ) e a reta $\R(1, -1, 0)$ (antissimétricos, autovalor $-1$ ). O lema dos núcleos não é um enunciado de existência: os coeficientes de Bézout são as fórmulas dos projetores.

Exemplo 3.16 (Os projetores também calculam a exponencial)

A mesma matriz de troca, um dividendo adiante. Como $A = \pi_+ - \pi_-$ com projetores ortogonais no sentido algébrico ( $\pi_+\pi_- = 0$ ), toda potência obedece a $A^k = \pi_+ + (-1)^k\pi_-$ , e a série exponencial se reagrupa por projetor:

\eu^{tA} = \sum_k \frac{t^k}{k!}\bigl(\pi_+ + (-1)^k\pi_-\bigr) = \eu^{t}\,\pi_+ + \eu^{-t}\,\pi_- = \begin{pmatrix} \cosh t & \sinh t & 0\\ \sinh t & \cosh t & 0\\ 0 & 0 & \eu^{t} \end{pmatrix}.

(Confira $t = 0$ : a identidade; derivada em $0$ : $A$ .) A decomposição espectral converte uma série de matrizes em duas séries escalares — exatamente o mecanismo que o Capítulo 16 vai acionar em todo sistema diagonalizável, e a razão pela qual as funções hiperbólicas governam acoplamentos simétricos.

Corolário 3.17 (Diagonalizabilidade pelo polinômio minimal)

$u$ é diagonalizável $\iff$ $\mu_u$ se decompõe sobre $K$ com raízes simples $\iff$ algum polinômio anulador de $u$ se decompõe com raízes simples.

Demonstração. Se $P(u) = 0$ com $P = \prod_{i}(X - \lambda_i)$ ( $\lambda_i$ distintos), o lema dá $E = \ker P(u) = \bigoplus_i \ker(u - \lambda_i)$ : uma soma direta de autoespaços, logo $u$ é diagonalizável (Teorema 3.6). Reciprocamente, um $u$ diagonalizável é anulado por $\prod_{\lambda \in \operatorname{Sp}u}(X - \lambda)$ (que anula cada autoespaço), o qual se decompõe com raízes simples; e $\mu_u$ o divide tendo as mesmas raízes (Proposição 3.12): $\mu_u$ é exatamente esse produto. ∎

Exemplo 3.18

As projeções satisfazem $p^2 = p$ : anuladas por $X(X-1)$ , que se decompõe com raízes simples — diagonalizáveis com espectro $\subseteq \{0, 1\}$ , e $E = \ker p \oplus \ker(p - \mathrm{id})$ : a análise geométrica do primeiro ano, redemonstrada em uma linha. As simetrias ( $s^2 = \mathrm{id}$ , anulador $X^2 - 1$ ): diagonalizáveis quando $\operatorname{char} K \neq 2$ , espectro $\subseteq \{\pm 1\}$ . Um endomorfismo com $u^3 = u^2$ e $u^2 \neq u$ : anulado por $X^2(X - 1)$ , não necessariamente diagonalizável — o critério o detecta (a raiz dupla $0$ precisa ser testada: diagonalizável se e somente se além disso $\ker u^2 = \ker u$ ).

Exemplo 3.19 (O corpo decide: uma rotação em $\R^3$ )

Seja $R$ o quarto de volta em torno do eixo $z$ :

R = \begin{pmatrix} 0 & -1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}, \qquad \chi_R = (X - 1)(X^2 + 1).

Sobre $\R$ : o único autovalor é $1$ , com autoespaço igual ao eixo $\R e_3$ — uma reta de vetores fixos e nenhuma outra redução: $R$ não é diagonalizável nem triangularizável em $\mathcal{M}_3(\R)$ ( $\chi_R$ não se decompõe). Sobre $\C$ : três autovalores distintos $1, \iu, -\iu$ , de modo que $R$ é diagonalizável, com autovetores $e_3$ e $e_1 \mp \iu e_2$ . A geometria era audível na álgebra: as rotações do plano não têm direções invariantes reais, e os autovalores complexos $\pm\iu$ de módulo $1$ guardam o ângulo ( $\pm\frac\pi2$ ) que a matriz real só consegue exprimir misturando coordenadas.

Exemplo 3.20 (Minimal contra característico)

Para $D = \operatorname{diag}(2, 2, 3)$ : $\chi_D = (X - 2)^2(X - 3)$ mas $\mu_D = (X - 2)(X - 3)$ , pois $(D - 2I)(D - 3I) = 0$ (verifique na base canônica), ao passo que nenhum dos fatores sozinho anula $D$ . Para o bloco de deslocamento $N = \left(\begin{smallmatrix}0 & 1\\ 0 & 0\end{smallmatrix}\right) \oplus (3)$ , isto é, $N' = \left(\begin{smallmatrix}0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 3\end{smallmatrix}\right)$ : $\chi_{N'} = X^2(X - 3)$ e $\mu_{N'} = X^2(X - 3)$ — a raiz dupla é genuinamente necessária, pois $N'$ não é diagonalizável do lado $\ker$ ( $N'e_2 = e_1 \neq 0$ ). Regra prática: $\mu$ e $\chi$ têm as mesmas raízes (Proposição 3.12); a multiplicidade em $\mu$ mede o tamanho do maior bloco nilpotente, e a de $\chi$ a dimensão total do subespaço característico.

Teorema 3.21 (Cayley–Hamilton)

$\chi_u(u) = 0$ ; por consequência, $\mu_u \mid \chi_u$ e $\deg \mu_u \leq n$ .

Demonstração. Fixe $x \neq 0$ e seja $d$ maximal com $(x, u(x), \dots, u^{d-1}(x))$ livre; escreva

u^d(x) = -a_0 x - a_1 u(x) - \dots - a_{d-1}u^{d-1}(x),

e ponha $P_x = X^d + a_{d-1}X^{d-1} + \dots + a_0$ , de modo que $P_x(u)(x) = 0$ . Complete a família livre numa base de $E$ : nela, $u$ tem a forma por blocos $\begin{pmatrix} C & \ast\\ 0 & D\end{pmatrix}$ , em que $C$ é a matriz companheira de $P_x$ , cujo polinômio característico é $P_x$ (desenvolva $\det(XI - C)$ ao longo da primeira coluna, por indução sobre $d$ ). Logo $\chi_u = P_x \cdot \chi_D$ , e

\chi_u(u)(x) = \chi_D(u)\bigl(P_x(u)(x)\bigr) = 0 .

O argumento vale para todo $x$ : $\chi_u(u) = 0$ . ∎

Exemplo 3.22 (Cayley–Hamilton em ação)

$A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ : $\chi_A = X^2 - 5X - 2$ , logo $A^2 = 5A + 2I$ . Toda potência de $A$ desaba para uma combinação de $I$ e $A$ :

A^4 = (5A + 2I)^2 = 25A^2 + 20A + 4I = 145A + 54I = \begin{pmatrix} 199 & 290\\ 435 & 634\end{pmatrix},

e a inversa vem de brinde: $A(A - 5I) = 2I$ dá

A^{-1} = \tfrac12(A - 5I) = \begin{pmatrix} -2 & 1\\ 3/2 & -1/2\end{pmatrix}.

A lição final: Cayley–Hamilton comprime toda a álgebra $K[A]$ em $\operatorname{Vect}(I, A, \dots, A^{n-1})$ — $\dim K[A] = \deg\mu_A \leq n$ , por maiores que sejam as potências de que você precise.

Observação 3.23 (Armadilhas comuns)

(i) Autovalores não se somam: $\operatorname{Sp}(A + B)$ não é $\operatorname{Sp}A + \operatorname{Sp}B$ , e uma soma de matrizes diagonalizáveis não precisa ser diagonalizável — $\left(\begin{smallmatrix}1 & 1\\ 0 & 0\end{smallmatrix}\right) + \left(\begin{smallmatrix}0 & 0\\ 0 & 1\end{smallmatrix}\right) = \left(\begin{smallmatrix}1 & 1\\ 0 & 1\end{smallmatrix}\right)$ é soma de duas matrizes diagonalizáveis (cada uma com autovalores distintos) e não é diagonalizável; só as famílias que comutam se comportam bem (Exercício 3.9). (ii) “ $\chi_u$ se decompõe” é uma hipótese sobre o corpo: uma rotação plana tem $\chi = X^2 - 2\cos\theta\,X + 1$ , que se decompõe sobre $\C$ , não sobre $\R$ — diagonalizável em $\mathcal{M}_2(\C)$ , não triangularizável em $\mathcal{M}_2(\R)$ . (iii) A desigualdade vai da geométrica $\leq$ à algébrica, nunca ao contrário; testar apenas $\dim E_\lambda \geq 1$ nada prova sobre a diagonalizabilidade. (iv) $\mu_u$ não é $\chi_u$ : a igualdade vale exatamente quando cada autovalor tem uma única cadeia de blocos (por exemplo, as matrizes companheiras, no problema de fim de semana deste capítulo); usar $\chi$ onde $\mu$ é necessário infla todo cálculo de potências. (v) As partes $d$ e $\nu$ de Dunford são polinômios em $u$ — uma decomposição $u = d' + \nu'$ com as propriedades certas mas com $d'\nu' \neq \nu'd'$ não é a de Dunford e nunca é única.

Observação 3.24 (Onde este capítulo é usado)

A redução é o cavalo de batalha do resto do livro: potências e exponenciais de matrizes movem os sistemas diferenciais lineares do Capítulo 16; o teorema espectral do Capítulo 12 é a diagonalização tornada ortogonal; as funções geradoras (Capítulo 23) redemonstram analiticamente as assintóticas de recorrência do problema de fim de semana deste capítulo. No volume do terceiro ano de graduação, o mesmo programa roda em dimensão infinita: a teoria espectral dos operadores compactos autoadjuntos, na qual sequências de autovalores substituem os espectros finitos, e a teoria de Perron–Frobenius das matrizes positivas, que explica por que os autovalores dominantes de problemas de contagem são positivos e simples.

3.3 Nilpotentes e a decomposição de Dunford

Proposição 3.25 (Endomorfismos nilpotentes)

Para $u$ com $\chi_u$ que se decompõe, as afirmações seguintes são equivalentes: $u^n = 0$ ; $u^k = 0$ para algum $k$ ; $\operatorname{Sp}(u) = \{0\}$ ; $\chi_u = X^n$ ; $u$ é triangularizável com diagonal nula. Um endomorfismo nilpotente tem $\mu_u = X^{\text{(índice de nilpotência)}}$ , e o índice satisfaz $\leq n$ .

Demonstração. $u^k = 0$ faz de todo autovalor uma raiz de $X^k$ : espectro $\{0\}$ (não vazio quando $\chi$ se decompõe — sobre $\C$ sempre). Então $\chi_u = X^n$ (todas as raízes nulas) e Cayley–Hamilton dá $u^n = 0$ ; a triangularização (Teorema 3.9) põe zeros na diagonal (a diagonal carrega os autovalores). Reciprocamente, seja $A$ estritamente triangular superior: $a_{ij} = 0$ para $j \leq i$ . Mostramos por indução que

(A^k)_{ij} = 0 \qquad \text{sempre que } j \leq i + k - 1,

isto é, cada potência empurra a região nula uma diagonal acima. Para $k = 1$ essa é a hipótese. Para o passo,

(A^{k+1})_{ij} = \sum_{\ell} (A^k)_{i\ell}\,a_{\ell j} ,

e cada termo se anula: ou $\ell \leq i + k - 1$ (o primeiro fator é $0$ por indução), ou $\ell \geq i + k$ , e nesse caso $j \leq i + k \leq \ell$ mata o segundo fator. Em $k = n$ a condição $j \leq i + n - 1$ vale para todos $i, j \leq n$ : $A^n = 0$ . O polinômio minimal divide $X^n$ e a anulação define o índice. ∎

Teorema 3.26 (Decomposição de Dunford)

Suponha que $\chi_u$ se decomponha sobre $K$ (automático para $K = \C$ ). Então existe um único par $(d, \nu)$ com

u = d + \nu, \qquad d \text{ diagonalizável}, \quad \nu \text{ nilpotente}, \quad d\nu = \nu d ,

e além disso $d$ e $\nu$ são polinômios em $u$ .

Demonstração. Existência. Escreva $\chi_u = \prod_{i=1}^{r} (X - \lambda_i)^{m_i}$ ( $\lambda_i$ distintos) e ponha $N_i = \ker(u - \lambda_i)^{m_i}$ , os subespaços característicos. Por Cayley–Hamilton e pelo lema dos núcleos (Teorema 3.14),

E = N_1 \oplus \dots \oplus N_r ,

com projeções $\pi_i$ polinomiais em $u$ ; cada $N_i$ é estável (polinômios em $u$ comutam com $u$ ). Defina $d = \sum_i \lambda_i \pi_i$ : um polinômio em $u$ , diagonalizável (ele age como $\lambda_i$ em $N_i$ , logo $E$ se decompõe em seus autoespaços). Então $\nu = u - d$ é um polinômio em $u$ (logo comuta com $d$ ) e, em cada $N_i$ , age como $u - \lambda_i$ , com $(u - \lambda_i)^{m_i} = 0$ aí: $\nu^{\max m_i} = 0$ em cada parcela, logo $\nu$ é nilpotente.

Unicidade. Seja $u = d' + \nu'$ outro par desse tipo. Como $d'$ e $\nu'$ comutam entre si, eles comutam com $u = d' + \nu'$ , logo com todo polinômio em $u$ — em particular com $d$ e $\nu$ . Então $d - d'$ é diagonalizável (duas aplicações diagonalizáveis que comutam são simultaneamente diagonalizáveis: Exercício 3.9) e é igual a $\nu' - \nu$ , que é nilpotente: se $\nu^k = 0$ e $\nu'^{k'} = 0$ , a comutatividade autoriza o desenvolvimento binomial

(\nu' - \nu)^{k + k' - 1} = \sum_{j=0}^{k+k'-1}\binom{k + k' - 1}{j} \,\nu'^{\,j}\,(-\nu)^{k + k' - 1 - j} ,

no qual todo termo morre: ou $j \geq k'$ (primeiro fator nulo), ou $k + k' - 1 - j \geq k$ (segundo fator nulo), e uma das duas condições sempre vale. Um nilpotente diagonalizável é nulo (seu espectro é $\{0\}$ e ele é diagonal em alguma base): $d = d'$ , $\nu = \nu'$ . ∎

Exemplo 3.27 (Potências e exponenciais)

$A = \begin{pmatrix} 3 & 1\\ -1 & 1\end{pmatrix}$ : $\chi_A = X^2 - 4X + 4 = (X-2)^2$ , um único autovalor $2$ , autoespaço de dimensão $1$ : não diagonalizável. Dunford: $D = 2I$ , $N = A - 2I = \begin{pmatrix} 1 & 1\\ -1 & -1\end{pmatrix}$ , $N^2 = 0$ . Então

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N , \qquad \eu^{tA} = \eu^{2t}(I + tN),

pelo binômio de Newton para elementos que comutam, resp. pela série exponencial (Capítulo 16) separada em parcelas que comutam. A redução transforma dinâmica matricial em dinâmica escalar.

Observação 3.28 (Perspectivas dentro deste volume)

A redução é um entroncamento; eis os quatro ramais a observar. No Capítulo 5, normas adaptadas transformam “todos os autovalores de módulo $< 1$ ” em “alguma norma de operador $< 1$ ”, fazendo os espectros governarem a convergência de potências e séries. No Capítulo 16, a receita do Exemplo 3.27 torna-se a solução geral de $X' = AX$ : Dunford separa $\eu^{tA}$ em blocos do tipo polinômio vezes exponencial, e a estabilidade se lê nas partes reais dos autovalores. No Capítulo 12, um produto escalar impõe o que a mera álgebra linear não consegue: as matrizes simétricas tornam-se ortogonalmente diagonalizáveis, sem nenhuma parte nilpotente. E no Capítulo 23, as assintóticas de autovalor dominante do problema de fim de semana deste capítulo reaparecem analiticamente, como a menor singularidade de uma função geradora — duas línguas para uma mesma taxa de crescimento.

3.4 Exercícios

Exercício 3.1 ★

Diagonalize (autovalores, bases dos autoespaços, $P$ invertível):

A = \begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix}, \qquad B = \begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0 \end{pmatrix}.

Solução

Solução de Exercício 3.1.

$A$ : $\chi_A = X^2 - 2X - 3 = (X - 3)(X + 1)$ . Autovetores: para $3$ : $(1,1)$ ; para $-1$ : $(1,-1)$ . Logo $P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ dá $P^{-1}AP = \operatorname{diag}(3, -1)$ .

$B = J - I$ , em que $J$ é a matriz de uns. $J$ tem posto $1$ com $Jv = 3v$ para $v = (1,1,1)$ e $Jw = 0$ no plano $x + y + z = 0$ : o espectro de $B$ é $\{2, -1\}$ com autoespaços $\operatorname{Vect}(1,1,1)$ (dimensão $1$ ) e $\{x + y + z = 0\}$ (dimensão $2$ , base $(1,-1,0), (1,0,-1)$ ). $P$ com essas três colunas dá $P^{-1}BP = \operatorname{diag}(2, -1, -1)$ .

Exercício 3.2 ★

Mostre que $C = \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}$ não é diagonalizável, de duas maneiras: pelos autoespaços e pelo polinômio minimal.

Solução

Solução de Exercício 3.2.

Autoespaços: $\chi_C = (X-1)^2$ , único autovalor $1$ ; $\ker(C - I) = \ker\begin{pmatrix} 0&1\\ 0&0\end{pmatrix}$ é a reta $\operatorname{Vect}(e_1)$ : dimensão $1 < 2 = m_1$ , logo não é diagonalizável (Teorema 3.6).

Polinômio minimal: $\mu_C$ divide $(X-1)^2$ e $C \neq I$ , logo $\mu_C = (X-1)^2$ : uma raiz dupla, logo não é diagonalizável (Corolário 3.17).

Exercício 3.3 ★

Seja $u$ tal que $u^2 - 5u + 6\,\mathrm{id} = 0$ . Prove que $u$ é diagonalizável, determine os espectros possíveis e calcule $u^k$ como combinação de $\mathrm{id}$ e $u$ .

Solução

Solução de Exercício 3.3.

$X^2 - 5X + 6 = (X-2)(X-3)$ : decompõe-se com raízes simples, logo $u$ é diagonalizável (Corolário 3.17), com $\operatorname{Sp}(u) \subseteq \{2, 3\}$ . Espectros possíveis: $\{2\}$ ( $u = 2\,\mathrm{id}$ ), $\{3\}$ ( $u = 3\,\mathrm{id}$ ) ou $\{2, 3\}$ .

Potências: procure $u^k = a_k\,\mathrm{id} + b_k\,u$ . Nos autoespaços, isso se lê $2^k = a_k + 2b_k$ e $3^k = a_k + 3b_k$ : resolvendo, $b_k = 3^k - 2^k$ , $a_k = 3\cdot2^k - 2\cdot 3^k$ :

u^k = (3\cdot 2^k - 2\cdot 3^k)\,\mathrm{id} + (3^k - 2^k)\, u .

(Válido para os três espectros: as identidades valem autovalor a autovalor.)

Exercício 3.4 ★★

Seja $u$ diagonalizável e $F$ um subespaço estável. Prove que $u|_F$ é diagonalizável (restrinja um polinômio anulador com raízes simples e que se decompõe).

Solução

Solução de Exercício 3.4.

$u$ diagonalizável: $P = \prod_{\lambda}(X - \lambda)$ sobre o espectro anula $u$ , decompõe-se e tem raízes simples. Então $P(u|_F) = P(u)|_F = 0$ : a restrição é anulada por um polinômio que se decompõe com raízes simples, logo é diagonalizável (Corolário 3.17).

Exercício 3.5 ★★

(Fibonacci) Seja $A = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ . Diagonalize $A$ sobre $\R$ e deduza a fórmula de Binet para a sequência de Fibonacci ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+1} = F_n + F_{n-1}$ ):

F_n = \frac{\varphi^n - \psi^n}{\sqrt 5}, \qquad \varphi = \frac{1 + \sqrt5}{2},\ \psi = \frac{1 - \sqrt5}{2}.

Solução

Solução de Exercício 3.5.

$\chi_A = X^2 - X - 1$ , de raízes $\varphi$ e $\psi$ (distintas): diagonalizável, com autovetores $(\varphi, 1)$ e $(\psi, 1)$ . A recorrência dá $\begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = A^n \begin{pmatrix}1\\ 0\end{pmatrix}$ . Decomponha $(1, 0)$ nos autovetores: $(1,0) = \frac{1}{\varphi - \psi}\bigl((\varphi, 1) - (\psi, 1)\bigr)$ com $\varphi - \psi = \sqrt5$ . Aplicar $A^n$ multiplica cada componente própria pela $n$ -ésima potência de seu autovalor; lendo a segunda coordenada:

F_n = \frac{\varphi^n - \psi^n}{\sqrt 5} .

(Confira: $n = 1$ dá $\frac{\varphi - \psi}{\sqrt5} = 1$ .)

Exercício 3.6 ★★

Sejam $u \in \mathcal{L}(E)$ com $u^2$ diagonalizável e $u$ invertível ( $K = \C$ ). Prove que $u$ é diagonalizável. Dê um contraexemplo quando $u$ não é invertível.

Solução

Solução de Exercício 3.6.

Seja $P = \prod_i (X - \mu_i)$ um anulador de $u^2$ que se decompõe com raízes simples $\mu_i$ (o espectro de $u^2$ ). Como $u$ é invertível, $0$ não é autovalor de $u^2$ ( $\det u^2 = (\det u)^2 \neq 0$ ), logo todos os $\mu_i \neq 0$ . Então

Q(X) = \prod_i (X^2 - \mu_i) = \prod_i (X - \sqrt{\mu_i})(X + \sqrt{\mu_i})

anula $u$ : $\;Q(u) = \prod_i (u^2 - \mu_i\,\mathrm{id}) = P(u^2) = 0$ . Suas raízes $\pm \sqrt{\mu_i}$ (raízes quadradas complexas) são duas a duas distintas porque os $\mu_i$ são distintos e não nulos ( $\sqrt{\mu_i} = -\sqrt{\mu_j}$ daria $\mu_i = \mu_j$ ). Decompõe-se com raízes simples: $u$ é diagonalizável.

Contraexemplo sem invertibilidade: $u = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : $u^2 = 0$ é diagonalizável, $u$ não é.

Exercício 3.7 ★★

Calcule a decomposição de Dunford, $A^k$ e $\eu^{tA}$ para

A = \begin{pmatrix} 2 & 1 & 0\\ 0 & 2 & 1\\ 0 & 0 & 2 \end{pmatrix}.

Solução

Solução de Exercício 3.7.

$A = 2I + N$ com $N$ o deslocamento ( $N e_2 = e_1$ , $Ne_3 = e_2$ ), $N^3 = 0$ , $N^2 = E_{13}$ : isso é a decomposição de Dunford ( $2I$ diagonal, $N$ nilpotente, e comutam; a unicidade faz dela a decomposição). Binômio com termos que comutam:

A^k = 2^k I + k 2^{k-1} N + \binom k2 2^{k-2} N^2 = \begin{pmatrix} 2^k & k2^{k-1} & \binom k2 2^{k-2}\\ 0 & 2^k & k2^{k-1}\\ 0 & 0 & 2^k \end{pmatrix},

\eu^{tA} = \eu^{2t}\Bigl(I + tN + \frac{t^2}{2}N^2\Bigr) = \eu^{2t}\begin{pmatrix} 1 & t & t^2/2\\ 0 & 1 & t\\ 0 & 0 & 1 \end{pmatrix}.

Exercício 3.8 ★★

Seja $A \in \mathcal{M}_n(\C)$ com $A^k = I$ para algum $k \geq 1$ . Prove que $A$ é diagonalizável e que seus autovalores são raízes $k$ -ésimas da unidade. Deduza que uma matriz complexa invertível de ordem finita semelhante a uma matriz triangular com diagonal de uns é a identidade.

Solução

Solução de Exercício 3.8.

$X^k - 1$ anula $A$ e se decompõe sobre $\C$ com as $k$ raízes distintas $\eu^{2\iu\pi j/k}$ : $A$ é diagonalizável (Corolário 3.17) e seus autovalores, raízes de $X^k - 1$ , são raízes $k$ -ésimas da unidade.

Se além disso $A$ é semelhante a uma matriz triangular com diagonal de uns: todos os autovalores valem $1$ , e $A$ , diagonalizável com único autovalor $1$ , é $P\,I\,P^{-1} = I$ .

Exercício 3.9 ★★★

(Diagonalização simultânea) Sejam $u, v$ diagonalizáveis e que comutam. Prove que eles são simultaneamente diagonalizáveis: alguma base diagonaliza os dois. (Cada autoespaço de $u$ é estável por $v$ ; diagonalize aí as restrições de $v$ , usando Exercício 3.4.)

Solução

Solução de Exercício 3.9.

Escreva $E = \bigoplus_\lambda E_\lambda(u)$ (Teorema 3.6). Cada $E_\lambda(u)$ é estável por $v$ : para $x \in E_\lambda$ , $u(v(x)) = v(u(x)) = \lambda v(x)$ . A restrição de $v$ a $E_\lambda(u)$ é diagonalizável (Exercício 3.4): escolha uma base de $E_\lambda(u)$ formada de autovetores de $v$ . Concatenando essas bases sobre todos os $\lambda$ obtém-se uma base de $E$ cujos vetores são autovetores de ambos $u$ (por pertencerem a $E_\lambda(u)$ ) e $v$ (por construção).

Exercício 3.10 ★★★

Seja $u \in \mathcal{L}(\C^n)$ . Prove que $u$ é diagonalizável se e somente se todo subespaço $u$ -estável tem um subespaço suplementar $u$ -estável. (Para $\Leftarrow$ : aplique a propriedade a $F = \sum_\lambda E_\lambda(u)$ , a soma de todos os autoespaços; se um suplementar estável $G$ fosse não nulo, triangularizar $u|_G$ produziria um autovetor de $u$ dentro de $G$ — contradizendo $G \cap F = \{0\}$ .)

Solução

Solução de Exercício 3.10.

( $\Rightarrow$ ) Seja $u$ diagonalizável e $F$ estável. Então $u|_F$ é diagonalizável (Exercício 3.4): $F$ tem uma base de autovetores, que se estende, dentro de cada autoespaço global $E_\lambda$ , a uma base de $E_\lambda$ (teorema da base incompleta dentro de $E_\lambda$ , partindo da parte da base de $F$ que aí se encontra — note que $F = \bigoplus_\lambda (F \cap E_\lambda)$ , pois $u|_F$ é diagonalizável). Os vetores acrescentados geram um suplementar estável (cada um está em algum $E_\lambda$ , logo o espaço que geram é estável por $u$ ).

( $\Leftarrow$ ) Seja $F = \sum_\lambda E_\lambda(u)$ (um subespaço estável) e $G$ um suplementar estável. Se $G \neq \{0\}$ : $\chi_{u|_G}$ se decompõe sobre $\C$ , logo $u|_G$ tem um autovetor $x \in G$ (Teorema 3.9 ou diretamente a existência de uma raiz); mas todo autovetor de $u$ está em $F$ , logo $x \in F \cap G = \{0\}$ : contradição. Portanto $G = \{0\}$ e $E = F$ : os autoespaços preenchem $E$ , isto é, $u$ é diagonalizável.

Exercício 3.11 ★★★

(Raio espectral à la Gelfand, $2\times2$ aperitivo da análise que vem) Seja $A \in \mathcal{M}_2(\C)$ com os dois autovalores de módulo $< 1$ . Prove que $A^k \to 0$ entrada a entrada quando $k \to \infty$ . (Triangularize: $A = P(T)P^{-1}$ com $T$ triangular superior; calcule $T^k$ explicitamente — distinga autovalores iguais e distintos — e majore.)

Solução

Solução de Exercício 3.11.

Triangularize: $A = PTP^{-1}$ , $T = \begin{pmatrix} \lambda & c\\ 0 & \mu\end{pmatrix}$ , $\abs\lambda, \abs\mu < 1$ . Então $A^k = PT^kP^{-1}$ , e basta que $T^k \to 0$ .

Autovalores distintos: a indução dá

T^k = \begin{pmatrix} \lambda^k & c\,\dfrac{\lambda^k - \mu^k}{\lambda - \mu}\\[4pt] 0 & \mu^k \end{pmatrix},

e cada entrada tende a $0$ ( $\abs{\lambda}^k, \abs\mu^k \to 0$ ).

Autovalores iguais ( $\mu = \lambda$ ): $T = \lambda I + cE_{12}$ e $T^k = \lambda^k I + k\lambda^{k-1}cE_{12}$ ; a entrada $k\lambda^{k-1} \to 0$ , pois $\abs\lambda < 1$ (a geométrica vence a polinomial). Nos dois casos $T^k \to 0$ entrada a entrada, logo $A^k = PT^kP^{-1} \to 0$ (a multiplicação matricial por $P, P^{-1}$ fixas é contínua nas entradas — cada entrada do produto é uma combinação linear fixa).

Exercício 3.12 ★★

Seja $u \in \mathcal{L}(\C^n)$ com $\operatorname{rk} u = 1$ ( $n \geq 2$ ). Mostre que $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ e que $u$ é diagonalizável se e somente se $\operatorname{tr} u \neq 0$ . (Lembre do Exercício 2.5 que $u^2 = (\operatorname{tr} u)\,u$ .)

Solução

Solução de Exercício 3.12.

$\ker u$ tem dimensão $n - 1$ (teorema do núcleo e da imagem), logo $0$ é autovalor de multiplicidade geométrica $n - 1$ , e $\chi_u$ é divisível por $X^{n-1}$ (Definição 3.3: geométrica $\leq$ algébrica). Escreva $\chi_u = X^{n-1}(X - \alpha)$ ; sendo o coeficiente de $X^{n-1}$ igual a $-\operatorname{tr} u$ , obtemos $\alpha = \operatorname{tr} u$ : $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ .

Se $\operatorname{tr} u \neq 0$ : o autovalor $\operatorname{tr} u$ é raiz de $\chi_u$ , logo carrega um autovetor; os autoespaços de $0$ e de $\operatorname{tr} u$ têm dimensões $n - 1$ e $\geq 1$ , com soma $\geq n$ : eles preenchem $E$ , e $u$ é diagonalizável (Teorema 3.6). Se $\operatorname{tr} u = 0$ : pelo Exercício 2.5, $u^2 = (\operatorname{tr} u)u = 0$ com $u \neq 0$ : $u$ é um nilpotente não nulo, e um nilpotente diagonalizável é nulo (Proposição 3.25): não é diagonalizável.

3.5 Problema: recorrências lineares e matrizes companheiras

Uma recorrência linear $u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_0 u_n$ é uma potência de matriz disfarçada, e a redução a converte em fórmulas fechadas, taxas de crescimento e estimativas de erro. Este problema de fim de semana desenvolve o dicionário — matrizes companheiras de um lado, o operador de deslocamento no espaço das sequências do outro — demonstra o teorema fundamental das recorrências lineares (a solução geral é $\sum_i Q_i(n)\lambda_i^n$ sobre as raízes do polinômio característico) e gasta os dividendos em aproximação diofantina de $\sqrt2$ , na contagem de passeios e palavras, e num anel de sequências acopladas que só a diagonalização simultânea consegue desembaraçar.

Problema 3.1

Problema de fim de semana — o teorema fundamental das recorrências lineares

Fixe $k \geq 1$ , escalares $a_0, \dots, a_{k-1} \in \C$ com $a_0 \neq 0$ , o polinômio mônico $P = X^k - a_{k-1}X^{k-1} - \dots - a_1 X - a_0$ e a recorrência

(\mathcal R)\colon\quad u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_1 u_{n+1} + a_0 u_n \qquad (n \geq 0).

A matriz companheira de $P$ é

C = \begin{pmatrix} 0 & 1 & & \\ & \ddots & \ddots & \\ & & 0 & 1\\ a_0 & a_1 & \cdots & a_{k-1} \end{pmatrix} \in \mathcal{M}_k(\C).

Parte I — O dicionário companheiro.

Mostre que uma sequência $(u_n)$ satisfaz $(\mathcal R)$ se e somente se os vetores $v_n = (u_n, u_{n+1}, \dots, u_{n+k-1})^{\mathsf T}$ satisfazem $v_{n+1} = Cv_n$ , e portanto $v_n = C^n v_0$ .
Prove que $\chi_C = P$ (desenvolva $\det(XI - C)$ ao longo da primeira coluna e faça indução sobre $k$ ), e depois que também $\mu_C = P$ (passe a $C^{\mathsf T}$ , para o qual $e_1$ é cíclico, e note que uma matriz e sua transposta têm o mesmo polinômio minimal).
Mostre que, para cada raiz $\lambda$ de $P$ , o vetor $(1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ gera o autoespaço de $C$ associado a $\lambda$ ; deduza que todo autoespaço de $C$ tem dimensão $1$ e que $C$ é diagonalizável se e somente se $P$ tem $k$ raízes distintas.
Suponha que $P$ tenha raízes distintas $\lambda_1, \dots, \lambda_k$ . Mostre que as sequências geométricas $(\lambda_i^n)_n$ formam uma base do espaço das soluções de $(\mathcal R)$ , de modo que toda solução é $u_n = \sum_i c_i\lambda_i^n$ para constantes $c_i$ únicas.
Resolva completamente: $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ .

Parte II — O operador de deslocamento e o teorema fundamental. Seja $\mathcal{S}$ o $\C$ -espaço vetorial de todas as sequências complexas e $S \in \mathcal{L}(\mathcal{S})$ o deslocamento, $S\bigl((u_n)_n\bigr) = (u_{n+1})_n$ .

Mostre que o conjunto solução de $(\mathcal R)$ é $\ker P(S)$ e que ele tem dimensão exatamente $k$ (leve uma solução a seus valores iniciais).
Explique por que o lema da decomposição em núcleos (Teorema 3.14) se aplica a $S$ no espaço $\mathcal{S}$ de dimensão infinita sem nenhuma mudança, e escreva a decomposição resultante de $\ker P(S)$ para $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ ( $\lambda_i$ distintos, todos não nulos pois $a_0 \neq 0$ ).
Para $\lambda \neq 0$ e $m \geq 1$ , mostre que

$\ker\,(S - \lambda\,\mathrm{id})^m = \bigl\{\,\bigl(Q(n)\,\lambda^n\bigr)_n : Q \in \C_{m-1}[X]\,\bigr\},$

de dimensão $m$ . (Calcule $(S - \lambda)\bigl(Q(n)\lambda^n\bigr) = \lambda^{n+1}(\Delta Q)(n)$ com $\Delta Q = Q(X + 1) - Q(X)$ e use que $\Delta$ baixa o grau; para a dimensão, majore-a por $m$ pelos valores iniciais.)
(O teorema fundamental das recorrências lineares) Conclua: se $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ com os $\lambda_i$ distintos e não nulos, as soluções de $(\mathcal R)$ são exatamente as sequências

$u_n = \sum_{i=1}^{r} Q_i(n)\,\lambda_i^n, \qquad Q_i \in \C_{m_i - 1}[X],$

com polinômios $Q_i$ unicamente determinados.
Resolva completamente: $u_{n+2} = 4u_{n+1} - 4u_n$ , $u_0 = 1$ , $u_1 = 0$ , e confira a resposta em $u_2$ .

Parte III — Raízes dominantes e dividendos diofantinos.

Suponha as raízes simples com $\abs{\lambda_1} > \abs{\lambda_i}$ para $i \geq 2$ , e $u_n = \sum_i c_i \lambda_i^n$ com $c_1 \neq 0$ . Mostre que $u_n \sim c_1\lambda_1^n$ e $u_{n+1}/u_n \to \lambda_1$ .
(Pell) Defina $a_{n+1} = a_n + 2b_n$ , $b_{n+1} = a_n + b_n$ , $a_0 = b_0 = 1$ . Mostre que $q(a, b) = a^2 - 2b^2$ satisfaz $q(a_{n+1}, b_{n+1}) = -q(a_n, b_n)$ , logo $a_n^2 - 2b_n^2 = (-1)^{n+1}$ ; relacione isso com o determinante de $M = \left(\begin{smallmatrix}1 & 2\\ 1 & 1\end{smallmatrix}\right)$ .
Deduza a estimativa de erro

$\Bigl|\frac{a_n}{b_n} - \sqrt2\Bigr| = \frac{1}{b_n\,(a_n + \sqrt2\,b_n)} \leq \frac{1}{2b_n^2},$

e mostre que ela decai geometricamente com razão $3 - 2\sqrt2$ (ache os autovalores de $M$ e o crescimento de $b_n$ ).
(Crescimento geral) A partir da questão 9, prove: (a) se toda raiz satisfaz $\abs{\lambda_i} \leq \rho$ , então $\abs{u_n} \leq C\,n^{m-1}\rho^n$ com $m = \max_i m_i$ ; (b) se existe uma única raiz $\lambda_1$ de módulo máximo e $Q_1 \neq 0$ , então $u_{n+1}/u_n \to \lambda_1$ — confira isso na solução da questão 10.

Parte IV — Contando passeios e palavras. Para um grafo finito com conjunto de vértices $\{1, \dots, N\}$ , a matriz de adjacência $A$ tem $A_{ij} = 1$ se $ij$ é uma aresta, e $0$ caso contrário.

Prove que $(A^n)_{ij}$ é o número de passeios de comprimento $n$ de $i$ até $j$ (sequências de $n$ arestas, cada passo ao longo de uma aresta).
(O triângulo) Para o grafo completo com $3$ vértices, $A = J - I$ : usando o espectro de $J$ (Exemplo 2.19), mostre que

$(A^n)_{ii} = \frac{2^n + 2(-1)^n}{3}, \qquad (A^n)_{ij} = \frac{2^n - (-1)^n}{3} \quad (i \neq j),$

e confira os dois em $n = 2$ listando os passeios.
(Palavras sem $11$ ) Seja $w_n$ o número de palavras binárias de comprimento $n$ sem dois $1$ consecutivos. Codifique as palavras por sua última letra para obter uma matriz de transferência, mostre que $w_{n+2} = w_{n+1} + w_n$ , deduza $w_n = F_{n+2}$ (Fibonacci, Exercício 3.5) e dê a taxa de crescimento $\lim w_{n+1}/w_n$ .
(O caminho) Para o grafo caminho $1 - 2 - 3$ , mostre que os autovalores de $A$ são $\sqrt2, 0, -\sqrt2$ com autovetores $(1, \pm\sqrt2, 1)$ e $(1, 0, -1)$ , e deduza que o número de passeios de comprimento $n$ de uma ponta à outra é $\bigl((\sqrt2)^n + (-\sqrt2)^n\bigr)/4$ : zero para $n$ ímpar, e $2^{\,n/2 - 1}$ para $n$ par. Confira em $n = 4$ .
(Fórmula do traço) Mostre que o número total de passeios fechados de comprimento $n$ (todos os pontos de partida) é $\operatorname{tr}(A^n) = \sum_i \lambda_i^n$ , e verifique-o no triângulo.

Parte V — Um anel de sequências: diagonalização simultânea. Fixe $k \geq 3$ , seja $\omega = \eu^{2\iu\pi/k}$ e seja $W \in \mathcal{M}_k(\C)$ o deslocamento cíclico: $W e_i = e_{i+1}$ (índices módulo $k$ , colunas indexadas por $0, \dots, k-1$ ).

Mostre que $W^{\mathsf T}$ é a matriz companheira de $X^k - 1$ , deduza $\chi_W = \mu_W = X^k - 1$ e que $W$ é diagonalizável com os $k$ autovalores simples $\omega^j$ e autovetores $f_j = (1, \omega^{-j}, \omega^{-2j}, \dots, \omega^{-(k-1)j})^{\mathsf T}$ .
Uma matriz circulante é $C = c_0 I + c_1 W + \dots + c_{k-1}W^{k-1}$ . Mostre que todas as circulantes comutam, que a base $(f_0, \dots, f_{k-1})$ diagonaliza todas elas simultaneamente, e que os autovalores de $C$ são $\widehat c(\omega^j) = \sum_m c_m \omega^{jm}$ , $j = 0, \dots, k-1$ .
Deduza $\det C = \prod_{j=0}^{k-1} \widehat c(\omega^j)$ e verifique que $k = 3$ recupera a fatoração de Exercício 2.8.
(A média do colar) Seja $x^{(n+1)} = Mx^{(n)}$ com $M = \frac12(W + W^{-1})$ : cada um de $k$ números dispostos em anel é substituído pela média de seus dois vizinhos. Mostre que os autovalores de $M$ são $\cos(2\pi j/k)$ e que o coeficiente de $x^{(0)}$ em $f_0$ é a média $\frac1k\sum_m x^{(0)}_m$ (some as coordenadas dos $f_j$ ).
Conclua: para $k$ ímpar, $x^{(n)}$ converge para o vetor constante cujo valor é a média dos valores iniciais; para $k = 4$ , exiba o autovalor responsável pela não convergência e a obstrução exata (um coeficiente de média alternada que deve se anular).
(Síntese) Em uma frase cada: como a matriz companheira converte a análise de $(\mathcal R)$ em redução; onde o lema da decomposição em núcleos não precisou de dimensão finita; por que os autovalores dominantes governam as taxas de crescimento e o erro diofantino; por que as potências da matriz de adjacência contam passeios; e o que se ganha com matrizes que comutam. Nomeie os dois cumes: o teorema fundamental das recorrências lineares e — para as matrizes positivas da Parte IV, no volume do terceiro ano de graduação — o teorema de Perron–Frobenius.

Solução

Solução de Problema 3.1.

1. As $k - 1$ primeiras coordenadas de $Cv_n$ são $u_{n+1}, \dots, u_{n+k-1}$ (a superdiagonal desloca), e a última é $a_0 u_n + \dots + a_{k-1}u_{n+k-1}$ . Assim $v_{n+1} = Cv_n$ vale para todo $n$ se e somente se as últimas coordenadas coincidem para todo $n$ , isto é, se e somente se $(\mathcal R)$ vale. Iterando, $v_n = C^nv_0$ .

2. Desenvolva $D_k(X) = \det(XI_k - C)$ ao longo da primeira coluna: as duas entradas não nulas são $X$ (posição $(1,1)$ ) e $-a_0$ (posição $(k,1)$ ). O primeiro menor tem a forma $D_{k-1}$ para os coeficientes $a_1, \dots, a_{k-1}$ ; o segundo menor é triangular superior com diagonal $-1$ : determinante $(-1)^{k-1}$ , com sinal $(-1)^{k+1}$ vindo da posição. A indução sobre $k$ (base $k = 1$ : $X - a_0$ ) dá

D_k(X) = X\bigl(X^{k-1} - a_{k-1}X^{k-2} - \dots - a_1\bigr) - a_0 = P(X).

Para $\mu_C$ : como $Q(C^{\mathsf T}) = Q(C)^{\mathsf T}$ para qualquer polinômio, $C$ e $C^{\mathsf T}$ têm os mesmos anuladores, logo o mesmo polinômio minimal. Para $C^{\mathsf T}$ : as colunas se leem $C^{\mathsf T}e_1 = e_2$ , …, $C^{\mathsf T}e_{k-1} = e_k$ , de modo que $(e_1, C^{\mathsf T}e_1, \dots, (C^{\mathsf T})^{k-1}e_1)$ é a base canônica: livre. Um polinômio $Q \neq 0$ de grau $< k$ tem então $Q(C^{\mathsf T})e_1 \neq 0$ (é uma combinação não trivial de vetores da base): $\deg\mu \geq k$ . Como $\mu \mid \chi = P$ com $\deg P = k$ : $\mu_C = P$ .

3. Para $v = (1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ : as linhas $1$ a $k-1$ de $Cv$ dão $\lambda, \lambda^2, \dots, \lambda^{k-1}$ , isto é, $\lambda$ vezes as primeiras $k - 1$ entradas de $v$ ; a última linha dá $\sum_m a_m\lambda^m = \lambda^k - P(\lambda) = \lambda^k = \lambda\cdot\lambda^{k-1}$ . Logo $Cv = \lambda v$ . Reciprocamente, as equações $(Cx)_i = \lambda x_i$ para $i < k$ leem-se $x_{i+1} = \lambda x_i$ : todo autovetor é proporcional a $v$ — todo autoespaço tem dimensão exatamente $1$ . Diagonalizável se e somente se as dimensões dos autoespaços somam $k$ (Teorema 3.6), se e somente se há $k$ autovalores distintos, se e somente se $P$ tem $k$ raízes distintas (os autovalores são as raízes de $\chi_C = P$ ).

4. Cada $(\lambda_i^n)_n$ resolve $(\mathcal R)$ : $\lambda_i^{n+k} = \lambda_i^n\,\lambda_i^k = \lambda_i^n\sum_m a_m\lambda_i^m$ . Liberdade: uma combinação nula $\sum_i c_i\lambda_i^n = 0$ para $n = 0, \dots, k-1$ é um sistema de Vandermonde (Exercício 2.11) nos $c_i$ : todos os $c_i = 0$ . O espaço das soluções tem dimensão $k$ (questão 6, cuja demonstração é elementar e independente): $k$ soluções livres formam uma base, e as coordenadas são únicas.

5. $P = X^2 - X - 6 = (X - 3)(X + 2)$ : solução geral $u_n = A\,3^n + B(-2)^n$ . Condições iniciais: $A + B = 1$ , $3A - 2B = 8$ : $A = 2$ , $B = -1$ :

u_n = 2\cdot 3^n - (-2)^n .

(Confira: $u_2 = u_1 + 6u_0 = 14$ e $2\cdot9 - 4 = 14$ .)

6. $P(S)\bigl((u_n)\bigr)$ é a sequência $n \mapsto u_{n+k} - a_{k-1}u_{n+k-1} - \dots - a_0u_n$ : ela se anula se e somente se $(\mathcal R)$ vale, de modo que o conjunto solução é $\ker P(S)$ , um subespaço. A aplicação $\ker P(S) \to \C^k$ , $u \mapsto (u_0, \dots, u_{k-1})$ , é linear, injetiva (a recorrência determina $u_{k}, u_{k+1}, \dots$ a partir dos $k$ primeiros valores, por indução) e sobrejetiva (defina $u_n$ recursivamente a partir de dados iniciais quaisquer): dimensão $k$ .

7. A demonstração do Teorema 3.14 usa apenas: a identidade de Bézout em $\C[X]$ e o fato de que polinômios num endomorfismo fixo comutam. Nenhum dos dois menciona a dimensão do espaço ambiente: o lema vale palavra por palavra para $S \in \mathcal{L}(\mathcal{S})$ . Logo

\ker P(S) = \bigoplus_{i=1}^{r} \ker\,(S - \lambda_i\,\mathrm{id})^{m_i}.

8. Para $Q \in \C[X]$ : $(S - \lambda)\bigl(Q(n)\lambda^n\bigr)_n$ tem $n$ -ésimo termo $Q(n{+}1)\lambda^{n+1} - \lambda Q(n)\lambda^n = \lambda^{n+1}(\Delta Q)(n)$ , com $\Delta Q = Q(X{+}1) - Q(X)$ de grau $\deg Q - 1$ (os termos dominantes se cancelam). Iterando, $(S - \lambda)^m\bigl(Q(n)\lambda^n\bigr) = \bigl(\lambda^{n+m}(\Delta^m Q)(n)\bigr)_n$ , e $\Delta^m Q = 0$ quando $\deg Q \leq m - 1$ : o conjunto da direita está contido no núcleo. Ele é um subespaço de dimensão $m$ : as sequências $(n^j\lambda^n)_n$ , $0 \leq j < m$ , são livres, pois $\sum_j c_j n^j\lambda^n = 0$ para todo $n$ força (dividindo por $\lambda^n \neq 0$ ) o polinômio $\sum_j c_jX^j$ a se anular em todo $n \in \N$ , logo a ser nulo. Reciprocamente, $\dim\ker(S - \lambda)^m \leq m$ : desenvolvendo $(S - \lambda)^m = \sum_j \binom mj(-\lambda)^{m-j}S^j$ , a equação $(S - \lambda)^m u = 0$ é uma recorrência linear de ordem $m$ (coeficiente dominante $1$ ), de modo que $u$ fica determinada por $u_0, \dots, u_{m-1}$ como na questão 6. A igualdade das dimensões conclui.

9. Combine as questões 7 e 8: toda solução se decompõe de modo único como soma de elementos dos $\ker(S - \lambda_i)^{m_i}$ , isto é, $u_n = \sum_i Q_i(n)\lambda_i^n$ com $\deg Q_i \leq m_i - 1$ ; os $Q_i$ são únicos porque a decomposição é direta e, dentro de cada parcela, os coeficientes de $Q_i$ são coordenadas na base $(n^j\lambda_i^n)_j$ (questão 8). Verificação de bom senso nas dimensões: $\sum_i m_i = k$ .

10. $P = X^2 - 4X + 4 = (X - 2)^2$ : soluções $(a + bn)2^n$ . Dados iniciais: $a = 1$ , $2(a + b) = 0$ , logo $b = -1$ :

u_n = (1 - n)\,2^n .

Confira: $u_2 = 4u_1 - 4u_0 = -4$ e $(1 - 2)\cdot4 = -4$ .

11. Escreva $u_n = \lambda_1^n\bigl(c_1 + \sum_{i\geq2} c_i(\lambda_i/\lambda_1)^n\bigr)$ ; cada razão tem módulo $< 1$ , logo o colchete tende a $c_1 \neq 0$ : $u_n \sim c_1\lambda_1^n$ . Em particular $u_n \neq 0$ para $n$ grande, e

\frac{u_{n+1}}{u_n} = \lambda_1\,\frac{c_1 + o(1)}{c_1 + o(1)} \longrightarrow \lambda_1 .

12. Calcule:

q(a_{n+1}, b_{n+1}) = (a_n + 2b_n)^2 - 2(a_n + b_n)^2 = -a_n^2 + 2b_n^2 = -q(a_n, b_n).

Com $q(a_0, b_0) = 1 - 2 = -1$ : $a_n^2 - 2b_n^2 = (-1)^{n+1}$ . Estruturalmente: $q(a, b) = (a - \sqrt2\,b)(a + \sqrt2\,b)$ e a aplicação linear $M$ multiplica o fator $a + \sqrt2 b$ por $1 + \sqrt2$ e o fator $a - \sqrt2 b$ por $1 - \sqrt2$ (calcule: $a_{n+1} + \sqrt2 b_{n+1} = (1 + \sqrt2)(a_n + \sqrt2 b_n)$ ); o produto é multiplicado por $(1 + \sqrt2)(1 - \sqrt2) = -1 = \det M$ a cada passo.

13. Como $a_n^2 - 2b_n^2 = (a_n - \sqrt2 b_n)(a_n + \sqrt2 b_n) = (-1)^{n+1}$ ,

\Bigl|\frac{a_n}{b_n} - \sqrt2\Bigr| = \frac{\abs{a_n^2 - 2b_n^2}}{b_n(a_n + \sqrt2 b_n)} = \frac{1}{b_n(a_n + \sqrt2 b_n)} \leq \frac1{2b_n^2},

usando $a_n \geq b_n \geq 1$ (indução: ambos crescem), logo $a_n + \sqrt2 b_n \geq (1 + \sqrt2)b_n \geq 2b_n$ . Autovalores de $M$ : $\chi_M = X^2 - 2X - 1$ , de raízes $1 \pm \sqrt2$ ; como $(a_0, b_0)$ tem componente não nula no autovetor dominante (todas as entradas positivas), $b_n \sim c(1 + \sqrt2)^n$ com $c > 0$ (questão 11). Logo o erro é $\asymp (1 + \sqrt2)^{-2n} = (3 + 2\sqrt2)^{-n}$ : decaimento geométrico de razão $1/(3 + 2\sqrt2) = 3 - 2\sqrt2 \approx 0.172$ .

14. (a) Da questão 9: $\abs{u_n} \leq \sum_i \abs{Q_i(n)}\abs{\lambda_i}^n \leq \bigl(\sum_i \abs{Q_i(n)}\bigr)\rho^n$ , e cada $\abs{Q_i(n)} \leq C_i n^{m_i - 1} \leq C_i n^{m-1}$ para $n \geq 1$ : some as constantes. (b) Sejam $\rho' = \max_{i \geq 2}\abs{\lambda_i} < \abs{\lambda_1}$ e $d = \deg Q_1$ , de coeficiente dominante $c \neq 0$ . Então $u_n = Q_1(n)\lambda_1^n + R_n$ com $\abs{R_n} \leq Cn^{m-1}\rho'^n$ , e

\frac{R_n}{Q_1(n)\lambda_1^n} = O\Bigl(n^{m-1-d} \bigl(\rho'/\abs{\lambda_1}\bigr)^n\Bigr) \longrightarrow 0

(a geométrica vence a polinomial). Logo

u_n \sim Q_1(n)\,\lambda_1^n \sim c\,n^d\lambda_1^n, \qquad \frac{u_{n+1}}{u_n} \longrightarrow \lambda_1 \quad\text{(pois } Q_1(n{+}1)/Q_1(n) \to 1\text{)}.

Confira na questão 10: para $u_n = (1-n)2^n$ a razão é

\frac{(-n)2^{n+1}}{(1-n)2^n} = 2\,\frac{-n}{1-n} \longrightarrow 2 = \lambda_1 .

15. Indução sobre $n$ . Para $n = 1$ , $A_{ij}$ conta os passeios de comprimento $1$ . Passo: um passeio de comprimento $n + 1$ de $i$ a $j$ é um passeio de comprimento $n$ de $i$ até algum vértice $\ell$ seguido de uma aresta $\ell j$ :

\#\{\text{passeios}\} = \sum_{\ell} (A^n)_{i\ell}A_{\ell j} = (A^{n+1})_{ij}.

16. $J = 3\Pi$ , em que $\Pi = J/3$ é a projeção sobre $\operatorname{Vect}(1,1,1)$ ao longo do plano $x + y + z = 0$ ( $\Pi^2 = \Pi$ , pois $J^2 = 3J$ ). Então $A = J - I = 2\Pi - (I - \Pi)$ e, como $\Pi$ e $I - \Pi$ são projeções complementares,

A^n = 2^n\,\Pi + (-1)^n (I - \Pi), \qquad\text{i.e.}\qquad (A^n)_{ij} = \frac{2^n}3 + (-1)^n\Bigl(\delta_{ij} - \frac13\Bigr),

o que dá as duas fórmulas exibidas. Em $n = 2$ : diagonal $(4 + 2)/3 = 2$ (passeios $i \to \ell \to i$ para os dois vizinhos $\ell$ ); fora da diagonal $(4 - 1)/3 = 1$ (o único passeio $i \to \ell \to j$ pelo terceiro vértice).

17. Sejam $w_n^{(0)}, w_n^{(1)}$ o número de palavras admissíveis de comprimento $n$ terminadas em $0$ , resp. em $1$ . Acrescentando uma letra: um $0$ pode seguir qualquer coisa, um $1$ só pode seguir um $0$ :

\begin{pmatrix} w_{n+1}^{(0)}\\ w_{n+1}^{(1)}\end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix} \begin{pmatrix} w_n^{(0)}\\ w_n^{(1)}\end{pmatrix}.

Somando, $w_{n+2} = w_{n+1} + w_n$ (ou: condicione na primeira letra). Com $w_1 = 2$ , $w_2 = 3$ : $w_n = F_{n+2}$ por indução ( $F_3 = 2$ , $F_4 = 3$ , mesma recorrência). Crescimento: as raízes de $X^2 - X - 1$ são $\varphi > \abs\psi$ (Exercício 3.5), e a componente em $\varphi$ é não nula (os $w_n$ são positivos e $\psi^n \to 0$ ), logo a questão 11 dá $w_{n+1}/w_n \to \varphi = \frac{1 + \sqrt5}2$ .

18. $A = \left(\begin{smallmatrix} 0&1&0\\ 1&0&1\\ 0&1&0\end{smallmatrix}\right)$ . Verificação:

A(1, \pm\sqrt2, 1)^{\mathsf T} = (\pm\sqrt2, 2, \pm\sqrt2)^{\mathsf T} = \pm\sqrt2\,(1, \pm\sqrt2, 1)^{\mathsf T}, \qquad A(1, 0, -1)^{\mathsf T} = 0 :

autovalores $\sqrt2, -\sqrt2, 0$ ( $= 2\cos\frac\pi4, 2\cos\frac{3\pi}4, 2\cos\frac\pi2$ ). Decomponha $e_1$ na base de autovetores e leia a terceira coordenada, ou use a simetria: com $v_\pm = (1, \pm\sqrt2, 1)$ , $v_0 = (1, 0, -1)$ , verifica-se $e_1 = \frac14 v_+ + \frac14 v_- + \frac12 v_0$ , de modo que, para $n \geq 1$ ,

(A^n)_{13} = \Bigl(\tfrac14(\sqrt2)^n v_+ + \tfrac14(-\sqrt2)^n v_- + 0\Bigr)_{\!3} = \frac{(\sqrt2)^n + (-\sqrt2)^n}{4},

zero para $n$ ímpar (grafo bipartido: as pontas estão a distância par), e $2\cdot 2^{n/2}/4 = 2^{n/2 - 1}$ para $n$ par. Em $n = 4$ : $2^{1} = 2$ , o que corresponde aos dois passeios $1\,2\,1\,2\,3$ e $1\,2\,3\,2\,3$ .

19. Os passeios fechados de comprimento $n$ a partir de $i$ são $(A^n)_{ii}$ ; somando sobre $i$ obtém-se $\operatorname{tr}(A^n)$ . Triangularizando $A$ (sobre $\C$ ), $A^n$ é triangular com diagonal $\lambda_i^n$ : $\operatorname{tr}(A^n) = \sum_i\lambda_i^n$ . Triângulo: $\operatorname{tr}(A^n) = 3\,\frac{2^n + 2(-1)^n}3 = 2^n + 2(-1)^n = 2^n + (-1)^n + (-1)^n$ : o espectro $\{2, -1, -1\}$ , coerente com a questão 16.

20. As colunas de $W^{\mathsf T}$ : $W^{\mathsf T}e_i = e_{i-1}$ para $i \geq 1$ e $W^{\mathsf T}e_0 = e_{k-1}$ ; renomeando na ordem $e_0, e_1, \dots$ isso é exatamente a matriz companheira de $X^k - 1$ ( $a_0 = 1$ , os demais $a_m = 0$ ). Questão 2: $\chi_{W} = \chi_{W^{\mathsf T}} = X^k - 1 = \mu_{W}$ . As raízes $\omega^j$ ( $j = 0, \dots, k-1$ ) são as $k$ raízes $k$ -ésimas distintas da unidade: $W$ é diagonalizável (questão 3, ou Exercício 3.8: $W^k = I$ ). Autovetores: $Wf_j = \sum_m \omega^{-jm}e_{m+1} = \sum_{m'}\omega^{-j(m'-1)}e_{m'} = \omega^j f_j$ .

21. As circulantes são polinômios em $W$ , e polinômios numa matriz fixa comutam entre si. Cada $f_j$ é autovetor de toda potência: $W^m f_j = \omega^{jm}f_j$ , logo

Cf_j = \sum_m c_m\omega^{jm} f_j = \widehat c(\omega^j)\,f_j :

a base $(f_0, \dots, f_{k-1})$ (livre: Vandermonde nos $\omega^{-j}$ distintos, Exercício 2.11) diagonaliza todas as circulantes de uma só vez, com os autovalores enunciados.

22. O determinante é o produto dos autovalores (diagonalize): $\det C = \prod_{j}\widehat c(\omega^j)$ . Para $k = 3$ , $c_0 = a$ , $c_1 = b$ , $c_2 = c$ e $\omega = j = \eu^{2\iu\pi/3}$ :

\det C = (a + b + c)(a + bj + cj^2)(a + bj^2 + cj^4),

e $j^4 = j$ : exatamente a fatoração de Exercício 2.8.

23. $M = \frac12(W + W^{-1})$ é uma circulante ( $W^{-1} = W^{k-1}$ ), com autovalores $\frac12(\omega^j + \omega^{-j}) = \cos\frac{2\pi j}k$ na mesma base $f_j$ . Coordenadas: escreva $x^{(0)} = \sum_j \alpha_j f_j$ . As coordenadas de $f_j$ somam $\sum_m \omega^{-jm}$ , o que vale $k$ para $j = 0$ e $0$ caso contrário (soma geométrica de razão $\omega^{-j} \neq 1$ ). Somando as coordenadas de $x^{(0)}$ : $\sum_m x^{(0)}_m = \alpha_0\,k$ , logo $\alpha_0 = \frac1k\sum_m x^{(0)}_m$ , a média.

24. $x^{(n)} = M^nx^{(0)} = \sum_j \alpha_j\cos^n\bigl(\tfrac{2\pi j}k\bigr)f_j$ . Para $k$ ímpar, $\abs{\cos(2\pi j/k)} < 1$ para todo $j \neq 0$ (o ângulo nunca vale $0$ nem $\pi$ ), de modo que todos os termos exceto $j = 0$ tendem a $0$ : $x^{(n)} \to \alpha_0 f_0$ , o vetor constante igual à média — promediar num anel ímpar iguala tudo. Para $k = 4$ os autovalores são $1, 0, -1, 0$ : o termo $j = 2$ $\alpha_2(-1)^nf_2$ com $f_2 = (1, -1, 1, -1)^{\mathsf T}$ oscila para sempre. A obstrução é a média alternada: multiplicando as coordenadas de $x^{(0)}$ por $(-1)^m$ e somando, o mesmo cálculo de soma geométrica dá $\sum_m (-1)^mx^{(0)}_m = 4\alpha_2$ : o processo converge se e somente se $x^{(0)}_0 - x^{(0)}_1 + x^{(0)}_2 - x^{(0)}_3 = 0$ , e então converge para a média.

25. A matriz companheira converte uma recorrência escalar de ordem $k$ numa recorrência vetorial de primeira ordem, de modo que as fórmulas fechadas viram enunciados sobre $C^n$ — o terreno de casa da redução (questões 1–5). O lema da decomposição em núcleos é álgebra polinomial pura (Bézout mais comutação), logo ele reparte $\ker P(S)$ mesmo com $\mathcal{S}$ de dimensão infinita (questões 7–9). Os autovalores dominantes governam o crescimento porque toda outra contribuição é geometricamente desprezível após a normalização — e é também por isso que o erro de Pell decai como o quadrado da raiz dominante (questões 11–14). As potências da matriz de adjacência contam passeios porque a multiplicação de matrizes soma sobre os vértices intermediários, de modo que os espectros contam passeios fechados (questões 15–19). Matrizes que comutam compartilham uma base de autovetores, e uma única base de Fourier diagonaliza toda a álgebra das circulantes de um golpe só (questões 20–24). Cumes: o teorema fundamental das recorrências lineares (questão 9); e, para matrizes não negativas, a razão pela qual raízes dominantes como $\varphi$ ou $1 + \sqrt2$ são automaticamente reais, positivas e simples é o teorema de Perron–Frobenius, demonstrado no volume do terceiro ano de graduação.