Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

21Matrices

Een matrix is een lineaire afbeelding uitgedrukt in coördinaten. Dit hoofdstuk stelt het woordenboek op — samenstelling wordt matrixproduct, bijectiviteit wordt inverteerbaarheid, basisverandering wordt conjugatie — en de algoritmische kant: rij-operaties, het berekenen van rangen en inversen. Voor het eerst ontmoet in het deel over de middelbare school, worden matrices nu gefundeerd in de theorie van Hoofdstukken 18, 19 en 20.

21.1 Matrices en lineaire afbeeldingen

Definitie 21.1

$\mathcal{M}_{n,p}(K)$ is de vectorruimte van $n \times p$ tabellen $A = (a_{ij})$ van scalairen ( $i$ : rij, $j$ : kolom), van dimensie $np$ (basis: de matrices $E_{ij}$ met één enkele $1$ ). Gegeven bases $\mathcal{B} = (e_1, \dots, e_p)$ van $E$ en $\mathcal{C}$ van $F$ ( $\dim F = n$ ), is de matrix van $u \in \mathcal{L}(E, F)$ de tabel waarvan de $j$ -de kolom de coördinaten van $u(e_j)$ in $\mathcal{C}$ opsomt:

\operatorname{Mat}_{\mathcal{B},\mathcal{C}}(u) = (a_{ij}), \qquad u(e_j) = \sum_{i=1}^{n} a_{ij}\, f_i .

De afbeelding $u \mapsto \operatorname{Mat}_{\mathcal{B},\mathcal{C}}(u)$ is een isomorfisme van $\mathcal{L}(E, F)$ naar $\mathcal{M}_{n,p}(K)$ (Propositie 20.2: een lineaire afbeelding is precies een keuze van beelden van de $e_j$ ).

Voorbeeld 21.2 (De afgeleide, als matrix)

Zij $D(P) = P'$ op $\R_3[X]$ . In de monomiaalbasis $(1, X, X^2, X^3)$ : $D(1) = 0$ , $D(X) = 1$ , $D(X^2) = 2X$ , $D(X^3) = 3X^2$ , dus

\operatorname{Mat}(D) = \begin{pmatrix} 0 & 1 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 3\\ 0 & 0 & 0 & 0 \end{pmatrix}.

In de gedeelde basis $\bigl(1,\ X,\ \frac{X^2}2,\ \frac{X^3}6\bigr)$ beeldt elke basisvector af op de vorige ( $D\bigl(\frac{X^k}{k!}\bigr) = \frac{X^{k-1}}{(k-1)!}$ ), en wordt de matrix de zuivere verschuiving: enen op de superdiagonaal, nullen elders. Twee lessen: de matrix hoort bij het paar (afbeelding, basis), niet bij de afbeelding alleen; en een goede basis maakt structuur in één oogopslag zichtbaar — de verschuivingsvorm toont onmiddellijk dat $D^4 = 0$ op $\R_3[X]$ , waarbij elke macht van de matrix haar diagonaal van enen een stap verder naar buiten duwt.

Definitie 21.3 (Product)

Voor $A \in \mathcal{M}_{n,p}$ en $B \in \mathcal{M}_{p,q}$ :

(AB)_{ik} = \sum_{j=1}^{p} a_{ij}\, b_{jk} \qquad (1 \leq i \leq n,\ 1 \leq k \leq q).

Dit is precies de matrix van de samenstelling: $\operatorname{Mat}(v \circ u) = \operatorname{Mat}(v)\, \operatorname{Mat}(u)$ (de bases sluiten in het midden op elkaar aan). Analoog, als $X$ de kolom van coördinaten van $x$ is, is de kolom van $u(x)$ gelijk aan $AX$ .

Bewijs van de samenstellingsformule.

v(u(e_k)) = v\Bigl(\sum_j b_{jk} f_j\Bigr) = \sum_j b_{jk}\, v(f_j) = \sum_j b_{jk} \sum_i a_{ij}\, g_i = \sum_i \Bigl(\sum_j a_{ij} b_{jk}\Bigr) g_i . \qedhere

∎

Propositie 21.4 (De algebra $\mathcal{M}_n(K)$ )

Vierkante matrices $\mathcal{M}_n(K)$ vormen een (niet-commutatieve voor $n \geq 2$ ) ring, met eenheidselement $I_n$ ; haar groep van eenheden is de algemene lineaire groep $GL_n(K)$ , die overeenkomt met de bijectieve endomorfismen. Voor $A, B \in \mathcal{M}_n(K)$ :

AB = I_n \implies A \in GL_n(K) \text{ en } B = A^{-1}

(eenzijdige inversen zijn tweezijdig, volgens Gevolg 20.9).

Bewijs. De ringaxioma’s dragen over vanuit $\mathcal{L}(E)$ via het isomorfisme van Definitie 21.1: het zet samenstelling om in product en som in som, dus associativiteit, distributiviteit en de rol van $I_n$ worden overgeërfd van de overeenkomstige feiten over afbeeldingen, zonder enige verificatie per element. Niet-commutativiteit: $E_{12}E_{21} = E_{11} \neq E_{22} = E_{21}E_{12}$ . Als $AB = I_n$ : het endomorfisme $a$ van $A$ voldoet aan $a \circ b = \mathrm{id}$ , dus $a$ is surjectief ( $x = a(b(x))$ toont een origineel van elke $x$ ), en dus bijectief in eindige dimensie (Gevolg 20.9); samenstellen van $a \circ b = \mathrm{id}$ met $a^{-1}$ aan de linkerkant geeft $b = a^{-1}$ , en dan geldt ook $b\circ a = \mathrm{id}$ : de eenzijdige inverse was al die tijd tweezijdig — een strikt eindigdimensionale gunst. ∎

Definitie 21.5 (Getransponeerde; spoor)

De getransponeerde van $A = (a_{ij}) \in \mathcal{M}_{n,p}$ is $A^{\mathsf T} = (a_{ji}) \in \mathcal{M}_{p,n}$ ; ze voldoet aan $(AB)^{\mathsf T} = B^{\mathsf T} A^{\mathsf T}$ en $(A^{\mathsf T})^{\mathsf T} = A$ . Het spoor van een vierkante matrix is $\operatorname{tr} A = \sum_i a_{ii}$ ; het is lineair, en

\operatorname{tr}(AB) = \operatorname{tr}(BA) \qquad (A \in \mathcal{M}_{n,p},\ B \in \mathcal{M}_{p,n}).

Bewijs van de identiteit van het spoor. $\operatorname{tr}(AB) = \sum_i \sum_j a_{ij} b_{ji}$ en $\operatorname{tr}(BA) = \sum_j \sum_i b_{ji} a_{ij}$ : dezelfde dubbele som. ∎

Voorbeeld 21.6 (Het spoor aan het werk)

De projectie uit Hoofdstuk 20 op $\operatorname{Vect}(1,1)$ langs $\operatorname{Vect}(0,1)$ , $p(x, y) = (x, x)$ , heeft matrix $A = \begin{pmatrix} 1 & 0\\ 1 & 0\end{pmatrix}$ in de canonieke basis: inderdaad $A^2 = A$ , en

\operatorname{tr} A = 1 = \operatorname{rk} A ,

wat Oefening 21.8 illustreert: voor idempotenten telt het spoor de dimensie van het beeld, in welke scheve basis de matrix ook geschreven wordt. Het invariantiemechanisme is de identiteit $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ :

\operatorname{tr}\bigl(P^{-1}(AP)\bigr) = \operatorname{tr}\bigl((AP)P^{-1}\bigr) = \operatorname{tr} A ,

dus alle matrices die gelijkvormig zijn met $A$ delen haar spoor — de eerste numerieke invariant van een endomorfisme, waarbij in Hoofdstuk 22 de determinant zich zal voegen (het paar $(s, p)$ uit het weekendprobleem hieronder).

Voorbeeld 21.7 (Symmetrisch plus antisymmetrisch)

Noem $A$ symmetrisch wanneer $A^{\mathsf T} = A$ , antisymmetrisch wanneer $A^{\mathsf T} = -A$ . Elke vierkante matrix splitst op unieke wijze als de ene plus de andere:

A = \underbrace{\frac{A + A^{\mathsf T}}{2}}_{\text{symmetrisch}} + \underbrace{\frac{A - A^{\mathsf T}}{2}}_{\text{antisymmetrisch}},

en een matrix die beide is, is nul ( $A = -A$ ): de twee verzamelingen zijn complementaire deelruimten van $\mathcal{M}_n(K)$ — het exacte analogon van de even/oneven splitsing van functies (Voorbeeld 18.11), waarbij transpositie de rol van $x \mapsto -x$ speelt. Dimensies: een symmetrische matrix is vrij op en boven de diagonaal, een antisymmetrische strikt erboven (nuldiagonaal):

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

en de balans in de telling is Grassmanns bevestiging van de directheid. Voor $n = 2$ : $\begin{pmatrix} 1 & 5\\ 1 & 2\end{pmatrix} = \begin{pmatrix} 1 & 3\\ 3 & 2\end{pmatrix} + \begin{pmatrix} 0 & 2\\ -2 & 0\end{pmatrix}$ . Symmetrische matrices keren terug als de tweede-afgeleidegegevens van Hoofdstuk 25 (het Monge-drietal $r, s, t$ ), en de symmetrisch-orthogonale worden geclassificeerd in Oefening 23.12.

21.2 Basisverandering

Definitie 21.8

Zij $\mathcal{B}, \mathcal{B}'$ bases van $E$ . De basisveranderingsmatrix $P = P_{\mathcal{B}\to\mathcal{B}'}$ heeft als kolommen de coördinaten van de nieuwe basisvectoren in de oude basis. Ze is inverteerbaar, $P^{-1} = P_{\mathcal{B}'\to\mathcal{B}}$ , en coördinaten transformeren volgens $X = PX'$ (oud $=$ $P\,\cdot$ nieuw).

Voorbeeld 21.9 (De basisveranderingsmatrix aflezen)

In $\R^2$ , van de canonieke $\mathcal B$ naar $\mathcal B' = \bigl((1,1), (1,-1)\bigr)$ :

P = P_{\mathcal B\to\mathcal B'} = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}

(nieuwe vectoren geschreven in oude coördinaten, kolom voor kolom). De vector van oude coördinaten $X = (3, 1)^{\mathsf T}$ heeft nieuwe coördinaten $X' = P^{-1}X = \frac12(3 + 1,\ 3 - 1)^{\mathsf T} = (2, 1)^{\mathsf T}$ : inderdaad $2(1,1) + 1(1,-1) = (3,1)$ . Let op de richting — de matrix $P$ is opgebouwd uit de nieuwe basis maar zet nieuwe naar oude coördinaten om ( $X = PX'$ ); van oud naar nieuw gaan kost de inverse. Na elke omzetting de controle $2(1,1) + (1,-1) = (3,1)$ opschrijven, betrapt de omgekeerde- $P$ -fout, die de meest voorkomende vergissing van het hoofdstuk is.

Stelling 21.10 (Basisverandering voor een afbeelding)

Zij $u \in \mathcal{L}(E)$ met matrix $A$ in $\mathcal{B}$ en $A'$ in $\mathcal{B}'$ , en $P = P_{\mathcal{B}\to\mathcal{B}'}$ . Dan

A' = P^{-1} A\, P .

Twee matrices die zo verband houden zijn gelijkvormig. (Voor $u \colon E \to F$ met twee paren bases is de formule $A' = Q^{-1} A P$ — equivalente matrices.)

Bewijs. Voor elke $x$ : $X = PX'$ en het beeld voldoet aan $Y = AX$ , $Y = PY'$ . Dus $PY' = APX'$ , d.w.z. $Y' = (P^{-1}AP)X'$ voor alle $X'$ : de matrix van $u$ in de nieuwe basis is $P^{-1}AP$ (neem voor $X'$ de canonieke kolommen). ∎

Voorbeeld 21.11 (Een goede basis maakt een afbeelding doorzichtig)

Zij $u(x, y) = (y, x)$ (verwisseling), met matrix $A = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ in de canonieke basis. In de basis $\mathcal B' = \bigl((1,1), (1,-1)\bigr)$ :

P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}, \qquad P^{-1} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}, \qquad P^{-1} A P = \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}.

Er was eigenlijk geen matrixproduct nodig: $u$ houdt $(1,1)$ vast en keert $(1,-1)$ om, dus in $\mathcal B'$ moet haar matrix $\operatorname{diag}(1, -1)$ zijn — de verwisseling is de spiegeling om de rechte $y = x$ . Voor een gegeven endomorfisme een basis vinden waarin zijn matrix diagonaal wordt, is het centrale probleem van het deel van Jaar 2 (reductietheorie); het weekendprobleem hieronder toont hoe ver veeltermidentiteiten alleen al reiken.

Voorbeeld 21.12 (Basisverandering, achterstevoren uitgevoerd)

De projectie op $F = \operatorname{Vect}(1,1)$ langs $G = \operatorname{Vect}(1,-1)$ heeft, in de aangepaste basis $\mathcal B' = \bigl((1,1),(1,-1)\bigr)$ , de doorzichtige matrix $A' = \operatorname{diag}(1, 0)$ . Om haar matrix in de canonieke basis te krijgen, passen we Stelling 21.10 achterstevoren toe, $A = P A' P^{-1}$ :

P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}, \quad P^{-1} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}, \quad A = P\begin{pmatrix} 1 & 0\\ 0 & 0\end{pmatrix}P^{-1} = \frac12\begin{pmatrix} 1 & 1\\ 1 & 1\end{pmatrix}.

Controle: $A^2 = A$ (idempotent), $\operatorname{tr} A = 1 = \operatorname{rk} A$ , en $A\binom{1}{1} = \binom11$ , $A\binom{1}{-1} = 0$ , zoals voorgeschreven. Deze omgekeerde richting — ontwerp de matrix in de goede basis, en conjugeer dan terug — is hoe rotatie-, spiegelings- en projectiematrices in de praktijk daadwerkelijk geproduceerd worden.

Stelling 21.13 (Rangnormaalvorm)

De rang van een matrix (de rang van haar kolommen, equivalent van de bijbehorende lineaire afbeelding) is de enige invariant van equivalentie: elke $A \in \mathcal{M}_{n,p}$ van rang $r$ is equivalent met

J_r = \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix},

en $\operatorname{rk}(A^{\mathsf T}) = \operatorname{rk}(A)$ : rijrang is gelijk aan kolomrang.

Bewijs. Zij $u \colon E \to F$ van rang $r$ . Kies een complement $S$ van $\ker u$ ( $\dim S = r$ , Stelling 20.7) met basis $(e_1, \dots, e_r)$ , aangevuld met een basis van $\ker u$ tot een basis van $E$ ; de beelden $f_i = u(e_i)$ , $i \leq r$ , vormen een basis van $\operatorname{im} u$ (de beperking is een isomorfisme), aangevuld tot een basis van $F$ . In deze bases is de matrix van $u$ precies $J_r$ . Dus $A = Q J_r P^{-1}$ voor inverteerbare $P, Q$ .

Transponeren: $A^{\mathsf T} = (P^{-1})^{\mathsf T} J_r^{\mathsf T} Q^{\mathsf T}$ met $J_r^{\mathsf T}$ van dezelfde vorm (rang $r$ ) en de buitenste factoren inverteerbaar (de getransponeerde van een inverteerbare is inverteerbaar, uit $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ toegepast op $AA^{-1} = I$ ): $\operatorname{rk} A^{\mathsf T} = r$ . ∎

21.3 Rij-operaties

Methode 21.14 (Gauss-eliminatie op matrices)

De drie elementaire rij-operaties — twee rijen verwisselen, een rij vermenigvuldigen met $\lambda \neq 0$ , een veelvoud van een rij bij een andere optellen — veranderen de rang niet (elk is linkervermenigvuldiging met een inverteerbare matrix). Algoritme: maak een pivot (meest linkse niet-nul element), veeg de kolom eronder schoon, ga naar de volgende rij en kolom; het aantal pivots van de resulterende trapvorm is de rang.

Berekening van de inverse: voer het algoritme uit op het blok $(A \mid I_n)$ tot het linkerblok $I_n$ wordt (mogelijk desda $A$ inverteerbaar is); het rechterblok is dan $A^{-1}$ — inderdaad, het product van de gebruikte elementaire matrices is gelijk aan $A^{-1}$ .

Voorbeeld 21.15

$A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ : herleid $(A \mid I_2)$ :

\begin{pmatrix} 1 & 2 & 1 & 0\\ 3 & 4 & 0 & 1 \end{pmatrix} \to \begin{pmatrix} 1 & 2 & 1 & 0\\ 0 & -2 & -3 & 1 \end{pmatrix} \to \begin{pmatrix} 1 & 0 & -2 & 1\\ 0 & 1 & \tfrac32 & -\tfrac12 \end{pmatrix},

(operaties: $L_2 \leftarrow L_2 - 3L_1$ ; daarna $L_1 \leftarrow L_1 + L_2$ , $L_2 \leftarrow -\frac12 L_2$ ). Dus $A^{-1} = \begin{pmatrix} -2 & 1 \\ \tfrac32 & -\tfrac12\end{pmatrix}$ . Controle: $AA^{-1} = I_2$ .

Voorbeeld 21.16 (Rang met een parameter, alleen met rijen)

Voor $m \in \R$ , de rang van $M_m = \begin{pmatrix} 1 & 1 & m\\ 1 & m & 1\\ m & 1 & 1\end{pmatrix}$ . Herleid: $L_2 \leftarrow L_2 - L_1$ en $L_3 \leftarrow L_3 - mL_1$ geven de rijen

(1,\ 1,\ m), \qquad (0,\ m - 1,\ 1 - m), \qquad (0,\ 1 - m,\ 1 - m^2).

Geval $m = 1$ : de laatste twee rijen verdwijnen — één pivot, $\operatorname{rk} M_1 = 1$ (alle drie de oorspronkelijke rijen waren gelijk). Geval $m \neq 1$ : schaal $L_2$ met $\frac1{m-1}$ en $L_3$ met $\frac1{1-m}$ om $(0, 1, -1)$ en $(0, 1, 1 + m)$ te krijgen, dan $L_3 \leftarrow L_3 - L_2 = (0, 0, m + 2)$ . Als $m = -2$ : twee pivots, rang $2$ ; anders drie pivots, rang $3$ . Samenvatting:

\operatorname{rk} M_m = \begin{cases} 1 & m = 1,\\ 2 & m = -2,\\ 3 & \text{anders}. \end{cases}

Dezelfde drempelwaarden zullen uit één determinantberekening in Hoofdstuk 22 rollen (de veelterm $-(m+2)(m-1)^2$ uit Oefening 22.7) — maar merk op wat eliminatie geeft en de determinant niet: de waarde van de rang in de gedegenereerde gevallen, niet enkel het feit dat hij daalde.

Voorbeeld 21.17 (Machten berekenen)

$A = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix} = I + N$ met $N = E_{12}$ , $N^2 = 0$ . Aangezien $I$ en $N$ commuteren, breekt het binomium van Newton (Propositie 7.20) af:

A^k = I + kN = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \qquad (k \in \N, \text{ en } k \in \Z \text{ met } A^{-1} = I - N).

Methode 21.18 ( $A^n$ berekenen: de drie routes)

Binomiumroute: als $A = \lambda I + N$ met $N$ nilpotent, breekt het binomium van Newton af (Voorbeeld 21.17, Oefening 21.5); het is van toepassing omdat $\lambda I$ met alles commuteert.
Veeltermroute: vind een veeltermidentiteit waaraan $A$ voldoet (in dimensie $2$ altijd $A^2 = sA - pI$ ) en herleid $X^n$ modulo deze; het weekendprobleem hieronder bouwt deze route volledig op.
Gelijkvormigheidsroute: vind een inverteerbare $P$ met $P^{-1}AP = D$ eenvoudig (diagonaal, of verschuiving), bereken $D^n$ , en maak ongedaan: $A^n = P D^n P^{-1}$ (Stelling 21.10, Voorbeeld 21.11); het systematisch zoeken naar zo’n $P$ is de reductietheorie van Jaar 2.

Welke route ook, controleer het resultaat op $n = 0, 1, 2$ : drie goedkope tests die bijna elke vergissing betrappen.

Opmerking 21.19 (Veelvoorkomende valkuilen: de prijs van niet-commutativiteit)

Elke identiteit van de scalaire algebra waarvan het bewijs factoren herordent, sterft in $\mathcal{M}_n(K)$ , $n \geq 2$ . Kwadraten: $(A + B)^2 = A^2 + AB + BA + B^2$ , en het middelste valt alleen samen tot $2AB$ als $AB = BA$ (Oefening 21.1). Machten van producten: $(AB)^k$ is $ABAB\cdots$ , niet $A^kB^k$ . Nuldelers: $E_{12}E_{12} = 0$ met $E_{12} \neq 0$ ; bijgevolg geen schrapping: $AB = AC$ impliceert $B = C$ enkel wanneer $A$ inverteerbaar is (vermenigvuldig met $A^{-1}$ — aan de juiste kant). Sporen: $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ altijd, maar $\operatorname{tr}(AB) \neq \operatorname{tr}A\operatorname{tr}B$ in het algemeen (neem $A = B = I_2$ : $2 \neq 4$ ), en $\operatorname{tr}(ABC) = \operatorname{tr}(BCA)$ (cyclisch) terwijl $\operatorname{tr}(ACB)$ kan verschillen. Getransponeerden keren om: $(AB)^{\mathsf T} = B^{\mathsf T}A^{\mathsf T}$ — de omkering vergeten is de meest voorkomende fout in orthogonaliteitsberekeningen (Hoofdstuk 23). Bij twijfel, test elke beweerde identiteit op $E_{12}$ en $E_{21}$ : het kleinste niet-commuterende paar weerlegt de meeste valse formules in één regel.

Opmerking 21.20 (Waar het woordenboek heen gaat)

Het matrixwoordenboek wordt op elke overige pagina van dit deel gebruikt: Hoofdstuk 22 kent aan elke vierkante matrix één enkel getal toe dat de inverteerbaarheid bepaalt, en lost $AX = B$ systematisch op; Hoofdstuk 23 zondert de matrices af die lengten behouden (orthogonale matrices); en in Hoofdstuk 25 is het tweede-ordegedrag van een functie van twee variabelen een symmetrische $2 \times 2$ matrix. Het spoor, hierboven bijna terloops ingevoerd, wordt een krachtige invariant: Oefeningen 21.6 en 21.8 geven een eerste voorproefje, en het deel van Jaar 2 bouwt er de eigenwaardetheorie op. Het weekendprobleem ontwikkelt het andere werkpaard: veeltermidentiteiten waaraan een matrix voldoet, die het berekenen van $A^n$ omzetten in een lineaire recurrentie met twee termen.

Opmerking 21.21 (Perspectieven binnen Boek 3)

Drie matrixfamilies die hier zijn ingevoerd hebben afspraken verderop in dit deel. Symmetrische matrices (Voorbeeld 21.7) dragen de tweede-ordegegevens van functies van twee variabelen: de Monge-test van Hoofdstuk 25 is een uitspraak over het tekengedrag van een symmetrische $2\times2$ matrix, en haar determinant $rt - s^2$ wordt berekend door de machinerie van Hoofdstuk 22. Orthogonale matrices ( $A^{\mathsf T}A = I$ ) zijn de isometrieën van Hoofdstuk 23, waar de getransponeerde eindelijk haar meetkundige betekenis verwerft: ze is de algebraïsche schaduw van het inwendig product. Inverteerbare matrices ondergaan hun praktische test in Hoofdstuk 22 — één getal, $\det A \neq 0$ — wat de zoektocht afsluit die dit hoofdstuk met rijherleiding begon. Spoor en determinant reizen dan als het invariante paar $(s, p)$ van het weekendprobleem, helemaal tot aan de eigenwaardetheorie van Jaar 2.

21.4 Oefeningen

Oefening 21.1 ★

Zij $A = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}$ en $B = \begin{pmatrix} 0 & 1 \\ 1 & 0\end{pmatrix}$ . Bereken $AB$ , $BA$ , $A^2 - B^2$ en $(A+B)(A-B)$ ; leg uit waarom de laatste twee verschillen.

Oplossing

Oplossing van Oefening 21.1.

AB = \begin{pmatrix} 2 & 1\\ 1 & 0\end{pmatrix}, \quad BA = \begin{pmatrix} 0 & 1\\ 1 & 2\end{pmatrix}, \quad A^2 - B^2 = \begin{pmatrix} 1 & 4\\ 0 & 1\end{pmatrix} - I = \begin{pmatrix} 0 & 4\\ 0 & 0\end{pmatrix},

(A+B)(A-B) = A^2 - AB + BA - B^2 = \begin{pmatrix} 0 & 4\\ 0 & 0\end{pmatrix} + \begin{pmatrix} -2 & 0\\ 0 & 2 \end{pmatrix} = \begin{pmatrix} -2 & 4\\ 0 & 2\end{pmatrix}.

Ze verschillen met $BA - AB \neq 0$ : de identiteit $(a+b)(a-b) = a^2 - b^2$ vereist commutativiteit, die hier faalt.

Oefening 21.2 ★

Bereken de rang van

M = \begin{pmatrix} 1 & 2 & 3\\ 2 & 4 & 6\\ 1 & 1 & 1 \end{pmatrix}, \qquad N = \begin{pmatrix} 1 & 1 & 0 & 2\\ 0 & 1 & 1 & 1\\ 1 & 2 & 1 & 3 \end{pmatrix}.

Oplossing

Oplossing van Oefening 21.2.

$M$ : $L_2 \leftarrow L_2 - 2L_1$ maakt de tweede rij nul; $L_3 \leftarrow L_3 - L_1$ geeft $(0, -1, -2)$ . Twee pivots: $\operatorname{rk} M = 2$ .

$N$ : $L_3 \leftarrow L_3 - L_1$ geeft $(0,1,1,1) = L_2$ ; dan $L_3 \leftarrow L_3 - L_2 = 0$ . Twee pivots: $\operatorname{rk} N = 2$ .

Oefening 21.3 ★

Inverteer, door rijherleiding, $A = \begin{pmatrix} 1 & 0 & 1\\ 2 & 1 & 1\\ 1 & 1 & 1 \end{pmatrix}$ , en controleer op één product.

Oplossing

Oplossing van Oefening 21.3.

$(A \mid I_3)$ herleiden: $L_2 \leftarrow L_2 - 2L_1$ , $L_3 \leftarrow L_3 - L_1$ :

\begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 1 & -1 & -2 & 1 & 0\\ 0 & 1 & 0 & -1 & 0 & 1 \end{pmatrix} \xrightarrow{L_3 \leftarrow L_3 - L_2} \begin{pmatrix} 1 & 0 & 1 & 1 & 0 & 0\\ 0 & 1 & -1 & -2 & 1 & 0\\ 0 & 0 & 1 & 1 & -1 & 1 \end{pmatrix},

dan $L_1 \leftarrow L_1 - L_3$ , $L_2 \leftarrow L_2 + L_3$ :

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

Controle: eerste rij van $A$ maal eerste kolom van $A^{-1}$ : $1 \cdot 0 + 0\cdot(-1) + 1\cdot 1 = 1$ ; maal tweede kolom: $1 - 0 - 1 = 0$ ; maal derde: $-1 + 0 + 1 = 0$ .

Oefening 21.4 ★

Schrijf de matrix, in de canonieke basis van $\R_2[X]$ , van het endomorfisme $u(P) = P(X + 1)$ . Leg uit, zonder berekening, waarom het inverteerbaar is, en geef de matrix van $u^{-1}$ .

Oplossing

Oplossing van Oefening 21.4.

$u(1) = 1$ , $u(X) = X + 1$ , $u(X^2) = X^2 + 2X + 1$ : kolommen van coördinaten in $(1, X, X^2)$ geven

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

$u$ is inverteerbaar omdat het de voor de hand liggende inverse $P \mapsto P(X - 1)$ heeft (samenstelling van substituties). Haar matrix wordt op dezelfde manier verkregen uit $u^{-1}(X^k) = (X-1)^k$ :

M^{-1} = \begin{pmatrix} 1 & -1 & 1\\ 0 & 1 & -2\\ 0 & 0 & 1 \end{pmatrix}.

Oefening 21.5 ★★

Zij $A = \begin{pmatrix} 2 & 1 \\ 0 & 2\end{pmatrix}$ . Schrijf $A = 2I + N$ , bereken $N^2$ , en leid $A^k$ af voor alle $k \in \N$ met het binomium van Newton.

Oplossing

Oplossing van Oefening 21.5.

$N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ , $N^2 = 0$ . Aangezien $2I$ en $N$ commuteren, breekt de binomiale ontwikkeling na twee termen af:

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N = \begin{pmatrix} 2^k & k\,2^{k-1}\\ 0 & 2^k\end{pmatrix}.

(Controleer $k = 2$ : $A^2 = \begin{pmatrix}4 & 4\\ 0 & 4\end{pmatrix}$ , correct via direct product.)

Oefening 21.6 ★★

Bewijs dat er geen matrices $A, B \in \mathcal{M}_n(K)$ bestaan (met $K = \R$ of $\C$ ) zodat $AB - BA = I_n$ . (Neem sporen.)

Oplossing

Oplossing van Oefening 21.6.

Sporen: $\operatorname{tr}(AB - BA) = \operatorname{tr}(AB) - \operatorname{tr}(BA) = 0$ (Definitie 21.5), terwijl $\operatorname{tr}(I_n) = n \neq 0$ in $\R$ of $\C$ . Geen oplossing. (Op oneindigdimensionale ruimten is de identiteit realiseerbaar — afleiden en vermenigvuldigen met $x$ voldoen eraan — juist omdat daar geen spoor bestaat.)

Oefening 21.7 ★★

Een matrix $A$ is nilpotent wanneer $A^m = 0$ voor een zekere $m$ . Bewijs dat $I - A$ dan inverteerbaar is, met

(I - A)^{-1} = I + A + A^2 + \dots + A^{m-1} .

Toepassing: inverteer $\begin{pmatrix} 1 & 2 & 3\\ 0 & 1 & 2\\ 0 & 0 & 1\end{pmatrix}$ .

Oplossing

Oplossing van Oefening 21.7.

Telescoperend product, alle machten van $A$ commuteren:

(I - A)(I + A + \dots + A^{m-1}) = I - A^m = I ,

en Propositie 21.4 waardeert de eenzijdige inverse op. Voor de toepassing: de gegeven matrix is $I + N$ met

N = \begin{pmatrix} 0 & 2 & 3\\ 0 & 0 & 2\\ 0&0&0 \end{pmatrix}, \quad N^2 = \begin{pmatrix} 0&0&4\\ 0&0&0\\ 0&0&0\end{pmatrix}, \quad N^3 = 0 ,

dus, door $A$ te vervangen door $-N$ in de formule:

(I + N)^{-1} = I - N + N^2 = \begin{pmatrix} 1 & -2 & 1\\ 0 & 1 & -2\\ 0 & 0 & 1 \end{pmatrix}.

Oefening 21.8 ★★

Zij $A \in \mathcal{M}_n(\R)$ met $A^2 = A$ (idempotent). Bewijs dat $\operatorname{tr} A = \operatorname{rk} A$ . (Interpreteer $A$ als een projectie en kies een aangepaste basis; Stelling 21.10 zegt dat het spoor basisonafhankelijk is aangezien $\operatorname{tr}(P^{-1}MP) = \operatorname{tr} M$ .)

Oplossing

Oplossing van Oefening 21.8.

$A^2 = A$ : het endomorfisme $a$ is een projectie (Stelling 20.15), $E = \operatorname{im} a \oplus \ker a$ met $\dim\operatorname{im} a = r = \operatorname{rk} A$ . In een basis aangepast aan deze ontbinding ( $r$ vectoren van het beeld, dan een basis van de kern), is de matrix van $a$ gelijk aan $\begin{pmatrix} I_r & 0\\ 0 & 0\end{pmatrix}$ , met spoor $r$ . Het spoor is invariant onder basisverandering: $\operatorname{tr}(P^{-1}MP) = \operatorname{tr}(MPP^{-1}) = \operatorname{tr} M$ volgens de cyclische identiteit. Dus $\operatorname{tr} A = r = \operatorname{rk} A$ .

Oefening 21.9 ★★★

Zij $J \in \mathcal{M}_n(\R)$ de matrix met overal enen. Bereken $J^2$ , en leid, voor $a, b \in \R$ , de voorwaarde voor inverteerbaarheid van $M = aI + bJ$ af samen met $M^{-1}$ (zoek een inverse van dezelfde vorm $\alpha I + \beta J$ ).

Oplossing

Oplossing van Oefening 21.9.

$J^2 = nJ$ (elk element van $J^2$ telt $n$ enen op). Zoek $M^{-1} = \alpha I + \beta J$ :

(aI + bJ)(\alpha I + \beta J) = a\alpha\, I + (a\beta + b\alpha + nb\beta)\, J .

Dit is gelijk aan $I$ desda $a\alpha = 1$ en $a\beta + b\alpha + nb\beta = 0$ , d.w.z. $\alpha = \frac1a$ en $\beta(a + nb) = -\frac ba$ . Als $a \neq 0$ en $a + nb \neq 0$ :

M^{-1} = \frac 1a I - \frac{b}{a(a + nb)}\, J .

Omgekeerd, als $a = 0$ : $M = bJ$ heeft rang $\leq 1 < n$ (voor $n \geq 2$ ): niet inverteerbaar ( $n = 1$ is het scalaire geval). Als $a + nb = 0$ : de vector $v = (1, \dots, 1)^{\mathsf T}$ voldoet aan $Mv = (a + nb)v = 0$ met $v \neq 0$ : niet inverteerbaar. Dus $M \in GL_n \iff a \neq 0$ en $a + nb \neq 0$ .

Oefening 21.10 ★★★

(Rangongelijkheden) Voor $A, B \in \mathcal{M}_n(K)$ , bewijs

\operatorname{rk}(A + B) \leq \operatorname{rk} A + \operatorname{rk} B, \qquad \operatorname{rk}(AB) \geq \operatorname{rk} A + \operatorname{rk} B - n .

(Voor de tweede — de ongelijkheid van Sylvester — pas rang–nulliteit toe op de beperking van de afbeelding van $A$ tot $\operatorname{im} B$ .)

Oplossing

Oplossing van Oefening 21.10.

Som: $\operatorname{im}(A + B) \subseteq \operatorname{im} A + \operatorname{im} B$ (elke $(A+B)x = Ax + Bx$ ), en Grassmann begrenst de dimensie van een som door de som van de dimensies.

Sylvester: zij $a$ de afbeelding van $A$ beperkt tot $V = \operatorname{im} B$ (dimensie $\operatorname{rk} B$ ). Haar beeld is $\operatorname{im}(AB)$ ( $a(Bx) = ABx$ ), en rang–nulliteit in $V$ :

\operatorname{rk} B = \dim\ker(a_{|V}) + \operatorname{rk}(AB) .

Nu $\ker(a_{|V}) \subseteq \ker A$ , van dimensie $n - \operatorname{rk} A$ : dus

\operatorname{rk}(AB) \geq \operatorname{rk} B - (n - \operatorname{rk} A) = \operatorname{rk} A + \operatorname{rk} B - n . \qedhere

Oefening 21.11 ★★

Zij $D = \operatorname{diag}(d_1, \dots, d_n)$ met de $d_i$ paarsgewijs verschillend.

Bewijs dat een matrix $A$ met $D$ commuteert desda $A$ diagonaal is. (Vergelijk de $(i,j)$ -elementen van $AD$ en $DA$ .)
Leid het centrum van $\mathcal{M}_n(K)$ af: de matrices die met elke matrix commuteren zijn precies de scalaire matrices $\lambda I_n$ . (Test tegen $D$ , dan tegen de matrices $E_{ij}$ .)

Oplossing

Oplossing van Oefening 21.11.

Per element, $(AD)_{ij} = a_{ij}\,d_j$ en $(DA)_{ij} = d_i\,a_{ij}$ . Dus $AD = DA$ desda $a_{ij}(d_j - d_i) = 0$ voor alle $i, j$ ; wanneer $i \neq j$ is de factor $d_j - d_i$ niet-nul, wat $a_{ij} = 0$ afdwingt: $A$ is diagonaal. Omgekeerd commuteren diagonaalmatrices met elkaar.
Als $A$ met elke matrix commuteert, commuteert hij met $\operatorname{diag}(1, 2, \dots, n)$ , dus $A = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ volgens (1). Dan $A E_{ij} = \lambda_i E_{ij}$ (alleen rij $i$ van $E_{ij}$ overleeft) terwijl $E_{ij} A = \lambda_j E_{ij}$ : commuteren met $E_{ij}$ dwingt $\lambda_i = \lambda_j$ af. Dus $A = \lambda I_n$ ; en scalaire matrices commuteren wel met alles. Het centrum van $\mathcal{M}_n(K)$ is $K\,I_n$ .

Oefening 21.12 ★★★

(Rang-één matrices) Zij $A \in \mathcal{M}_n(K)$ , $A \neq 0$ .

Bewijs dat $\operatorname{rk} A = 1$ desda $A = CL$ voor een niet-nul kolom $C \in \mathcal{M}_{n,1}$ en een niet-nul rij $L \in \mathcal{M}_{1,n}$ .
Voor zo’n $A$ , bewijs $A^2 = (\operatorname{tr} A)\,A$ ; leid af dat een rang-één matrix nilpotent is desda haar spoor nul is.
Als $\operatorname{tr} A \neq -1$ , bewijs dat $I_n + A$ is inverteerbaar met

$(I_n + A)^{-1} = I_n - \frac{1}{1 + \operatorname{tr} A}\,A ,$

en dat $I_n + A$ niet inverteerbaar is wanneer $\operatorname{tr} A = -1$ . (Vind een vector die door $I_n + A$ op nul wordt afgebeeld.)

Oplossing

Oplossing van Oefening 21.12.

Als $\operatorname{rk} A = 1$ : het beeld van $A$ is een rechte $\operatorname{Vect}(C)$ , $C \neq 0$ , dus de $j$ -de kolom van $A$ is $\ell_j\,C$ voor scalairen $\ell_j$ (niet allemaal nul), d.w.z. $A = C L$ met $L = (\ell_1, \dots, \ell_n) \neq 0$ . Omgekeerd, als $A = CL \neq 0$ , zijn alle kolommen veelvouden van $C$ : rang $1$ .
$A^2 = C\,(L C)\,L$ , en $LC$ is de scalair $\sum_i \ell_i c_i = \operatorname{tr}(CL) = \operatorname{tr} A$ . Dus $A^2 = (\operatorname{tr} A)\,A$ , en dus per inductie $A^m = (\operatorname{tr} A)^{m-1} A$ . Als $\operatorname{tr} A \neq 0$ , verdwijnt geen enkele macht; als $\operatorname{tr} A = 0$ , dan $A^2 = 0$ : een rang-één matrix is nilpotent desda haar spoor nul is.
Met $t = \operatorname{tr} A \neq -1$ :

$(I_n + A)\Bigl(I_n - \frac{A}{1 + t}\Bigr) = I_n + A - \frac{A + A^2}{1 + t} = I_n + A - \frac{(1 + t)A}{1 + t} = I_n ,$

met behulp van $A^2 = tA$ . Als $t = -1$ : $(I_n + A)A = A + A^2 = A - A = 0$ met $A \neq 0$ , dus $I_n + A$ beeldt elke (niet-nul) kolom van $A$ op nul af: niet injectief, niet inverteerbaar.

21.5 Probleem: machten van een matrix via veeltermdeling

Probleem 21.1

$A^{100}$ element voor element berekenen is hopeloos; het berekenen via een veeltermidentiteit waaraan $A$ voldoet is drie regels. Dit probleem bouwt de methode van nul op: euclidische deling van $X^n$ , de identiteit $A^2 - sA + pI = 0$ waaraan elke $2 \times 2$ matrix voldoet (de stelling van Cayley–Hamilton in dimensie $2$ ), en het woordenboek tussen matrixmachten en lineaire recurrenties — met de Fibonacci-getallen als doorlopend voorbeeld.

Deel I — De restrekening. Leg $s, p \in K$ vast en $D = X^2 - sX + p$ .

Verantwoord dat er voor elke $n \in \N$ unieke $Q_n \in K[X]$ en $(a_n, b_n) \in K^2$ bestaan met

$X^n = Q_n\,D + a_n X + b_n ,$

en bereken $(a_0, b_0)$ en $(a_1, b_1)$ .
Vermenigvuldig met $X$ en deel opnieuw, en stel de recurrenties

$a_{n+1} = s\,a_n + b_n, \qquad b_{n+1} = -p\,a_n ,$

op, en leid $a_{n+2} = s\,a_{n+1} - p\,a_n$ af: de coëfficiëntenrij gehoorzaamt aan de lineaire recurrentie die bij $D$ hoort.
Veronderstel dat $D$ twee verschillende wortels $\lambda \neq \mu$ heeft. Bewijs, door de delingsidentiteit te evalueren,

$a_n = \frac{\lambda^n - \mu^n}{\lambda - \mu}, \qquad b_n = \frac{\lambda\mu^n - \mu\lambda^n}{\lambda - \mu} .$
Veronderstel $D = (X - \lambda)^2$ . Bewijs, met behulp van de afgeleide van de delingsidentiteit, $a_n = n\lambda^{n-1}$ en $b_n = (1 - n)\lambda^{n}$ .
Toon aan dat het substitueren van een vaste matrix $M \in \mathcal{M}_k(K)$ in veeltermen sommen en producten respecteert: $(PQ)(M) = P(M)\,Q(M)$ . Leid af dat als $D(M) = 0$ , dan

$M^n = a_n\,M + b_n\,I \qquad (n \in \N).$

Deel II — Dimensie 2: spoor, determinantgetal, Cayley–Hamilton. Voor $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ stel $s = a + d = \operatorname{tr} A$ en $p = ad - bc$ (het getal dat Hoofdstuk 22 de determinant zal noemen).

Verifieer door directe berekening de Cayley–Hamilton-identiteit in dimensie $2$ :

$A^2 - s\,A + p\,I_2 = 0 .$
Bewijs door directe uitwerking dat $p$ multiplicatief is: met voor de hand liggende notatie, $p(AB) = p(A)\,p(B)$ . Toon vervolgens aan: $A$ is inverteerbaar desda $p \neq 0$ , in welk geval

$A^{-1} = \frac1p\,\bigl(s\,I_2 - A\bigr).$
Zij $A = \begin{pmatrix} 1 & 1\\ 0 & 2\end{pmatrix}$ . Bereken $s$ , $p$ , de wortels van $D$ , en leid een gesloten formule voor $A^n$ af; controleer ze tegen een directe berekening van $A^2$ .
Zij $A = \begin{pmatrix} 3 & 1\\ -1 & 1\end{pmatrix}$ . Toon aan dat $D$ een dubbele wortel heeft en bereken $A^n$ ; controleer bij $n = 2$ .
Zij $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ en definieer de Fibonacci-getallen door $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ . Bewijs

$F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\end{pmatrix} \quad (n \geq 1),$

leid de formule van Binet $F_n = \dfrac{\varphi^n - \psi^n}{\sqrt5}$ af waarbij $\varphi = \frac{1 + \sqrt5}2$ , $\psi = \frac{1 - \sqrt5}2$ , en, met behulp van vraag 7, de identiteit van Cassini $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ .

Deel III — Lineaire recurrenties, structureel. Leg $s, p \in K$ vast met $p \neq 0$ , en zij $E_D$ de verzameling van rijen met $u_{n+2} = s\,u_{n+1} - p\,u_n$ voor alle $n$ .

Toon aan dat $E_D$ een vectorruimte van dimensie $2$ is (pas Oefening 19.10 aan).
Toon aan dat de rij $(a_n)$ uit Deel I het element van $E_D$ is met beginwaarden $0, 1$ , en dat elke $u \in E_D$ voldoet aan

$u_n = u_1\,a_n + u_0\,b_n \qquad (n \in \N),$

met $(b_n)$ zoals in Deel I: de delingsresten lossen alle recurrenties tegelijk op.
Als $\lambda \neq \mu$ de wortels van $D$ zijn, toon aan dat $\bigl((\lambda^n), (\mu^n)\bigr)$ een basis van $E_D$ is; als $D = (X-\lambda)^2$ met $\lambda \neq 0$ , toon aan dat $\bigl((\lambda^n), (n\lambda^n)\bigr)$ er een is.
Los volledig op: $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ ; controleer het antwoord op $u_2$ en $u_3$ .
Zij $C = \begin{pmatrix} 0 & 1\\ -p & s\end{pmatrix}$ (de begeleidende matrix van $D$ ). Toon aan dat

$\begin{pmatrix} u_{n}\\ u_{n+1}\end{pmatrix} = C^n \begin{pmatrix} u_0\\ u_1\end{pmatrix} \quad (u \in E_D),$

en dat $\operatorname{tr} C = s$ en $p(C) = p$ : de recurrentie en de matrix dragen dezelfde veelterm $D$ .

Deel IV — Graad drie. Zij $D_3 = X^3 - \alpha X^2 - \beta X - \gamma$ en

C_3 = \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ \gamma & \beta & \alpha \end{pmatrix}.

Toon aan dat $D_3(C_3) = 0$ . (Bereken de beelden van de canonieke basisvectoren onder machten van $C_3$ : de afbeelding van $C_3$ stuurt $e_1 \mapsto \dots \mapsto$ een combinatie die door de laatste rij wordt afgedwongen.)
Toon aan dat als $D_3$ drie verschillende wortels $\lambda_1, \lambda_2, \lambda_3$ heeft, de rest $R_n$ van $X^n$ gedeeld door $D_3$ de Lagrange-interpolant is van de waarden $\lambda_i^n$ in de knopen $\lambda_i$ (Stelling 8.23); leid af dat elk element van $C_3^{\,n}$ een vaste lineaire combinatie is van $\lambda_1^n, \lambda_2^n, \lambda_3^n$ .
Los op: $u_{n+3} = 2u_{n+2} + u_{n+1} - 2u_n$ met $u_0 = 0$ , $u_1 = 1$ , $u_2 = 1$ . (Ontbind $D_3 = (X - 1)(X + 1)(X - 2)$ .) Controleer op $u_3$ .
Bereken de rest van $X^n$ modulo $(X - \lambda)^3$ (Taylorontwikkeling van $X^n$ in $\lambda$ ), en leid een formule voor $(\lambda I + N)^n$ af wanneer $N^3 = 0$ en $N$ commuteert met alles in zicht; controleer ze tegen het binomium van Newton.
Toon aan dat voor $D_3$ met verschillende wortels de algemene oplossing van de recurrentie van orde $3$ gelijk is aan $u_n = c_1 \lambda_1^n + c_2\lambda_2^n + c_3\lambda_3^n$ : bewijs dat de drie meetkundige rijen een basis van de oplossingsruimte vormen. (Voor de vrijheid, evalueer een nulcombinatie in $n = 0, 1, 2$ en herken een interpolatiestelsel in de verschillende knopen $\lambda_i$ .)

Deel V — Fibonacci-deeltallen, en synthese.

Bewijs $F_1 + F_2 + \dots + F_n = F_{n+2} - 1$ .
Leid uit $F^{m+n} = F^m F^n$ de optelformule

$F_{m+n} = F_{m+1}F_n + F_m F_{n-1},$

af, en leid $F_{2n} = F_n(F_{n+1} + F_{n-1})$ af.
Bewijs dat $F_n$ het dichtstbijzijnde gehele getal bij $\varphi^n/\sqrt5$ is voor elke $n \geq 0$ .
Zij $t_n = \operatorname{tr}(F^n) = F_{n+1} + F_{n-1}$ (de Lucas-getallen $L_n$ ). Toon aan $t_{n+2} = t_{n+1} + t_n$ , $t_1 = 1$ , $t_2 = 3$ , dat $L_n = \varphi^n + \psi^n$ , en herwin $F_{2n} = F_n L_n$ .
Synthese, in vier zinnen: waarom de machten van een $2 \times 2$ matrix in het vlak $\operatorname{Vect}(I, A)$ van $\mathcal{M}_2(K)$ leven (welk dimensieargument een kwadratische identiteit garandeert, en welke expliciete identiteit Deel II opleverde); hoe euclidische deling machtsverheffing omzet in een recurrentie met twee termen; welke uitspraak van dit probleem het geval $n = 2$ is van een stelling die in alle dimensies geldt (noem ze, en zeg waar ze in deze reeks bewezen wordt); en wat de constructie van de begeleidende matrix aan het plaatje toevoegt.

Oplossing

Oplossing van Probleem 21.1.

1. Euclidische deling van $X^n$ door de monische $D$ van graad $2$ (Stelling 8.3): quotiënt en rest bestaan en zijn uniek, en de rest heeft graad $\leq 1$ : $X^n = Q_n D + a_n X + b_n$ . Voor $n = 0$ : $Q_0 = 0$ , $(a_0, b_0) = (0, 1)$ ; voor $n = 1$ : $(a_1, b_1) = (1, 0)$ .

2. Vermenigvuldig met $X$ en herleid $X^2 = D + sX - p$ :

X^{n+1} = X Q_n D + a_n X^2 + b_n X = (X Q_n + a_n)\,D + (s\,a_n + b_n)\,X - p\,a_n .

De laatste uitdrukking heeft de vorm van een rest (graad $\leq 1$ ), dus volgens de uniciteit $a_{n+1} = s a_n + b_n$ en $b_{n+1} = -p a_n$ . Substitutie van $b_{n+1} = -pa_n$ in $a_{n+2} = s a_{n+1} + b_{n+1}$ geeft $a_{n+2} = s\,a_{n+1} - p\,a_n$ .

3. Evalueer $X^n = Q_n D + a_n X + b_n$ in de wortels: $\lambda^n = a_n\lambda + b_n$ en $\mu^n = a_n\mu + b_n$ . Aftrekken en delen door $\lambda - \mu \neq 0$ :

a_n = \frac{\lambda^n - \mu^n}{\lambda - \mu}, \qquad b_n = \lambda^n - a_n\lambda = \frac{\lambda\mu^n - \mu\lambda^n}{\lambda - \mu} .

4. In de dubbele wortel: $\lambda^n = a_n\lambda + b_n$ . De identiteit afleiden, $nX^{n-1} = Q_n'\,(X - \lambda)^2 + 2Q_n\,(X - \lambda) + a_n$ , en evalueren in $\lambda$ : $a_n = n\lambda^{n-1}$ ; dan $b_n = \lambda^n - n\lambda^{n} = (1 - n)\lambda^{n}$ .

5. Voor $P = \sum_i p_i X^i$ en $Q = \sum_j q_j X^j$ ,

P(M)\,Q(M) = \sum_{i,j} p_i q_j M^{i+j} = (PQ)(M),

omdat machten van de enkele matrix $M$ met elkaar commuteren (sommen zijn duidelijk door lineariteit). Als $D(M) = 0$ , geeft substitutie van $M$ in $X^n = Q_n D + a_n X + b_n$ dat $M^n = Q_n(M)\,D(M) + a_n M + b_n I = a_n M + b_n I$ .

6. Directe producten:

A^2 = \begin{pmatrix} a^2 + bc & b(a + d)\\ c(a + d) & d^2 + bc \end{pmatrix}, \qquad s A = \begin{pmatrix} a(a+d) & b(a+d)\\ c(a+d) & d(a+d) \end{pmatrix},

dus $A^2 - sA$ heeft nul niet-diagonale elementen en diagonale elementen $a^2 + bc - a^2 - ad = bc - ad = -p$ : $A^2 - sA + pI_2 = 0$ .

7. Met $A' = \begin{pmatrix} a' & b'\\ c' & d'\end{pmatrix}$ , uitwerken van $p(AA') = (aa' + bc')(cb' + dd') - (ab' + bd')(ca' + dc')$ : de termen $aa'cb'$ en $ab'ca'$ heffen elkaar op, de termen $bc'dd'$ en $bd'dc'$ heffen elkaar op, en wat overblijft is

aa'dd' - bca'd' + bcb'c' - adb'c' = (ad - bc)(a'd' - b'c') = p(A)\,p(A').

Als $p \neq 0$ , geeft Cayley–Hamilton $A\,\bigl(\tfrac1p(sI_2 - A)\bigr) = \tfrac1p(sA - A^2) = I_2$ , waaruit de inverse volgt (en Propositie 21.4 maakt hem tweezijdig). Als $p = 0$ en $A$ inverteerbaar zou zijn, geeft multiplicativiteit $1 = p(I_2) = p(A)\,p(A^{-1}) = 0$ : onmogelijk. Dus $A \in GL_2 \iff p \neq 0$ .

8. $s = 3$ , $p = 2$ , $D = X^2 - 3X + 2 = (X - 1)(X - 2)$ : $\lambda = 2$ , $\mu = 1$ , dus $a_n = 2^n - 1$ en $b_n = 2 - 2^n$ (vraag 3). Dus

A^n = (2^n - 1)A + (2 - 2^n)I = \begin{pmatrix} 1 & 2^n - 1\\ 0 & 2^n \end{pmatrix}.

Controle: $A^2 = \begin{pmatrix} 1 & 3\\ 0 & 4\end{pmatrix}$ zowel via de formule als door direct te kwadrateren.

9. $s = 4$ , $p = 3\cdot1 - 1\cdot(-1) = 4$ : $D = X^2 - 4X + 4 = (X - 2)^2$ , dubbele wortel $\lambda = 2$ . Vraag 4: $a_n = n\,2^{n-1}$ , $b_n = (1 - n)2^n$ , dus

A^n = n\,2^{n-1}A + (1 - n)2^n I = 2^{n-1}\begin{pmatrix} n + 2 & n\\ -n & 2 - n \end{pmatrix}.

Bij $n = 2$ : $2\begin{pmatrix} 4 & 2\\ -2 & 0\end{pmatrix} = \begin{pmatrix} 8 & 4\\ -4 & 0 \end{pmatrix}$ , wat $A^2$ direct berekend is.

10. Inductie: $F^1 = \begin{pmatrix} F_2 & F_1\\ F_1 & F_0\end{pmatrix}$ , en

F^{n+1} = F^n F = \begin{pmatrix} F_{n+1} + F_n & F_{n+1}\\ F_n + F_{n-1} & F_n \end{pmatrix} = \begin{pmatrix} F_{n+2} & F_{n+1}\\ F_{n+1} & F_n \end{pmatrix}.

Hier $s = 1$ , $p = -1$ , $D = X^2 - X - 1$ met wortels $\varphi, \psi$ ( $\varphi - \psi = \sqrt5$ , $\varphi\psi = -1$ ). De rij $(F_n)$ heeft $F_0 = 0 = a_0$ , $F_1 = 1 = a_1$ en gehoorzaamt aan dezelfde recurrentie als $(a_n)$ : $F_n = a_n = (\varphi^n - \psi^n)/\sqrt5$ , de formule van Binet. Cassini: door de multiplicativiteit van vraag 7 toe te passen op $F^n$ ,

F_{n+1}F_{n-1} - F_n^2 = p(F^n) = p(F)^n = (-1)^n .

11. De voorwaarde is lineair en bevat de nulrij: een deelruimte. Per inductie bepalen $u_0, u_1$ de rij $u$ lineair, en elk paar beginwaarden wordt door precies één oplossing gerealiseerd: zoals in Oefening 19.10 wordt $E_D$ bijectief en lineair geparametriseerd door $(u_0, u_1) \in K^2$ : $\dim E_D = 2$ .

12. $(a_n)$ gehoorzaamt aan de recurrentie (vraag 2) met $a_0 = 0$ , $a_1 = 1$ . Zo ook $(b_n)$ : $b_{n+2} = -p\,a_{n+1} = -p(s a_n + b_n) = s\,b_{n+1} - p\,b_n$ (door $b_{n+1} = -pa_n$ tweemaal te gebruiken), met $b_0 = 1$ , $b_1 = 0$ . De combinatie $v_n = u_1 a_n + u_0 b_n$ is dan een oplossing met $v_0 = u_0$ , $v_1 = u_1$ ; twee oplossingen met dezelfde beginwaarden vallen samen (inductie), dus $u_n = u_1 a_n + u_0 b_n$ voor alle $n$ .

13. $(\lambda^n)$ is een oplossing desda $\lambda^{n+2} = s\lambda^{n+1} - p\lambda^n$ voor alle $n$ , d.w.z. $D(\lambda) = 0$ (na delen door $\lambda^n \neq 0$ ; merk op $\lambda, \mu \neq 0$ aangezien $p = \lambda\mu \neq 0$ ). Vrijheid van $\bigl((\lambda^n), (\mu^n)\bigr)$ : een relatie bij $n = 0, 1$ geeft $c + c' = 0$ , $c\lambda + c'\mu = 0$ , dus $c(\lambda - \mu) = 0$ : $c = c' = 0$ . Twee vrije vectoren in dimensie $2$ : een basis. Dubbele wortel: $\bigl((n\lambda^n)\bigr)$ is een oplossing aangezien, met $s = 2\lambda$ , $p = \lambda^2$ :

s(n+1)\lambda^{n+1} - p\,n\lambda^n = \lambda^{n+2}\bigl(2(n+1) - n\bigr) = (n+2)\lambda^{n+2} ;

vrijheid bij $n = 0, 1$ : $c = 0$ , dan $c'\lambda = 0$ met $\lambda \neq 0$ .

14. $D = X^2 - X - 6 = (X - 3)(X + 2)$ . Algemene oplossing $u_n = A\,3^n + B(-2)^n$ ; de beginvoorwaarden geven $A + B = 1$ en $3A - 2B = 8$ , dus $A = 2$ , $B = -1$ :

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

Controle: $u_2 = 18 - 4 = 14 = u_1 + 6u_0$ ; $u_3 = 54 + 8 = 62 = u_2 + 6u_1 = 14 + 48$ .

15. $C\begin{pmatrix} u_n\\ u_{n+1}\end{pmatrix} = \begin{pmatrix} u_{n+1}\\ -p\,u_n + s\,u_{n+1}\end{pmatrix} = \begin{pmatrix} u_{n+1}\\ u_{n+2}\end{pmatrix}$ , en inductie geeft de formule met $C^n$ . Bovendien $\operatorname{tr} C = 0 + s = s$ en $p(C) = 0\cdot s - 1\cdot(-p) = p$ : de begeleidende matrix heeft precies $D$ als haar Cayley–Hamilton-veelterm.

16. Voor elke oplossing $u$ van $u_{n+3} = \alpha u_{n+2} + \beta u_{n+1} + \gamma u_n$ voldoen de toestandsvectoren $v_n = (u_n, u_{n+1}, u_{n+2})^{\mathsf T}$ aan $C_3 v_n = v_{n+1}$ (de eerste twee rijen verschuiven, de laatste rij past de recurrentie toe). Dus

D_3(C_3)\,v_0 = v_3 - \alpha v_2 - \beta v_1 - \gamma v_0 ,

waarvan de drie componenten $u_{k+3} - \alpha u_{k+2} - \beta u_{k+1} - \gamma u_k = 0$ zijn ( $k = 0, 1, 2$ ). Aangezien de begintoestand $v_0 = (u_0, u_1, u_2)^{\mathsf T}$ heel $K^3$ doorloopt (beginwaarden zijn vrij), beeldt de matrix $D_3(C_3)$ elke vector op nul af: $D_3(C_3) = 0$ .

17. Schrijf $X^n = Q\,D_3 + R_n$ met $\deg R_n \leq 2$ en evalueer in elke wortel: $\lambda_i^n = R_n(\lambda_i)$ . Dus $R_n$ is een veelterm van graad $\leq 2$ die de drie waarden $\lambda_i^n$ in de drie verschillende knopen $\lambda_i$ interpoleert: volgens de uniciteit in Stelling 8.23, $R_n = \sum_i \lambda_i^n L_i$ met $(L_i)$ de Lagrange-basis van de knopen. Substitutie van $C_3$ (vragen 5 en 16):

C_3^{\,n} = R_n(C_3) = \sum_{i=1}^{3} \lambda_i^n\,L_i(C_3),

met de drie matrices $L_i(C_3)$ onafhankelijk van $n$ : elk element van $C_3^{\,n}$ is een vaste combinatie van $\lambda_1^n, \lambda_2^n, \lambda_3^n$ .

18. $D_3 = X^3 - 2X^2 - X + 2 = (X-1)(X+1)(X-2)$ . Algemene oplossing $u_n = A + B(-1)^n + C\,2^n$ . Beginvoorwaarden: $A + B + C = 0$ , $A - B + 2C = 1$ , $A + B + 4C = 1$ . De eerste van de derde aftrekken: $3C = 1$ , $C = \frac13$ ; dan $A + B = -\frac13$ en $A - B = \frac13$ : $A = 0$ , $B = -\frac13$ . Dus

u_n = \frac{2^n - (-1)^n}{3}

(de Jacobsthal-getallen). Controle: $u_3 = \frac{8 + 1}{3} = 3 = 2u_2 + u_1 - 2u_0 = 2 + 1 - 0$ .

19. Taylorontwikkeling van de veelterm $X^n$ in $\lambda$ :

X^n = \sum_{k=0}^{n} \binom nk \lambda^{n-k}(X - \lambda)^k ,

en alle termen met $k \geq 3$ zijn deelbaar door $(X - \lambda)^3$ : de rest is

R_n = \lambda^n + n\lambda^{n-1}(X - \lambda) + \binom n2\lambda^{n-2}(X - \lambda)^2 .

Voor $M = \lambda I + N$ met $N^3 = 0$ : $(M - \lambda I)^3 = N^3 = 0$ , dus vraag 5 geeft

M^n = \lambda^n I + n\lambda^{n-1} N + \binom n2 \lambda^{n-2} N^2 ,

wat precies de binomiale ontwikkeling van $(\lambda I + N)^n$ is, afgebroken bij $N^2$ — de twee methoden komen overeen.

20. De oplossingsruimte heeft dimensie $3$ (dezelfde parametrisatie door $(u_0, u_1, u_2)$ als in vraag 11), en elke $(\lambda_i^n)$ is een oplossing. Vrijheid: veronderstel $c_1\lambda_1^n + c_2\lambda_2^n + c_3\lambda_3^n = 0$ voor $n = 0, 1, 2$ . Fixeer $i$ en zij $L_i = \sum_{k \leq 2} p_k X^k$ de Lagrange-veelterm van de knopen met $L_i(\lambda_j) = \delta_{ij}$ . Dan

0 = \sum_{k=0}^{2} p_k\Bigl(\sum_j c_j\lambda_j^k\Bigr) = \sum_j c_j\,L_i(\lambda_j) = c_i .

Dus alle $c_i = 0$ : drie vrije oplossingen in dimensie $3$ , een basis; de algemene oplossing is $c_1\lambda_1^n + c_2\lambda_2^n + c_3\lambda_3^n$ .

21. Uit $F_k = F_{k+2} - F_{k+1}$ telescopeert de som:

\sum_{k=1}^{n} F_k = \sum_{k=1}^{n}\bigl(F_{k+2} - F_{k+1}\bigr) = F_{n+2} - F_2 = F_{n+2} - 1 .

22. Neem het $(1,2)$ -element van $F^{m+n} = F^m F^n$ : de linkerkant is $F_{m+n}$ ; de rechterkant is (rij $1$ van $F^m$ ) maal (kolom $2$ van $F^n$ ), d.w.z. $F_{m+1}F_n + F_m F_{n-1}$ . Met $m = n$ :

F_{2n} = F_{n+1}F_n + F_nF_{n-1} = F_n\,(F_{n+1} + F_{n-1}).

23. Volgens Binet, $F_n - \dfrac{\varphi^n}{\sqrt5} = -\dfrac{\psi^n}{\sqrt5}$ , en $\abs\psi = \frac{\sqrt5 - 1}2 < 1$ , dus

\Bigl|F_n - \frac{\varphi^n}{\sqrt5}\Bigr| \leq \frac{1}{\sqrt5} < \frac12 \qquad (n \geq 0):

$F_n$ is het dichtstbijzijnde gehele getal bij $\varphi^n/\sqrt5$ .

24. $t_n = F_{n+1} + F_{n-1}$ is een combinatie van verschoven Fibonacci-rijen, en voldoet dus aan dezelfde recurrentie: $t_{n+2} = t_{n+1} + t_n$ ; en $t_1 = F_2 + F_0 = 1$ , $t_2 = F_3 + F_1 = 3$ : dit zijn de Lucas-getallen $L_n$ . De rij $\varphi^n + \psi^n$ is een oplossing met dezelfde eerste twee waarden ( $\varphi + \psi = 1$ , $\varphi^2 + \psi^2 = ( \varphi + \psi)^2 - 2\varphi\psi = 3$ ), dus $L_n = \varphi^n + \psi^n$ . Ten slotte

F_n L_n = \frac{(\varphi^n - \psi^n)(\varphi^n + \psi^n)}{\sqrt5} = \frac{\varphi^{2n} - \psi^{2n}}{\sqrt5} = F_{2n},

wat vraag 22 herwint.

25. (i) De vijf matrices $I, A, A^2, A^3, A^4$ leven in de $4$ -dimensionale $\mathcal{M}_2(K)$ , dus een of andere niet-nul veelterm van graad $\leq 4$ annuleert $A$ ; Deel II verscherpte dit tot de expliciete kwadratische $A^2 = sA - pI$ , die alle machten vastlegt in het vlak $\operatorname{Vect}(I, A)$ . (ii) Euclidische deling herleidt $X^n$ modulo die kwadratische, en de twee coëfficiënten van de rest gehoorzamen aan de recurrentie met twee termen $a_{n+2} = s\,a_{n+1} - p\,a_n$ : machtsverheffing is iteratie geworden. (iii) Vraag 6 is het geval $n = 2$ van de stelling van Cayley–Hamilton, geldig in elke dimensie en bewezen in het deel van Jaar 2. (iv) De begeleidende matrix sluit de lus: elke lineaire recurrentie is een matrixmacht, met dezelfde veelterm $D$ die als spoor-en-determinantgegevens verschijnt, dus de restrekening lost recurrenties op en berekent machten in één beweging.