Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

3Reductie van endomorfismen

Om een endomorfisme te doorgronden, zoekt men de richtingen die het alleen maar uitrekt. Dit hoofdstuk bouwt het gereedschap — eigenwaarden, karakteristieke en minimale veeltermen, het kernontbindingslemma — en oogst de vruchten: criteria voor diagonalisatie en trigonalisatie, Cayley–Hamilton, de Dunford-ontbinding, en het berekenen van machten en exponentiëlen waarop Hoofdstuk 16 zal teren. Overal is $E$ een eindigdimensionale $K$ -vectorruimte ( $K = \R$ of $\C$ ) en $u \in \mathcal{L}(E)$ , met $n = \dim E$ .

3.1 Eigenwaarden en eigenvectoren

Definitie 3.1

Een $\lambda \in K$ heet 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 de eigenwaarden is het spectrum $\operatorname{Sp}(u)$ . Een deelruimte $F$ heet stabiel wanneer $u(F) \subseteq F$ ; eigenruimten zijn stabiel, en op een stabiele deelruimte is het geïnduceerde endomorfisme $u|_F$ gedefinieerd.

Stelling 3.2 (Onafhankelijkheid van de eigenruimten)

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

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

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

dus geeft de inductiehypothese $(\lambda_i - \lambda_r)x_i = 0$ , dat wil zeggen $x_i = 0$ voor $i < r$ , en daarna $x_r = 0$ . Een directe som van ruimten ongelijk aan nul in een ruimte van dimensie $n$ heeft hoogstens $n$ termen. ∎

De matrix A = psmallmatrix2 & 1\\ 1 & 2 psmallmatrix werkend op het vlak: de generieke vector e_1 wordt van zijn rechte af geduwd, maar de eigenrichtingen v_1 = (1,1) en v_2 = (1,-1) worden alleen maar uitgerekt — met 3 en met 1 (zodat Av_2 = v_2: het gestippelde beeld valt samen met v_2). Diagonaliseren is overgaan op de basis (v_1, v_2), waarin A gelijk wordt aan diag(3, 1). — De matrix $A = \left(\begin{smallmatrix}2 & 1\\ 1 & 2\end{smallmatrix}\right)$ werkend op het vlak: de generieke vector $e_1$ wordt van zijn rechte af geduwd, maar de eigenrichtingen $v_1 = (1,1)$ en $v_2 = (1,-1)$ worden alleen maar uitgerekt — met $3$ en met $1$ (zodat $Av_2 = v_2$ : het gestippelde beeld valt samen met $v_2$ ). Diagonaliseren is overgaan op de basis $(v_1, v_2)$ , waarin $A$ gelijk wordt aan $\operatorname{diag}(3, 1)$ .

Definitie 3.3 (Karakteristieke veelterm)

$\chi_u(X) = \det(X\,\mathrm{id} - u)$ — in elke basis berekend als $\det(XI_n - A)$ , een monische veelterm van graad $n$ , invariant onder gelijkvormigheid (Stelling 2.17). Haar nulpunten 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 nulpunt van $\chi_u$ ; de meetkundige multipliciteit is $\dim E_\lambda$ , en er geldt $1 \leq \dim E_\lambda \leq m_\lambda$ .

Bewijs van de genoemde feiten. De uitspraken over de coëfficiënten: ontwikkel $\det(XI - A)$ met de permutatieformule; de identieke permutatie draagt $\prod_i (X - a_{ii}) = X^n - (\sum a_{ii})X^{n-1} + \dots$ bij, en elke andere permutatie houdt hoogstens $n - 2$ diagonaalplaatsen vast en draagt dus graad $\leq n - 2$ bij: de twee hoogste coëfficiënten zijn zoals beweerd; en $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 dan blokbovendriehoekig met linksboven het blok $\lambda I_d$ , zodat $\chi_u(X) = (X - \lambda)^d\, \chi_{\text{(onderste blok)}}(X)$ : de multipliciteit van $\lambda$ is minstens $d$ . ∎

Voorbeeld 3.4 (Dezelfde $\chi$ , andere meetkunde)

De matrices

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

hebben dezelfde karakteristieke veelterm $(X - 2)^2$ , hetzelfde spoor, dezelfde determinant en hetzelfde spectrum — en toch zijn zij niet gelijkvormig: bij de eerste heeft $E_2$ dimensie $2$ (meetkundige multipliciteit $2$ ), bij de tweede dimensie $1$ . De karakteristieke veelterm ziet alleen de algebraïsche multipliciteiten; de dimensies van de eigenruimten zijn de fijnere invariant, en de minimale veelterm beslist ( $X - 2$ tegenover $(X - 2)^2$ ). Moraal voor elke bespreking van diagonaliseerbaarheid: $\chi$ stelt de kandidatenlijst op, maar de kernen brengen de stemmen uit.

Definitie 3.5 (Diagonaliseerbaar, trigonaliseerbaar)

$u$ heet diagonaliseerbaar wanneer $E$ een basis van eigenvectoren bezit (voor een matrix: gelijkvormig met een diagonaalmatrix), en trigonaliseerbaar wanneer haar matrix in een zekere basis bovendriehoekig is.

Stelling 3.6 (Criteria voor diagonaliseerbaarheid)

De volgende uitspraken zijn gelijkwaardig:

$u$ is diagonaliseerbaar;
$E = \bigoplus_{\lambda \in \operatorname{Sp} u} E_\lambda$ ;
$\chi_u$ valt over $K$ in lineaire factoren uiteen en $\dim E_\lambda = m_\lambda$ voor elke eigenwaarde;
(voldoende, niet nodig) $\chi_u$ heeft $n$ verschillende nulpunten in $K$ .

Bewijs. (1 $\iff$ 2): een basis van eigenvectoren valt uiteen in basissen van de $E_\lambda$ , en omgekeerd geeft het aaneenschakelen van basissen van de directe termen een basis van $E$ (Stelling 3.2 maakt de som direct; de gelijkheid van dimensies maakt haar alles).

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

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

waarbij de middelste gelijkheid geldt omdat de graad van een veelterm die in lineaire factoren uiteenvalt de som van haar nulpuntmultipliciteiten is: de som is heel $E$ . Merk op waar elke hypothese werd gebruikt: het uiteenvallen vulde de graad, de gelijkheid van multipliciteiten vulde de dimensies.

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

Methode 3.7 (Diagonaliseerbaarheid beslissen)

Test in de praktijk in deze volgorde — elke stap kan het werk al afmaken. (1) Dient zich een annihilerende veelterm aan die in lineaire factoren met enkelvoudige nulpunten uiteenvalt ( $u^2 = \mathrm{id}$ , $u^2 = u$ , $u^k = \mathrm{id}$ )? Zo ja: dan is $u$ diagonaliseerbaar, zonder rekenwerk (Gevolg 3.17 hieronder). (2) Bereken $\chi_u$ ; heeft zij $n$ verschillende nulpunten in $K$ , dan is $u$ diagonaliseerbaar (Stelling 3.6 (4)). (3) Zo niet, vergelijk dan, uitsluitend voor elk meervoudig nulpunt $\lambda$ , de waarde $\dim\ker(u - \lambda\,\mathrm{id})$ met de multipliciteit $m_\lambda$ : elk tekort doodt de diagonaliseerbaarheid, en overal gelijkheid bewijst haar. Bereken nooit de eigenruimten van enkelvoudige nulpunten (hun dimensie is gedwongen $1$ ), en trigonaliseer nooit alleen om te beslissen.

Voorbeeld 3.8 (Diagonalisatie aan het werk)

$A = I + J = \left(\begin{smallmatrix}2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2\end{smallmatrix}\right)$ , met $J$ de matrix vol enen: uit $\operatorname{Sp}(J) = \{3, 0\}$ (Voorbeeld 2.19) volgt $\operatorname{Sp}(A) = \{4, 1\}$ , met eigenruimten $\R(1,1,1)$ en het vlak $\{x + y + z = 0\}$ : dimensies $1 + 2 = 3$ , dus diagonaliseerbaar (Stelling 3.6 (2)). Machten zonder ook maar één basisovergangsmatrix: met $\Pi = J/3$ de projector op $\R(1,1,1)$ geldt

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 voor $k = 1$ : $\frac{4-1}3 J + I = A$ .) Het inzicht om te onthouden: zodra de eigenruimten zichtbaar zijn, berekenen spectrale projectoren machten sneller dan $PDP^{-1}$ ooit zal doen — en de formule toont de dynamica: $A^k$ groeit als $4^k$ langs $(1,1,1)$ en blijft op het orthogonale vlak staan waar het staat.

Stelling 3.9 (Trigonalisatie)

$u$ is trigonaliseerbaar over $K$ dan en slechts dan als $\chi_u$ over $K$ in lineaire factoren uiteenvalt. In het bijzonder is elk endomorfisme van een $\C$ -vectorruimte trigonaliseerbaar.

Bewijs. ( $\Rightarrow$ ) De karakteristieke veelterm van een driehoeksmatrix is $\prod(X - t_{ii})$ : die valt uiteen.

( $\Leftarrow$ ) Inductie naar $n$ . Omdat $\chi_u$ uiteenvalt, heeft zij een nulpunt $\lambda$ : kies een eigenvector $e_1$ . In een basis die met $e_1$ begint, is de matrix $\begin{pmatrix} \lambda & \ast\\ 0 & B\end{pmatrix}$ , en $\chi_u = (X - \lambda)\chi_B$ : dus valt ook $\chi_B$ uiteen. De inductiehypothese toegepast op de $(n-1) \times (n-1)$ -matrix $B$ geeft een inverteerbare $Q$ met $Q^{-1}BQ$ bovendriehoekig; de hele matrix conjugeren met $\begin{pmatrix}1 & 0\\ 0 & Q\end{pmatrix}$ maakt haar driehoekig. ∎

Voorbeeld 3.10 (Met de hand trigonaliseren)

$B = \begin{pmatrix}3 & -1\\ 1 & 1\end{pmatrix}$ : hier is $\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 rechte opgespannen door $e_1' = (1, 1)$ : één eigenwaarde, een eendimensionale eigenruimte — niet diagonaliseerbaar, maar wel trigonaliseerbaar (Stelling 3.9). Vul de basis aan met $e_2' = (1, 0)$ en reken:

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

zodat de matrix in de basis $(e_1', e_2')$ gelijk is aan $T = \left(\begin{smallmatrix}2 & 1\\ 0 & 2\end{smallmatrix}\right)$ . Het inzicht om te onthouden: de diagonaal van $T$ lag vast (beide elementen moeten de dubbele eigenwaarde $2$ zijn); alleen het hoekelement hing van de keuze van $e_2'$ af, en door $e_2'$ te herschalen kan het elke waarde ongelijk aan nul krijgen — de hardnekkige “ $1$ ” is de schaduw van het nilpotente deel dat Dunford zal isoleren.

3.2 Veeltermen van een endomorfisme

Definitie 3.11

Zet voor $P = \sum a_k X^k \in K[X]$ de afbeelding $P(u) = \sum a_k u^k \in \mathcal{L}(E)$ . De afbeelding $P \mapsto P(u)$ is een morfisme van algebra’s $K[X] \to \mathcal{L}(E)$ (Definitie 1.33); haar kern $\{P : P(u) = 0\}$ is een ideaal van $K[X]$ , ongelijk aan nul (de familie $(\mathrm{id}, u, \dots, u^{n^2})$ is afhankelijk in het $n^2$ -dimensionale $\mathcal{L}(E)$ ), en wordt 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$ ; de eigenwaarden van $u$ zijn nulpunten van elke annihilerende veelterm, en de nulpunten van $\mu_u$ zijn precies de eigenwaarden.
Is $F$ stabiel, dan geldt $\mu_{u|_F} \mid \mu_u$ .

Bewijs. (1) De deelbaarheid is de definitie van een voortbrenger. Geldt $u(x) = \lambda x$ met $x \neq 0$ , dan is $0 = P(u)(x) = P(\lambda)x$ , dus $P(\lambda) = 0$ : eigenwaarden zijn nulpunten van annihilerende veeltermen, in het bijzonder van $\mu_u$ . Omgekeerd, is $\lambda$ een nulpunt, dan is $\mu_u = (X - \lambda)Q$ met $Q(u) \neq 0$ (de graad van $\mu_u$ is minimaal): kies $y$ met $Q(u)(y) \neq 0$ ; dan toont $(u - \lambda)(Q(u)(y)) = \mu_u(u)(y) = 0$ de eigenvector $Q(u)(y)$ .

(2) Er geldt $\mu_u(u|_F) = \mu_u(u)|_F = 0$ ; pas nu (1) toe op $u|_F$ . ∎

Voorbeeld 3.13 (Minimale veeltermen met de hand gevonden)

De minimale veelterm wordt gevonden door achtereenvolgende graden te proberen. Voor de matrix $J \in \mathcal{M}_3(\R)$ vol enen: $J \neq \lambda I$ (graad $1$ valt af), en $J^2 = 3J$ , dus

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

graad $2$ , uiteenvallend, met enkelvoudige nulpunten — dus is $J$ diagonaliseerbaar met spectrum $\{0, 3\}$ (Gevolg 3.17 hieronder), wat Voorbeeld 2.19 bevestigt zonder ook maar één determinant. Voor de verwisselingsmatrix $A$ uit Voorbeeld 3.15: uit $A \neq \pm I$ en $A^2 = I$ volgt $\mu_A = X^2 - 1$ . In beide gevallen is het patroon hetzelfde: raad uit de structuur een identiteit van lage graad (rang één dwingt $J^2 = (\operatorname{tr}J)\,J$ af; een involutie dwingt $A^2 = I$ af) en ga daarna na dat geen echte deler annihileert. Minimale veeltermen worden meestal gevonden, niet uit $\chi$ berekend.

Stelling 3.14 (Kernontbindingslemma)

Is $P = P_1 P_2 \cdots P_r$ met paarsgewijs onderling ondeelbare $P_i$ , dan geldt

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

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

Bewijs. Het volstaat het geval $r = 2$ te behandelen en daarna te induceren. Bézout in $K[X]$ (Stelling 1.26) geeft $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}.

Ligt $x \in \ker P(u)$ , dan is $P_2(u)(x_2) = U(u)\,P(u)(x) = 0$ (veeltermen in $u$ commuteren), dus $x_2 \in \ker P_2(u)$ , en symmetrisch $x_1 \in \ker P_1(u)$ : de som vult $\ker P(u)$ ; beide termen liggen in $\ker P(u)$ omdat $P_i \mid P$ . Directheid: uit $x \in \ker P_1(u) \cap \ker P_2(u)$ volgt $x = U(u)P_1(u)x + V(u)P_2(u)x = 0$ . De formules voor $x_1$ en $x_2$ tonen 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 is $A^2 = I$ : de veelterm $X^2 - 1 = (X - 1)(X + 1)$ annihileert $A$ , haar factoren zijn onderling ondeelbaar, en Bézout is expliciet:

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

Volgens het bewijs van Stelling 3.14 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 rechte $\R(1, -1, 0)$ (antisymmetrisch, eigenwaarde $-1$ ). Het kernlemma is geen uitspraak over bestaan alleen: de coëfficiënten van Bézout zijn de formules voor de projectoren.

Voorbeeld 3.16 (Projectoren berekenen ook de exponentiële)

Dezelfde verwisselingsmatrix, één opbrengst verder. Omdat $A = \pi_+ - \pi_-$ met projectoren die in algebraïsche zin orthogonaal zijn ( $\pi_+\pi_- = 0$ ), voldoet elke macht aan $A^k = \pi_+ + (-1)^k\pi_-$ , en de exponentiële reeks hergroepeert zich 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 voor $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 laten lopen, en de reden dat hyperbolische functies symmetrische koppelingen besturen.

Gevolg 3.17 (Diagonaliseerbaarheid via de minimale veelterm)

$u$ is diagonaliseerbaar $\iff$ $\mu_u$ valt over $K$ uiteen met enkelvoudige nulpunten $\iff$ een zekere annihilerende veelterm van $u$ valt uiteen met enkelvoudige nulpunten.

Bewijs. Geldt $P(u) = 0$ met $P = \prod_{i}(X - \lambda_i)$ (verschillende $\lambda_i$ ), dan 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)$ (die doodt elke eigenruimte), en die veelterm valt uiteen met enkelvoudige nulpunten; en $\mu_u$ deelt haar terwijl beide dezelfde nulpunten hebben (Propositie 3.12): $\mu_u$ is precies dat product. ∎

Voorbeeld 3.18

Projecties voldoen aan $p^2 = p$ : geannihileerd door $X(X-1)$ , dat uiteenvalt met enkelvoudige nulpunten — dus diagonaliseerbaar met spectrum $\subseteq \{0, 1\}$ , en $E = \ker p \oplus \ker(p - \mathrm{id})$ : de meetkundige analyse uit bachelorjaar 1, in één regel opnieuw bewezen. Symmetrieën ( $s^2 = \mathrm{id}$ , annihilator $X^2 - 1$ ): diagonaliseerbaar zodra $\operatorname{char} K \neq 2$ , met spectrum $\subseteq \{\pm 1\}$ . Een endomorfisme met $u^3 = u^2$ en $u^2 \neq u$ : geannihileerd door $X^2(X - 1)$ , en niet noodzakelijk diagonaliseerbaar — het criterium ziet dat (het dubbele nulpunt $0$ moet worden getest: diagonaliseerbaar dan en slechts dan als 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 als eigenruimte de as $\R e_3$ — één rechte van vaste vectoren en geen verdere reductie: $R$ is in $\mathcal{M}_3(\R)$ noch diagonaliseerbaar noch trigonaliseerbaar ( $\chi_R$ valt niet uiteen). 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 in de algebra al hoorbaar: 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 door coördinaten te mengen kan uitdrukken.

Voorbeeld 3.20 (Minimaal tegenover karakteristiek)

Voor $D = \operatorname{diag}(2, 2, 3)$ is $\chi_D = (X - 2)^2(X - 3)$ maar $\mu_D = (X - 2)(X - 3)$ , want $(D - 2I)(D - 3I) = 0$ (ga het op de canonieke basis na), terwijl geen van beide factoren $D$ alleen doodt. Voor het verschuivingsblok $N = \left(\begin{smallmatrix}0 & 1\\ 0 & 0\end{smallmatrix}\right) \oplus (3)$ , dat wil zeggen $N' = \left(\begin{smallmatrix}0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 3\end{smallmatrix}\right)$ , geldt $\chi_{N'} = X^2(X - 3)$ én $\mu_{N'} = X^2(X - 3)$ — het dubbele nulpunt is hier werkelijk nodig, omdat $N'$ aan de kernkant niet diagonaliseerbaar is ( $N'e_2 = e_1 \neq 0$ ). Vuistregel: $\mu$ en $\chi$ hebben dezelfde nulpunten (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)

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

Bewijs. Leg $x \neq 0$ vast en zij $d$ maximaal zodanig dat $(x, u(x), \dots, u^{d-1}(x))$ vrij is; schrijf

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

en zet $P_x = X^d + a_{d-1}X^{d-1} + \dots + a_0$ , zodat $P_x(u)(x) = 0$ . Vul de vrije familie aan tot een basis van $E$ : daarin heeft $u$ de 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, met inductie naar $d$ ). Bijgevolg is $\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$ : dus $\chi_u(u) = 0$ . ∎

Voorbeeld 3.22 (Cayley–Hamilton aan het werk)

$A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ : hier is $\chi_A = X^2 - 5X - 2$ , dus $A^2 = 5A + 2I$ . Elke macht van $A$ klapt in elkaar 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 krijgen we er gratis bij: uit $A(A - 5I) = 2I$ volgt

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

Het inzicht om te onthouden: Cayley–Hamilton perst de hele algebra $K[A]$ samen tot $\operatorname{Vect}(I, A, \dots, A^{n-1})$ — $\dim K[A] = \deg\mu_A \leq n$ , hoe hoog de machten ook zijn die je nodig hebt.

Opmerking 3.23 (Klassieke 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 met verschillende eigenwaarden) en is niet diagonaliseerbaar; alleen commuterende families gedragen zich netjes (Oefening 3.9). (ii) “ $\chi_u$ valt uiteen” is een hypothese over het lichaam: een rotatie in het vlak heeft $\chi = X^2 - 2\cos\theta\,X + 1$ , die over $\C$ wel en over $\R$ niet uiteenvalt — diagonaliseerbaar in $\mathcal{M}_2(\C)$ , niet trigonaliseerbaar in $\mathcal{M}_2(\R)$ . (iii) De ongelijkheid loopt van meetkundig naar algebraïsch, nooit andersom; alleen $\dim E_\lambda \geq 1$ nagaan bewijst niets over diagonaliseerbaarheid. (iv) $\mu_u$ is niet $\chi_u$ : gelijkheid geldt precies wanneer elke eigenwaarde één enkele blokketen heeft (bijvoorbeeld bij begeleidende matrices, de weekendopgave van dit hoofdstuk); $\chi$ gebruiken waar $\mu$ nodig is, blaast elke machtsberekening op. (v) De $d$ en $\nu$ van Dunford zijn veeltermen in $u$ — een ontbinding $u = d' + \nu'$ met de juiste eigenschappen maar met $d'\nu' \neq \nu'd'$ is geen Dunford en is nooit eenduidig.

Opmerking 3.24 (Waar dit hoofdstuk wordt gebruikt)

De reductie is het werkpaard van de rest van het boek: machten en exponentiëlen van matrices drijven de lineaire differentiaalstelsels van Hoofdstuk 16; de spectraalstelling van Hoofdstuk 12 is diagonalisatie, orthogonaal gemaakt; genererende functies (Hoofdstuk 23) leiden de asymptotiek van de recurrenties uit de weekendopgave van dit hoofdstuk analytisch opnieuw af. In het volume van bachelorjaar 3 loopt hetzelfde programma in oneindige dimensie: de spectraaltheorie van compacte zelftoegevoegde operatoren, waar rijen van eigenwaarden de plaats van eindige spectra innemen, en de theorie van Perron–Frobenius voor positieve matrices, die verklaart waarom de dominante eigenwaarden van telproblemen positief en enkelvoudig zijn.

3.3 Nilpotenten en de Dunford-ontbinding

Propositie 3.25 (Nilpotente endomorfismen)

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

Bewijs. Uit $u^k = 0$ volgt dat elke eigenwaarde een nulpunt van $X^k$ is: spectrum $\{0\}$ (niet leeg zodra $\chi$ uiteenvalt — over $\C$ altijd). Dan is $\chi_u = X^n$ (alle nulpunten zijn nul) en geeft Cayley–Hamilton $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 met inductie aan dat

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

dat wil zeggen: elke macht duwt het nulgebied één diagonaal hoger. Voor $k = 1$ is dat 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$ volgens de inductiehypothese), ofwel $\ell \geq i + k$ , en dan doodt $j \leq i + k \leq \ell$ de tweede factor. Bij $k = n$ geldt de voorwaarde $j \leq i + n - 1$ voor alle $i, j \leq n$ : dus $A^n = 0$ . De minimale veelterm deelt $X^n$ , en de annihilatie definieert de index. ∎

Stelling 3.26 (Dunford-ontbinding)

Neem aan dat $\chi_u$ over $K$ uiteenvalt (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 zet $N_i = \ker(u - \lambda_i)^{m_i}$ , de karakteristieke deelruimten. Volgens Cayley–Hamilton en het kernlemma (Stelling 3.14) is

E = N_1 \oplus \dots \oplus N_r ,

met projecties $\pi_i$ die veeltermen in $u$ zijn; elke $N_i$ is stabiel (veeltermen in $u$ commuteren met $u$ ). Definieer $d = \sum_i \lambda_i \pi_i$ : een veelterm in $u$ , diagonaliseerbaar (zij werkt op $N_i$ als $\lambda_i$ , zodat $E$ in haar eigenruimten uiteenvalt). Dan is $\nu = u - d$ een veelterm in $u$ (en commuteert dus met $d$ ), en op elke $N_i$ werkt zij als $u - \lambda_i$ , waar $(u - \lambda_i)^{m_i} = 0$ : dus $\nu^{\max m_i} = 0$ op elke term, en $\nu$ is nilpotent.

Eenduidigheid. Zij $u = d' + \nu'$ een tweede zulk paar. Omdat $d'$ en $\nu'$ met elkaar commuteren, commuteren zij met $u = d' + \nu'$ en dus met elke veelterm in $u$ — in het bijzonder met $d$ en $\nu$ . Dan is $d - d'$ diagonaliseerbaar (twee commuterende diagonaliseerbare afbeeldingen zijn simultaan diagonaliseerbaar: Oefening 3.9) en gelijk aan $\nu' - \nu$ , dat nilpotent is: geldt $\nu^k = 0$ en $\nu'^{k'} = 0$ , dan staat de commutatie de binomiale ontwikkeling 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), ofwel $k + k' - 1 - j \geq k$ (tweede factor nul), en één van beide geldt altijd. Een diagonaliseerbare nilpotent is nul (haar spectrum is $\{0\}$ en zij is in een zekere basis diagonaal): dus $d = d'$ en $\nu = \nu'$ . ∎

Voorbeeld 3.27 (Machten en exponentiëlen)

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

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

volgens het binomium voor commuterende termen, respectievelijk de exponentiële reeks (Hoofdstuk 16) gesplitst over commuterende termen. Reductie maakt van matrixdynamica scalaire dynamica.

Opmerking 3.28 (Vooruitblik binnen dit volume)

De reductie is een knooppunt; let op deze vier spaken. In Hoofdstuk 5 maken aangepaste normen van “alle eigenwaarden hebben modulus $< 1$ ” de uitspraak “een zekere operatornorm is $< 1$ ”, zodat spectra de convergentie van machten en reeksen gaan besturen. In Hoofdstuk 16 wordt het recept van Voorbeeld 3.27 de algemene oplossing van $X' = AX$ : Dunford splitst $\eu^{tA}$ in blokken van het type veelterm maal exponentiële, en de stabiliteit is af te lezen aan de reële delen van de eigenwaarden. In Hoofdstuk 12 dwingt een inproduct af wat lineaire algebra alleen niet kan: symmetrische matrices worden orthogonaal diagonaliseerbaar, zonder enig nilpotent deel. En in Hoofdstuk 23 keert de asymptotiek van de dominante eigenwaarde uit de weekendopgave 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, basissen van de eigenruimten, een 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$ : hier is $\chi_A = X^2 - 2X - 3 = (X - 3)(X + 1)$ . Eigenvectoren: bij $3$ de vector $(1,1)$ , bij $-1$ de vector $(1,-1)$ . Met $P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ geldt dus $P^{-1}AP = \operatorname{diag}(3, -1)$ .

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

Oefening 3.2 ★

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

Oplossing

Oplossing van Oefening 3.2.

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

Via de minimale veelterm: $\mu_C$ deelt $(X-1)^2$ en $C \neq I$ , dus $\mu_C = (X-1)^2$ : een dubbel nulpunt, en dus niet diagonaliseerbaar (Gevolg 3.17).

Oefening 3.3 ★

Zij $u$ zodanig dat $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)$ : uiteenvallend met enkelvoudige nulpunten, 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$ ; oplossen geeft $b_k = 3^k - 2^k$ en $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 .

(Dit geldt voor alle drie de spectra: de identiteiten gelden per eigenwaarde.)

Oefening 3.4 ★★

Zij $u$ diagonaliseerbaar en $F$ een stabiele deelruimte. Bewijs dat $u|_F$ diagonaliseerbaar is (beperk een annihilerende veelterm met enkelvoudige nulpunten die uiteenvalt).

Oplossing

Oplossing van Oefening 3.4.

Omdat $u$ diagonaliseerbaar is, annihileert $P = \prod_{\lambda}(X - \lambda)$ over het spectrum de afbeelding $u$ , en $P$ valt uiteen met enkelvoudige nulpunten. Dan is $P(u|_F) = P(u)|_F = 0$ : de beperking wordt geannihileerd door een uiteenvallende veelterm met enkelvoudige nulpunten en is 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 daaruit de formule van Binet af voor de rij van 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}.

Oplossing

Oplossing van Oefening 3.5.

$\chi_A = X^2 - X - 1$ , met nulpunten $\varphi$ en $\psi$ (verschillend): dus 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$ . Het toepassen van $A^n$ vermenigvuldigt elke eigencomponent met de $n$ -de macht van haar eigenwaarde; de tweede coördinaat aflezen geeft

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

(Controle: voor $n = 1$ geeft dit $\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)$ een annihilerende veelterm van $u^2$ die uiteenvalt met enkelvoudige nulpunten $\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 zijn alle $\mu_i \neq 0$ . Dan annihileert

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

de afbeelding $u$ : immers $Q(u) = \prod_i (u^2 - \mu_i\,\mathrm{id}) = P(u^2) = 0$ . Haar nulpunten $\pm \sqrt{\mu_i}$ (complexe vierkantswortels) zijn paarsgewijs verschillend omdat de $\mu_i$ verschillend en ongelijk aan nul zijn (uit $\sqrt{\mu_i} = -\sqrt{\mu_j}$ zou $\mu_i = \mu_j$ volgen). Uiteenvallend met enkelvoudige nulpunten: dus is $u$ diagonaliseerbaar.

Tegenvoorbeeld zonder inverteerbaarheid: $u = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ ; hier is $u^2 = 0$ diagonaliseerbaar en $u$ 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 verschuiving ( $N e_2 = e_1$ , $Ne_3 = e_2$ ), $N^3 = 0$ en $N^2 = E_{13}$ : dit is de Dunford-ontbinding ( $2I$ diagonaal, $N$ nilpotent, en zij commuteren; de eenduidigheid maakt het de enige). Het binomium voor commuterende termen geeft

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 dat haar eigenwaarden $k$ -de eenheidswortels zijn. Leid af dat een inverteerbare complexe matrix van eindige orde die gelijkvormig is met een driehoeksmatrix met diagonaal vol enen, de identiteit is.

Oplossing

Oplossing van Oefening 3.8.

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

Is $A$ bovendien gelijkvormig met een driehoeksmatrix met diagonaal vol enen, dan zijn alle eigenwaarden gelijk aan $1$ , en is $A$ , diagonaliseerbaar met enige eigenwaarde $1$ , gelijk aan $P\,I\,P^{-1} = I$ .

Oefening 3.9 ★★★

(Simultane diagonalisatie) Zijn $u, v$ diagonaliseerbaar en commuterend. Bewijs dat zij simultaan diagonaliseerbaar zijn: een zekere basis diagonaliseert beide. (Elke eigenruimte van $u$ is $v$ -stabiel; diagonaliseer daar de beperkingen van $v$ , 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$ is $u(v(x)) = v(u(x)) = \lambda v(x)$ . De beperking van $v$ tot $E_\lambda(u)$ is diagonaliseerbaar (Oefening 3.4): kies een basis van $E_\lambda(u)$ die uit eigenvectoren van $v$ bestaat. Deze basissen over alle $\lambda$ aaneenschakelen geeft een basis van $E$ waarvan de vectoren eigenvectoren van zowel $u$ (omdat zij in $E_\lambda(u)$ liggen) als $v$ (per constructie) zijn.

Oefening 3.10 ★★★

Zij $u \in \mathcal{L}(\C^n)$ . Bewijs dat $u$ diagonaliseerbaar is dan en slechts dan als elke $u$ -stabiele deelruimte een $u$ -stabiel complement bezit. (Voor $\Leftarrow$ : pas de eigenschap toe op $F = \sum_\lambda E_\lambda(u)$ , de som van alle eigenruimten; was een stabiel complement $G$ ongelijk aan nul, dan zou het trigonaliseren van $u|_G$ een eigenvector van $u$ binnen $G$ opleveren — 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$ tot een basis van $E_\lambda$ laat uitbreiden (de onvolledige-basisstelling binnen $E_\lambda$ , uitgaande van het deel van de basis van $F$ dat daar ligt — merk op dat $F = \bigoplus_\lambda (F \cap E_\lambda)$ omdat $u|_F$ diagonaliseerbaar is). De toegevoegde vectoren spannen een stabiel complement op (elk ligt in een 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. Was $G \neq \{0\}$ , dan valt $\chi_{u|_G}$ over $\C$ uiteen, dus heeft $u|_G$ een eigenvector $x \in G$ (Stelling 3.9, of rechtstreeks het bestaan van een nulpunt); maar elke eigenvector van $u$ ligt in $F$ , dus $x \in F \cap G = \{0\}$ : tegenspraak. Bijgevolg is $G = \{0\}$ en $E = F$ : de eigenruimten vullen $E$ , dat wil zeggen $u$ is diagonaliseerbaar.

Oefening 3.11 ★★★

(Spectraalstraal in het klein, een voorproefje van de analyse die komt) Zij $A \in \mathcal{M}_2(\C)$ met beide eigenwaarden van modulus $< 1$ . Bewijs dat $A^k \to 0$ element voor element als $k \to \infty$ . (Trigonaliseer: $A = P(T)P^{-1}$ met $T$ bovendriehoekig; bereken $T^k$ expliciet — onderscheid gelijke en verschillende eigenwaarden — en schat af.)

Oplossing

Oplossing van Oefening 3.11.

Trigonaliseer: $A = PTP^{-1}$ met $T = \begin{pmatrix} \lambda & c\\ 0 & \mu\end{pmatrix}$ en $\abs\lambda, \abs\mu < 1$ . Dan is $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 elk element gaat naar $0$ (want $\abs{\lambda}^k, \abs\mu^k \to 0$ ).

Gelijke eigenwaarden ( $\mu = \lambda$ ): hier is $T = \lambda I + cE_{12}$ en $T^k = \lambda^k I + k\lambda^{k-1}cE_{12}$ ; het element $k\lambda^{k-1}$ gaat naar $0$ omdat $\abs\lambda < 1$ (meetkundig wint van polynomiaal). In beide gevallen gaat $T^k$ element voor element naar $0$ , en dus $A^k = PT^kP^{-1} \to 0$ (vermenigvuldigen met vaste $P$ en $P^{-1}$ is continu in de elementen — elk element 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 aan dat $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ , en dat $u$ diagonaliseerbaar is dan en slechts dan als $\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$ (dimensiestelling), dus is $0$ een eigenwaarde met 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)$ ; omdat de coëfficiënt van $X^{n-1}$ gelijk is aan $-\operatorname{tr} u$ , volgt $\alpha = \operatorname{tr} u$ : dus $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ .

Is $\operatorname{tr} u \neq 0$ , dan is de eigenwaarde $\operatorname{tr} u$ een nulpunt van $\chi_u$ en draagt zij dus een eigenvector; de eigenruimten bij $0$ en bij $\operatorname{tr} u$ hebben dimensies $n - 1$ en $\geq 1$ , samen $\geq n$ : zij vullen $E$ , en $u$ is diagonaliseerbaar (Stelling 3.6). Is $\operatorname{tr} u = 0$ , dan geeft Oefening 2.5 dat $u^2 = (\operatorname{tr} u)u = 0$ met $u \neq 0$ : $u$ is een nilpotent ongelijk aan nul, en een diagonaliseerbare nilpotent is nul (Propositie 3.25): dus 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 vermomde matrixmacht, en de reductie zet haar om in gesloten formules, groeisnelheden en foutschattingen. Deze weekendopgave bouwt het woordenboek op — begeleidende matrices aan de ene kant, de verschuivingsoperator op de ruimte van rijen aan de andere —, bewijst de hoofdstelling over lineaire recurrenties (de algemene oplossing is $\sum_i Q_i(n)\lambda_i^n$ over de nulpunten van de karakteristieke veelterm) en besteedt de opbrengst aan de diofantische benadering van $\sqrt2$ , aan het tellen van wandelingen en woorden, en aan een ring van gekoppelde rijen die alleen door simultane diagonalisatie te ontwarren is.

Probleem 3.1

Weekendopgave — de hoofdstelling over lineaire recurrenties

Leg $k \geq 1$ vast, scalairen $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 woordenboek van de begeleidende matrix.

Toon aan dat een rij $(u_n)$ aan $(\mathcal R)$ voldoet dan en slechts dan als de vectoren $v_n = (u_n, u_{n+1}, \dots, u_{n+k-1})^{\mathsf T}$ voldoen aan $v_{n+1} = Cv_n$ , en dus $v_n = C^n v_0$ .
Bewijs dat $\chi_C = P$ (ontwikkel $\det(XI - C)$ langs de eerste kolom en induceer naar $k$ ), en vervolgens dat ook $\mu_C = P$ (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 aan dat voor elk nulpunt $\lambda$ van $P$ de vector $(1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ de eigenruimte van $C$ bij $\lambda$ opspant; leid af dat elke eigenruimte van $C$ dimensie $1$ heeft, en dat $C$ diagonaliseerbaar is dan en slechts dan als $P$ $k$ verschillende nulpunten heeft.
Neem aan dat $P$ verschillende nulpunten $\lambda_1, \dots, \lambda_k$ heeft. Toon aan dat de meetkundige rijen $(\lambda_i^n)_n$ een basis vormen van de oplossingsruimte van $(\mathcal R)$ , zodat elke oplossing $u_n = \sum_i c_i\lambda_i^n$ is voor eenduidig bepaalde constanten $c_i$ .
Los volledig op: $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ .

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

Toon aan dat de oplossingsverzameling van $(\mathcal R)$ gelijk is aan $\ker P(S)$ , en dat zij precies dimensie $k$ heeft (stuur een oplossing naar haar beginwaarden).
Leg uit waarom het kernontbindingslemma (Stelling 3.14) zonder enige wijziging op $S$ toepasbaar is op het oneindigdimensionale $\mathcal{S}$ , en schrijf de resulterende ontbinding van $\ker P(S)$ op voor $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ (verschillende $\lambda_i$ , alle ongelijk aan nul omdat $a_0 \neq 0$ ).
Toon voor $\lambda \neq 0$ en $m \geq 1$ aan dat

$\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; begrens voor de dimensie door $m$ via de beginwaarden.)
(De hoofdstelling over lineaire recurrenties) Besluit: is $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ met verschillende $\lambda_i$ die alle ongelijk aan nul zijn, dan 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 eenduidig 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 nulpunten en diofantische opbrengsten.

Neem aan dat de nulpunten enkelvoudig zijn met $\abs{\lambda_1} > \abs{\lambda_i}$ voor $i \geq 2$ , en dat $u_n = \sum_i c_i \lambda_i^n$ met $c_1 \neq 0$ . Toon aan dat $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$ , met $a_0 = b_0 = 1$ . Toon aan dat $q(a, b) = a^2 - 2b^2$ voldoet aan $q(a_{n+1}, b_{n+1}) = -q(a_n, b_n)$ , en dus $a_n^2 - 2b_n^2 = (-1)^{n+1}$ ; breng dit in verband met de determinant van $M = \left(\begin{smallmatrix}1 & 2\\ 1 & 1\end{smallmatrix}\right)$ .
Leid de foutschatting

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

af, en toon aan dat zij meetkundig afneemt met factor $3 - 2\sqrt2$ (bepaal de eigenwaarden van $M$ en de groei van $b_n$ ).
(Algemene groei) Bewijs uit vraag 9: (a) voldoet elk nulpunt aan $\abs{\lambda_i} \leq \rho$ , dan is $\abs{u_n} \leq C\,n^{m-1}\rho^n$ met $m = \max_i m_i$ ; (b) is er precies één nulpunt $\lambda_1$ van maximale modulus en is $Q_1 \neq 0$ , dan geldt $u_{n+1}/u_n \to \lambda_1$ — ga dit na op de oplossing van vraag 10.

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

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

$(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 voor $n = 2$ door de wandelingen op te sommen.
(Woorden zonder $11$ ) Zij $w_n$ het aantal binaire woorden van lengte $n$ zonder twee opeenvolgende enen. Codeer de woorden naar hun laatste letter om een overdrachtsmatrix te krijgen, toon aan dat $w_{n+2} = w_{n+1} + w_n$ , leid af dat $w_n = F_{n+2}$ (Fibonacci, Oefening 3.5), en geef de groeisnelheid $\lim w_{n+1}/w_n$ .
(Het pad) Toon voor de padgraaf $1 - 2 - 3$ aan dat de eigenwaarden van $A$ gelijk zijn aan $\sqrt2, 0, -\sqrt2$ met eigenvectoren $(1, \pm\sqrt2, 1)$ en $(1, 0, -1)$ , en leid af dat het aantal wandelingen van lengte $n$ van het ene uiteinde naar het andere gelijk is aan $\bigl((\sqrt2)^n + (-\sqrt2)^n\bigr)/4$ : nul voor oneven $n$ , en $2^{\,n/2 - 1}$ voor even $n$ . Controleer dit voor $n = 4$ .
(Spoorformule) Toon aan dat het totale aantal gesloten wandelingen van lengte $n$ (over alle beginpunten) gelijk is aan $\operatorname{tr}(A^n) = \sum_i \lambda_i^n$ , en ga dit na op de driehoek.

Deel V — Een ring van rijen: simultane diagonalisatie. Leg $k \geq 3$ vast, zij $\omega = \eu^{2\iu\pi/k}$ , en zij $W \in \mathcal{M}_k(\C)$ de cyclische verschuiving: $W e_i = e_{i+1}$ (indices modulo $k$ , kolommen genummerd $0, \dots, k-1$ ).

Toon aan dat $W^{\mathsf T}$ de begeleidende matrix van $X^k - 1$ is, leid af dat $\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 aan dat alle circulante matrices commuteren, dat de basis $(f_0, \dots, f_{k-1})$ ze alle tegelijk diagonaliseert, en dat de eigenwaarden van $C$ gelijk zijn aan $\widehat c(\omega^j) = \sum_m c_m \omega^{jm}$ , $j = 0, \dots, k-1$ .
Leid af dat $\det C = \prod_{j=0}^{k-1} \widehat c(\omega^j)$ , en ga na dat $k = 3$ de factorisatie van Oefening 2.8 teruggeeft.
(Het halssnoergemiddelde) Zij $x^{(n+1)} = Mx^{(n)}$ met $M = \frac12(W + W^{-1})$ : elk van $k$ getallen die in een ring liggen wordt vervangen door het gemiddelde van zijn twee buren. Toon aan dat de eigenwaarden van $M$ gelijk zijn aan $\cos(2\pi j/k)$ , en dat de coëfficiënt van $x^{(0)}$ op $f_0$ het gemiddelde $\frac1k\sum_m x^{(0)}_m$ is (tel de coördinaten van de $f_j$ op).
Besluit: voor oneven $k$ convergeert $x^{(n)}$ naar de constante vector met als waarde het gemiddelde van de beginwaarden; geef voor $k = 4$ de eigenwaarde die voor de niet-convergentie verantwoordelijk is, en de exacte hindernis (een coëfficiënt van het alternerende gemiddelde die nul moet zijn).
(Synthese) In telkens één zin: hoe de begeleidende matrix de analyse van $(\mathcal R)$ omzet in reductie; waar het kernontbindingslemma geen eindige dimensie nodig had; waarom dominante eigenwaarden de groeisnelheden en de diofantische fout besturen; waarom machten van de adjacentiematrix wandelingen tellen; en wat commuterende matrices opleveren. Noem de twee toppen: de hoofdstelling over lineaire recurrenties, en — voor de positieve matrices van Deel IV, in het volume van bachelorjaar 3 — 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 bovendiagonaal verschuift), en de laatste is $a_0 u_n + \dots + a_{k-1}u_{n+k-1}$ . Dus geldt $v_{n+1} = Cv_n$ voor alle $n$ dan en slechts dan als de laatste coördinaten voor alle $n$ overeenkomen, dat wil zeggen dan en slechts dan als $(\mathcal R)$ geldt. Itereren geeft $v_n = C^nv_0$ .

2. Ontwikkel $D_k(X) = \det(XI_k - C)$ langs de eerste kolom: de twee elementen ongelijk aan nul zijn $X$ (plaats $(1,1)$ ) en $-a_0$ (plaats $(k,1)$ ). De eerste minor heeft de vorm van $D_{k-1}$ 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}$ vanwege de plaats. Inductie naar $k$ (basisgeval $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 annihilerende veeltermen en dus dezelfde minimale veelterm. Voor $C^{\mathsf T}$ luiden de kolommen $C^{\mathsf T}e_1 = e_2$ , …, $C^{\mathsf T}e_{k-1} = e_k$ , zodat $(e_1, C^{\mathsf T}e_1, \dots, (C^{\mathsf T})^{k-1}e_1)$ de canonieke basis is: vrij. Een veelterm $Q \neq 0$ van graad $< k$ voldoet dan aan $Q(C^{\mathsf T})e_1 \neq 0$ (het is een niet-triviale combinatie van basisvectoren): dus $\deg\mu \geq k$ . Omdat $\mu \mid \chi = P$ met $\deg P = k$ , volgt $\mu_C = P$ .

3. Voor $v = (1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ geven de rijen $1$ tot $k-1$ van $Cv$ de waarden $\lambda, \lambda^2, \dots, \lambda^{k-1}$ , dat wil zeggen $\lambda$ maal de eerste $k - 1$ componenten 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$ juist $x_{i+1} = \lambda x_i$ : elke eigenvector is evenredig met $v$ — dus heeft elke eigenruimte precies dimensie $1$ . En $C$ is diagonaliseerbaar dan en slechts dan als de dimensies van de eigenruimten samen $k$ zijn (Stelling 3.6), dan en slechts dan als er $k$ verschillende eigenwaarden zijn, dan en slechts dan als $P$ $k$ verschillende nulpunten heeft (de eigenwaarden zijn de nulpunten 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 Vandermonde-stelsel (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 dus een basis, en de coördinaten zijn eenduidig.

5. $P = X^2 - X - 6 = (X - 3)(X + 2)$ : algemene oplossing $u_n = A\,3^n + B(-2)^n$ . Beginvoorwaarden: $A + B = 1$ en $3A - 2B = 8$ , dus $A = 2$ en $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$ : zij verdwijnt dan en slechts dan als $(\mathcal R)$ geldt, dus is de oplossingsverzameling gelijk aan $\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 met inductie $u_{k}, u_{k+1}, \dots$ uit de eerste $k$ waarden) en surjectief (definieer $u_n$ recursief uit willekeurige begingegevens): dimensie $k$ .

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

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

8. Voor $Q \in \C[X]$ heeft $(S - \lambda)\bigl(Q(n)\lambda^n\bigr)_n$ als $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 kopterm valt weg). Itereren geeft $(S - \lambda)^m\bigl(Q(n)\lambda^n\bigr) = \bigl(\lambda^{n+m}(\Delta^m Q)(n)\bigr)_n$ , en $\Delta^m Q = 0$ zodra $\deg Q \leq m - 1$ : de verzameling in het rechterlid ligt dus in de kern. Zij is een deelruimte van dimensie $m$ : de rijen $(n^j\lambda^n)_n$ met $0 \leq j < m$ zijn vrij, want uit $\sum_j c_j n^j\lambda^n = 0$ voor alle $n$ volgt (na deling door $\lambda^n \neq 0$ ) dat de veelterm $\sum_j c_jX^j$ in elke $n \in \N$ verdwijnt en dus nul is. Omgekeerd is $\dim\ker(S - \lambda)^m \leq m$ : werk $(S - \lambda)^m = \sum_j \binom mj(-\lambda)^{m-j}S^j$ uit; de vergelijking $(S - \lambda)^m u = 0$ is een lineaire recurrentie van orde $m$ (met kopcoëfficiënt $1$ ), dus wordt $u$ bepaald door $u_0, \dots, u_{m-1}$ zoals in vraag 6. De gelijkheid van de dimensies besluit.

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

10. $P = X^2 - 4X + 4 = (X - 2)^2$ : de oplossingen zijn $(a + bn)2^n$ . Begingegevens: $a = 1$ en $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 verhouding heeft modulus $< 1$ , dus gaat de haak naar $c_1 \neq 0$ : $u_n \sim c_1\lambda_1^n$ . In het bijzonder is $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. Reken uit:

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$ volgt $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$ (reken na: $a_{n+1} + \sqrt2 b_{n+1} = (1 + \sqrt2)(a_n + \sqrt2 b_n)$ ); het product wordt bij elke stap vermenigvuldigd met $(1 + \sqrt2)(1 - \sqrt2) = -1 = \det M$ .

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

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

waarbij $a_n \geq b_n \geq 1$ (met inductie: beide stijgen), zodat $a_n + \sqrt2 b_n \geq (1 + \sqrt2)b_n \geq 2b_n$ . Eigenwaarden van $M$ : $\chi_M = X^2 - 2X - 1$ , met nulpunten $1 \pm \sqrt2$ ; omdat $(a_0, b_0)$ een component ongelijk aan nul heeft op de dominante eigenvector (alle componenten zijn positief), is $b_n \sim c(1 + \sqrt2)^n$ met $c > 0$ (vraag 11). De fout is dus $\asymp (1 + \sqrt2)^{-2n} = (3 + 2\sqrt2)^{-n}$ : meetkundige afname met factor $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 $\abs{Q_i(n)} \leq C_i n^{m_i - 1} \leq C_i n^{m-1}$ voor $n \geq 1$ : tel de constanten op. (b) Zij $\rho' = \max_{i \geq 2}\abs{\lambda_i} < \abs{\lambda_1}$ , $d = \deg Q_1$ en $c \neq 0$ de kopcoëfficiënt. Dan is $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

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

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

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

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

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

16. Er geldt $J = 3\Pi$ , waarbij $\Pi = J/3$ de projectie op $\operatorname{Vect}(1,1,1)$ langs het vlak $x + y + z = 0$ is ( $\Pi^2 = \Pi$ omdat $J^2 = 3J$ ). Dan is $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{dus}\qquad (A^n)_{ij} = \frac{2^n}3 + (-1)^n\Bigl(\delta_{ij} - \frac13\Bigr),

wat de twee gevraagde formules geeft. Voor $n = 2$ : op de diagonaal $(4 + 2)/3 = 2$ (de wandelingen $i \to \ell \to i$ over de twee buren $\ell$ ); buiten de diagonaal $(4 - 1)/3 = 1$ (de ene wandeling $i \to \ell \to j$ via de derde knoop).

17. Zijn $w_n^{(0)}$ en $w_n^{(1)}$ het aantal toegelaten woorden van lengte $n$ die op $0$ respectievelijk op $1$ eindigen. Bij het toevoegen van een letter mag een $0$ op alles volgen en 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}.

Optellen geeft $w_{n+2} = w_{n+1} + w_n$ (of: onderscheid naar de eerste letter). Met $w_1 = 2$ en $w_2 = 3$ volgt met inductie $w_n = F_{n+2}$ ( $F_3 = 2$ , $F_4 = 3$ , dezelfde recurrentie). Groei: de nulpunten van $X^2 - X - 1$ zijn $\varphi > \abs\psi$ (Oefening 3.5), en de component bij $\varphi$ is ongelijk aan nul (de $w_n$ zijn positief en $\psi^n \to 0$ ), dus geeft vraag 11 dat $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 af, of gebruik de symmetrie: met $v_\pm = (1, \pm\sqrt2, 1)$ en $v_0 = (1, 0, -1)$ gaat men na dat $e_1 = \frac14 v_+ + \frac14 v_- + \frac12 v_0$ , zodat 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$ (de graaf is bipartiet: de uiteinden liggen op even afstand), en $2\cdot 2^{n/2}/4 = 2^{n/2 - 1}$ voor even $n$ . Voor $n = 4$ : $2^{1} = 2$ , in overeenstemming met de twee wandelingen $1\,2\,1\,2\,3$ en $1\,2\,3\,2\,3$ .

19. Het aantal gesloten wandelingen van lengte $n$ vanuit $i$ is $(A^n)_{ii}$ ; sommeren over $i$ geeft $\operatorname{tr}(A^n)$ . Trigonaliseren we $A$ (over $\C$ ), dan is $A^n$ driehoekig met diagonaal $\lambda_i^n$ : $\operatorname{tr}(A^n) = \sum_i\lambda_i^n$ . Voor de driehoek: $\operatorname{tr}(A^n) = 3\,\frac{2^n + 2(-1)^n}3 = 2^n + 2(-1)^n = 2^n + (-1)^n + (-1)^n$ , dat wil zeggen het spectrum $\{2, -1, -1\}$ , in overeenstemming 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}$ ; hernoemen we in de volgorde $e_0, e_1, \dots$ , dan is dit precies de begeleidende matrix van $X^k - 1$ ( $a_0 = 1$ , de overige $a_m = 0$ ). Vraag 2 geeft $\chi_{W} = \chi_{W^{\mathsf T}} = X^k - 1 = \mu_{W}$ . De nulpunten $\omega^j$ ( $j = 0, \dots, k-1$ ) zijn de $k$ verschillende $k$ -de eenheidswortels: dus is $W$ 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. Circulante matrices zijn veeltermen in $W$ , en veeltermen in een vaste matrix commuteren onderling. 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 alle circulante matrices tegelijk, met de genoemde eigenwaarden.

22. De determinant is het product van de eigenwaarden (diagonaliseer): $\det C = \prod_{j}\widehat c(\omega^j)$ . Voor $k = 3$ , met $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 circulante matrix ( $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$ tellen op tot $\sum_m \omega^{-jm}$ , wat $k$ is voor $j = 0$ en anders $0$ (een meetkundige som met reden $\omega^{-j} \neq 1$ ). Tellen we de coördinaten van $x^{(0)}$ op, dan komt er $\sum_m x^{(0)}_m = \alpha_0\,k$ , dus $\alpha_0 = \frac1k\sum_m x^{(0)}_m$ , het gemiddelde.

24. Er geldt $x^{(n)} = M^nx^{(0)} = \sum_j \alpha_j\cos^n\bigl(\tfrac{2\pi j}k\bigr)f_j$ . Voor oneven $k$ is $\abs{\cos(2\pi j/k)} < 1$ voor elke $j \neq 0$ (de hoek is nooit $0$ of $\pi$ ), dus gaan alle termen behalve $j = 0$ naar $0$ : $x^{(n)} \to \alpha_0 f_0$ , de constante vector met als waarde het gemiddelde — middelen op een oneven ring maakt gelijk. Voor $k = 4$ zijn de eigenwaarden $1, 0, -1, 0$ : de term bij $j = 2$ , te weten $\alpha_2(-1)^nf_2$ met $f_2 = (1, -1, 1, -1)^{\mathsf T}$ , blijft eeuwig oscilleren. De hindernis is het alternerende gemiddelde: vermenigvuldigen we de coördinaten van $x^{(0)}$ met $(-1)^m$ en tellen we op, dan geeft dezelfde meetkundige som $\sum_m (-1)^mx^{(0)}_m = 4\alpha_2$ : het proces convergeert dan en slechts dan als $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 vectorrecurrentie van orde één, zodat gesloten formules uitspraken over $C^n$ worden — het eigen terrein van de reductie (vragen 1–5). Het kernontbindingslemma is zuivere veeltermalgebra (Bézout plus commutatie) en splitst dus $\ker P(S)$ ook al is $\mathcal{S}$ oneindigdimensionaal (vragen 7–9). Dominante eigenwaarden besturen de groei omdat elke andere bijdrage na normalisatie meetkundig verwaarloosbaar is — en daarom neemt de fout bij Pell af als het kwadraat van het dominante nulpunt (vragen 11–14). Machten van de adjacentiematrix tellen wandelingen omdat matrixvermenigvuldiging over de tussenknopen sommeert, zodat spectra gesloten wandelingen tellen (vragen 15–19). Commuterende matrices delen een eigenbasis, en één fourierbasis diagonaliseert dan in één klap de hele algebra van de circulante matrices (vragen 20–24). De toppen: de hoofdstelling over lineaire recurrenties (vraag 9); en voor niet-negatieve matrices is de reden dat dominante nulpunten als $\varphi$ of $1 + \sqrt2$ vanzelf reëel, positief en enkelvoudig zijn, de stelling van Perron–Frobenius, bewezen in het volume van bachelorjaar 3.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst