Universitaire wiskunde — Bachelor jaar 1 · Bachelor jaar 1

21Matrices

Een matrix is een lineaire afbeelding, opgeschreven in coördinaten. Dit hoofdstuk zet het woordenboek op — samenstelling wordt matrixproduct, bijectiviteit wordt inverteerbaarheid, basisverandering wordt conjugatie — en de algoritmische kant: rij-operaties, berekening van rangen en inversen. Matrices, voor het eerst ontmoet in het bovenbouwvolume, worden 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 de $n \times p$ tabellen $A = (a_{ij})$ 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)$ op $\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 monomiale basis $(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)$ wordt elke basisvector op de vorige afgebeeld ( $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 moralen: 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 ogenblikkelijk dat $D^4 = 0$ op $\R_3[X]$ , waarbij elke macht van de matrix haar diagonaal enen één 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)$ (met in het midden overeenstemmende bases). Evenzo is, als $X$ de kolom coördinaten van $x$ is, de kolom van $u(x)$ gelijk aan $AX$ .

Bewijs van de formule voor de samenstelling.

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

De vierkante matrices $\mathcal{M}_n(K)$ vormen een (voor $n \geq 2$ niet-commutatieve) 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)$ geldt

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 reizen mee vanuit $\mathcal{L}(E)$ langs het isomorfisme van Definitie 21.1: dat zet samenstelling om in product en som in som, zodat de associativiteit, de distributiviteit en de rol van $I_n$ worden geërfd van de overeenkomstige feiten over afbeeldingen, zonder enige verificatie per ingang. Niet-commutativiteit: $E_{12}E_{21} = E_{11} \neq E_{22} = E_{21}E_{12}$ . Is $AB = I_n$ , dan voldoet het endomorfisme $a$ van $A$ aan $a \circ b = \mathrm{id}$ , zodat $a$ surjectief is ( $x = a(b(x))$ toont een origineel van elke $x$ ), en dus bijectief in eindige dimensie (Gevolg 20.9); links met $a^{-1}$ samenstellen van $a \circ b = \mathrm{id}$ geeft $b = a^{-1}$ , en dan 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}$ ; zij 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 voor 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 in de canonieke basis de matrix $A = \begin{pmatrix} 1 & 0\\ 1 & 0\end{pmatrix}$ : inderdaad is $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 is geschreven. Het mechanisme van de invariantie 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 ,

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

Voorbeeld 21.7 (Symmetrisch plus antisymmetrisch)

Noem $A$ symmetrisch wanneer $A^{\mathsf T} = A$ , en antisymmetrisch wanneer $A^{\mathsf T} = -A$ . Elke vierkante matrix splitst zich eenduidig 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 splitsing in even en oneven functies (Voorbeeld 18.11), waarbij het transponeren de rol van $x \mapsto -x$ speelt. Dimensies: een symmetrische matrix is vrij op en boven de diagonaal, een antisymmetrische strikt erboven (met nuldiagonaal):

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

en dat de telling klopt, is de bevestiging van de directheid door Grassmann. 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 gegevens van de tweede afgeleide in Hoofdstuk 25 (het drietal $r, s, t$ van Monge), en de symmetrisch-orthogonale worden in Oefening 23.12 geclassificeerd.

21.2 Basisverandering

Definitie 21.8

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

Voorbeeld 21.9 (De matrix van basisverandering lezen)

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}

(de nieuwe vectoren geschreven in oude coördinaten, kolom voor kolom). De vector met 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 is $2(1,1) + 1(1,-1) = (3,1)$ . Let op de richting — de matrix $P$ wordt uit de nieuwe basis gebouwd maar zet nieuw om in oud ( $X = PX'$ ); van oud naar nieuw gaan kost de inverse. De controle $2(1,1) + (1,-1) = (3,1)$ opschrijven na elke omzetting vangt de fout met de omgekeerde $P$ op, die de meest voorkomende fout 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 is

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

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

Bewijs. Voor elke $x$ geldt $X = PX'$ en voldoet het beeld aan $Y = AX$ , $Y = PY'$ . Dus $PY' = APX'$ , dat wil zeggen $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 moet haar matrix in $\mathcal B'$ gelijk zijn aan $\operatorname{diag}(1, -1)$ — de verwisseling is de spiegeling in de rechte $y = x$ . Voor een gegeven endomorfisme een basis vinden waarin zijn matrix diagonaal wordt, is het centrale probleem van het volume van bachelorjaar 2 (reductietheorie); de weekendopgave hieronder toont hoe ver veeltermidentiteiten alleen al reiken.

Voorbeeld 21.12 (Basisverandering, achterstevoren gelopen)

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, laat men Stelling 21.10 achterstevoren lopen, $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 terug — is hoe matrices van rotaties, spiegelingen en projecties in de praktijk werkelijk worden gemaakt.

Stelling 21.13 (Normaalvorm van de rang)

De rang van een matrix (de rang van haar kolommen, equivalent die van de bijbehorende lineaire afbeelding) is de enige invariant van de 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)$ : de rijrang is gelijk aan de kolomrang.

Bewijs. Zij $u \colon E \to F$ van rang $r$ . Kies een complementaire $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 die bases is de matrix van $u$ precies $J_r$ . Dus $A = Q J_r P^{-1}$ met 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 gedaante (rang $r$ ) en met inverteerbare buitenste factoren (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 met $\lambda \neq 0$ vermenigvuldigen, een veelvoud van een rij bij een andere optellen — veranderen de rang niet (elk is een linkse vermenigvuldiging met een inverteerbare matrix). Algoritme: maak een spil (de meest linkse ingang ongelijk aan nul), veeg haar kolom eronder schoon, en ga naar de volgende rij en kolom; het aantal spillen van de resulterende trapvorm is de rang.

Berekening van de inverse: laat het algoritme lopen op het blok $(A \mid I_n)$ tot het linkerblok $I_n$ wordt (mogelijk dan en slechts dan als $A$ inverteerbaar is); het rechterblok is dan $A^{-1}$ — immers, het product van de gebruikte elementaire matrices is gelijk aan $A^{-1}$ .

Voorbeeld 21.15

$A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix}$ : reduceer $(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},

(bewerkingen: $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}$ . Reduceer: $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 worden nul — één spil, $\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, en daarna $L_3 \leftarrow L_3 - L_2 = (0, 0, m + 2)$ . Is $m = -2$ : twee spillen, rang $2$ ; anders drie spillen, rang $3$ . Samengevat:

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

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

Voorbeeld 21.17 (Machten berekenen)

$A = \begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix} = I + N$ met $N = E_{12}$ en $N^2 = 0$ . Omdat $I$ en $N$ commuteren, breekt het binomium (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 wegen)

Binomiale weg: is $A = \lambda I + N$ met $N$ nilpotent, dan breekt het binomium af (Voorbeeld 21.17, Oefening 21.5); het is toepasbaar omdat $\lambda I$ met alles commuteert.
Veeltermweg: zoek een veeltermidentiteit waaraan $A$ voldoet (in dimensie $2$ altijd $A^2 = sA - pI$ ) en reduceer $X^n$ modulo die identiteit; de weekendopgave hieronder bouwt deze weg volledig op.
Gelijkvormigheidsweg: zoek een inverteerbare $P$ met $P^{-1}AP = D$ eenvoudig (diagonaal, of een verschuiving), bereken $D^n$ , en draai terug: $A^n = P D^n P^{-1}$ (Stelling 21.10, Voorbeeld 21.11); het systematisch zoeken naar zo’n $P$ is de reductietheorie van bachelorjaar 2.

Welke weg men ook neemt, controleer het resultaat bij $n = 0, 1, 2$ : drie goedkope tests die vrijwel elke misstap opvangen.

Opmerking 21.19 (Veelgemaakte fouten: de prijs van de niet-commutativiteit)

Elke identiteit uit de scalaire algebra waarvan het bewijs factoren herordent, sterft in $\mathcal{M}_n(K)$ met $n \geq 2$ . Kwadraten: $(A + B)^2 = A^2 + AB + BA + B^2$ , en het midden stort alleen in 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 wegstrepen: $AB = AC$ impliceert $B = C$ alleen wanneer $A$ inverteerbaar is (vermenigvuldig met $A^{-1}$ — aan de juiste kant). Sporen: $\operatorname{tr}(AB) = \operatorname{tr}(BA)$ geldt 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 berekeningen met orthogonaliteit (Hoofdstuk 23). Bij twijfel: toets 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 resterende bladzijde van dit volume gebruikt: Hoofdstuk 22 hangt aan elke vierkante matrix één getal dat over de inverteerbaarheid beslist, en lost $AX = B$ systematisch op; Hoofdstuk 23 zondert de matrices af die lengten bewaren (orthogonale matrices); en in Hoofdstuk 25 is het gedrag van tweede orde van een functie van twee veranderlijken 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 voorproef, en het volume van bachelorjaar 2 bouwt er de theorie van de eigenwaarden op. De weekendopgave ontwikkelt het andere werkpaard: veeltermidentiteiten waaraan een matrix voldoet, die de berekening van $A^n$ omzetten in een lineaire recurrentie met twee termen.

Opmerking 21.21 (Vooruitzichten binnen boek 3)

Drie families matrices die hier zijn ingevoerd, hebben verderop in dit volume een afspraak. Symmetrische matrices (Voorbeeld 21.7) dragen de gegevens van de tweede orde van functies van twee veranderlijken: de toets van Monge uit Hoofdstuk 25 is een uitspraak over het tekengedrag van een symmetrische $2\times2$ matrix, en haar determinant $rt - s^2$ wordt met de machinerie van Hoofdstuk 22 berekend. Orthogonale matrices ( $A^{\mathsf T}A = I$ ) zijn de isometrieën van Hoofdstuk 23, waar de getransponeerde eindelijk haar meetkundige betekenis krijgt: zij is de algebraïsche schaduw van het inproduct. Inverteerbare matrices ontmoeten hun praktische toets in Hoofdstuk 22 — één getal, $\det A \neq 0$ — waarmee de zoektocht wordt gesloten die dit hoofdstuk met rijreductie begon. Spoor en determinant reizen daarna verder als het invariante paar $(s, p)$ van de weekendopgave, helemaal tot in de theorie van de eigenwaarden van bachelorjaar 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}.

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

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$ doodt de tweede rij; $L_3 \leftarrow L_3 - L_1$ geeft $(0, -1, -2)$ . Twee spillen: $\operatorname{rk} M = 2$ .

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

Oefening 21.3 ★

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

Oplossing

Oplossing van Oefening 21.3.

Reductie van $(A \mid I_3)$ : $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},

daarna $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: de eerste rij van $A$ maal de eerste kolom van $A^{-1}$ : $1 \cdot 0 + 0\cdot(-1) + 1\cdot 1 = 1$ ; maal de tweede kolom: $1 - 0 - 1 = 0$ ; maal de 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 zonder berekening uit waarom zij 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$ : de kolommen 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 zij de voor de hand liggende inverse $P \mapsto P(X - 1)$ heeft (samenstelling van substituties). Haar matrix wordt op dezelfde wijze 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 met het binomium $A^k$ af voor alle $k \in \N$ .

Oplossing

Oplossing van Oefening 21.5.

$N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ , $N^2 = 0$ . Omdat $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}.

(Controle bij $k = 2$ : $A^2 = \begin{pmatrix}4 & 4\\ 0 & 4\end{pmatrix}$ , juist volgens het rechtstreekse product.)

Oefening 21.6 ★★

Bewijs dat er geen matrices $A, B \in \mathcal{M}_n(K)$ (met $K = \R$ of $\C$ ) bestaan met $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 wel realiseerbaar — afleiden en vermenigvuldigen met $x$ voldoen eraan — precies omdat er daar geen spoor bestaat.)

Oefening 21.7 ★★

Een matrix $A$ heet nilpotent wanneer $A^m = 0$ voor 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, waarbij alle machten van $A$ commuteren:

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

en Propositie 21.4 tilt 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, met $-N$ in plaats van $A$ 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$ . (Vat $A$ op als een projectie en kies een aangepaste basis; Stelling 21.10 zegt dat het spoor niet van de basis afhangt, want $\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 die aan deze ontbinding is aangepast ( $r$ vectoren van het beeld, daarna 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. Bijgevolg is $\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 daaruit voor $a, b \in \R$ de voorwaarde voor de 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$ (elke ingang 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$ dan en slechts dan als $a\alpha = 1$ en $a\beta + b\alpha + nb\beta = 0$ , dat wil zeggen $\alpha = \frac1a$ en $\beta(a + nb) = -\frac ba$ . Is $a \neq 0$ en $a + nb \neq 0$ , dan

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

Omgekeerd: is $a = 0$ , dan heeft $M = bJ$ rang $\leq 1 < n$ (voor $n \geq 2$ ): niet inverteerbaar ( $n = 1$ is het scalaire geval). Is $a + nb = 0$ , dan voldoet de vector $v = (1, \dots, 1)^{\mathsf T}$ 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 ★★★

(Ongelijkheden voor de rang) Bewijs voor $A, B \in \mathcal{M}_n(K)$ :

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

(Pas voor de tweede — de ongelijkheid van Sylvester — de dimensiestelling 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$ (van dimensie $\operatorname{rk} B$ ). Haar beeld is $\operatorname{im}(AB)$ (want $a(Bx) = ABx$ ), en de dimensiestelling in $V$ geeft

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

Nu is $\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 dan en slechts dan als $A$ diagonaal is. (Vergelijk de ingangen $(i,j)$ 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$ . (Toets tegen $D$ , en daarna tegen de matrices $E_{ij}$ .)

Oplossing

Oplossing van Oefening 21.11.

Per ingang is $(AD)_{ij} = a_{ij}\,d_j$ en $(DA)_{ij} = d_i\,a_{ij}$ . Dus $AD = DA$ dan en slechts dan als $a_{ij}(d_j - d_i) = 0$ voor alle $i, j$ ; voor $i \neq j$ is de factor $d_j - d_i$ niet nul, wat $a_{ij} = 0$ afdwingt: $A$ is diagonaal. Omgekeerd commuteren diagonale matrices met elkaar.
Commuteert $A$ met elke matrix, dan commuteert zij met $\operatorname{diag}(1, 2, \dots, n)$ , dus is $A = \operatorname{diag}(\lambda_1, \dots, \lambda_n)$ volgens (1). Dan is $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. Bijgevolg $A = \lambda I_n$ ; en scalaire matrices commuteren inderdaad met alles. Het centrum van $\mathcal{M}_n(K)$ is $K\,I_n$ .

Oefening 21.12 ★★★

(Matrices van rang één) Zij $A \in \mathcal{M}_n(K)$ , $A \neq 0$ .

Bewijs dat $\operatorname{rk} A = 1$ dan en slechts dan als $A = CL$ voor een kolom $C \in \mathcal{M}_{n,1}$ ongelijk aan nul en een rij $L \in \mathcal{M}_{1,n}$ ongelijk aan nul.
Bewijs voor zo’n $A$ dat $A^2 = (\operatorname{tr} A)\,A$ ; leid af dat een matrix van rang één nilpotent is dan en slechts dan als haar spoor nul is.
Bewijs dat als $\operatorname{tr} A \neq -1$ , de matrix $I_n + A$ inverteerbaar is 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$ . (Zoek een vector die door $I_n + A$ wordt gedood.)

Oplossing

Oplossing van Oefening 21.12.

Is $\operatorname{rk} A = 1$ , dan is het beeld van $A$ een rechte $\operatorname{Vect}(C)$ met $C \neq 0$ , dus is de $j$ -de kolom van $A$ gelijk aan $\ell_j\,C$ voor scalairen $\ell_j$ (niet alle nul), dat wil zeggen $A = C L$ met $L = (\ell_1, \dots, \ell_n) \neq 0$ . Omgekeerd, is $A = CL \neq 0$ , dan 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 met inductie $A^m = (\operatorname{tr} A)^{m-1} A$ . Is $\operatorname{tr} A \neq 0$ , dan wordt geen enkele macht nul; is $\operatorname{tr} A = 0$ , dan is $A^2 = 0$ : een matrix van rang één is nilpotent dan en slechts dan als 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 $A^2 = tA$ . Is $t = -1$ , dan is $(I_n + A)A = A + A^2 = A - A = 0$ met $A \neq 0$ , zodat $I_n + A$ elke kolom van $A$ ongelijk aan nul doodt: niet injectief, niet inverteerbaar.

21.5 Opgave: machten van een matrix via veeltermdeling

Probleem 21.1

$A^{100}$ ingang voor ingang berekenen is hopeloos; het berekenen via een veeltermidentiteit waaraan $A$ voldoet, kost drie regels. Deze opgave bouwt de methode vanaf nul op: de 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 machten van matrices en lineaire recurrenties — met de fibonaccigetallen als doorlopend voorbeeld.

Deel I — Het rekenen met resten. Leg $s, p \in K$ vast en stel $D = X^2 - sX + p$ .

Verantwoord dat er voor elke $n \in \N$ eenduidige $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)$ .
Stel, door met $X$ te vermenigvuldigen en opnieuw te delen, de recursies

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

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

$a_n = \frac{\lambda^n - \mu^n}{\lambda - \mu}, \qquad b_n = \frac{\lambda\mu^n - \mu\lambda^n}{\lambda - \mu} .$
Stel dat $D = (X - \lambda)^2$ . Bewijs met de afgeleide van de delingsidentiteit dat $a_n = n\lambda^{n-1}$ en $b_n = (1 - n)\lambda^{n}$ .
Toon aan dat het invullen 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. Stel voor $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ dat $s = a + d = \operatorname{tr} A$ en $p = ad - bc$ (het getal dat Hoofdstuk 22 de determinant zal noemen).

Ga door rechtstreekse berekening de identiteit van Cayley–Hamilton in dimensie $2$ na:

$A^2 - s\,A + p\,I_2 = 0 .$
Bewijs door rechtstreeks uit te werken dat $p$ multiplicatief is: met de voor de hand liggende notatie, $p(AB) = p(A)\,p(B)$ . Toon daarna aan dat $A$ inverteerbaar is dan en slechts dan als $p \neq 0$ , en dat dan

$A^{-1} = \frac1p\,\bigl(s\,I_2 - A\bigr).$
Zij $A = \begin{pmatrix} 1 & 1\\ 0 & 2\end{pmatrix}$ . Bereken $s$ , $p$ en de wortels van $D$ , en leid een gesloten formule voor $A^n$ af; toets haar aan een rechtstreekse 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 fibonaccigetallen door $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ . Bewijs dat

$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, met $\varphi = \frac{1 + \sqrt5}2$ en $\psi = \frac{1 - \sqrt5}2$ , en met 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$ met $p \neq 0$ vast, en zij $E_D$ de verzameling van de 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)$ als in deel I: de resten van de deling lossen alle recurrenties tegelijk op.
Zijn $\lambda \neq \mu$ de wortels van $D$ , toon dan aan dat $\bigl((\lambda^n), (\mu^n)\bigr)$ een basis van $E_D$ is; is $D = (X-\lambda)^2$ met $\lambda \neq 0$ , toon dan 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$ ; toets het antwoord aan $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 interpolant van Lagrange is van de waarden $\lambda_i^n$ in de knooppunten $\lambda_i$ (Stelling 8.23); leid af dat elke ingang 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 bij $u_3$ .
Bereken de rest van $X^n$ modulo $(X - \lambda)^3$ (taylorontwikkeling van $X^n$ in $\lambda$ ), en leid een formule af voor $(\lambda I + N)^n$ wanneer $N^3 = 0$ en $N$ met alles in zicht commuteert; toets haar aan het binomium.
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. (Evalueer voor de vrijheid een nulcombinatie bij $n = 0, 1, 2$ en herken een interpolatiestelsel in de verschillende knooppunten $\lambda_i$ .)

Deel V — Fibonacci-dividenden, en synthese.

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

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

af, en daaruit $F_{2n} = F_n(F_{n+1} + F_{n-1})$ .
Bewijs dat $F_n$ voor elke $n \geq 0$ het dichtstbijzijnde gehele getal bij $\varphi^n/\sqrt5$ is.
Zij $t_n = \operatorname{tr}(F^n) = F_{n+1} + F_{n-1}$ (de lucasgetallen $L_n$ ). Toon aan dat $t_{n+2} = t_{n+1} + t_n$ , $t_1 = 1$ , $t_2 = 3$ , dat $L_n = \varphi^n + \psi^n$ , en vind $F_{2n} = F_n L_n$ terug.
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 de euclidische deling machtsverheffen omzet in een recurrentie met twee termen; welke uitspraak van deze opgave het geval $n = 2$ is van een stelling die in alle dimensies geldt (benoem haar, en zeg waar zij in deze reeks wordt bewezen); en wat de constructie met de begeleidende matrix aan het beeld 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 eenduidig, 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 reduceer $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 gedaante van een rest (graad $\leq 1$ ), dus geeft de eenduidigheid $a_{n+1} = s a_n + b_n$ en $b_{n+1} = -p a_n$ . Invullen 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$ geeft

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$ . Afleiden van de identiteit geeft $nX^{n-1} = Q_n'\,(X - \lambda)^2 + 2Q_n\,(X - \lambda) + a_n$ , en evaluatie in $\lambda$ : $a_n = n\lambda^{n-1}$ ; daarna $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$ is

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

omdat de machten van de ene matrix $M$ met elkaar commuteren (de sommen zijn duidelijk wegens de lineariteit). Is $D(M) = 0$ , dan geeft het invullen 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. Rechtstreekse 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 heeft $A^2 - sA$ nullen buiten de diagonaal en op de diagonaal de waarden $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}$ geeft het 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'$ eveneens, en wat overblijft is

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

Is $p \neq 0$ , dan geeft Cayley–Hamilton dat $A\,\bigl(\tfrac1p(sI_2 - A)\bigr) = \tfrac1p(sA - A^2) = I_2$ , waaruit de inverse volgt (en Propositie 21.4 maakt haar tweezijdig). Is $p = 0$ en zou $A$ inverteerbaar zijn, dan geeft de 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). Bijgevolg

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 volgens de formule als door rechtstreeks te kwadrateren.

9. $s = 4$ , $p = 3\cdot1 - 1\cdot(-1) = 4$ : $D = X^2 - 4X + 4 = (X - 2)^2$ , met 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}$ , en dat is $A^2$ rechtstreeks berekend.

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 is $s = 1$ , $p = -1$ , $D = X^2 - X - 1$ met wortels $\varphi$ en $\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: toepassing van de multiplicativiteit uit vraag 7 op $F^n$ geeft

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. Met inductie bepalen $u_0, u_1$ de rij $u$ lineair, en wordt elk paar beginwaarden 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$ . Hetzelfde geldt voor $(b_n)$ : $b_{n+2} = -p\,a_{n+1} = -p(s a_n + b_n) = s\,b_{n+1} - p\,b_n$ (met twee keer $b_{n+1} = -pa_n$ ), 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 is $u_n = u_1 a_n + u_0 b_n$ voor alle $n$ .

13. $(\lambda^n)$ is een oplossing dan en slechts dan als $\lambda^{n+2} = s\lambda^{n+1} - p\lambda^n$ voor alle $n$ , dat wil zeggen $D(\lambda) = 0$ (na deling door $\lambda^n \neq 0$ ; merk op dat $\lambda, \mu \neq 0$ omdat $p = \lambda\mu \neq 0$ ). Vrijheid van $\bigl((\lambda^n), (\mu^n)\bigr)$ : een betrekking bij $n = 0, 1$ geeft $c + c' = 0$ en $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 want, met $s = 2\lambda$ en $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} ;

de vrijheid bij $n = 0, 1$ : $c = 0$ , en daarna $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 is $\operatorname{tr} C = 0 + s = s$ en $p(C) = 0\cdot s - 1\cdot(-p) = p$ : de begeleidende matrix heeft precies $D$ als haar veelterm van Cayley–Hamilton.

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

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$ ). Omdat de begintoestand $v_0 = (u_0, u_1, u_2)^{\mathsf T}$ heel $K^3$ doorloopt (de beginwaarden zijn vrij), doodt de matrix $D_3(C_3)$ elke vector: $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 is $R_n$ een veelterm van graad $\leq 2$ die de drie waarden $\lambda_i^n$ in de drie verschillende knooppunten $\lambda_i$ interpoleert: wegens de eenduidigheid in Stelling 8.23 is $R_n = \sum_i \lambda_i^n L_i$ met $(L_i)$ de Lagrange-basis van de knooppunten. Invullen van $C_3$ (de vragen 5 en 16) geeft

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$ : elke ingang 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$ . Aftrekken van de eerste van de derde: $3C = 1$ , dus $C = \frac13$ ; daarna $A + B = -\frac13$ en $A - B = \frac13$ : $A = 0$ , $B = -\frac13$ . Bijgevolg

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

(de jacobsthalgetallen). 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$ is $(M - \lambda I)^3 = N^3 = 0$ , dus geeft vraag 5

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

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

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

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 zijn 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 de ingang $(1,2)$ van $F^{m+n} = F^m F^n$ : het linkerlid is $F_{m+n}$ ; het rechterlid is (rij $1$ van $F^m$ ) maal (kolom $2$ van $F^n$ ), dat wil zeggen $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 is $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 fibonaccirijen 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 lucasgetallen $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 is

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

waarmee vraag 22 wordt teruggevonden.

25. (i) De vijf matrices $I, A, A^2, A^3, A^4$ leven in het $4$ -dimensionale $\mathcal{M}_2(K)$ , dus doodt een veelterm ongelijk aan nul van graad $\leq 4$ de matrix $A$ ; deel II scherpte dit aan tot de expliciete kwadratische $A^2 = sA - pI$ , die alle machten in het vlak $\operatorname{Vect}(I, A)$ opsluit. (ii) De euclidische deling reduceert $X^n$ modulo die kwadratische veelterm, 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$ : machtsverheffen is iteratie geworden. (iii) Vraag 6 is het geval $n = 2$ van de stelling van Cayley–Hamilton, die in elke dimensie geldt en in het volume van bachelorjaar 2 wordt bewezen. (iv) De begeleidende matrix sluit de kring: elke lineaire recurrentie is een macht van een matrix, met dezelfde veelterm $D$ die als gegevens van spoor en determinant verschijnt, zodat het rekenen met resten recurrenties oplost en machten berekent in één beweging.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst