Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

3Reductie van endomorfismen

Om een endomorfisme te begrijpen, vind de richtingen die het slechts rekt. Dit hoofdstuk bouwt de machinerie — eigenwaarden, karakteristieke en minimale veeltermen, het kernontbindingslemma — en haar beloningen: diagonaliseerbaarheids- en trigonaliseerbaarheidscriteria, Cayley–Hamilton, de Dunford-ontbinding, en de berekening van machten en exponentialen die Hoofdstuk 16 zal voeden. Overal is $E$ een eindigdimensionale $K$ -vectorruimte ( $K = \R$ of $\C$ ) en $u \in \mathcal{L}(E)$ , $n = \dim E$ .

3.1 Eigenwaarden en eigenvectoren

Definitie 3.1

$\lambda \in K$ is een eigenwaarde van $u$ wanneer $u(x) = \lambda x$ voor zekere $x \neq 0$ (een eigenvector); de eigenruimte is $E_\lambda(u) = \ker(u - \lambda\,\mathrm{id})$ . De verzameling van eigenwaarden is het spectrum $\operatorname{Sp}(u)$ . Een deelruimte $F$ is stabiel wanneer $u(F) \subseteq F$ ; eigenruimten zijn stabiel, en stabiele deelruimten laten geïnduceerde endomorfismen $u|_F$ toe.

Stelling 3.2 (Onafhankelijkheid van eigenruimten)

Eigenvectoren behorend bij paarsgewijs verschillende eigenwaarden vormen een vrije familie; equivalent, is de som van de eigenruimten $E_{\lambda_1} + \dots + E_{\lambda_r}$ (verschillende $\lambda_i$ ) direct. In het bijzonder heeft $u$ hoogstens $n$ eigenwaarden.

Bewijs. Door inductie op $r$ . Stel $x_1 + \dots + x_r = 0$ met $x_i \in E_{\lambda_i}$ , de uitspraak bekend voor $r - 1$ . Pas $u$ toe en trek $\lambda_r$ maal de relatie af:

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

dus door inductie elke $(\lambda_i - \lambda_r)x_i = 0$ , d.w.z. $x_i = 0$ voor $i < r$ , dan $x_r = 0$ . Directe sommen van niet-nulle ruimten in een ruimte van dimensie $n$ hebben hoogstens $n$ sommanden. ∎

De matrix A = psmallmatrix2 & 1\\ 1 & 2 psmallmatrix werkend op het vlak: de generieke vector e_1 wordt van haar lijn gestoten, maar de eigenrichtingen v_1 = (1,1) en v_2 = (1,-1) worden slechts gerekt — met 3 en met 1 (dus Av_2 = v_2: het gestippelde beeld valt samen met v_2). Diagonaliseren is de overgang naar de basis (v_1, v_2), waar A diag(3, 1) wordt. — De matrix $A = \left(\begin{smallmatrix}2 & 1\\ 1 & 2\end{smallmatrix}\right)$ werkend op het vlak: de generieke vector $e_1$ wordt van haar lijn gestoten, maar de eigenrichtingen $v_1 = (1,1)$ en $v_2 = (1,-1)$ worden slechts gerekt — met $3$ en met $1$ (dus $Av_2 = v_2$ : het gestippelde beeld valt samen met $v_2$ ). Diagonaliseren is de overgang naar de basis $(v_1, v_2)$ , waar $A$ $\operatorname{diag}(3, 1)$ wordt.

Definitie 3.3 (Karakteristieke veelterm)

$\chi_u(X) = \det(X\,\mathrm{id} - u)$ — berekend in elke basis als $\det(XI_n - A)$ , een monische veelterm van graad $n$ , invariant onder gelijkvormigheid (Stelling 2.17). Haar wortels in $K$ zijn precies de eigenwaarden ( $\lambda$ eigenwaarde $\iff u - \lambda\,\mathrm{id}$ niet injectief $\iff \chi_u(\lambda) = 0$ ), en

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

De algebraïsche multipliciteit $m_\lambda$ van een eigenwaarde is haar multipliciteit als wortel van $\chi_u$ ; de meetkundige multipliciteit is $\dim E_\lambda$ , en $1 \leq \dim E_\lambda \leq m_\lambda$ .

Bewijs van de gestelde feiten. De coëfficiëntclaims: ontwikkel $\det(XI - A)$ door de permutatieformule; de identiteitspermutatie draagt $\prod_i (X - a_{ii}) = X^n - (\sum a_{ii})X^{n-1} + \dots$ bij, en elke andere permutatie fixeert hoogstens $n - 2$ diagonaalposities, bijdragend graad $\leq n - 2$ : de top twee coëfficiënten zijn zoals gesteld; $X = 0$ geeft de constante term $\det(-A) = (-1)^n\det A$ .

Meetkundig $\leq$ algebraïsch: zij $d = \dim E_\lambda$ en vul een basis van $E_\lambda$ aan tot een basis van $E$ ; de matrix van $u$ is blokbovendriehoekig met linksboven blok $\lambda I_d$ , dus $\chi_u(X) = (X - \lambda)^d\, \chi_{\text{(onderblok)}}(X)$ : de multipliciteit van $\lambda$ is minstens $d$ . ∎

Voorbeeld 3.4 (Zelfde $\chi$ , verschillende meetkunde)

De matrices

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

delen de karakteristieke veelterm $(X - 2)^2$ , het spoor, de determinant, het spectrum — maar zijn niet gelijkvormig: de eerste heeft $E_2$ van dimensie $2$ (meetkundige multipliciteit $2$ ), de tweede van dimensie $1$ . De karakteristieke veelterm ziet alleen algebraïsche multipliciteiten; de eigenruimtedimensies zijn de fijnere invariant, en de minimale veelterm beslecht ( $X - 2$ versus $(X - 2)^2$ ). Moraal voor alle diagonaliseerbaarheidsdiscussies: $\chi$ shortlist de kandidaten, maar kernen brengen de stemmen uit.

Definitie 3.5 (Diagonaliseerbaar, trigonaliseerbaar)

$u$ is diagonaliseerbaar wanneer $E$ een basis van eigenvectoren heeft (matrix: gelijkvormig met een diagonaalmatrix); trigonaliseerbaar wanneer haar matrix in zekere basis bovendriehoekig is.

Stelling 3.6 (Diagonaliseerbaarheidscriteria)

De volgende zijn equivalent:

$u$ is diagonaliseerbaar;
$E = \bigoplus_{\lambda \in \operatorname{Sp} u} E_\lambda$ ;
$\chi_u$ splitst over $K$ en $\dim E_\lambda = m_\lambda$ voor elke eigenwaarde;
(voldoende, niet noodzakelijk) $\chi_u$ heeft $n$ verschillende wortels in $K$ .

Bewijs. (1 $\iff$ 2): een basis van eigenvectoren sorteert in bases van de $E_\lambda$ ’s, en omgekeerd geeft concatenatie van bases van de directe sommanden een basis van $E$ (Stelling 3.2 maakt de som direct; dimensiegelijkheid maakt haar alles).

(2 $\iff$ 3): in de diagonale basis splitst $\chi_u = \prod (X - \lambda)^{\dim E_\lambda}$ met matchende multipliciteiten. Omgekeerd, stel $\chi_u$ splitst met $\dim E_\lambda = m_\lambda$ overal; dan heeft de directe som van de eigenruimten (direct door Stelling 3.2) dimensie

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

de middelste gelijkheid omdat de graad van een gesplitste veelterm de som van haar wortelmultipliciteiten is: de som is heel $E$ . Merk waar elke hypothese werkte: splijting vulde de graad, multipliciteitsgelijkheid vulde de dimensies.

(4 $\Rightarrow$ 1): $n$ verschillende eigenwaarden geven $n$ onafhankelijke eigenvectoren (Stelling 3.2): een basis. ∎

Methode 3.7 (Diagonaliseerbaarheid beslissen)

In de praktijk, test in deze volgorde — elke stap kan de klus klaren. (1) Presenteert zich een annulerende veelterm met eenvoudige gesplitste wortels ( $u^2 = \mathrm{id}$ , $u^2 = u$ , $u^k = \mathrm{id}$ )? Zo ja: diagonaliseerbaar, geen berekening (Gevolg 3.17 hieronder). (2) Bereken $\chi_u$ ; als ze $n$ verschillende wortels in $K$ heeft: diagonaliseerbaar (Stelling 3.6 (4)). (3) Anders, voor elke meervoudige wortel $\lambda$ alleen, vergelijk $\dim\ker(u - \lambda\,\mathrm{id})$ met de multipliciteit $m_\lambda$ : elk tekort doodt diagonaliseerbaarheid; gelijkheid overal bewijst ze. Bereken nooit eigenruimten van enkelvoudige wortels (hun dimensie is gedwongen $1$ ), en trigonaliseer nooit alleen om te beslissen.

Voorbeeld 3.8 (Diagonaliseren aan het werk)

$A = I + J = \left(\begin{smallmatrix}2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2\end{smallmatrix}\right)$ , met $J$ de all-eens-matrix: uit $\operatorname{Sp}(J) = \{3, 0\}$ (Voorbeeld 2.19), $\operatorname{Sp}(A) = \{4, 1\}$ , met eigenruimten $\R(1,1,1)$ en het vlak $\{x + y + z = 0\}$ : dimensies $1 + 2 = 3$ , diagonaliseerbaar (Stelling 3.6 (2)). Machten zonder enige basisveranderingsmatrix: met $\Pi = J/3$ de projector op $\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 .

(Controle $k = 1$ : $\frac{4-1}3 J + I = A$ .) Het sluitende inzicht: wanneer de eigenruimten zichtbaar zijn, berekenen spectrale projectoren machten sneller dan $PDP^{-1}$ ooit zal — en de formule toont de dynamica: $A^k$ groeit als $4^k$ langs $(1,1,1)$ en blijft staan op het orthogonale vlak.

Stelling 3.9 (Trigonalisatie)

$u$ is trigonaliseerbaar over $K$ desda $\chi_u$ over $K$ splitst. In het bijzonder is elk endomorfisme van een $\C$ -vectorruimte trigonaliseerbaar.

Bewijs. ( $\Rightarrow$ ) De karakteristieke veelterm van een driehoekige matrix is $\prod(X - t_{ii})$ : gesplitst.

( $\Leftarrow$ ) Inductie op $n$ . Omdat $\chi_u$ splitst, heeft ze een wortel $\lambda$ : kies een eigenvector $e_1$ . In een basis beginnend met $e_1$ is de matrix $\begin{pmatrix} \lambda & \ast\\ 0 & B\end{pmatrix}$ , en $\chi_u = (X - \lambda)\chi_B$ : $\chi_B$ splitst ook. Door de inductiehypothese toegepast op de $(n-1) \times (n-1)$ -matrix $B$ is er een inverteerbare $Q$ met $Q^{-1}BQ$ bovendriehoekig; conjugatie van de hele matrix door $\begin{pmatrix}1 & 0\\ 0 & Q\end{pmatrix}$ driehoekigt haar. ∎

Voorbeeld 3.10 (Met de hand trigonaliseren)

$B = \begin{pmatrix}3 & -1\\ 1 & 1\end{pmatrix}$ : $\chi_B = X^2 - 4X + 4 = (X - 2)^2$ , en $\ker(B - 2I) = \ker\left(\begin{smallmatrix}1 & -1\\ 1 & -1\end{smallmatrix}\right)$ is de lijn opgespannen door $e_1' = (1, 1)$ : één eigenwaarde, een eendimensionale eigenruimte — niet diagonaliseerbaar, maar trigonaliseerbaar (Stelling 3.9). Vul de basis aan met $e_2' = (1, 0)$ en bereken:

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

dus in de basis $(e_1', e_2')$ is de matrix $T = \left(\begin{smallmatrix}2 & 1\\ 0 & 2\end{smallmatrix}\right)$ . Het sluitende inzicht: de diagonaal van $T$ was gedwongen (beide entries moeten de dubbele eigenwaarde $2$ zijn); alleen de hoekentry hing af van de keuze van $e_2'$ , en herschalen van $e_2'$ kan er elke niet-nulle waarde van maken — de weerstandige “ $1$ ” is de schaduw van het nilpotente deel dat Dunford zal isoleren.

3.2 Veeltermen van een endomorfisme

Definitie 3.11

Voor $P = \sum a_k X^k \in K[X]$ , stel $P(u) = \sum a_k u^k \in \mathcal{L}(E)$ . De afbeelding $P \mapsto P(u)$ is een morfisme van algebras $K[X] \to \mathcal{L}(E)$ (Definitie 1.33); haar kern $\{P : P(u) = 0\}$ is een ideaal van $K[X]$ , niet-nul (de familie $(\mathrm{id}, u, \dots, u^{n^2})$ is afhankelijk in de $n^2$ -dimensionale $\mathcal{L}(E)$ ), dus voortgebracht door een unieke monische veelterm $\mu_u$ : de minimale veelterm (Stelling 1.26).

Propositie 3.12

$P(u) = 0 \iff \mu_u \mid P$ ; eigenwaarden van $u$ zijn wortels van elke annulerende veelterm, en de wortels van $\mu_u$ zijn precies de eigenwaarden.
Als $F$ stabiel is, $\mu_{u|_F} \mid \mu_u$ .

Bewijs. (1) De deelbaarheid is de definitie van een voortbrenger. Als $u(x) = \lambda x$ , $x \neq 0$ , dan $0 = P(u)(x) = P(\lambda)x$ , dus $P(\lambda) = 0$ : eigenwaarden zijn wortels van annihilatoren, in het bijzonder van $\mu_u$ . Omgekeerd, als $\lambda$ een wortel is, $\mu_u = (X - \lambda)Q$ met $Q(u) \neq 0$ (graad van $\mu_u$ minimaal): kies $y$ met $Q(u)(y) \neq 0$ ; dan $(u - \lambda)(Q(u)(y)) = \mu_u(u)(y) = 0$ vertoont de eigenvector $Q(u)(y)$ .

(2) $\mu_u(u|_F) = \mu_u(u)|_F = 0$ , en pas (1) toe op $u|_F$ . ∎

Voorbeeld 3.13 (Minimale veeltermen met de hand gevonden)

De minimale veelterm wordt berekend door opeenvolgende graden te testen. Voor de all-eens-matrix $J \in \mathcal{M}_3(\R)$ : $J \neq \lambda I$ (graad $1$ is uit), en $J^2 = 3J$ , dus

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

graad $2$ , gesplitst, enkelvoudige wortels — $J$ is diagonaliseerbaar met spectrum $\{0, 3\}$ (Gevolg 3.17 hieronder), bevestigend Voorbeeld 2.19 zonder één enkele determinant. Voor de swapmatrix $A$ van Voorbeeld 3.15: $A \neq \pm I$ en $A^2 = I$ geven $\mu_A = X^2 - 1$ . In beide gevallen is het patroon hetzelfde: raad een lage-graad-identiteit uit de structuur (rang één dwingt $J^2 = (\operatorname{tr}J)\,J$ ; een involutie dwingt $A^2 = I$ ), controleer dan dat geen echte deler annuleert. Minimale veeltermen worden meestal gevonden, niet berekend uit $\chi$ .

Stelling 3.14 (Kernontbindingslemma)

Als $P = P_1 P_2 \cdots P_r$ met de $P_i$ paarsgewijs relatief priem, dan

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

en de projecties op de sommanden zijn veeltermen in $u$ .

Bewijs. Het volstaat $r = 2$ te behandelen en te induceren. Bézout in $K[X]$ (Stelling 1.26): $U P_1 + V P_2 = 1$ , dus voor elke $x$ ,

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

Als $x \in \ker P(u)$ : $P_2(u)(x_2) = U(u)\,P(u)(x) = 0$ (veeltermen in $u$ commuten), dus $x_2 \in \ker P_2(u)$ , en symmetrisch $x_1 \in \ker P_1(u)$ : de som vult $\ker P(u)$ ; beide sommanden zitten in $\ker P(u)$ ( $P_i \mid P$ ). Directheid: $x \in \ker P_1(u) \cap \ker P_2(u)$ geeft $x = U(u)P_1(u)x + V(u)P_2(u)x = 0$ . De formules voor $x_1, x_2$ vertonen de projecties als $V(u)P_2(u)$ en $U(u)P_1(u)$ . ∎

Voorbeeld 3.15 (Het kernlemma met expliciete projectoren)

Zij $A = \left(\begin{smallmatrix}0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{smallmatrix}\right)$ (verwissel de eerste twee coördinaten). Dan $A^2 = I$ : de veelterm $X^2 - 1 = (X - 1)(X + 1)$ annuleert $A$ , haar factoren zijn relatief priem, en Bézout is expliciet:

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

Het bewijs van Stelling 3.14 volgend, zijn de projecties op $\ker(A - I)$ en $\ker(A + I)$ de veeltermen in $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}.

Controle: $\pi_+ + \pi_- = I$ , $\pi_+\pi_- = 0$ , $\pi_\pm^2 = \pi_\pm$ , en de beelden zijn het vlak $\{x = y\}$ (symmetrische vectoren, eigenwaarde $1$ ) en de lijn $\R(1, -1, 0)$ (antisymmetrisch, eigenwaarde $-1$ ). Het kernlemma is geen bestaanuitspraak: Bézout-coëfficiënten zijn de projectorformules.

Voorbeeld 3.16 (Projectoren berekenen ook de exponentiaal)

Dezelfde swapmatrix, één dividend verder. Omdat $A = \pi_+ - \pi_-$ met algebraïsch-orthogonale projectoren ( $\pi_+\pi_- = 0$ ), gehoorzaamt elke macht $A^k = \pi_+ + (-1)^k\pi_-$ , en de exponentiaalreeks hergroepeert per projector:

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

(Controle $t = 0$ : de identiteit; afgeleide in $0$ : $A$ .) De eigenontbinding zet een matrixreeks om in twee scalaire reeksen — precies het mechanisme dat Hoofdstuk 16 op elk diagonaliseerbaar stelsel zal draaien, en de reden dat hyperbolische functies symmetrische koppelingen regeren.

Gevolg 3.17 (Diagonaliseerbaarheid via de minimale veelterm)

$u$ is diagonaliseerbaar $\iff$ $\mu_u$ splitst over $K$ met enkelvoudige wortels $\iff$ zekere annulerende veelterm van $u$ splitst met enkelvoudige wortels.

Bewijs. Als $P(u) = 0$ met $P = \prod_{i}(X - \lambda_i)$ (verschillende $\lambda_i$ ), geeft het lemma $E = \ker P(u) = \bigoplus_i \ker(u - \lambda_i)$ : een directe som van eigenruimten, dus is $u$ diagonaliseerbaar (Stelling 3.6). Omgekeerd wordt een diagonaliseerbare $u$ gedood door $\prod_{\lambda \in \operatorname{Sp}u}(X - \lambda)$ (ze doodt elke eigenruimte), die splitst met enkelvoudige wortels; en $\mu_u$ deelt haar terwijl ze dezelfde wortels heeft (Propositie 3.12): $\mu_u$ is precies dat product. ∎

Voorbeeld 3.18

Projecties voldoen aan $p^2 = p$ : geannuleerd door $X(X-1)$ , gesplitst enkelvoudige wortels — diagonaliseerbaar met spectrum $\subseteq \{0, 1\}$ , en $E = \ker p \oplus \ker(p - \mathrm{id})$ : de meetkundige analyse van Jaar 1, opnieuw bewezen in één regel. Symmetrieën ( $s^2 = \mathrm{id}$ , annihilator $X^2 - 1$ ): diagonaliseerbaar wanneer $\operatorname{char} K \neq 2$ , spectrum $\subseteq \{\pm 1\}$ . Een endomorfisme met $u^3 = u^2$ en $u^2 \neq u$ : geannuleerd door $X^2(X - 1)$ , niet noodzakelijk diagonaliseerbaar — het criterium detecteert het (dubbele wortel $0$ moet worden getest: diagonaliseerbaar desda bovendien $\ker u^2 = \ker u$ ).

Voorbeeld 3.19 (Het lichaam beslist: een rotatie in $\R^3$ )

Zij $R$ de kwartslag om de $z$ -as:

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

Over $\R$ : de enige eigenwaarde is $1$ , met eigenruimte de as $\R e_3$ — één lijn vaste vectoren, en geen verdere reductie: $R$ is noch diagonaliseerbaar noch trigonaliseerbaar in $\mathcal{M}_3(\R)$ ( $\chi_R$ splitst niet). Over $\C$ : drie verschillende eigenwaarden $1, \iu, -\iu$ , dus is $R$ diagonaliseerbaar, met eigenvectoren $e_3$ en $e_1 \mp \iu e_2$ . De meetkunde was hoorbaar in de algebra: rotaties in het vlak hebben geen reële invariante richtingen, en de complexe eigenwaarden $\pm\iu$ van modulus $1$ bewaren de hoek ( $\pm\frac\pi2$ ) die de reële matrix alleen kan uitdrukken door coördinaten te mengen.

Voorbeeld 3.20 (Minimaal versus karakteristiek)

Voor $D = \operatorname{diag}(2, 2, 3)$ : $\chi_D = (X - 2)^2(X - 3)$ maar $\mu_D = (X - 2)(X - 3)$ , omdat $(D - 2I)(D - 3I) = 0$ (controleer op de canonieke basis) terwijl geen van beide factoren alleen $D$ doodt. Voor het shiftblok $N = \left(\begin{smallmatrix}0 & 1\\ 0 & 0\end{smallmatrix}\right) \oplus (3)$ , d.w.z. $N' = \left(\begin{smallmatrix}0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 3\end{smallmatrix}\right)$ : $\chi_{N'} = X^2(X - 3)$ en $\mu_{N'} = X^2(X - 3)$ — de dubbele wortel is echt nodig omdat $N'$ niet diagonaliseerbaar is aan de kern-kant ( $N'e_2 = e_1 \neq 0$ ). Vuistregel: $\mu$ en $\chi$ delen hun wortels (Propositie 3.12); de multipliciteit in $\mu$ meet de grootte van het grootste nilpotente blok, die in $\chi$ de totale dimensie van de karakteristieke deelruimte.

Stelling 3.21 (Cayley–Hamilton)

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

Bewijs. Fixeer $x \neq 0$ en zij $d$ maximaal met $(x, u(x), \dots, u^{d-1}(x))$ vrij; schrijf

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

en stel $P_x = X^d + a_{d-1}X^{d-1} + \dots + a_0$ , dus $P_x(u)(x) = 0$ . Vul de vrije familie aan tot een basis van $E$ : daarop heeft $u$ blokvorm $\begin{pmatrix} C & \ast\\ 0 & D\end{pmatrix}$ waarbij $C$ de begeleidende matrix van $P_x$ is, waarvan de karakteristieke veelterm $P_x$ is (ontwikkel $\det(XI - C)$ langs de eerste kolom, door inductie op $d$ ). Dus $\chi_u = P_x \cdot \chi_D$ , en

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

Het argument geldt voor elke $x$ : $\chi_u(u) = 0$ . ∎

Voorbeeld 3.22 (Cayley–Hamilton aan het werk)

$A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ : $\chi_A = X^2 - 5X - 2$ , dus $A^2 = 5A + 2I$ . Elke macht van $A$ stort in tot een combinatie van $I$ en $A$ :

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

en de inverse komt gratis: $A(A - 5I) = 2I$ geeft

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

Het sluitende inzicht: Cayley–Hamilton comprimeert heel de algebra $K[A]$ tot $\operatorname{Vect}(I, A, \dots, A^{n-1})$ — $\dim K[A] = \deg\mu_A \leq n$ , hoe groot de machten die u nodig heeft ook zijn.

Opmerking 3.23 (Veelvoorkomende valkuilen)

(i) Eigenwaarden tellen niet op: $\operatorname{Sp}(A + B)$ is niet $\operatorname{Sp}A + \operatorname{Sp}B$ , en een som van diagonaliseerbare matrices hoeft niet diagonaliseerbaar te zijn — $\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)$ is een som van twee diagonaliseerbare matrices (elk heeft verschillende eigenwaarden) en is niet diagonaliseerbaar; alleen commuterende families gedragen zich (Oefening 3.9). (ii) “ $\chi_u$ splitst” is een hypothese over het lichaam: een vlakrotatie heeft $\chi = X^2 - 2\cos\theta\,X + 1$ , gesplitst over $\C$ , niet over $\R$ — diagonaliseerbaar in $\mathcal{M}_2(\C)$ , niet trigonaliseerbaar in $\mathcal{M}_2(\R)$ . (iii) De ongelijkheid loopt meetkundig $\leq$ algebraïsch, nooit omgekeerd; alleen $\dim E_\lambda \geq 1$ testen bewijst niets over diagonaliseerbaarheid. (iv) $\mu_u$ is niet $\chi_u$ : gelijkheid geldt precies wanneer elke eigenwaarde een enkele blokketen heeft (bijv. begeleidende matrices, het weekendprobleem van dit hoofdstuk); $\chi$ gebruiken waar $\mu$ nodig is blaast elke machtsberekening op. (v) Dunfords $d$ en $\nu$ zijn veeltermen in $u$ — een ontbinding $u = d' + \nu'$ met de juiste eigenschappen maar $d'\nu' \neq \nu'd'$ is niet Dunford en is nooit uniek.

Opmerking 3.24 (Waar dit hoofdstuk wordt gebruikt)

Reductie is het werkpaard van de rest van het boek: machten en exponentialen van matrices drijven de lineaire differentiaalstelsels van Hoofdstuk 16; de spectraalstelling van Hoofdstuk 12 is diagonaliseren orthogonaal gemaakt; genererende functies (Hoofdstuk 23) herleiden de recurrentie-asymptotiek van het weekendprobleem van dit hoofdstuk analytisch. In het Bachelor jaar 3-volume loopt hetzelfde programma in oneindige dimensie: de spectraaltheorie van compacte zelfgeadjungeerde operatoren, waar eigenwaardenvolgordes eindige spectra vervangen, en de Perron–Frobenius-theorie van positieve matrices, die verklaart waarom dominante eigenwaarden van telproblemen positief en enkelvoudig zijn.

3.3 Nilpotenten en de Dunford-ontbinding

Propositie 3.25 (Nilpotente endomorfismen)

Voor $u$ met $\chi_u$ gesplitst zijn de volgende equivalent: $u^n = 0$ ; $u^k = 0$ voor zekere $k$ ; $\operatorname{Sp}(u) = \{0\}$ ; $\chi_u = X^n$ ; $u$ is trigonaliseerbaar met nulle diagonaal. Een nilpotent endomorfisme heeft $\mu_u = X^{\text{(nilpotentie-index)}}$ , en index $\leq n$ .

Bewijs. $u^k = 0$ maakt elke eigenwaarde een wortel van $X^k$ : spectrum $\{0\}$ (niet-leeg wanneer $\chi$ splitst — over $\C$ altijd). Dan $\chi_u = X^n$ (alle wortels nul) en Cayley–Hamilton geeft $u^n = 0$ ; trigonalisatie (Stelling 3.9) zet nullen op de diagonaal (de diagonaal draagt de eigenwaarden). Omgekeerd, zij $A$ strikt bovendriehoekig: $a_{ij} = 0$ voor $j \leq i$ . We tonen door inductie dat

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

d.w.z. elke macht duwt de nulle regio één diagonaal hoger. Voor $k = 1$ is dit de hypothese. Voor de stap,

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

en elke term verdwijnt: ofwel $\ell \leq i + k - 1$ (de eerste factor is $0$ door inductie) of $\ell \geq i + k$ , in welk geval $j \leq i + k \leq \ell$ de tweede factor doodt. Bij $k = n$ geldt de voorwaarde $j \leq i + n - 1$ voor alle $i, j \leq n$ : $A^n = 0$ . De minimale veelterm deelt $X^n$ en annihilatie definieert de index. ∎

Stelling 3.26 (Dunford-ontbinding)

Stel $\chi_u$ splitst over $K$ (automatisch voor $K = \C$ ). Dan bestaat er een uniek paar $(d, \nu)$ met

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

en bovendien zijn $d$ en $\nu$ veeltermen in $u$ .

Bewijs. Bestaan. Schrijf $\chi_u = \prod_{i=1}^{r} (X - \lambda_i)^{m_i}$ (verschillende $\lambda_i$ ) en stel $N_i = \ker(u - \lambda_i)^{m_i}$ , de karakteristieke deelruimten. Door Cayley–Hamilton en het kernlemma (Stelling 3.14),

E = N_1 \oplus \dots \oplus N_r ,

met projecties $\pi_i$ veelterm in $u$ ; elke $N_i$ is stabiel (veeltermen in $u$ commuten met $u$ ). Definieer $d = \sum_i \lambda_i \pi_i$ : een veelterm in $u$ , diagonaliseerbaar (ze werkt als $\lambda_i$ op $N_i$ , dus ontbindt $E$ in haar eigenruimten). Dan is $\nu = u - d$ een veelterm in $u$ (dus commuteert met $d$ ), en op elke $N_i$ werkt ze als $u - \lambda_i$ , met $(u - \lambda_i)^{m_i} = 0$ daar: $\nu^{\max m_i} = 0$ op elke sommand, dus is $\nu$ nilpotent.

Uniciteit. Zij $u = d' + \nu'$ een ander zulk paar. Omdat $d'$ en $\nu'$ met elkaar commuten, commuten ze met $u = d' + \nu'$ , dus met elke veelterm in $u$ — in het bijzonder met $d$ en $\nu$ . Dan is $d - d'$ diagonaliseerbaar (twee commuterende diagonaliseerbare afbeeldingen zijn gelijktijdig diagonaliseerbaar: Oefening 3.9) en gelijk aan $\nu' - \nu$ , die nilpotent is: als $\nu^k = 0$ en $\nu'^{k'} = 0$ , laat commutatie de binomiaalontwikkeling toe

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

waarin elke term sterft: ofwel $j \geq k'$ (eerste factor nul) of $k + k' - 1 - j \geq k$ (tweede factor nul), en één van de twee geldt altijd. Een diagonaliseerbare nilpotente is nul (haar spectrum is $\{0\}$ en ze is diagonaal in zekere basis): $d = d'$ , $\nu = \nu'$ . ∎

Voorbeeld 3.27 (Machten en exponentialen)

$A = \begin{pmatrix} 3 & 1\\ -1 & 1\end{pmatrix}$ : $\chi_A = X^2 - 4X + 4 = (X-2)^2$ , enkele eigenwaarde $2$ , eigenruimte van dimensie $1$ : niet diagonaliseerbaar. Dunford: $D = 2I$ , $N = A - 2I = \begin{pmatrix} 1 & 1\\ -1 & -1\end{pmatrix}$ , $N^2 = 0$ . Dan

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

door de commuterende binomiaalstelling, resp. de exponentiaalreeks (Hoofdstuk 16) gesplitst op commuterende sommanden. Reductie zet matrixdynamica om in scalaire dynamica.

Opmerking 3.28 (Perspectieven binnen dit volume)

Reductie is een knooppunt; hier zijn de vier spaken om te volgen. In Hoofdstuk 5 zetten aangepaste normen “alle eigenwaarden van modulus $< 1$ ” om in “zekere operatornorm $< 1$ ”, waardoor spectra convergentie van machten en reeksen regeren. In Hoofdstuk 16 wordt het recept van Voorbeeld 3.27 de algemene oplossing van $X' = AX$ : Dunford splijt $\eu^{tA}$ in veelterm-maal-exponentiaal-blokken, en stabiliteit leest de reële delen van eigenwaarden af. In Hoofdstuk 12 dwingt een scalair product wat loutere lineaire algebra niet kan: symmetrische matrices worden orthogonaal diagonaliseerbaar, zonder nilpotent deel. En in Hoofdstuk 23 keren de dominante-eigenwaarde-asymptotiek van het weekendprobleem van dit hoofdstuk analytisch terug, als de kleinste singulariteit van een genererende functie — twee talen voor één groeisnelheid.

3.4 Oefeningen

Oefening 3.1 ★

Diagonaliseer (eigenwaarden, bases van eigenruimten, inverteerbare $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}.

Oplossing

Oplossing van Oefening 3.1.

$A$ : $\chi_A = X^2 - 2X - 3 = (X - 3)(X + 1)$ . Eigenvectoren: voor $3$ : $(1,1)$ ; voor $-1$ : $(1,-1)$ . Dus $P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ geeft $P^{-1}AP = \operatorname{diag}(3, -1)$ .

$B = J - I$ waarbij $J$ de all-eens-matrix is. $J$ heeft rang $1$ met $Jv = 3v$ voor $v = (1,1,1)$ en $Jw = 0$ op het vlak $x + y + z = 0$ : spectrum van $B$ is $\{2, -1\}$ met eigenruimten $\operatorname{Vect}(1,1,1)$ (dimensie $1$ ) en $\{x + y + z = 0\}$ (dimensie $2$ , basis $(1,-1,0), (1,0,-1)$ ). $P$ met deze drie kolommen geeft $P^{-1}BP = \operatorname{diag}(2, -1, -1)$ .

Oefening 3.2 ★

Toon dat $C = \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}$ niet diagonaliseerbaar is, tweemaal: via eigenruimten, en via de minimale veelterm.

Oplossing

Oplossing van Oefening 3.2.

Eigenruimten: $\chi_C = (X-1)^2$ , enkele eigenwaarde $1$ ; $\ker(C - I) = \ker\begin{pmatrix} 0&1\\ 0&0\end{pmatrix}$ is de lijn $\operatorname{Vect}(e_1)$ : dimensie $1 < 2 = m_1$ , dus niet diagonaliseerbaar (Stelling 3.6).

Minimale veelterm: $\mu_C$ deelt $(X-1)^2$ en $C \neq I$ , dus $\mu_C = (X-1)^2$ : een dubbele wortel, dus niet diagonaliseerbaar (Gevolg 3.17).

Oefening 3.3 ★

Zij $u$ voldoen aan $u^2 - 5u + 6\,\mathrm{id} = 0$ . Bewijs dat $u$ diagonaliseerbaar is, bepaal de mogelijke spectra, en bereken $u^k$ als combinatie van $\mathrm{id}$ en $u$ .

Oplossing

Oplossing van Oefening 3.3.

$X^2 - 5X + 6 = (X-2)(X-3)$ : gesplitst met enkelvoudige wortels, dus is $u$ diagonaliseerbaar (Gevolg 3.17), met $\operatorname{Sp}(u) \subseteq \{2, 3\}$ . Mogelijke spectra: $\{2\}$ ( $u = 2\,\mathrm{id}$ ), $\{3\}$ ( $u = 3\,\mathrm{id}$ ), of $\{2, 3\}$ .

Machten: zoek $u^k = a_k\,\mathrm{id} + b_k\,u$ . Op de eigenruimten luidt dit $2^k = a_k + 2b_k$ en $3^k = a_k + 3b_k$ : oplossend, $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 .

(Geldig voor alle drie de spectra: de identiteiten gelden eigenwaarde-gewijs.)

Oefening 3.4 ★★

Zij $u$ diagonaliseerbaar en $F$ een stabiele deelruimte. Bewijs dat $u|_F$ diagonaliseerbaar is (beperk een annulerende veelterm met enkelvoudige gesplitste wortels).

Oplossing

Oplossing van Oefening 3.4.

$u$ diagonaliseerbaar: $P = \prod_{\lambda}(X - \lambda)$ over het spectrum annuleert $u$ , splitst, enkelvoudige wortels. Dan $P(u|_F) = P(u)|_F = 0$ : de restrictie wordt geannuleerd door een gesplitste veelterm met enkelvoudige wortels, dus diagonaliseerbaar (Gevolg 3.17).

Oefening 3.5 ★★

(Fibonacci) Zij $A = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ . Diagonaliseer $A$ over $\R$ , en leid de formule van Binet af voor de Fibonacci-rij ( $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}.

Oplossing

Oplossing van Oefening 3.5.

$\chi_A = X^2 - X - 1$ , wortels $\varphi$ en $\psi$ (verschillend): diagonaliseerbaar, met eigenvectoren $(\varphi, 1)$ en $(\psi, 1)$ . De recurrentie geeft $\begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = A^n \begin{pmatrix}1\\ 0\end{pmatrix}$ . Ontbind $(1, 0)$ op de eigenvectoren: $(1,0) = \frac{1}{\varphi - \psi}\bigl((\varphi, 1) - (\psi, 1)\bigr)$ met $\varphi - \psi = \sqrt5$ . $A^n$ toepassen vermenigvuldigt elke eigencomponent met de $n$ -de macht van haar eigenwaarde; de tweede coördinaat lezend:

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

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

Oefening 3.6 ★★

Zij $u \in \mathcal{L}(E)$ met $u^2$ diagonaliseerbaar en $u$ inverteerbaar ( $K = \C$ ). Bewijs dat $u$ diagonaliseerbaar is. Geef een tegenvoorbeeld wanneer $u$ niet inverteerbaar is.

Oplossing

Oplossing van Oefening 3.6.

Zij $P = \prod_i (X - \mu_i)$ $u^2$ annuleert, gesplitst met enkelvoudige wortels $\mu_i$ (het spectrum van $u^2$ ). Omdat $u$ inverteerbaar is, is $0$ geen eigenwaarde van $u^2$ ( $\det u^2 = (\det u)^2 \neq 0$ ), dus alle $\mu_i \neq 0$ . Dan

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

annuleert $u$ : $\;Q(u) = \prod_i (u^2 - \mu_i\,\mathrm{id}) = P(u^2) = 0$ . Haar wortels $\pm \sqrt{\mu_i}$ (complexe vierkantswortels) zijn paarsgewijs verschillend omdat de $\mu_i$ verschillend en niet-nul zijn ( $\sqrt{\mu_i} = -\sqrt{\mu_j}$ zou $\mu_i = \mu_j$ geven). Gesplitst + enkelvoudige wortels: $u$ is diagonaliseerbaar.

Tegenvoorbeeld zonder inverteerbaarheid: $u = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : $u^2 = 0$ is diagonaliseerbaar, $u$ is het niet.

Oefening 3.7 ★★

Bereken de Dunford-ontbinding, $A^k$ , en $\eu^{tA}$ voor

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

Oplossing

Oplossing van Oefening 3.7.

$A = 2I + N$ met $N$ de shift ( $N e_2 = e_1$ , $Ne_3 = e_2$ ), $N^3 = 0$ , $N^2 = E_{13}$ : dit is de Dunford-ontbinding ( $2I$ diagonaal, $N$ nilpotent, ze commuten; uniciteit maakt haar de unieke). Binomiaal met commuterende termen:

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

Oefening 3.8 ★★

Zij $A \in \mathcal{M}_n(\C)$ met $A^k = I$ voor zekere $k \geq 1$ . Bewijs dat $A$ diagonaliseerbaar is en haar eigenwaarden $k$ -de eenheidswortels zijn. Leid af dat een eindige-orde inverteerbare complexe matrix gelijkvormig met een driehoekige matrix met eenheidsdiagonaal de identiteit is.

Oplossing

Oplossing van Oefening 3.8.

$X^k - 1$ annuleert $A$ en splitst over $\C$ met de $k$ verschillende wortels $\eu^{2\iu\pi j/k}$ : $A$ is diagonaliseerbaar (Gevolg 3.17) en haar eigenwaarden, wortels van $X^k - 1$ , zijn $k$ -de eenheidswortels.

Als bovendien $A$ gelijkvormig is met een driehoekige matrix met eenheidsdiagonaal: alle eigenwaarden gelijk $1$ , en $A$ , diagonaliseerbaar met enige eigenwaarde $1$ , is $P\,I\,P^{-1} = I$ .

Oefening 3.9 ★★★

(Gelijktijdige diagonaliseerbaarheid) Zij $u, v$ diagonaliseerbaar en commuterend. Bewijs dat ze gelijktijdig diagonaliseerbaar zijn: zekere basis diagonaliseert beide. (Elke eigenruimte van $u$ is $v$ -stabiel; diagonaliseer de restricties van $v$ daar, met Oefening 3.4.)

Oplossing

Oplossing van Oefening 3.9.

Schrijf $E = \bigoplus_\lambda E_\lambda(u)$ (Stelling 3.6). Elke $E_\lambda(u)$ is $v$ -stabiel: voor $x \in E_\lambda$ , $u(v(x)) = v(u(x)) = \lambda v(x)$ . De restrictie van $v$ tot $E_\lambda(u)$ is diagonaliseerbaar (Oefening 3.4): kies een basis van $E_\lambda(u)$ bestaande uit $v$ -eigenvectoren. Concatenatie van deze bases over alle $\lambda$ geeft een basis van $E$ waarvan de vectoren eigenvectoren zijn van beide $u$ (door lidmaatschap van $E_\lambda(u)$ ) en $v$ (per constructie).

Oefening 3.10 ★★★

Zij $u \in \mathcal{L}(\C^n)$ . Bewijs dat $u$ diagonaliseerbaar is desda elke $u$ -stabiele deelruimte een $u$ -stabiele complementaire deelruimte heeft. (Voor $\Leftarrow$ : pas de eigenschap toe op $F = \sum_\lambda E_\lambda(u)$ , de som van alle eigenruimten; als een stabiel complement $G$ niet-nul was, zou trigonaliseren van $u|_G$ een eigenvector van $u$ in $G$ produceren — in strijd met $G \cap F = \{0\}$ .)

Oplossing

Oplossing van Oefening 3.10.

( $\Rightarrow$ ) Zij $u$ diagonaliseerbaar en $F$ stabiel. Dan is $u|_F$ diagonaliseerbaar (Oefening 3.4): $F$ heeft een basis van eigenvectoren, die zich, binnen elke globale eigenruimte $E_\lambda$ , uitbreidt tot een basis van $E_\lambda$ (onvolledige-basisstelling binnen $E_\lambda$ , startend vanuit het deel van de basis van $F$ dat daar ligt — merk op $F = \bigoplus_\lambda (F \cap E_\lambda)$ omdat $u|_F$ diagonaliseerbaar is). De toegevoegde vectoren spannen een stabiel complement op (elk ligt in zekere $E_\lambda$ , dus is hun opspansel $u$ -stabiel).

( $\Leftarrow$ ) Zij $F = \sum_\lambda E_\lambda(u)$ (een stabiele deelruimte) en $G$ een stabiel complement. Als $G \neq \{0\}$ : $\chi_{u|_G}$ splitst over $\C$ , dus heeft $u|_G$ een eigenvector $x \in G$ (Stelling 3.9 of direct bestaan van een wortel); maar elke eigenvector van $u$ ligt in $F$ , dus $x \in F \cap G = \{0\}$ : contradictie. Dus $G = \{0\}$ en $E = F$ : de eigenruimten vullen $E$ , d.w.z. $u$ is diagonaliseerbaar.

Oefening 3.11 ★★★

(Spectrale straal à la Gelfand-lite, $2\times2$ -smaak van de analyse die komt) Zij $A \in \mathcal{M}_2(\C)$ met beide eigenwaarden van modulus $< 1$ . Bewijs dat $A^k \to 0$ entrygewijs als $k \to \infty$ . (Trigonaliseer: $A = P(T)P^{-1}$ met $T$ bovendriehoekig; bereken $T^k$ expliciet — onderscheid gelijke en verschillende eigenwaarden — en begrens.)

Oplossing

Oplossing van Oefening 3.11.

Trigonaliseer: $A = PTP^{-1}$ , $T = \begin{pmatrix} \lambda & c\\ 0 & \mu\end{pmatrix}$ , $\abs\lambda, \abs\mu < 1$ . Dan $A^k = PT^kP^{-1}$ , en het volstaat dat $T^k \to 0$ .

Verschillende eigenwaarden: inductie geeft

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

en elke entry neigt naar $0$ ( $\abs{\lambda}^k, \abs\mu^k \to 0$ ).

Gelijke eigenwaarden ( $\mu = \lambda$ ): $T = \lambda I + cE_{12}$ en $T^k = \lambda^k I + k\lambda^{k-1}cE_{12}$ ; de entry $k\lambda^{k-1} \to 0$ omdat $\abs\lambda < 1$ (geometrisch verslaat polynomiaal). In beide gevallen $T^k \to 0$ entrygewijs, dus $A^k = PT^kP^{-1} \to 0$ (matrixvermenigvuldiging met vaste $P, P^{-1}$ is continu in de entries — elke entry van het product is een vaste lineaire combinatie).

Oefening 3.12 ★★

Zij $u \in \mathcal{L}(\C^n)$ met $\operatorname{rk} u = 1$ ( $n \geq 2$ ). Toon dat $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ , en dat $u$ diagonaliseerbaar is desda $\operatorname{tr} u \neq 0$ . (Herinner uit Oefening 2.5 dat $u^2 = (\operatorname{tr} u)\,u$ .)

Oplossing

Oplossing van Oefening 3.12.

$\ker u$ heeft dimensie $n - 1$ (rang–nulheid), dus is $0$ een eigenwaarde van meetkundige multipliciteit $n - 1$ , en is $\chi_u$ deelbaar door $X^{n-1}$ (Definitie 3.3: meetkundig $\leq$ algebraïsch). Schrijf $\chi_u = X^{n-1}(X - \alpha)$ ; de coëfficiënt van $X^{n-1}$ is $-\operatorname{tr} u$ , dus $\alpha = \operatorname{tr} u$ : $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ .

Als $\operatorname{tr} u \neq 0$ : de eigenwaarde $\operatorname{tr} u$ is een wortel van $\chi_u$ , dus draagt ze een eigenvector; de eigenruimten voor $0$ en $\operatorname{tr} u$ hebben dimensies $n - 1$ en $\geq 1$ , sommerend tot $\geq n$ : ze vullen $E$ , en $u$ is diagonaliseerbaar (Stelling 3.6). Als $\operatorname{tr} u = 0$ : door Oefening 2.5, $u^2 = (\operatorname{tr} u)u = 0$ met $u \neq 0$ : $u$ is een niet-nulle nilpotente, en een diagonaliseerbare nilpotente is nul (Propositie 3.25): niet diagonaliseerbaar.

3.5 Probleem: Lineaire recurrenties en begeleidende matrices

Een lineaire recurrentie $u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_0 u_n$ is een matrixmacht in vermomming, en reductie zet ze om in gesloten formules, groeisnelheden, en foutschattingen. Dit weekendprobleem ontwikkelt het woordenboek — begeleidende matrices aan de ene kant, de shiftoperator op de rijruimte aan de andere — bewijst de fundamentele stelling van lineaire recurrenties (de algemene oplossing is $\sum_i Q_i(n)\lambda_i^n$ over de wortels van de karakteristieke veelterm), en besteedt de dividenden aan Diophantische benadering van $\sqrt2$ , aan het tellen van wandelingen en woorden, en aan een ring van gekoppelde rijen die alleen gelijktijdige diagonaliseerbaarheid kan ontwarren.

Probleem 3.1

Weekendprobleem — de fundamentele stelling van lineaire recurrenties

Fixeer $k \geq 1$ , scalaren $a_0, \dots, a_{k-1} \in \C$ met $a_0 \neq 0$ , de monische veelterm $P = X^k - a_{k-1}X^{k-1} - \dots - a_1 X - a_0$ , en de recurrentie

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

De begeleidende matrix van $P$ is

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

Deel I — Het begeleidende woordenboek.

Toon dat een rij $(u_n)$ aan $(\mathcal R)$ voldoet desda de vectoren $v_n = (u_n, u_{n+1}, \dots, u_{n+k-1})^{\mathsf T}$ voldoen aan $v_{n+1} = Cv_n$ , dus $v_n = C^n v_0$ .
Bewijs dat $\chi_C = P$ (ontwikkel $\det(XI - C)$ langs de eerste kolom en induceer op $k$ ), dan dat $\mu_C = P$ eveneens (ga over op $C^{\mathsf T}$ , waarvoor $e_1$ cyclisch is, en merk op dat een matrix en haar getransponeerde dezelfde minimale veelterm hebben).
Toon dat voor elke wortel $\lambda$ van $P$ de vector $(1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ de eigenruimte van $C$ voor $\lambda$ opspant; leid af dat elke eigenruimte van $C$ dimensie $1$ heeft, en dat $C$ diagonaliseerbaar is desda $P$ $k$ verschillende wortels heeft.
Stel $P$ heeft verschillende wortels $\lambda_1, \dots, \lambda_k$ . Toon dat de meetkundige rijen $(\lambda_i^n)_n$ een basis vormen van de oplossingsruimte van $(\mathcal R)$ , dus is elke oplossing $u_n = \sum_i c_i\lambda_i^n$ voor unieke constanten $c_i$ .
Los volledig op: $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ .

Deel II — De shiftoperator en de fundamentele stelling. Zij $\mathcal{S}$ de $\C$ -vectorruimte van alle complexe rijen en $S \in \mathcal{L}(\mathcal{S})$ de shift, $S\bigl((u_n)_n\bigr) = (u_{n+1})_n$ .

Toon dat de oplossingsverzameling van $(\mathcal R)$ $\ker P(S)$ is, en dat ze precies dimensie $k$ heeft (beeld een oplossing af op haar beginwaarden).
Leg uit waarom het kernontbindingslemma (Stelling 3.14) van toepassing is op $S$ op de oneindigdimensionale $\mathcal{S}$ zonder enige verandering, en schrijf de resulterende ontbinding van $\ker P(S)$ voor $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ (verschillende $\lambda_i$ , alle niet-nul omdat $a_0 \neq 0$ ).
Voor $\lambda \neq 0$ en $m \geq 1$ , toon

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

van dimensie $m$ . (Bereken $(S - \lambda)\bigl(Q(n)\lambda^n\bigr) = \lambda^{n+1}(\Delta Q)(n)$ met $\Delta Q = Q(X + 1) - Q(X)$ , en gebruik dat $\Delta$ de graad verlaagt; voor de dimensie, begrens ze met $m$ via beginwaarden.)
(De fundamentele stelling van lineaire recurrenties) Concludeer: als $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ met de $\lambda_i$ verschillend en niet-nul, zijn de oplossingen van $(\mathcal R)$ precies de rijen

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

met uniek bepaalde veeltermen $Q_i$ .
Los volledig op: $u_{n+2} = 4u_{n+1} - 4u_n$ , $u_0 = 1$ , $u_1 = 0$ , en controleer het antwoord op $u_2$ .

Deel III — Dominante wortels en Diophantische dividenden.

Stel de wortels zijn enkelvoudig met $\abs{\lambda_1} > \abs{\lambda_i}$ voor $i \geq 2$ , en $u_n = \sum_i c_i \lambda_i^n$ met $c_1 \neq 0$ . Toon $u_n \sim c_1\lambda_1^n$ en $u_{n+1}/u_n \to \lambda_1$ .
(Pell) Definieer $a_{n+1} = a_n + 2b_n$ , $b_{n+1} = a_n + b_n$ , $a_0 = b_0 = 1$ . Toon dat $q(a, b) = a^2 - 2b^2$ voldoet aan $q(a_{n+1}, b_{n+1}) = -q(a_n, b_n)$ , dus $a_n^2 - 2b_n^2 = (-1)^{n+1}$ ; relateer dit aan de determinant van $M = \left(\begin{smallmatrix}1 & 2\\ 1 & 1\end{smallmatrix}\right)$ .
Leid de foutschatting af

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

en toon dat ze geometrisch vervalt met ratio $3 - 2\sqrt2$ (vind de eigenwaarden van $M$ en de groei van $b_n$ ).
(Algemene groei) Uit vraag 9, bewijs: (a) als elke wortel $\abs{\lambda_i} \leq \rho$ voldoet, dan $\abs{u_n} \leq C\,n^{m-1}\rho^n$ met $m = \max_i m_i$ ; (b) als er een unieke wortel $\lambda_1$ van maximale modulus is en $Q_1 \neq 0$ , dan $u_{n+1}/u_n \to \lambda_1$ — controleer op de oplossing van vraag 10.

Deel IV — Wandelen en woorden tellen. Voor een eindige graaf met knopenverzameling $\{1, \dots, N\}$ heeft de adjacentiematrix $A$ $A_{ij} = 1$ als $ij$ een rand is, anders $0$ .

Bewijs dat $(A^n)_{ij}$ het aantal wandelingen van lengte $n$ van $i$ naar $j$ is (rijen van $n$ randen, elke stap langs een rand).
(De driehoek) Voor de complete graaf op $3$ knopen, $A = J - I$ : met het spectrum van $J$ (Voorbeeld 2.19), toon

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

en controleer beide bij $n = 2$ door wandelingen op te sommen.
(Woorden zonder $11$ ) Zij $w_n$ het aantal binaire woorden van lengte $n$ zonder twee opeenvolgende $1$ ’en. Codeer woorden door hun laatste letter om een transfermatrix te krijgen, toon $w_{n+2} = w_{n+1} + w_n$ , leid af $w_n = F_{n+2}$ (Fibonacci, Oefening 3.5), en geef de groeisnelheid $\lim w_{n+1}/w_n$ .
(Het pad) Voor de padgraaf $1 - 2 - 3$ , toon dat de eigenwaarden van $A$ $\sqrt2, 0, -\sqrt2$ zijn met eigenvectoren $(1, \pm\sqrt2, 1)$ en $(1, 0, -1)$ , en leid af dat het aantal wandelingen van lengte $n$ van eind tot eind $\bigl((\sqrt2)^n + (-\sqrt2)^n\bigr)/4$ is: nul voor oneven $n$ , en $2^{\,n/2 - 1}$ voor even $n$ . Controleer bij $n = 4$ .
(Spoorformule) Toon dat het totale aantal gesloten wandelingen van lengte $n$ (alle startpunten) $\operatorname{tr}(A^n) = \sum_i \lambda_i^n$ is, en verifieer op de driehoek.

Deel V — Een ring van rijen: gelijktijdige diagonaliseerbaarheid. Fixeer $k \geq 3$ , zij $\omega = \eu^{2\iu\pi/k}$ , en zij $W \in \mathcal{M}_k(\C)$ de cyclische shift: $W e_i = e_{i+1}$ (indices mod $k$ , kolommen geïndexeerd $0, \dots, k-1$ ).

Toon dat $W^{\mathsf T}$ de begeleidende matrix van $X^k - 1$ is, leid af $\chi_W = \mu_W = X^k - 1$ , en dat $W$ diagonaliseerbaar is met de $k$ enkelvoudige eigenwaarden $\omega^j$ en eigenvectoren $f_j = (1, \omega^{-j}, \omega^{-2j}, \dots, \omega^{-(k-1)j})^{\mathsf T}$ .
Een circulante matrix is $C = c_0 I + c_1 W + \dots + c_{k-1}W^{k-1}$ . Toon dat alle circulanten commuten, dat de basis $(f_0, \dots, f_{k-1})$ alle ervan gelijktijdig diagonaliseert, en dat de eigenwaarden van $C$ $\widehat c(\omega^j) = \sum_m c_m \omega^{jm}$ zijn, $j = 0, \dots, k-1$ .
Leid af $\det C = \prod_{j=0}^{k-1} \widehat c(\omega^j)$ , en controleer dat $k = 3$ de factorisatie van Oefening 2.8 herwint.
(Het kettinggemiddelde) Zij $x^{(n+1)} = Mx^{(n)}$ met $M = \frac12(W + W^{-1})$ : elk van $k$ getallen in een ring gerangschikt wordt vervangen door het gemiddelde van zijn twee buren. Toon dat de eigenwaarden van $M$ $\cos(2\pi j/k)$ zijn, en dat de coëfficiënt van $x^{(0)}$ op $f_0$ het gemiddelde $\frac1k\sum_m x^{(0)}_m$ is (sommeer de coördinaten van de $f_j$ ).
Concludeer: voor oneven $k$ convergeert $x^{(n)}$ naar de constante vector waarvan de waarde het gemiddelde van de beginwaarden is; voor $k = 4$ , vertoon de eigenwaarde verantwoordelijk voor niet-convergentie en de exacte obstructie (een alternerend-gemiddelde- coëfficiënt die moet verdwijnen).
(Synthese) In één zin elk: hoe de begeleidende matrix analyse van $(\mathcal R)$ omzet in reductie; waar het kernontbindingslemma geen eindige dimensie nodig had; waarom dominante eigenwaarden groeisnelheden en Diophantische fout regeren; waarom machten van de adjacentiematrix wandelingen tellen; en wat commuterende matrices kopen. Noem de twee toppen: de fundamentele stelling van lineaire recurrenties, en — voor de positieve matrices van Deel IV, in het Bachelor jaar 3-volume — de stelling van Perron–Frobenius.

Oplossing

Oplossing van Probleem 3.1.

1. De eerste $k - 1$ coördinaten van $Cv_n$ zijn $u_{n+1}, \dots, u_{n+k-1}$ (de superdiagonaalverschuivingen), en de laatste is $a_0 u_n + \dots + a_{k-1}u_{n+k-1}$ . Dus $v_{n+1} = Cv_n$ geldt voor alle $n$ desda de laatste coördinaten voor alle $n$ matchen, d.w.z. desda $(\mathcal R)$ geldt. Itererend, $v_n = C^nv_0$ .

2. Ontwikkel $D_k(X) = \det(XI_k - C)$ langs de eerste kolom: de twee niet-nulle entries zijn $X$ (positie $(1,1)$ ) en $-a_0$ (positie $(k,1)$ ). De eerste minor is $D_{k-1}$ -vormig voor de coëfficiënten $a_1, \dots, a_{k-1}$ ; de tweede minor is bovendriehoekig met diagonaal $-1$ : determinant $(-1)^{k-1}$ , met teken $(-1)^{k+1}$ van de positie. Inductie op $k$ (basis $k = 1$ : $X - a_0$ ) geeft

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

Voor $\mu_C$ : omdat $Q(C^{\mathsf T}) = Q(C)^{\mathsf T}$ voor elke veelterm, hebben $C$ en $C^{\mathsf T}$ dezelfde annihilatoren, dus dezelfde minimale veelterm. Voor $C^{\mathsf T}$ : de kolommen lezen $C^{\mathsf T}e_1 = e_2$ , …, $C^{\mathsf T}e_{k-1} = e_k$ , dus is $(e_1, C^{\mathsf T}e_1, \dots, (C^{\mathsf T})^{k-1}e_1)$ de canonieke basis: vrij. Een veelterm $Q \neq 0$ van graad $< k$ heeft dan $Q(C^{\mathsf T})e_1 \neq 0$ (ze is een niet-triviale combinatie van basisvectoren): $\deg\mu \geq k$ . Omdat $\mu \mid \chi = P$ met $\deg P = k$ : $\mu_C = P$ .

3. Voor $v = (1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ : rijen $1$ tot $k-1$ van $Cv$ geven $\lambda, \lambda^2, \dots, \lambda^{k-1}$ , d.w.z. $\lambda$ maal de eerste $k - 1$ entries van $v$ ; de laatste rij geeft $\sum_m a_m\lambda^m = \lambda^k - P(\lambda) = \lambda^k = \lambda\cdot\lambda^{k-1}$ . Dus $Cv = \lambda v$ . Omgekeerd luiden de vergelijkingen $(Cx)_i = \lambda x_i$ voor $i < k$ $x_{i+1} = \lambda x_i$ : elke eigenvector is proportioneel met $v$ — elke eigenruimte heeft precies dimensie $1$ . Diagonaliseerbaar desda de eigenruimtedimensies tot $k$ sommeren (Stelling 3.6) desda er $k$ verschillende eigenwaarden zijn desda $P$ $k$ verschillende wortels heeft (de eigenwaarden zijn de wortels van $\chi_C = P$ ).

4. Elke $(\lambda_i^n)_n$ lost $(\mathcal R)$ op: $\lambda_i^{n+k} = \lambda_i^n\,\lambda_i^k = \lambda_i^n\sum_m a_m\lambda_i^m$ . Vrijheid: een verdwijnende combinatie $\sum_i c_i\lambda_i^n = 0$ voor $n = 0, \dots, k-1$ is een Vandermondestelsel (Oefening 2.11) in de $c_i$ : alle $c_i = 0$ . De oplossingsruimte heeft dimensie $k$ (vraag 6, waarvan het bewijs elementair en onafhankelijk is): $k$ vrije oplossingen vormen een basis, en coördinaten zijn uniek.

5. $P = X^2 - X - 6 = (X - 3)(X + 2)$ : algemene oplossing $u_n = A\,3^n + B(-2)^n$ . Beginvoorwaarden: $A + B = 1$ , $3A - 2B = 8$ : $A = 2$ , $B = -1$ :

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

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

6. $P(S)\bigl((u_n)\bigr)$ is de rij $n \mapsto u_{n+k} - a_{k-1}u_{n+k-1} - \dots - a_0u_n$ : ze verdwijnt desda $(\mathcal R)$ geldt, dus is de oplossingsverzameling $\ker P(S)$ , een deelruimte. De afbeelding $\ker P(S) \to \C^k$ , $u \mapsto (u_0, \dots, u_{k-1})$ , is lineair, injectief (de recurrentie bepaalt $u_{k}, u_{k+1}, \dots$ uit de eerste $k$ waarden, door inductie) en surjectief (definieer $u_n$ recursief uit willekeurige beginwaarden): dimensie $k$ .

7. Het bewijs van Stelling 3.14 gebruikt alleen: de Bézout-identiteit in $\C[X]$ , en het feit dat veeltermen in een vast endomorfisme commuten. Geen van beide noemt de dimensie van de omgevingsruimte: het lemma geldt letterlijk voor $S \in \mathcal{L}(\mathcal{S})$ . Dus

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

8. Voor $Q \in \C[X]$ : $(S - \lambda)\bigl(Q(n)\lambda^n\bigr)_n$ heeft $n$ -de term $Q(n{+}1)\lambda^{n+1} - \lambda Q(n)\lambda^n = \lambda^{n+1}(\Delta Q)(n)$ , met $\Delta Q = Q(X{+}1) - Q(X)$ van graad $\deg Q - 1$ (de leidende termen cancelleren). Itererend, $(S - \lambda)^m\bigl(Q(n)\lambda^n\bigr) = \bigl(\lambda^{n+m}(\Delta^m Q)(n)\bigr)_n$ , en $\Delta^m Q = 0$ wanneer $\deg Q \leq m - 1$ : de rechterverzameling is bevat in de kern. Ze is een deelruimte van dimensie $m$ : de rijen $(n^j\lambda^n)_n$ , $0 \leq j < m$ , zijn vrij, omdat $\sum_j c_j n^j\lambda^n = 0$ voor alle $n$ (delen door $\lambda^n \neq 0$ ) de veelterm $\sum_j c_jX^j$ dwingt te verdwijnen in elke $n \in \N$ , dus nul te zijn. Omgekeerd $\dim\ker(S - \lambda)^m \leq m$ : ontwikkelend $(S - \lambda)^m = \sum_j \binom mj(-\lambda)^{m-j}S^j$ , is de vergelijking $(S - \lambda)^m u = 0$ een lineaire recurrentie van orde $m$ (leidende coëfficiënt $1$ ), dus is $u$ bepaald door $u_0, \dots, u_{m-1}$ zoals in vraag 6. Dimensiegelijkheid besluit.

9. Combineer vragen 7 en 8: elke oplossing ontbindt uniek als som van elementen van de $\ker(S - \lambda_i)^{m_i}$ , d.w.z. $u_n = \sum_i Q_i(n)\lambda_i^n$ met $\deg Q_i \leq m_i - 1$ ; de $Q_i$ zijn uniek omdat de ontbinding direct is en, binnen elke sommand, de coëfficiënten van $Q_i$ coördinaten zijn in de basis $(n^j\lambda_i^n)_j$ (vraag 8). Saniteitscontrole op dimensies: $\sum_i m_i = k$ .

10. $P = X^2 - 4X + 4 = (X - 2)^2$ : oplossingen $(a + bn)2^n$ . Beginwaarden: $a = 1$ , $2(a + b) = 0$ , dus $b = -1$ :

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

Controle: $u_2 = 4u_1 - 4u_0 = -4$ , en $(1 - 2)\cdot4 = -4$ .

11. Schrijf $u_n = \lambda_1^n\bigl(c_1 + \sum_{i\geq2} c_i(\lambda_i/\lambda_1)^n\bigr)$ ; elke ratio heeft modulus $< 1$ , dus neigt de haak naar $c_1 \neq 0$ : $u_n \sim c_1\lambda_1^n$ . In het bijzonder $u_n \neq 0$ voor grote $n$ , en

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

12. Bereken:

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

Met $q(a_0, b_0) = 1 - 2 = -1$ : $a_n^2 - 2b_n^2 = (-1)^{n+1}$ . Structureel: $q(a, b) = (a - \sqrt2\,b)(a + \sqrt2\,b)$ en de lineaire afbeelding $M$ vermenigvuldigt de factor $a + \sqrt2 b$ met $1 + \sqrt2$ en de factor $a - \sqrt2 b$ met $1 - \sqrt2$ (bereken: $a_{n+1} + \sqrt2 b_{n+1} = (1 + \sqrt2)(a_n + \sqrt2 b_n)$ ); het product wordt vermenigvuldigd met $(1 + \sqrt2)(1 - \sqrt2) = -1 = \det M$ bij elke stap.

13. Omdat $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},

gebruikend $a_n \geq b_n \geq 1$ (inductie: beide stijgen) dus $a_n + \sqrt2 b_n \geq (1 + \sqrt2)b_n \geq 2b_n$ . Eigenwaarden van $M$ : $\chi_M = X^2 - 2X - 1$ , wortels $1 \pm \sqrt2$ ; omdat $(a_0, b_0)$ een niet-nulle component op de dominante eigenvector heeft (alle entries positief), $b_n \sim c(1 + \sqrt2)^n$ met $c > 0$ (vraag 11). Dus is de fout $\asymp (1 + \sqrt2)^{-2n} = (3 + 2\sqrt2)^{-n}$ : geometrisch verval met ratio $1/(3 + 2\sqrt2) = 3 - 2\sqrt2 \approx 0.172$ .

14. (a) Uit vraag 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$ , en elke $\abs{Q_i(n)} \leq C_i n^{m_i - 1} \leq C_i n^{m-1}$ voor $n \geq 1$ : sommeer de constanten. (b) Zij $\rho' = \max_{i \geq 2}\abs{\lambda_i} < \abs{\lambda_1}$ en $d = \deg Q_1$ , leidende coëfficiënt $c \neq 0$ . Dan $u_n = Q_1(n)\lambda_1^n + R_n$ met $\abs{R_n} \leq Cn^{m-1}\rho'^n$ , en

\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

(geometrisch verslaat polynomiaal). Dus

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

Controle op vraag 10: voor $u_n = (1-n)2^n$ is de ratio

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

15. Inductie op $n$ . Voor $n = 1$ telt $A_{ij}$ wandelingen van lengte $1$ . Stap: een wandeling van lengte $n + 1$ van $i$ naar $j$ is een wandeling van lengte $n$ van $i$ naar zekere knoop $\ell$ gevolgd door een rand $\ell j$ :

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

16. $J = 3\Pi$ waarbij $\Pi = J/3$ de projectie is op $\operatorname{Vect}(1,1,1)$ langs het vlak $x + y + z = 0$ ( $\Pi^2 = \Pi$ omdat $J^2 = 3J$ ). Dan $A = J - I = 2\Pi - (I - \Pi)$ , en omdat $\Pi$ en $I - \Pi$ complementaire projecties zijn,

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

wat de twee weergegeven formules geeft. Bij $n = 2$ : diagonaal $(4 + 2)/3 = 2$ (wandelingen $i \to \ell \to i$ voor de twee buren $\ell$ ); buitendiagonaal $(4 - 1)/3 = 1$ (de enkele wandeling $i \to \ell \to j$ door de derde knoop).

17. Zij $w_n^{(0)}, w_n^{(1)}$ toegelaten woorden van lengte $n$ eindigend op $0$ , resp. $1$ tellen. Een letter toevoegen: een $0$ mag op alles volgen, een $1$ alleen op een $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}.

Sommerend, $w_{n+2} = w_{n+1} + w_n$ (of: conditioneer op de eerste letter). Met $w_1 = 2$ , $w_2 = 3$ : $w_n = F_{n+2}$ door inductie ( $F_3 = 2$ , $F_4 = 3$ , zelfde recurrentie). Groei: de wortels van $X^2 - X - 1$ zijn $\varphi > \abs\psi$ (Oefening 3.5), en de $\varphi$ -component is niet-nul (de $w_n$ zijn positief en $\psi^n \to 0$ ), dus geeft vraag 11 $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)$ . Controle:

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 :

eigenwaarden $\sqrt2, -\sqrt2, 0$ ( $= 2\cos\frac\pi4, 2\cos\frac{3\pi}4, 2\cos\frac\pi2$ ). Ontbind $e_1$ op de eigenbasis en lees de derde coördinaat, of gebruik symmetrie: met $v_\pm = (1, \pm\sqrt2, 1)$ , $v_0 = (1, 0, -1)$ , controleert men $e_1 = \frac14 v_+ + \frac14 v_- + \frac12 v_0$ , dus voor $n \geq 1$

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

nul voor oneven $n$ (bipartiete graaf: einden liggen op even afstand), en $2\cdot 2^{n/2}/4 = 2^{n/2 - 1}$ voor even $n$ . Bij $n = 4$ : $2^{1} = 2$ , matchend de twee wandelingen $1\,2\,1\,2\,3$ en $1\,2\,3\,2\,3$ .

19. Gesloten wandelingen van lengte $n$ vanuit $i$ zijn $(A^n)_{ii}$ ; sommeren over $i$ geeft $\operatorname{tr}(A^n)$ . Trigonaliserend $A$ (over $\C$ ), is $A^n$ driehoekig met diagonaal $\lambda_i^n$ : $\operatorname{tr}(A^n) = \sum_i\lambda_i^n$ . Driehoek: $\operatorname{tr}(A^n) = 3\,\frac{2^n + 2(-1)^n}3 = 2^n + 2(-1)^n = 2^n + (-1)^n + (-1)^n$ : het spectrum $\{2, -1, -1\}$ , consistent met vraag 16.

20. De kolommen van $W^{\mathsf T}$ : $W^{\mathsf T}e_i = e_{i-1}$ voor $i \geq 1$ en $W^{\mathsf T}e_0 = e_{k-1}$ ; herlabelen in de volgorde $e_0, e_1, \dots$ is dit precies de begeleidende matrix van $X^k - 1$ ( $a_0 = 1$ , andere $a_m = 0$ ). Vraag 2: $\chi_{W} = \chi_{W^{\mathsf T}} = X^k - 1 = \mu_{W}$ . De wortels $\omega^j$ ( $j = 0, \dots, k-1$ ) zijn de $k$ verschillende $k$ -de eenheidswortels: $W$ is diagonaliseerbaar (vraag 3, of Oefening 3.8: $W^k = I$ ). Eigenvectoren: $Wf_j = \sum_m \omega^{-jm}e_{m+1} = \sum_{m'}\omega^{-j(m'-1)}e_{m'} = \omega^j f_j$ .

21. Circulanten zijn veeltermen in $W$ , en veeltermen in een vaste matrix commuten met elkaar. Elke $f_j$ is een eigenvector van elke macht: $W^m f_j = \omega^{jm}f_j$ , dus

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

de basis $(f_0, \dots, f_{k-1})$ (vrij: Vandermonde in de verschillende $\omega^{-j}$ , Oefening 2.11) diagonaliseert elke circulant tegelijk, met de gestelde eigenwaarden.

22. De determinant is het product van de eigenwaarden (diagonaliseer): $\det C = \prod_{j}\widehat c(\omega^j)$ . Voor $k = 3$ , $c_0 = a$ , $c_1 = b$ , $c_2 = c$ en $\omega = j = \eu^{2\iu\pi/3}$ :

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

en $j^4 = j$ : precies de factorisatie van Oefening 2.8.

23. $M = \frac12(W + W^{-1})$ is een circulant ( $W^{-1} = W^{k-1}$ ), met eigenwaarden $\frac12(\omega^j + \omega^{-j}) = \cos\frac{2\pi j}k$ op dezelfde basis $f_j$ . Coördinaten: schrijf $x^{(0)} = \sum_j \alpha_j f_j$ . De coördinaten van $f_j$ sommeren tot $\sum_m \omega^{-jm}$ , wat $k$ is voor $j = 0$ en $0$ anders (geometrische som met ratio $\omega^{-j} \neq 1$ ). Sommerend de coördinaten van $x^{(0)}$ : $\sum_m x^{(0)}_m = \alpha_0\,k$ , dus $\alpha_0 = \frac1k\sum_m x^{(0)}_m$ , het gemiddelde.

24. $x^{(n)} = M^nx^{(0)} = \sum_j \alpha_j\cos^n\bigl(\tfrac{2\pi j}k\bigr)f_j$ . Voor oneven $k$ , $\abs{\cos(2\pi j/k)} < 1$ voor elke $j \neq 0$ (de hoek is nooit $0$ of $\pi$ ), dus neigen alle termen behalve $j = 0$ naar $0$ : $x^{(n)} \to \alpha_0 f_0$ , de constante vector gelijk aan het gemiddelde — middelen op een oneven ring egaliseert. Voor $k = 4$ zijn de eigenwaarden $1, 0, -1, 0$ : de $j = 2$ -term $\alpha_2(-1)^nf_2$ met $f_2 = (1, -1, 1, -1)^{\mathsf T}$ oscilleert eeuwig. De obstructie is het alternerende gemiddelde: de coördinaten van $x^{(0)}$ met $(-1)^m$ vermenigvuldigen en sommeren, dezelfde geometrische-som-berekening geeft $\sum_m (-1)^mx^{(0)}_m = 4\alpha_2$ : het proces convergeert desda $x^{(0)}_0 - x^{(0)}_1 + x^{(0)}_2 - x^{(0)}_3 = 0$ , en convergeert dan naar het gemiddelde.

25. De begeleidende matrix zet een scalaire recurrentie van orde $k$ om in een eerste-orde vectorrecurrentie, zodat gesloten formules uitspraken over $C^n$ worden — het thuisveld van reductie (vragen 1–5). Het kernontbindingslemma is pure veeltermalgebra (Bézout plus commutatie), dus splijt ze $\ker P(S)$ hoewel $\mathcal{S}$ oneindigdimensionaal is (vragen 7–9). Dominante eigenwaarden regeren groei omdat elke andere bijdrage na normalisatie geometrisch verwaarloosbaar is — wat ook is waarom de Pell-fout vervalt met het kwadraat van de dominante wortel (vragen 11–14). Machten van de adjacentiematrix tellen wandelingen omdat matrixvermenigvuldiging over tussenliggende knopen sommeert, zodat spectra gesloten wandelingen tellen (vragen 15–19). Commuterende matrices delen een eigenbasis, en één Fourierbasis diagonaliseert dan heel de circulante algebra in één slag (vragen 20–24). Toppen: de fundamentele stelling van lineaire recurrenties (vraag 9); en voor niet-negatieve matrices is de reden dat dominante wortels zoals $\varphi$ of $1 + \sqrt2$ automatisch reëel, positief en enkelvoudig zijn de stelling van Perron–Frobenius, bewezen in het Bachelor jaar 3-volume.