Matemáticas universitarias — Grado 2 · Bachelor Year 2

3Reducción de endomorfismos

Para entender un endomorfismo, encuentre las direcciones que simplemente se estira. Este capítulo construye la maquinaria — valores propios, característica y polinomios mínimos, la descomposición del núcleo lema — y sus recompensas: diagonalización y trigonalización criterios, Cayley–Hamilton, el Descomposición de Dunford y el cálculo de potencias y exponenciales que Capítulo 16 se alimentará. En todo momento, $E$ es un espacio vectorial $K$ de dimensión finita ( $K = \R$ o $\C$ ) y $u \in \mathcal{L}(E)$ , $n = \dim E$ .

3.1 Valores propios y vectores propios

Definición 3.1

$\lambda \in K$ es un valor propio de $u$ cuando $u(x) = \lambda x$ para algunos $x \neq 0$ (un vector propio); el espacio propio es $E_\lambda(u) = \ker(u - \lambda\,\mathrm{id})$ . El conjunto de valores propios es el espectro $\operatorname{Sp}(u)$ . Un subespacio $F$ es estable cuando $u(F) \subseteq F$ ; los espacios propios son estables y los subespacios estables permiten endomorfismos inducidos $u|_F$ .

Teorema 3.2 (Independencia de espacios propios)

Vectores propios asociado con valores propios distintos por pares forman un familia libre; equivalentemente, la suma de espacios propios $E_{\lambda_1} + \dots + E_{\lambda_r}$ ( $\lambda_i$ distinto) es directo. En particular, $u$ tiene como máximo $n$ valores propios.

Demostración. Por inducción en $r$ . Supongamos $x_1 + \dots + x_r = 0$ con $x_i \in E_{\lambda_i}$ , la declaración conocida por $r - 1$ . Aplicar $u$ y restar $\lambda_r$ veces la relación:

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

entonces, por inducción, cada $(\lambda_i - \lambda_r)x_i = 0$ , es decir, $x_i = 0$ para $i < r$ , luego $x_r = 0$ . Sumas directas de espacios distintos de cero en un El espacio de dimensión $n$ tiene como máximo $n$ sumandos. ∎

La matriz A = psmallmatrix2 & 1\\ 1 & 2 psmallmatrix que actúa sobre el plano: el vector genérico e_1 se sale de su línea, pero las direcciones propias v_1 = (1,1)y v_2 = (1,-1)simplemente se estiran — por 3 y por 1 (por lo tanto, Av_2 = v_2: la imagen discontinua coincide con v_2). La diagonalización es el cambio a la base (v_1, v_2), donde A se convierte en diag(3, 1). — La matriz $A = \left(\begin{smallmatrix}2 & 1\\ 1 & 2\end{smallmatrix}\right)$ que actúa sobre el plano: el vector genérico $e_1$ se sale de su línea, pero las direcciones propias $v_1 = (1,1)$ y $v_2 = (1,-1)$ simplemente se estiran — por $3$ y por $1$ (por lo tanto, $Av_2 = v_2$ : la imagen discontinua coincide con $v_2$ ). La diagonalización es el cambio a la base $(v_1, v_2)$ , donde $A$ se convierte en $\operatorname{diag}(3, 1)$ .

Definición 3.3 (Polinomio caracteristico)

$\chi_u(X) = \det(X\,\mathrm{id} - u)$ — calculado en cualquier base como $\det(XI_n - A)$ , un mónico polinomio de grado $n$ , invariante bajo similitud (Teorema 2.17). Sus raíces en $K$ son exactamente las valores propios ( $\lambda$ valor propio $\iff u - \lambda\,\mathrm{id}$ no inyectivo $\iff \chi_u(\lambda) = 0$ ), y

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

El multiplicidad algebraica $m_\lambda$ de un valor propio es su multiplicidad como raíz de $\chi_u$ ; el geométrico multiplicidad es $\dim E_\lambda$ y $1 \leq \dim E_\lambda \leq m_\lambda$ .

Prueba de los hechos relacionados. El coeficiente afirma: expandir $\det(XI - A)$ por la permutación fórmula; la permutación de identidad contribuye $\prod_i (X - a_{ii}) = X^n - (\sum a_{ii})X^{n-1} + \dots$ , y todas las demás permutaciones corrige en la mayoría de las posiciones diagonales $n - 2$ , contribuyendo al grado $\leq n - 2$ : los dos coeficientes superiores son como se indican; $X = 0$ da la término constante $\det(-A) = (-1)^n\det A$ .

Geométrico $\leq$ algebraico: sea $d = \dim E_\lambda$ y complete un base de $E_\lambda$ en una base de $E$ ; la matriz de $u$ es bloque triangular superior con el bloque superior izquierdo $\lambda I_d$ , entonces $\chi_u(X) = (X - \lambda)^d\, \chi_{\text{(bottom block)}}(X)$ : la multiplicidad de $\lambda$ es al menos $d$ . ∎

Ejemplo 3.4 (Igual $\chi$ , geometría diferente)

las matrices

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

compartir el polinomio característico $(X - 2)^2$ , el rastro, el determinante, espectro — aún no son similares: el primero tiene $E_2$ de dimensión $2$ (multiplicidad geométrica $2$ ), la segunda de dimensión $1$ . El polinomio característico sólo ve multiplicidades algebraicas; las dimensiones espacio propio son las invariante más fino, y el polinomio mínimo arbitra ( $X - 2$ frente a $(X - 2)^2$ ). Moraleja para todos diagonalizabilidad discusiones: $\chi$ preselecciona a los candidatos, pero los núcleos se emiten los votos.

Definición 3.5 (Diagonalizable, trigonalizable)

$u$ es diagonalizable cuando $E$ tiene un base de vectores propios (matriz: similar a una matriz diagonal); trigonalizable cuando su matriz en algún La base es triangular superior.

Teorema 3.6 (Criterios de diagonalizabilidad)

Los siguientes son equivalentes:

$u$ es diagonalizable;
$E = \bigoplus_{\lambda \in \operatorname{Sp} u} E_\lambda$ ;
$\chi_u$ se divide en $K$ y $\dim E_\lambda = m_\lambda$ por cada valor propio;
(suficiente, no necesario) $\chi_u$ tiene raíces distintas $n$ en $K$ .

Demostración. (1 $\iff$ 2): una base de vectores propios se ordena en bases de la $E_\lambda$ y, a la inversa, concatenar bases del directo Summands da una base de $E$ . (Teorema 3.2 hace la suma directa; igualdad de dimensiones lo hace todo).

(2 $\iff$ 3): en la base diagonal, $\chi_u = \prod (X - \lambda)^{\dim E_\lambda}$ se divide con multiplicidades coincidentes. Por el contrario, supongamos que $\chi_u$ se divide con $\dim E_\lambda = m_\lambda$ en todo momento; luego la suma directa del espacios propios (directo por Teorema 3.2) tiene dimensión

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

la igualdad media porque el grado de un polinomio dividido es el suma de sus multiplicidades de raíces: la suma es todo $E$ . Nota donde funcionó cada hipótesis: la división llenó el grado, la igualdad de multiplicidades llenó las dimensiones.

(4 $\Rightarrow$ 1): $n$ distinto valores propios da $n$ independiente vectores propios (Teorema 3.2): una base. ∎

Método 3.7 (Decidir la diagonalizabilidad)

En la práctica, pruebe en este orden: cada paso puede finalizar el trabajo. (1) ¿Tiene un polinomio aniquilador con división simple? ¿Las raíces se presentan ( $u^2 = \mathrm{id}$ , $u^2 = u$ , $u^k = \mathrm{id}$ )? En caso afirmativo: diagonalizable, sin cálculo (Corolario 3.17 a continuación). (2) Calcular $\chi_u$ ; si tiene $n$ raíces distintas en $K$ : diagonalizable (Teorema 3.6 (4)). (3) En caso contrario, para cada raíz múltiple $\lambda$ solamente, compare $\dim\ker(u - \lambda\,\mathrm{id})$ con la multiplicidad $m_\lambda$ : cualquiera el déficit mata a diagonalizabilidad; la igualdad en todas partes lo demuestra. Nunca calcule espacios propios de raíces simples (su dimensión es obligado a ser $1$ ), y nunca trigonalizar sólo para decidir.

Ejemplo 3.8 (Diagonalización puesta en marcha)

$A = I + J = \left(\begin{smallmatrix}2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2\end{smallmatrix}\right)$ , con $J$ la matriz de todos unos: desde $\operatorname{Sp}(J) = \{3, 0\}$ (Ejemplo 2.19), $\operatorname{Sp}(A) = \{4, 1\}$ , con espacios propios $\R(1,1,1)$ y el plano $\{x + y + z = 0\}$ : dimensiones $1 + 2 = 3$ , diagonalizable (Teorema 3.6 (2)). Poderes sin ningún matriz de cambio de base: con $\Pi = J/3$ el proyector en $\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 .

(Consulte $k = 1$ : $\frac{4-1}3 J + I = A$ ). La información final: cuando los espacios propios son visibles, espectrales proyectores poderes de cómputo más rápidos de lo que $PDP^{-1}$ alguna vez lo hará, y el La fórmula muestra la dinámica: $A^k$ crece como $4^k$ a lo largo $(1,1,1)$ y permanece en el plano ortogonal.

Teorema 3.9 (Trigonalización)

$u$ es trigonalizable sobre $K$ si y sólo si $\chi_u$ se divide $K$ . En particular, cada endomorfismo de un espacio vectorial $\C$ es trigonalizable.

Demostración. ( $\Rightarrow$ ) El polinomio característico de una matriz triangular. es $\prod(X - t_{ii})$ : dividido.

( $\Leftarrow$ ) Inducción en $n$ . Dado que $\chi_u$ se divide, tiene un raíz $\lambda$ : elija un vector propio $e_1$ . En una base que comienza con $e_1$ , la matriz es $\begin{pmatrix} \lambda & \ast\\ 0 & B\end{pmatrix}$ y $\chi_u = (X - \lambda)\chi_B$ : $\chi_B$ se divide también. Por la hipótesis de inducción aplicada a la matriz $(n-1) \times (n-1)$ $B$ , existe una $Q$ invertible con $Q^{-1}BQ$ superior triangular; conjugar toda la matriz con $\begin{pmatrix}1 & 0\\ 0 & Q\end{pmatrix}$ la triangulariza. ∎

Ejemplo 3.10 (Trigonalizando a mano)

$B = \begin{pmatrix}3 & -1\\ 1 & 1\end{pmatrix}$ : $\chi_B = X^2 - 4X + 4 = (X - 2)^2$ y $\ker(B - 2I) = \ker\left(\begin{smallmatrix}1 & -1\\ 1 & -1\end{smallmatrix}\right)$ es la línea abarcada por $e_1' = (1, 1)$ : un valor propio, un unidimensional espacio propio — no diagonalizable, pero trigonalizable (Teorema 3.9). Complete la base con $e_2' = (1, 0)$ y calcule:

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

entonces en la base $(e_1', e_2')$ la matriz es $T = \left(\begin{smallmatrix}2 & 1\\ 0 & 2\end{smallmatrix}\right)$ . el Información final: la diagonal de $T$ fue forzada (ambas entradas debe ser el doble valor propio $2$ ); solo la entrada de la esquina dependía de la elección de $e_2'$ , y reescalar $e_2'$ puede hacer cualquier valor distinto de cero — el resistente “ $1$ ” es la sombra de la parte nilpotente que Dunford aislará.

3.2 Polinomios de un endomorfismo

Definición 3.11

Para $P = \sum a_k X^k \in K[X]$ , configure $P(u) = \sum a_k u^k \in \mathcal{L}(E)$ . El mapa $P \mapsto P(u)$ es un morfismo de álgebras. $K[X] \to \mathcal{L}(E)$ (Definición 1.33); su núcleo $\{P : P(u) = 0\}$ es un ideal de $K[X]$ , distinto de cero (el La familia $(\mathrm{id}, u, \dots, u^{n^2})$ está vinculada en el $n^2$ -dimensional $\mathcal{L}(E)$ ), por lo tanto generado por un único polinomio mónico $\mu_u$ : el mínimo polinomio (Teorema 1.26).

Proposición 3.12

$P(u) = 0 \iff \mu_u \mid P$ ; valores propios de $u$ son raíces de cada polinomio aniquilador, y las raíces de $\mu_u$ son exactamente y valores propios.
Si $F$ es estable, $\mu_{u|_F} \mid \mu_u$ .

Demostración. (1) La divisibilidad es la definición de generador. Si $u(x) = \lambda x$ , $x \neq 0$ , entonces $0 = P(u)(x) = P(\lambda)x$ , entonces $P(\lambda) = 0$ : valores propios son raíces de aniquiladores, en particular de $\mu_u$ . Por el contrario, si $\lambda$ es una raíz, $\mu_u = (X - \lambda)Q$ con $Q(u) \neq 0$ (grado de $\mu_u$ mínimo): elija $y$ con $Q(u)(y) \neq 0$ ; entonces $(u - \lambda)(Q(u)(y)) = \mu_u(u)(y) = 0$ exhibe el vector propio $Q(u)(y)$ .

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

Ejemplo 3.13 (Polinomios mínimos encontrados a mano)

El polinomio mínimo se calcula probando sucesivos grados. Para la matriz de todos unos $J \in \mathcal{M}_3(\R)$ : $J \neq \lambda I$ (el grado $1$ está fuera) y $J^2 = 3J$ , por lo que

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

grado $2$ , división, raíces simples — $J$ es diagonalizable con espectro $\{0, 3\}$ (Corolario 3.17 a continuación), confirmando Ejemplo 2.19 sin un solo determinante. Para la matriz de intercambio $A$ de Ejemplo 3.15: $A \neq \pm I$ y $A^2 = I$ dan $\mu_A = X^2 - 1$ . En ambos casos el patrón es el Lo mismo: adivina una identidad de bajo grado a partir de la estructura. (el rango uno fuerza a $J^2 = (\operatorname{tr}J)\,J$ ; una involución fuerzas $A^2 = I$ ), luego verifique que no haya un divisor adecuado aniquila. Polinomios mínimos suelen ser encontró, no calculado a partir de $\chi$ .

Teorema 3.14 (Lema de análisis del kernel)

Si $P = P_1 P_2 \cdots P_r$ con el coprimo por pares $P_i$ , entonces

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

y las proyecciones sobre los sumandos son polinomios en $u$ .

Demostración. Basta tratar $r = 2$ e inducir. Bézout en $K[X]$ (Teorema 1.26): $U P_1 + V P_2 = 1$ , entonces para cada $x$ ,

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

Si $x \in \ker P(u)$ : $P_2(u)(x_2) = U(u)\,P(u)(x) = 0$ (polinomios en $u$ conmutar), entonces $x_2 \in \ker P_2(u)$ , y simétricamente $x_1 \in \ker P_1(u)$ : la suma llena $\ker P(u)$ ; ambos mandamientos se sientan dentro de $\ker P(u)$ ( $P_i \mid P$ ). Directo: $x \in \ker P_1(u) \cap \ker P_2(u)$ da $x = U(u)P_1(u)x + V(u)P_2(u)x = 0$ . el Las fórmulas para $x_1, x_2$ muestran las proyecciones como $V(u)P_2(u)$ y $U(u)P_1(u)$ . ∎

Ejemplo 3.15 (El lema del núcleo con proyectores explícitos)

Dejemos que $A = \left(\begin{smallmatrix}0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{smallmatrix}\right)$ (intercambie las dos primeras coordenadas). Entonces $A^2 = I$ : el polinomio $X^2 - 1 = (X - 1)(X + 1)$ aniquila a $A$ , sus factores son coprimos y Bézout es explícito:

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

Siguiendo la prueba de Teorema 3.14, el Las proyecciones sobre $\ker(A - I)$ y $\ker(A + I)$ son las polinomios en $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}.

Verifique: $\pi_+ + \pi_- = I$ , $\pi_+\pi_- = 0$ , $\pi_\pm^2 = \pi_\pm$ , y las imágenes son el plano $\{x = y\}$ (simétrico). vectores, valor propio $1$ ) y la línea $\R(1, -1, 0)$ (antisimétrico, valor propio $-1$ ). El lema del núcleo no es un declaración de existencia: Bézout coeficientes son el Fórmulas del proyector.

Ejemplo 3.16 (Los proyectores también calculan el exponencial.)

La misma matriz de swap, un dividendo más. Desde $A = \pi_+ - \pi_-$ con proyectores ortogonales en sentido algebraico ( $\pi_+\pi_- = 0$ ), cada potencia obedece a $A^k = \pi_+ + (-1)^k\pi_-$ , y la serie exponencial se reagrupa por proyector:

\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}.

(Marque $t = 0$ : la identidad; derivada en $0$ : $A$ ). La descomposición propia convierte una serie de matrices en dos escalares. serie — el mecanismo exacto que Capítulo 16 se ejecuta en todos los sistemas diagonalizable, y la razón es hiperbólica Las funciones gobiernan los acoplamientos simétricos.

Corolario 3.17 (Diagonalizabilidad mediante el polinomio mínimo)

$u$ es diagonalizable $\iff$ $\mu_u$ se divide en $K$ con simple raíces $\iff$ algún polinomio aniquilador de $u$ se divide con raíces simples.

Demostración. Si $P(u) = 0$ con $P = \prod_{i}(X - \lambda_i)$ (distinto $\lambda_i$ ), el lema da $E = \ker P(u) = \bigoplus_i \ker(u - \lambda_i)$ : una suma directa de espacios propios, por lo que $u$ es diagonalizable (Teorema 3.6). Por el contrario, un diagonalizable $u$ es asesinado por $\prod_{\lambda \in \operatorname{Sp}u}(X - \lambda)$ (mata a cada espacio propio), que se divide con simples raíces; y $\mu_u$ lo divide teniendo las mismas raíces (Proposición 3.12): $\mu_u$ es exactamente ese producto. ∎

Ejemplo 3.18

Proyecciones satisfacen $p^2 = p$ : aniquilado por $X(X-1)$ , dividido simple raíces — diagonalizable con espectro $\subseteq \{0, 1\}$ y $E = \ker p \oplus \ker(p - \mathrm{id})$ : análisis geométrico del año 1, reprobado en una línea. Simetrías ( $s^2 = \mathrm{id}$ , aniquilador $X^2 - 1$ ): diagonalizable cuando $\operatorname{char} K \neq 2$ , espectro $\subseteq \{\pm 1\}$ . Un endomorfismo con $u^3 = u^2$ y $u^2 \neq u$ : aniquilado por $X^2(X - 1)$ , no necesariamente diagonalizable — el criterio lo detecta (doble raíz $0$ debe ser probado: diagonalizable si además $\ker u^2 = \ker u$ ).

Ejemplo 3.19 (El campo decide: una rotación en $\R^3$ )

Sea $R$ el cuarto de vuelta alrededor del eje $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$ : el único valor propio es $1$ , siendo espacio propio el eje $\R e_3$ — una línea de vectores fijos y ninguna más reducción: $R$ no es ni diagonalizable ni trigonalizable en $\mathcal{M}_3(\R)$ ( $\chi_R$ no se divide). Más de $\C$ : tres distinto valores propios $1, \iu, -\iu$ , por lo que $R$ es diagonalizable, con vectores propios $e_3$ y $e_1 \mp \iu e_2$ . La geometría era audible en el álgebra: las rotaciones en el plano no tienen real direcciones invariantes, y el complejo valores propios $\pm\iu$ de El módulo $1$ almacena el ángulo ( $\pm\frac\pi2$ ) que forma el real. La matriz solo se puede expresar mezclando coordenadas.

Ejemplo 3.20 (Mínimo versus característico)

Para $D = \operatorname{diag}(2, 2, 3)$ : $\chi_D = (X - 2)^2(X - 3)$ pero $\mu_D = (X - 2)(X - 3)$ , desde $(D - 2I)(D - 3I) = 0$ (verifique sobre la base canónica) mientras que ningún factor por sí solo mata $D$ . Para el bloque de cambios $N = \left(\begin{smallmatrix}0 & 1\\ 0 & 0\end{smallmatrix}\right) \oplus (3)$ , es decir, $N' = \left(\begin{smallmatrix}0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 3\end{smallmatrix}\right)$ : $\chi_{N'} = X^2(X - 3)$ y $\mu_{N'} = X^2(X - 3)$ — la doble raíz es realmente necesaria porque $N'$ no es diagonalizable en el lado $\ker$ ( $N'e_2 = e_1 \neq 0$ ). Regla general: $\mu$ y $\chi$ comparten sus raíces (Proposición 3.12); la multiplicidad en $\mu$ mide el tamaño del bloque nilpotente más grande, el que está en $\chi$ la dimensión total del subespacio característico.

Teorema 3.21 (Cayley–Hamilton)

$\chi_u(u) = 0$ ; en consecuencia $\mu_u \mid \chi_u$ y $\deg \mu_u \leq n$ .

Demostración. Arregla $x \neq 0$ y deja que $d$ sea máximo con $(x, u(x), \dots, u^{d-1}(x))$ gratis; escribir

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

y configure $P_x = X^d + a_{d-1}X^{d-1} + \dots + a_0$ , por lo que $P_x(u)(x) = 0$ . Complete la familia libre en una base de $E$ : en ella, $u$ tiene formulario de bloque $\begin{pmatrix} C & \ast\\ 0 & D\end{pmatrix}$ donde $C$ es la matriz compañera de $P_x$ , cuyo polinomio característico es $P_x$ (expandir $\det(XI - C)$ a lo largo de la primera columna, por inducción en $d$ ). Por lo tanto $\chi_u = P_x \cdot \chi_D$ , y

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

El argumento es válido para cada $x$ : $\chi_u(u) = 0$ . ∎

Ejemplo 3.22 (Cayley–Hamilton en el trabajo)

$A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ : $\chi_A = X^2 - 5X - 2$ , entonces $A^2 = 5A + 2I$ . Cada poder de $A$ colapsa a un combinación de $I$ y $A$ :

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

y el inverso sale gratis: $A(A - 5I) = 2I$ da

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

La idea final: Cayley–Hamilton comprime todo el álgebra $K[A]$ en $\operatorname{Vect}(I, A, \dots, A^{n-1})$ — $\dim K[A] = \deg\mu_A \leq n$ , por grandes que sean las potencias que necesites.

Observación 3.23 (Errores comunes)

(i) Valores propios no agregue: $\operatorname{Sp}(A + B)$ no es $\operatorname{Sp}A + \operatorname{Sp}B$ , y una suma de Las matrices diagonalizable no necesitan ser diagonalizable — $\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)$ es una suma de dos matrices diagonalizable (cada una tiene valores propios distinta) y no es diagonalizable; solo se comportan las familias desplazarse (Ejercicio 3.9). (ii) “ $\chi_u$ divisiones” es una hipótesis sobre el campo: una rotación del plano tiene $\chi = X^2 - 2\cos\theta\,X + 1$ , dividido sobre $\C$ , no sobre $\R$ — diagonalizable en $\mathcal{M}_2(\C)$ , no trigonalizable en $\mathcal{M}_2(\R)$ . (iii) La desigualdad es geométrica $\leq$ algebraico, nunca al revés; probar solo $\dim E_\lambda \geq 1$ no prueba nada sobre diagonalizabilidad. (iv) $\mu_u$ no es $\chi_u$ : la igualdad se cumple exactamente cuando cada valor propio tiene un cadena de bloques única (por ejemplo, matrices complementarias, las de este capítulo). problema de fin de semana); usando $\chi$ donde se necesita $\mu$ se infla cada cálculo de potencia. (v) $d$ y $\nu$ de Dunford son polinomios en $u$ — una descomposición $u = d' + \nu'$ con el propiedades correctas pero $d'\nu' \neq \nu'd'$ es no Dunford y nunca es único.

Observación 3.24 (Dónde se utiliza este capítulo)

La reducción es el caballo de batalla del resto del libro: poderes y exponenciales de matrices impulsan los sistemas diferenciales lineales de Capítulo 16; el teorema espectral de Capítulo 12 ¿La diagonalización se hace ortogonal? funciones generadoras (Capítulo 23) volver a derivar las asintóticas de recurrencia de este Analíticamente el problema del fin de semana del capítulo. En el volumen del año 3, mismo programa se ejecuta en dimensión infinita: la teoría espectral de operadores autoadjuntos compactos, donde las secuencias valor propio reemplazan espectros finitos, y la teoría de Perron-Frobenius de matrices, lo que explica por qué valores propios dominante de Los problemas de conteo son positivos y simples.

3.3 Nilpotentes y la descomposición de Dunford

Proposición 3.25 (endomorfismos nilpotentes)

Para $u$ con división $\chi_u$ , lo siguiente es equivalente: $u^n = 0$ ; $u^k = 0$ para algunos $k$ ; $\operatorname{Sp}(u) = \{0\}$ ; $\chi_u = X^n$ ; $u$ es trigonalizable con diagonal cero. Un nilpotente endomorfismo tiene $\mu_u = X^{\text{(nilpotence index)}}$ y un índice $\leq n$ .

Demostración. $u^k = 0$ hace que cada valor propio sea una raíz de $X^k$ : espectro $\{0\}$ (no vacío cuando $\chi$ se divide — sobre $\C$ siempre). Luego $\chi_u = X^n$ (todas las raíces son cero) y Cayley-Hamilton da $u^n = 0$ ; trigonalización (Teorema 3.9) pone ceros en la diagonal (la diagonal lleva el valores propios). Por el contrario, sea $A$ estrictamente triangular superior: $a_{ij} = 0$ para $j \leq i$ . Demostramos por inducción que

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

es decir, cada potencia empuja la región cero una diagonal más arriba. Para $k = 1$ esta es la hipótesis. Para el paso,

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

y cada término desaparece: $\ell \leq i + k - 1$ (el primero factor es $0$ por inducción) o $\ell \geq i + k$ , en cuyo caso $j \leq i + k \leq \ell$ mata el segundo factor. En $k = n$ el La condición $j \leq i + n - 1$ se cumple para todos los $i, j \leq n$ : $A^n = 0$ . El polinomio mínimo divide $X^n$ y la aniquilación define el índice. ∎

Teorema 3.26 (Desglose de Dunford)

Supongamos que $\chi_u$ se divide en $K$ (automático para $K = \C$ ). entonces hay un par único $(d, \nu)$ con

u = d + \nu, \qquad d \text{ diagonalizable}, \quad \nu \text{ nilpotent}, \quad d\nu = \nu d ,

y además $d$ y $\nu$ son polinomios en $u$ .

Demostración. Existencia. Escriba $\chi_u = \prod_{i=1}^{r} (X - \lambda_i)^{m_i}$ ( $\lambda_i$ distinto) y configure $N_i = \ker(u - \lambda_i)^{m_i}$ , el subespacios característicos. Por Cayley–Hamilton y el lema del núcleo (Teorema 3.14),

E = N_1 \oplus \dots \oplus N_r ,

con proyecciones del polinomio $\pi_i$ en $u$ ; cada $N_i$ es estable (Los polinomios en $u$ conmutan con $u$ ). Defina $d = \sum_i \lambda_i \pi_i$ : un polinomio en $u$ , diagonalizable (actúa como $\lambda_i$ en $N_i$ , por lo que $E$ se descompone en su espacios propios). Entonces $\nu = u - d$ es un polinomio en $u$ (por lo tanto conmuta con $d$ ), y en cada $N_i$ actúa como $u - \lambda_i$ , con $(u - \lambda_i)^{m_i} = 0$ allí: $\nu^{\max m_i} = 0$ en cada sumando, por lo que $\nu$ es nilpotente.

Unicidad. Sea $u = d' + \nu'$ otro par de esos. desde $d'$ y $\nu'$ conmutan entre sí, conmutan con $u = d' + \nu'$ , por lo tanto con cada polinomio en $u$ — en particular con $d$ y $\nu$ . Entonces $d - d'$ es diagonalizable (dos Los mapas diagonalizable son simultáneamente diagonalizable: Ejercicio 3.9) y es igual a $\nu' - \nu$ , que es nilpotente: si $\nu^k = 0$ y $\nu'^{k'} = 0$ , conmutación licencia la expansión del binomio

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

en el que cada término muere: ya sea $j \geq k'$ (primer factor cero) o $k + k' - 1 - j \geq k$ (segundo factor cero), y uno de los dos siempre se cumple. Un nilpotente diagonalizable es cero (su espectro es $\{0\}$ y es diagonal en alguna base): $d = d'$ , $\nu = \nu'$ . ∎

Ejemplo 3.27 (Potencias y exponenciales)

$A = \begin{pmatrix} 3 & 1\\ -1 & 1\end{pmatrix}$ : $\chi_A = X^2 - 4X + 4 = (X-2)^2$ , único valor propio $2$ , espacio propio de dimensión $1$ : no diagonalizable. Dunford: $D = 2I$ , $N = A - 2I = \begin{pmatrix} 1 & 1\\ -1 & -1\end{pmatrix}$ , $N^2 = 0$ . entonces

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

por el teorema del binomio de conmutación, respectivamente la serie exponencial (Capítulo 16) dividido en órdenes de traslado. Giros de reducción dinámica matricial en dinámica escalar.

Observación 3.28 (Perspectivas dentro de este volumen)

La reducción es un centro; Aquí están los cuatro radios a tener en cuenta. en Capítulo 5, las normas adaptadas convierten “todos los valores propios de módulo $< 1$ ” en “alguna norma de operador $< 1$ ”, haciendo Los espectros gobiernan la convergencia de potencias y series. en Capítulo 16, la receta de Ejemplo 3.27 se convierte en la solución general de $X' = AX$ : Dunford divide $\eu^{tA}$ en bloques polinomiales multiplicados por exponenciales y lecturas de estabilidad las partes reales de valores propios. En Capítulo 12, un El producto escalar fuerza lo que el mero álgebra lineal no puede: simétrico. las matrices se convierten en ortogonalmente diagonalizable, sin parte nilpotente en absoluto. Y en Capítulo 23, el valor propio dominante asintóticas del fin de semana de este capítulo. problema reaparece analíticamente, como la singularidad más pequeña de un Función generadora: dos idiomas para una tasa de crecimiento.

3.4 Ceremonias

Ejercicio 3.1 ★

Diagonalizar (valores propios, bases de espacios propios, invertible $P$ ):

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

Solución

Solución de Ejercicio 3.1.

$A$ : $\chi_A = X^2 - 2X - 3 = (X - 3)(X + 1)$ . Vectores propios: para $3$ : $(1,1)$ ; para $-1$ : $(1,-1)$ . Entonces $P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ da $P^{-1}AP = \operatorname{diag}(3, -1)$ .

$B = J - I$ donde $J$ es la matriz de todos unos. $J$ tiene el rango $1$ con $Jv = 3v$ para $v = (1,1,1)$ y $Jw = 0$ en el avión $x + y + z = 0$ : espectro de $B$ es $\{2, -1\}$ con espacios propios $\operatorname{Vect}(1,1,1)$ (dimensión $1$ ) y $\{x + y + z = 0\}$ (dimensión $2$ , base $(1,-1,0), (1,0,-1)$ ). $P$ con estos tres columnas dan $P^{-1}BP = \operatorname{diag}(2, -1, -1)$ .

Ejercicio 3.2 ★

Mostrar que $C = \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}$ no lo es diagonalizable, dos veces: vía espacios propios y vía mínimo polinomio.

Solución

Solución de Ejercicio 3.2.

Espacios propios: $\chi_C = (X-1)^2$ , soltero valor propio $1$ ; $\ker(C - I) = \ker\begin{pmatrix} 0&1\\ 0&0\end{pmatrix}$ es el línea $\operatorname{Vect}(e_1)$ : dimensión $1 < 2 = m_1$ , por lo que no diagonalizable (Teorema 3.6).

Polinomio mínimo: $\mu_C$ divide $(X-1)^2$ y $C \neq I$ , entonces $\mu_C = (X-1)^2$ : una raíz doble, entonces no diagonalizable (Corolario 3.17).

Ejercicio 3.3 ★

Deje que $u$ satisfaga a $u^2 - 5u + 6\,\mathrm{id} = 0$ . Demuestre que $u$ es diagonalizable, determine los espectros posibles y calcule $u^k$ como una combinación de $\mathrm{id}$ y $u$ .

Solución

Solución de Ejercicio 3.3.

$X^2 - 5X + 6 = (X-2)(X-3)$ : dividido con raíces simples, por lo que $u$ es diagonalizable (Corolario 3.17), con $\operatorname{Sp}(u) \subseteq \{2, 3\}$ . Posibles espectros: $\{2\}$ ( $u = 2\,\mathrm{id}$ ), $\{3\}$ ( $u = 3\,\mathrm{id}$ ), o $\{2, 3\}$ .

Poderes: buscar $u^k = a_k\,\mathrm{id} + b_k\,u$ . En el espacios propios, esto dice $2^k = a_k + 2b_k$ y $3^k = a_k + 3b_k$ : resolviendo, $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 los tres espectros: las identidades se mantienen en cuanto a valores propios).

Ejercicio 3.4 ★★

Sea $u$ diagonalizable y $F$ un subespacio estable. demostrar que $u|_F$ es diagonalizable (restringir un polinomio aniquilador con raíces simples divididas).

Solución

Solución de Ejercicio 3.4.

$u$ diagonalizable: $P = \prod_{\lambda}(X - \lambda)$ sobre el espectro aniquila $u$ , escisiones, raíces simples. Entonces $P(u|_F) = P(u)|_F = 0$ : la restricción es aniquilada por un polinomio dividido con raíces simples, por lo tanto diagonalizable (Corolario 3.17).

Ejercicio 3.5 ★★

(Fibonacci) Sea $A = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ . Diagonalice $A$ sobre $\R$ y deduzca la fórmula de Binet para Secuencia 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}.

Solución

Solución de Ejercicio 3.5.

$\chi_A = X^2 - X - 1$ , raíces $\varphi$ y $\psi$ (distintas): diagonalizable, con vectores propios $(\varphi, 1)$ y $(\psi, 1)$ . La recurrencia da $\begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = A^n \begin{pmatrix}1\\ 0\end{pmatrix}$ . Descomponer $(1, 0)$ en el vectores propios: $(1,0) = \frac{1}{\varphi - \psi}\bigl((\varphi, 1) - (\psi, 1)\bigr)$ con $\varphi - \psi = \sqrt5$ . Aplicando $A^n$ multiplica cada componente propio por su $n$ -ésima potencia de valor propio; leyendo la segunda coordenada:

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

(Compruebe: $n = 1$ da $\frac{\varphi - \psi}{\sqrt5} = 1$ ).

Ejercicio 3.6 ★★

Vamos $u \in \mathcal{L}(E)$ con $u^2$ diagonalizable y $u$ reversible ( $K = \C$ ). Demuestre que $u$ es diagonalizable. dar un contraejemplo cuando $u$ no es invertible.

Solución

Solución de Ejercicio 3.6.

Deja que $P = \prod_i (X - \mu_i)$ aniquile a $u^2$ , divídelo con simple raíces $\mu_i$ (el espectro de $u^2$ ). Dado que $u$ es invertible, $0$ no es un valor propio de $u^2$ ( $\det u^2 = (\det u)^2 \neq 0$ ), por lo que todos $\mu_i \neq 0$ . entonces

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

aniquila $u$ : $\;Q(u) = \prod_i (u^2 - \mu_i\,\mathrm{id}) = P(u^2) = 0$ . Sus raíces $\pm \sqrt{\mu_i}$ (raíces cuadradas complejas) son distintas por pares porque los $\mu_i$ son distintos y distintos de cero ( $\sqrt{\mu_i} = -\sqrt{\mu_j}$ daría $\mu_i = \mu_j$ ). División + raíces simples: $u$ es diagonalizable.

Contraejemplo sin invertibilidad: $u = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : $u^2 = 0$ es diagonalizable, $u$ no lo es.

Ejercicio 3.7 ★★

Calcule Descomposición de Dunford, $A^k$ y $\eu^{tA}$ para

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

Solución

Solución de Ejercicio 3.7.

$A = 2I + N$ con $N$ el turno ( $N e_2 = e_1$ , $Ne_3 = e_2$ ), $N^3 = 0$ , $N^2 = E_{13}$ : este is el Descomposición de Dunford ( $2I$ diagonal, $N$ nilpotentes, conmutan; la unicidad lo hace el uno). Binomio con términos de desplazamiento:

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

Ejercicio 3.8 ★★

Deje $A \in \mathcal{M}_n(\C)$ con $A^k = I$ para algunos $k \geq 1$ . Demuestre que $A$ es diagonalizable y su valores propios es $k$ -ésimo raíces de la unidad. Deducir que una matriz compleja invertible de orden finito similar a una matriz triangular con diagonal unitaria es la identidad.

Solución

Solución de Ejercicio 3.8.

$X^k - 1$ aniquila a $A$ y se divide en $\C$ con el $k$ distinto raíces $\eu^{2\iu\pi j/k}$ : $A$ es diagonalizable (Corolario 3.17) y su valores propios, raíces de $X^k - 1$ , son $k$ -ésimas raíces de la unidad.

Si además $A$ es similar a una matriz triangular con unidad diagonal: todos valores propios son iguales a $1$ y $A$ , diagonalizable con único valor propio $1$ , es $P\,I\,P^{-1} = I$ .

Ejercicio 3.9 ★★★

(Diagonalización simultánea) Sea $u, v$ diagonalizable y desplazamientos. Demostrar que son simultáneamente diagonalizable: alguna base diagonaliza a ambos. (Each espacio propio of $u$ is $v$ -stable; diagonalize the restrictions of $v$ there, using Ejercicio 3.4.)

Solución

Solución de Ejercicio 3.9.

Escribe $E = \bigoplus_\lambda E_\lambda(u)$ (Teorema 3.6). Cada $E_\lambda(u)$ es $v$ -estable: para $x \in E_\lambda$ , $u(v(x)) = v(u(x)) = \lambda v(x)$ . La restricción de $v$ a $E_\lambda(u)$ es diagonalizable (Ejercicio 3.4): elige una base de $E_\lambda(u)$ hecha de $v$ -vectores propios. Concatenando estas bases sobre todo $\lambda$ da una base de $E$ cuyos vectores son vectores propios de ambos $u$ (por membresía en $E_\lambda(u)$ ) y $v$ (por construcción).

Ejercicio 3.10 ★★★

Deje $u \in \mathcal{L}(\C^n)$ . Demuestre que $u$ es diagonalizable si y solo si cada subespacio estable $u$ tiene un subespacio estable $u$ subespacio suplementario. (For $\Leftarrow$ : apply the property to $F = \sum_\lambda E_\lambda(u)$ , the sum of all espacios propios; if a stable supplement $G$ were nonzero, trigonalizing $u|_G$ would produce an vector propio of $u$ inside $G$ — contradicting $G \cap F = \{0\}$ .)

Solución

Solución de Ejercicio 3.10.

( $\Rightarrow$ ) Sea $u$ diagonalizable y $F$ estable. entonces $u|_F$ es diagonalizable (Ejercicio 3.4): $F$ tiene un base de vectores propios, que se extiende, dentro de cada espacio propio global $E_\lambda$ , a una base de $E_\lambda$ (teorema de base incompleta dentro de $E_\lambda$ , a partir de la parte de la base de $F$ que se encuentra allí — nota $F = \bigoplus_\lambda (F \cap E_\lambda)$ desde $u|_F$ es diagonalizable). Los vectores agregados abarcan un establo. suplemento (cada uno se encuentra en algún $E_\lambda$ , por lo que su intervalo es $u$ -estable).

( $\Leftarrow$ ) Dejemos que $F = \sum_\lambda E_\lambda(u)$ (un establo subspace) y $G$ un suplemento estable. Si $G \neq \{0\}$ : $\chi_{u|_G}$ se divide sobre $\C$ , por lo que $u|_G$ tiene un vector propio $x \in G$ (Teorema 3.9 o directamente la existencia de una raíz); pero cada vector propio de $u$ se encuentra en $F$ , por lo que $x \in F \cap G = \{0\}$ : contradicción. Por lo tanto $G = \{0\}$ y $E = F$ : el espacios propios llena $E$ , es decir, $u$ es diagonalizable.

Ejercicio 3.11 ★★★

(Radio espectral por Gelfand-lite, $2\times2$ sabor de análisis para ven) Dejemos $A \in \mathcal{M}_2(\C)$ con ambos valores propios de módulo $< 1$ . Demuestre que $A^k \to 0$ de entrada es $k \to \infty$ . (Trigonalize: $A = P(T)P^{-1}$ with $T$ upper triangular; compute $T^k$ explicitly — distinguish equal and distinct valores propios — and bound.)

Solución

Solución de Ejercicio 3.11.

Trigonalizar: $A = PTP^{-1}$ , $T = \begin{pmatrix} \lambda & c\\ 0 & \mu\end{pmatrix}$ , $\abs\lambda, \abs\mu < 1$ . Entonces $A^k = PT^kP^{-1}$ , y basta con que $T^k \to 0$ .

Distinct valores propios: da inducción

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

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

Equal valores propios ( $\mu = \lambda$ ): $T = \lambda I + cE_{12}$ y $T^k = \lambda^k I + k\lambda^{k-1}cE_{12}$ ; la entrada $k\lambda^{k-1} \to 0$ desde $\abs\lambda < 1$ (ritmos geométricos polinomio). En ambos casos $T^k \to 0$ de entrada, por lo tanto $A^k = PT^kP^{-1} \to 0$ (la multiplicación de matrices por $P, P^{-1}$ fijo es continuo en las entradas — cada entrada del producto es un valor fijo combinación lineal).

Ejercicio 3.12 ★★

Deje $u \in \mathcal{L}(\C^n)$ con $\operatorname{rk} u = 1$ ( $n \geq 2$ ). Muestre que $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ , y que $u$ es diagonalizable si y sólo si $\operatorname{tr} u \neq 0$ . (Recall from Ejercicio 2.5 that $u^2 = (\operatorname{tr} u)\,u$ .)

Solución

Solución de Ejercicio 3.12.

$\ker u$ tiene la dimensión $n - 1$ (rango–nulidad), por lo que $0$ es un valor propio de multiplicidad geométrica $n - 1$ , y $\chi_u$ es divisible por $X^{n-1}$ (Definición 3.3: geométrico $\leq$ algebraico). Escribe $\chi_u = X^{n-1}(X - \alpha)$ ; el coeficiente de Siendo $X^{n-1}$ $-\operatorname{tr} u$ , obtenemos $\alpha = \operatorname{tr} u$ : $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ .

Si $\operatorname{tr} u \neq 0$ : el valor propio $\operatorname{tr} u$ es una raíz de $\chi_u$ , por lo que lleva una vector propio; el espacios propios para $0$ y $\operatorname{tr} u$ tienen dimensiones $n - 1$ y $\geq 1$ , sumando $\geq n$ : complete $E$ y $u$ es diagonalizable (Teorema 3.6). Si $\operatorname{tr} u = 0$ : por Ejercicio 2.5, $u^2 = (\operatorname{tr} u)u = 0$ con $u \neq 0$ : $u$ es un nilpotente distinto de cero y un diagonalizable nilpotente es cero (Proposición 3.25): no diagonalizable.

3.5 Problema: recurrencias lineales y matrices complementarias

Una recurrencia lineal $u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_0 u_n$ es un poder matricial disfrazado, y la reducción lo convierte en fórmulas cerradas, tasas de crecimiento y estimaciones de errores. este fin de semana El problema desarrolla el diccionario — matrices complementarias en una. lado, el operador de turno en el espacio de secuencias en el otro — prueba el teorema fundamental de las recurrencias lineales (la solución general es $\sum_i Q_i(n)\lambda_i^n$ sobre las raíces del polinomio característico), y gasta los dividendos en Aproximación diofántica de $\sqrt2$ , sobre el recuento de paseos y palabras, y en un anillo de secuencias acopladas que sólo La diagonalización simultánea puede desenredar.

Problema 3.1

Problema del fin de semana — el teorema fundamental de recurrencias lineales

Se corrigieron $k \geq 1$ , los escalares $a_0, \dots, a_{k-1} \in \C$ con $a_0 \neq 0$ , el polinomio mónico $P = X^k - a_{k-1}X^{k-1} - \dots - a_1 X - a_0$ y la recurrencia.

(\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).

El matriz acompañante de $P$ es

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 — The companion dictionary.

Demuestre que una secuencia $(u_n)$ satisface $(\mathcal R)$ si y sólo si los vectores $v_n = (u_n, u_{n+1}, \dots, u_{n+k-1})^{\mathsf T}$ satisfacen $v_{n+1} = Cv_n$ , por lo tanto $v_n = C^n v_0$ .
Demuestre que $\chi_C = P$ (expandir $\det(XI - C)$ a lo largo del primera columna e inducción en $k$ ), luego ese $\mu_C = P$ también (pass to $C^{\mathsf T}$ , for which $e_1$ is cíclico, and note that a matrix and its transponer have the same polinomio mínimo).
Demuestre que para cada raíz $\lambda$ de $P$ , el vector $(1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ abarca el espacio propio de $C$ para $\lambda$ ; deducir que cada espacio propio de $C$ tiene la dimensión $1$ , y que $C$ es diagonalizable si y sólo si $P$ tiene $k$ raíces distintas.
Supongamos que $P$ tiene raíces distintas $\lambda_1, \dots, \lambda_k$ . Demuestre que las sucesiones geométricas $(\lambda_i^n)_n$ forman la base del espacio de soluciones. de $(\mathcal R)$ , por lo que cada solución es $u_n = \sum_i c_i\lambda_i^n$ para constantes únicas $c_i$ .
Resolver completamente: $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ .

Parte II — The shift operator and the fundamental theorem. Sea $\mathcal{S}$ el espacio vectorial $\C$ de todas las secuencias complejas y $S \in \mathcal{L}(\mathcal{S})$ el turno, $S\bigl((u_n)_n\bigr) = (u_{n+1})_n$ .

Demuestre que el conjunto de soluciones de $(\mathcal R)$ es $\ker P(S)$ y que tiene la dimensión exactamente $k$ (mapa un solución a sus valores iniciales).
Explique por qué el lema de descomposición del núcleo (Teorema 3.14) se aplica a $S$ en el $\mathcal{S}$ de dimensión infinita sin ningún cambio, y escriba la descomposición resultante de $\ker P(S)$ para $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ (distinto $\lambda_i$ , todos distintos de cero desde $a_0 \neq 0$ ).
Para $\lambda \neq 0$ y $m \geq 1$ , mostrar

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

de dimensión $m$ . (Compute $(S - \lambda)\bigl(Q(n)\lambda^n\bigr) = \lambda^{n+1}(\Delta Q)(n)$ with $\Delta Q = Q(X + 1) - Q(X)$ , and use that $\Delta$ drops the degree; for the dimension, bound it by $m$ via initial values.)
(El teorema fundamental de las recurrencias lineales) Concluye: si $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ con el $\lambda_i$ distintos y distintos de cero, las soluciones de $(\mathcal R)$ son exactamente las secuencias

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

con polinomios determinados de forma única $Q_i$ .
Resuelva completamente: $u_{n+2} = 4u_{n+1} - 4u_n$ , $u_0 = 1$ , $u_1 = 0$ y verifique la respuesta en $u_2$ .

Parte III — Dominant roots and Diophantine dividends.

Supongamos que las raíces son simples con $\abs{\lambda_1} > \abs{\lambda_i}$ para $i \geq 2$ y $u_n = \sum_i c_i \lambda_i^n$ con $c_1 \neq 0$ . Mostrar $u_n \sim c_1\lambda_1^n$ y $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$ . Muestra que $q(a, b) = a^2 - 2b^2$ satisface $q(a_{n+1}, b_{n+1}) = -q(a_n, b_n)$ , por lo tanto $a_n^2 - 2b_n^2 = (-1)^{n+1}$ ; relacionar esto con el determinante de $M = \left(\begin{smallmatrix}1 & 2\\ 1 & 1\end{smallmatrix}\right)$ .
Deducir la estimación del error

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

y muestre que decae geométricamente con la relación $3 - 2\sqrt2$ (find the valores propios of $M$ and the growth of $b_n$ ).
(Crecimiento general) De la pregunta 9, demuestre: (a) si cada raíz satisface $\abs{\lambda_i} \leq \rho$ , entonces $\abs{u_n} \leq C\,n^{m-1}\rho^n$ con $m = \max_i m_i$ ; (b) si hay una raíz única $\lambda_1$ de máximo módulo y $Q_1 \neq 0$ , luego $u_{n+1}/u_n \to \lambda_1$ — verifíquelo en la solución de la pregunta 10.

Parte IV — Counting walks and words. Para un gráfico finito con conjunto de vértices $\{1, \dots, N\}$ , el matriz de adyacencia $A$ tiene $A_{ij} = 1$ si $ij$ es una ventaja, más $0$ .

Demuestre que $(A^n)_{ij}$ es el número de recorridos de longitud $n$ de $i$ a $j$ (secuencias de aristas $n$ , cada paso a lo largo de un borde).
(El triángulo) Para ver el gráfico completo en los vértices $3$ , $A = J - I$ : usando el espectro de $J$ (Ejemplo 2.19), mostrar

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

y verifique ambos en $n = 2$ enumerando los paseos.
(Palabras sin $11$ ) Sea $w_n$ el número de binarios palabras de longitud $n$ sin dos $1$ consecutivos. Codifica palabras por su última letra para obtener una transferencia matriz, mostrar $w_{n+2} = w_{n+1} + w_n$ , deducir $w_n = F_{n+2}$ (Fibonacci, Ejercicio 3.5), y dé la tasa de crecimiento $\lim w_{n+1}/w_n$ .
(La ruta) Para el gráfico de ruta $1 - 2 - 3$ , muestre el valores propios de $A$ son $\sqrt2, 0, -\sqrt2$ con vectores propios $(1, \pm\sqrt2, 1)$ y $(1, 0, -1)$ , y deducir que el número de recorridos de longitud $n$ desde el final para finalizar es $\bigl((\sqrt2)^n + (-\sqrt2)^n\bigr)/4$ : cero para $n$ impar y $2^{\,n/2 - 1}$ para $n$ par. Consultar en $n = 4$ .
(Fórmula de seguimiento) Muestra que el número total de caminatas de longitud $n$ (todos los puntos de partida) son $\operatorname{tr}(A^n) = \sum_i \lambda_i^n$ , y verifíquelo en el triángulo.

Part V — A ring of sequences: simultaneous diagonalization. Reparar $k \geq 3$ , dejar $\omega = \eu^{2\iu\pi/k}$ , y sea $W \in \mathcal{M}_k(\C)$ el turno cíclico: $W e_i = e_{i+1}$ (índices mod $k$ , columnas indexadas $0, \dots, k-1$ ).

Demuestre que $W^{\mathsf T}$ es la matriz compañera de $X^k - 1$ , deduzca $\chi_W = \mu_W = X^k - 1$ , y que $W$ es diagonalizable con el $k$ simple valores propios $\omega^j$ y vectores propios $f_j = (1, \omega^{-j}, \omega^{-2j}, \dots, \omega^{-(k-1)j})^{\mathsf T}$ .
Una matriz circulante es $C = c_0 I + c_1 W + \dots + c_{k-1}W^{k-1}$ . Demuestre que todos los circulantes viajan, que la base $(f_0, \dots, f_{k-1})$ diagonaliza todo de ellos simultáneamente, y que el valores propios de $C$ son $\widehat c(\omega^j) = \sum_m c_m \omega^{jm}$ , $j = 0, \dots, k-1$ .
Deduce $\det C = \prod_{j=0}^{k-1} \widehat c(\omega^j)$ , y comprueba que $k = 3$ recupera el factorización de Ejercicio 2.8.
(El collar promedio) Deja $x^{(n+1)} = Mx^{(n)}$ con $M = \frac12(W + W^{-1})$ : cada uno de los números $k$ ordenados en un anillo se reemplaza por el promedio de sus dos vecinos. Mostrar el valores propios de $M$ son $\cos(2\pi j/k)$ , y que el coeficiente de $x^{(0)}$ en $f_0$ es la media $\frac1k\sum_m x^{(0)}_m$ (sume las coordenadas de $f_j$ ).
Concluye: para $k$ impar, $x^{(n)}$ converge al vector constante cuyo valor es la media del inicial valores; para $k = 4$ , exhiba el responsable de valor propio. por la no convergencia y la obstrucción exacta (un coeficiente de media alterna que debe desaparecer).
(Síntesis) En una frase cada uno: cómo el compañero La matriz convierte el análisis de $(\mathcal R)$ en reducción; donde se necesita el lema de descomposición del núcleo ninguna dimensión finita; por qué gobierna el dominante valores propios tasas de crecimiento y error diofántico; ¿Por qué los poderes del paseos de recuento de matriz de adyacencia; y que desplazamientos comprar matrices. Nombra las dos cumbres: la fundamental teorema de recurrencias lineales, y — para el positivo matrices de la Parte IV, en el volumen del Año 3 — el Teorema de Perron-Frobenius.

Solución

Solución de Problema 3.1.

1. Las primeras coordenadas $k - 1$ de $Cv_n$ son $u_{n+1}, \dots, u_{n+k-1}$ (los desplazamientos superdiagonales), y la última es $a_0 u_n + \dots + a_{k-1}u_{n+k-1}$ . Entonces $v_{n+1} = Cv_n$ se mantiene para todos $n$ si las últimas coordenadas coinciden con todos $n$ , es decir, si $(\mathcal R)$ se mantiene. Iterando, $v_n = C^nv_0$ .

2. Expande $D_k(X) = \det(XI_k - C)$ a lo largo de la primera columna: las dos entradas distintas de cero son $X$ (posición $(1,1)$ ) y $-a_0$ (posición $(k,1)$ ). El primer menor tiene forma de $D_{k-1}$ . para los coeficientes $a_1, \dots, a_{k-1}$ ; el segundo menor es triangular superior con diagonal $-1$ : determinante $(-1)^{k-1}$ , con signo $(-1)^{k+1}$ de la posición. Inducción en $k$ (base $k = 1$ : $X - a_0$ ) da

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$ : desde $Q(C^{\mathsf T}) = Q(C)^{\mathsf T}$ para cualquier polinomio, $C$ y $C^{\mathsf T}$ tienen el mismo aniquiladores, de ahí el mismo polinomio mínimo. Para $C^{\mathsf T}$ : el las columnas dicen $C^{\mathsf T}e_1 = e_2$ , …, $C^{\mathsf T}e_{k-1} = e_k$ , por lo que $(e_1, C^{\mathsf T}e_1, \dots, (C^{\mathsf T})^{k-1}e_1)$ es la base canónica: gratis. Un polinomio $Q \neq 0$ de grado $< k$ tiene entonces $Q(C^{\mathsf T})e_1 \neq 0$ (es una combinación no trivial de vectores base): $\deg\mu \geq k$ . Como $\mu \mid \chi = P$ con $\deg P = k$ : $\mu_C = P$ .

3. Para $v = (1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ : las filas $1$ a $k-1$ de $Cv$ dan $\lambda, \lambda^2, \dots, \lambda^{k-1}$ , es decir, $\lambda$ multiplicadas por las primeras entradas $k - 1$ de $v$ ; la última fila da $\sum_m a_m\lambda^m = \lambda^k - P(\lambda) = \lambda^k = \lambda\cdot\lambda^{k-1}$ . Entonces $Cv = \lambda v$ . Por el contrario, las ecuaciones $(Cx)_i = \lambda x_i$ para $i < k$ lee $x_{i+1} = \lambda x_i$ : cualquier vector propio es proporcional a $v$ — cada espacio propio tiene una dimensión exacta $1$ . Diagonalizable si las dimensiones espacio propio suman $k$ (Teorema 3.6) si hay $k$ distintos valores propios si $P$ tiene raíces distintas $k$ (las valores propios son las raíces de $\chi_C = P$ ).

4. Cada $(\lambda_i^n)_n$ resuelve $(\mathcal R)$ : $\lambda_i^{n+k} = \lambda_i^n\,\lambda_i^k = \lambda_i^n\sum_m a_m\lambda_i^m$ . La libertad: una desaparición combinación $\sum_i c_i\lambda_i^n = 0$ para $n = 0, \dots, k-1$ es un sistema Vandermonde (Ejercicio 2.11) en el $c_i$ : todos $c_i = 0$ . El espacio de solución tiene dimensión $k$ (pregunta 6, cuya prueba es elemental e independiente): $k$ soluciones gratuitas forman una base y las coordenadas son únicas.

5. $P = X^2 - X - 6 = (X - 3)(X + 2)$ : solución general $u_n = A\,3^n + B(-2)^n$ . Condiciones iniciales: $A + B = 1$ , $3A - 2B = 8$ : $A = 2$ , $B = -1$ :

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

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

6. $P(S)\bigl((u_n)\bigr)$ es la secuencia $n \mapsto u_{n+k} - a_{k-1}u_{n+k-1} - \dots - a_0u_n$ : desaparece si y así $(\mathcal R)$ se cumple, por lo que el conjunto de soluciones es $\ker P(S)$ , un subespacio. El mapa $\ker P(S) \to \C^k$ , $u \mapsto (u_0, \dots, u_{k-1})$ , es lineal, inyectivo (la recurrencia determina $u_{k}, u_{k+1}, \dots$ a partir de los primeros valores de $k$ , por inducción) y sobreyectiva (defina $u_n$ recursivamente a partir de cualquier dato inicial): dimensión $k$ .

7. La prueba de usos Teorema 3.14 sólo: la identidad de Bézout en $\C[X]$ , y el hecho de que polinomios en un endomorfismo fijo conmutan. Ninguno menciona la dimensión del espacio ambiental: el lema se cumple palabra por palabra para $S \in \mathcal{L}(\mathcal{S})$ . Por lo tanto

\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$ tiene $n$ -ésimo término $Q(n{+}1)\lambda^{n+1} - \lambda Q(n)\lambda^n = \lambda^{n+1}(\Delta Q)(n)$ , con $\Delta Q = Q(X{+}1) - Q(X)$ de grado $\deg Q - 1$ (los términos principales se cancelan). iterando, $(S - \lambda)^m\bigl(Q(n)\lambda^n\bigr) = \bigl(\lambda^{n+m}(\Delta^m Q)(n)\bigr)_n$ y $\Delta^m Q = 0$ cuando $\deg Q \leq m - 1$ : el conjunto de la derecha está contenido en el núcleo. Es un subespacio de dimensión $m$ : las secuencias $(n^j\lambda^n)_n$ , $0 \leq j < m$ , son libres, ya que $\sum_j c_j n^j\lambda^n = 0$ para todas las fuerzas $n$ (dividiendo por $\lambda^n \neq 0$ ) el polinomio $\sum_j c_jX^j$ desaparecerá en cada $n \in \N$ , por lo tanto, cero. Por el contrario $\dim\ker(S - \lambda)^m \leq m$ : al expandir $(S - \lambda)^m = \sum_j \binom mj(-\lambda)^{m-j}S^j$ , la ecuación $(S - \lambda)^m u = 0$ es una recurrencia lineal de orden $m$ (coeficiente principal $1$ ), por lo que $u$ está determinado por $u_0, \dots, u_{m-1}$ como en pregunta 6. Concluye igualdad de dimensiones.

9. Combine las preguntas 7 y 8: cada solución se descompone únicamente como una suma de elementos de $\ker(S - \lambda_i)^{m_i}$ , es decir, $u_n = \sum_i Q_i(n)\lambda_i^n$ con $\deg Q_i \leq m_i - 1$ ; el $Q_i$ son únicos porque el La descomposición es directa y, dentro de cada suma, la Los coeficientes de $Q_i$ son coordenadas en la base. $(n^j\lambda_i^n)_j$ (pregunta 8). Verificación de cordura en las dimensiones: $\sum_i m_i = k$ .

10. $P = X^2 - 4X + 4 = (X - 2)^2$ : soluciones $(a + bn)2^n$ . Datos iniciales: $a = 1$ , $2(a + b) = 0$ , entonces $b = -1$ :

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

Verifique: $u_2 = 4u_1 - 4u_0 = -4$ y $(1 - 2)\cdot4 = -4$ .

11. Escribe $u_n = \lambda_1^n\bigl(c_1 + \sum_{i\geq2} c_i(\lambda_i/\lambda_1)^n\bigr)$ ; cada relación tiene módulo $< 1$ , por lo que el corchete tiende a $c_1 \neq 0$ : $u_n \sim c_1\lambda_1^n$ . En particular $u_n \neq 0$ para $n$ grande, y

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

12. Calcular:

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

Con $q(a_0, b_0) = 1 - 2 = -1$ : $a_n^2 - 2b_n^2 = (-1)^{n+1}$ . Estructuralmente: $q(a, b) = (a - \sqrt2\,b)(a + \sqrt2\,b)$ y el mapa lineal $M$ multiplica el factor $a + \sqrt2 b$ por $1 + \sqrt2$ y el factor $a - \sqrt2 b$ por $1 - \sqrt2$ (calcular: $a_{n+1} + \sqrt2 b_{n+1} = (1 + \sqrt2)(a_n + \sqrt2 b_n)$ ); el producto se multiplica por $(1 + \sqrt2)(1 - \sqrt2) = -1 = \det M$ en cada paso.

13. Desde $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$ (inducción: ambos aumentan) entonces $a_n + \sqrt2 b_n \geq (1 + \sqrt2)b_n \geq 2b_n$ . Valores propios de $M$ : $\chi_M = X^2 - 2X - 1$ , raíces $1 \pm \sqrt2$ ; desde $(a_0, b_0)$ tiene un componente distinto de cero en el vector propio dominante (todas las entradas positivo), $b_n \sim c(1 + \sqrt2)^n$ con $c > 0$ (pregunta 11). Por tanto, el error es $\asymp (1 + \sqrt2)^{-2n} = (3 + 2\sqrt2)^{-n}$ : decaimiento geométrico con relación $1/(3 + 2\sqrt2) = 3 - 2\sqrt2 \approx 0.172$ .

14. (a) De la pregunta 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$ , y cada $\abs{Q_i(n)} \leq C_i n^{m_i - 1} \leq C_i n^{m-1}$ para $n \geq 1$ : sume las constantes. (b) Sean $\rho' = \max_{i \geq 2}\abs{\lambda_i} < \abs{\lambda_1}$ y $d = \deg Q_1$ , coeficiente principal $c \neq 0$ . Luego $u_n = Q_1(n)\lambda_1^n + R_n$ con $\abs{R_n} \leq Cn^{m-1}\rho'^n$ , y

\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

(polinomio de tiempos geométricos). entonces

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{(since } Q_1(n{+}1)/Q_1(n) \to 1\text{)}.

Verifique la pregunta 10: para $u_n = (1-n)2^n$ la relación es

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

15. Inducción en $n$ . Para $n = 1$ , $A_{ij}$ cuenta paseos de longitud $1$ . Paso: un recorrido de longitud $n + 1$ desde $i$ hasta $j$ es un paseo de longitud $n$ desde $i$ hasta algún vértice $\ell$ seguido de una arista $\ell j$ :

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

16. $J = 3\Pi$ donde $\Pi = J/3$ es la proyección sobre $\operatorname{Vect}(1,1,1)$ a lo largo del avión $x + y + z = 0$ ( $\Pi^2 = \Pi$ desde $J^2 = 3J$ ). Entonces $A = J - I = 2\Pi - (I - \Pi)$ , y como $\Pi$ y $I - \Pi$ son complementarios proyecciones,

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),

que da las dos fórmulas mostradas. En $n = 2$ : diagonal $(4 + 2)/3 = 2$ (camina $i \to \ell \to i$ para los dos vecinos $\ell$ ); $(4 - 1)/3 = 1$ fuera de la diagonal (el recorrido único $i \to \ell \to j$ a través del tercer vértice).

17. Deje que $w_n^{(0)}, w_n^{(1)}$ cuente las palabras admisibles de longitud $n$ que termina en $0$ , resp. $1$ . Adjuntando una letra: a $0$ puede seguir cualquier cosa, un $1$ solo un $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}.

Sumando, $w_{n+2} = w_{n+1} + w_n$ (o: condición en el primer carta). Con $w_1 = 2$ , $w_2 = 3$ : $w_n = F_{n+2}$ por inducción ( $F_3 = 2$ , $F_4 = 3$ , misma recurrencia). Crecimiento: las raíces de $X^2 - X - 1$ son $\varphi > \abs\psi$ (Ejercicio 3.5), y el componente $\varphi$ es distinto de cero (los $w_n$ son positivos y $\psi^n \to 0$ ), así que pregunte 11 da $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)$ . Comprobar:

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 :

valores propios $\sqrt2, -\sqrt2, 0$ ( $= 2\cos\frac\pi4, 2\cos\frac{3\pi}4, 2\cos\frac\pi2$ ). Descomponer $e_1$ en el base propia y leer la tercera coordenada, o usar simetría: con $v_\pm = (1, \pm\sqrt2, 1)$ , $v_0 = (1, 0, -1)$ , uno marca $e_1 = \frac14 v_+ + \frac14 v_- + \frac12 v_0$ , entonces 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},

cero para $n$ impar (gráfico bipartito: los extremos están a una distancia par), y $2\cdot 2^{n/2}/4 = 2^{n/2 - 1}$ para incluso $n$ . En $n = 4$ : $2^{1} = 2$ , haciendo coincidir los dos paseos $1\,2\,1\,2\,3$ y $1\,2\,3\,2\,3$ .

19. Los paseos cerrados de longitud $n$ desde $i$ son $(A^n)_{ii}$ ; sumando $i$ da $\operatorname{tr}(A^n)$ . Trigonalizando $A$ (sobre $\C$ ), $A^n$ es triangular con 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$ : el espectro $\{2, -1, -1\}$ , consistente con la pregunta 16.

20. Las columnas de $W^{\mathsf T}$ : $W^{\mathsf T}e_i = e_{i-1}$ para $i \geq 1$ y $W^{\mathsf T}e_0 = e_{k-1}$ ; reetiquetado en el orden $e_0, e_1, \dots$ este es exactamente el matriz complementaria de $X^k - 1$ ( $a_0 = 1$ , otra $a_m = 0$ ). Pregunta 2: $\chi_{W} = \chi_{W^{\mathsf T}} = X^k - 1 = \mu_{W}$ . Las raíces $\omega^j$ ( $j = 0, \dots, k-1$ ) son las $k$ distintas raíces de unidad $k$ : $W$ es diagonalizable (pregunta 3, o Ejercicio 3.8: $W^k = I$ ). Vectores propios: $Wf_j = \sum_m \omega^{-jm}e_{m+1} = \sum_{m'}\omega^{-j(m'-1)}e_{m'} = \omega^j f_j$ .

21. Los circulantes son polinomios en $W$ y los polinomios en una matriz fija conmutan entre sí. Cada $f_j$ es un vector propio de cada potencia: $W^m f_j = \omega^{jm}f_j$ , entonces

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

la base $(f_0, \dots, f_{k-1})$ (gratis: Vandermonde en el distinta $\omega^{-j}$ , Ejercicio 2.11) diagonaliza cada circulante a la vez, con el indicado valores propios.

22. El determinante es el producto del valores propios (diagonalizar): $\det C = \prod_{j}\widehat c(\omega^j)$ . Para $k = 3$ , $c_0 = a$ , $c_1 = b$ , $c_2 = c$ y $\omega = j = \eu^{2\iu\pi/3}$ :

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

y $j^4 = j$ : exactamente la factorización de Ejercicio 2.8.

23. $M = \frac12(W + W^{-1})$ es un circulante ( $W^{-1} = W^{k-1}$ ), con valores propios $\frac12(\omega^j + \omega^{-j}) = \cos\frac{2\pi j}k$ en la misma base $f_j$ . Coordenadas: escribir $x^{(0)} = \sum_j \alpha_j f_j$ . Las coordenadas de $f_j$ suman $\sum_m \omega^{-jm}$ , que es $k$ para $j = 0$ y $0$ en caso contrario (suma geométrica con relación $\omega^{-j} \neq 1$ ). Sumando las coordenadas de $x^{(0)}$ : $\sum_m x^{(0)}_m = \alpha_0\,k$ , entonces $\alpha_0 = \frac1k\sum_m x^{(0)}_m$ , la media.

24. $x^{(n)} = M^nx^{(0)} = \sum_j \alpha_j\cos^n\bigl(\tfrac{2\pi j}k\bigr)f_j$ . Para $k$ impar, $\abs{\cos(2\pi j/k)} < 1$ por cada $j \neq 0$ (el ángulo es nunca $0$ o $\pi$ ), por lo que todos los términos excepto $j = 0$ tienden a $0$ : $x^{(n)} \to \alpha_0 f_0$ , el vector constante igual al media — promediar en un anillo impar iguala. Para $k = 4$ el valores propios son $1, 0, -1, 0$ : el término $j = 2$ $\alpha_2(-1)^nf_2$ con $f_2 = (1, -1, 1, -1)^{\mathsf T}$ oscila para siempre. La obstrucción es la media alterna: multiplicando las coordenadas de $x^{(0)}$ por $(-1)^m$ y sumando, el mismo cálculo de suma geométrica da $\sum_m (-1)^mx^{(0)}_m = 4\alpha_2$ : el proceso converge si y solo $x^{(0)}_0 - x^{(0)}_1 + x^{(0)}_2 - x^{(0)}_3 = 0$ , y luego converge a la media.

25. La matriz complementaria convierte una recurrencia escalar de orden $k$ en una recurrencia vectorial de primer orden, de modo que las fórmulas cerradas se convierten en declaraciones sobre $C^n$ — reducciones terreno de origen (preguntas 1 a 5). El lema de descomposición del núcleo es álgebra polinómica pura (Bézout más conmutación), por lo que se divide $\ker P(S)$ aunque $\mathcal{S}$ es de dimensión infinita (preguntas 7–9). Los dominantes valores propios gobiernan el crecimiento porque cualquier otra contribución es geométricamente insignificante después normalización — que es también la razón por la que el error Pell decae en el cuadrado de la raíz dominante (preguntas 11–14). poderes de la el recuento de matrices de adyacencia camina porque las sumas de multiplicación de matrices sobre vértices intermedios, por lo que los espectros cuentan recorridos cerrados (preguntas 15–19). Las matrices de conmutación comparten una base propia, y una base de Fourier luego diagonaliza toda el álgebra circulante de un solo golpe (preguntas 20-24). Cumbres: lo fundamental teorema de recurrencias lineales (pregunta 9); y para no negativo matrices, la razón por la que las raíces dominantes como $\varphi$ o $1 + \sqrt2$ son automáticamente reales, positivas y simples es la Teorema de Perron-Frobenius, demostrado en el volumen del año 3.