Wiskunde bovenbouw · Grades 10–12

30Matrices en grafen

Een matrix is een rechthoekige tabel van getallen, die opgeteld en vermenigvuldigd worden volgens regels die zo ontworpen zijn dat de algebra van de matrices het samenstellen van lineaire transformaties weergeeft. Matrices lossen lineaire stelsels op, sturen gekoppelde recursieve rijen aan en tellen wandelingen in netwerken — de wiskunde achter zoekmachines en algoritmen voor kortste paden.

30.1 Algebra van de matrices

Definitie 30.1 (Matrix)

Een $m \times n$ -matrix is een tabel van reële getallen met $m$ rijen en $n$ kolommen: $A = (a_{ij})$ , waarbij $a_{ij}$ de ingang in rij $i$ , kolom $j$ is. Twee matrices van hetzelfde formaat worden ingang per ingang opgeteld, en $\lambda A = (\lambda a_{ij})$ .

Definitie 30.2 (Product van matrices)

Zij $A$ een $m \times n$ -matrix en $B$ een $n \times p$ -matrix. Het product $AB$ is de $m \times p$ -matrix met als ingang $(i,j)$

(AB)_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj}

(de regel “rij $i$ van $A$ maal kolom $j$ van $B$ ”).

Voorbeeld 30.3

$\begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} = \begin{pmatrix} 2 & 3\\ 4 & 7\end{pmatrix}$ , terwijl $\begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} = \begin{pmatrix} 3 & 4\\ 4 & 6\end{pmatrix}$ : het vermenigvuldigen van matrices is niet commutatief.

Propositie 30.4 (Rekenregels voor matrices)

Telkens wanneer de formaten de producten zinvol maken, geldt

(AB)C = A(BC), \qquad A(B + C) = AB + AC, \qquad (A+B)C = AC + BC,

en de eenheidsmatrix $I_n$ (enen op de diagonaal, nullen elders) voldoet aan $I_m A = A I_n = A$ voor $A$ van formaat $m \times n$ .

Bewijs. Alles zijn verificaties ingang per ingang vanuit Definitie 30.2; de associativiteit, als enige niet triviaal, komt neer op het verwisselen van twee eindige sommen: $\bigl((AB)C\bigr)_{ij} = \sum_l \left(\sum_k a_{ik}b_{kl}\right) c_{lj} = \sum_k a_{ik} \left(\sum_l b_{kl} c_{lj}\right) = \bigl(A(BC)\bigr)_{ij}$ . ∎

Definitie 30.5 (Inverse)

Een vierkante matrix $A$ van formaat $n$ heet inverteerbaar als er een matrix $B$ bestaat met $AB = BA = I_n$ ; $B$ is dan uniek en wordt $A^{-1}$ genoteerd.

Propositie 30.6 (Inverse van een $2\times2$ -matrix)

Zij $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ en $\det A = ad - bc$ (de determinant). Dan is $A$ inverteerbaar als en slechts als $\det A \neq 0$ , en in dat geval geldt

A^{-1} = \frac{1}{ad - bc}\begin{pmatrix} d & -b\\ -c & a\end{pmatrix}.

Bewijs. Een berekening geeft $A \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} = \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} A = (ad - bc) I_2$ ; is $ad - bc \neq 0$ , deel dan. Omgekeerd: is $ad - bc = 0$ , dan zijn de kolommen van $A$ evenredig, en dus ook die van $AB$ voor elke $B$ ; maar de kolommen van $I_2$ zijn niet evenredig, dus geen enkele $B$ kan aan $AB = I_2$ voldoen. ∎

Methode 30.7 (Lineaire stelsels)

Het stelsel $\begin{cases} ax + by = e\\ cx + dy = f \end{cases}$ is de matrixvergelijking $AX = Y$ met $X = \begin{pmatrix} x \\ y\end{pmatrix}$ en $Y = \begin{pmatrix} e \\ f\end{pmatrix}$ . Is $\det A \neq 0$ , dan is de unieke oplossing $X = A^{-1}Y$ . Hetzelfde formalisme behandelt $n$ vergelijkingen in $n$ onbekenden.

30.2 Machten van matrices en recursieve rijen

Definitie 30.8

Voor een vierkante matrix $A$ en $k \in \N$ is $A^k = A \times \dots \times A$ ( $k$ factoren), met $A^0 = I$ .

Methode 30.9 (Diagonaal plus nilpotent, en het diagonaliseerbare geval)

Twee standaardmanieren om $A^k$ te berekenen:

Is $A = \lambda I + N$ met $N^2 = 0$ , dan krimpt het binomium van Newton (hier geldig, want $I$ en $N$ commuteren) tot twee termen: $A^k = \lambda^k I + k \lambda^{k-1} N$ .
Vind je een inverteerbare $P$ met $A = PDP^{-1}$ en $D$ diagonaal, dan is $A^k = P D^k P^{-1}$ , en $D^k$ bereken je ingang per ingang. (Zo’n $P$ systematisch vinden is de theorie van het diagonaliseren, uitgewerkt aan de universiteit; op dit niveau wordt $P$ gegeven.)

Voorbeeld 30.10 (Gekoppelde rijen)

Zij $u_{n+1} = 3u_n + v_n$ en $v_{n+1} = u_n + 3v_n$ . Met $X_n = \begin{pmatrix} u_n\\ v_n \end{pmatrix}$ en $A = \begin{pmatrix} 3 & 1\\ 1 & 3\end{pmatrix}$ krijgen we $X_{n+1} = AX_n$ , dus $X_n = A^n X_0$ . De hulprijen $s_n = u_n + v_n$ en $d_n = u_n - v_n$ voldoen aan $s_{n+1} = 4s_n$ en $d_{n+1} = 2d_n$ , dus is $s_n = 4^n s_0$ en $d_n = 2^n d_0$ , en

u_n = \frac{4^n(u_0+v_0) + 2^n(u_0-v_0)}{2}, \qquad v_n = \frac{4^n(u_0+v_0) - 2^n(u_0-v_0)}{2}.

(Achter de schermen: $(1,1)$ en $(1,-1)$ zijn de richtingen van de eigenvectoren van $A$ .)

30.3 Grafen en wandelingen

Definitie 30.11 (Graaf, verbindingsmatrix)

Een graaf bestaat uit toppen $1, 2, \dots, n$ en bogen die bepaalde paren toppen verbinden (geordende paren voor een gerichte graaf). Zijn verbindingsmatrix is de $n \times n$ -matrix $M$ met $m_{ij} = 1$ als er een boog van $i$ naar $j$ loopt, en $0$ anders. Een wandeling van lengte $k$ van $i$ naar $j$ is een opeenvolging van $k$ bogen die van $i$ naar $j$ leidt.

M = pmatrix 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 pmatrix Een gerichte graaf en zijn verbindingsmatrix (): m_ij = 1 precies wanneer er een boog van i naar j loopt. — $M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ Een gerichte graaf en zijn verbindingsmatrix (Oefening 30.6): $m_{ij} = 1$ precies wanneer er een boog van $i$ naar $j$ loopt.

Stelling 30.12 (Wandelingen tellen)

Het aantal wandelingen van lengte $k$ van top $i$ naar top $j$ is de ingang $(i,j)$ van $M^k$ .

Bewijs. Inductie op $k$ . Voor $k = 1$ is dit de definitie van $M$ . Onderstel de bewering voor $k$ . Een wandeling van lengte $k+1$ van $i$ naar $j$ is een wandeling van lengte $k$ van $i$ naar een zekere top $l$ , gevolgd door een boog van $l$ naar $j$ ; volgens het som- en het productprincipe is hun aantal

\sum_{l=1}^{n} \bigl(M^k\bigr)_{il}\, m_{lj} = \bigl(M^{k+1}\bigr)_{ij}. \qedhere

∎

Voorbeeld 30.13

Voor de driehoeksgraaf ( $3$ toppen, alle paren verbonden) is $M = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0\end{pmatrix}$ en $M^2 = \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2\end{pmatrix}$ : vanuit elke top zijn er $2$ wandelingen van lengte $2$ terug naar zichzelf (via een van beide buren) en $1$ naar elke andere top.

30.4 Oefeningen

Oefening 30.1 ★

Zij $A = \begin{pmatrix} 1 & 2\\ 0 & 1 \end{pmatrix}$ en $B = \begin{pmatrix} 2 & 0\\ 1 & 1 \end{pmatrix}$ . Bereken $A + B$ , $AB$ , $BA$ en $A^2$ .

Oplossing

Oplossing van Oefening 30.1.

A + B = \begin{pmatrix} 3 & 2\\ 1 & 2\end{pmatrix}, \quad AB = \begin{pmatrix} 4 & 2\\ 1 & 1\end{pmatrix}, \quad BA = \begin{pmatrix} 2 & 4\\ 1 & 3\end{pmatrix}, \quad A^2 = \begin{pmatrix} 1 & 4\\ 0 & 1\end{pmatrix}.

Merk op dat $AB \neq BA$ .

Oefening 30.2 ★

Ga na of de volgende matrices inverteerbaar zijn, en bereken de inversen waar ze bestaan:

A = \begin{pmatrix} 2 & 5\\ 1 & 3\end{pmatrix}, \qquad B = \begin{pmatrix} 3 & 6\\ 2 & 4\end{pmatrix}.

Oplossing

Oplossing van Oefening 30.2.

$\det A = 6 - 5 = 1 \neq 0$ : $A^{-1} = \begin{pmatrix} 3 & -5\\ -1 & 2 \end{pmatrix}$ . $\det B = 12 - 12 = 0$ : $B$ is niet inverteerbaar.

Oefening 30.3 ★

Los het stelsel $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 \end{cases}$ op door een matrix te inverteren.

Oplossing

Oplossing van Oefening 30.3.

Het stelsel is $AX = Y$ met $A$ als in Oefening 30.2 en $Y = \begin{pmatrix} 1\\ 2\end{pmatrix}$ :

X = A^{-1}Y = \begin{pmatrix} 3 & -5\\ -1 & 2\end{pmatrix} \begin{pmatrix} 1\\ 2\end{pmatrix} = \begin{pmatrix} -7\\ 3\end{pmatrix}: \qquad x = -7,\ y = 3 .

Oefening 30.4 ★★

Zij $A = \begin{pmatrix} 2 & 1\\ 0 & 2\end{pmatrix} = 2I + N$ met $N = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$ .

Ga na dat $N^2 = 0$ en dat $I$ en $N$ commuteren.
Leid $A^k$ af voor alle $k \in \N$ en controleer de formule voor $k=2$ met een rechtstreekse berekening.

Oplossing

Oplossing van Oefening 30.4.

1. $N^2 = \begin{pmatrix} 0&1\\0&0\end{pmatrix} \begin{pmatrix} 0&1\\0&0\end{pmatrix} = 0$ , en $I$ commuteert met elke matrix.

2. Omdat de twee termen commuteren, is het binomium van Newton toepasbaar, en verdwijnen alle termen met $N^2$ :

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 voor $k = 2$ : $A^2 = \begin{pmatrix} 2&1\\0&2\end{pmatrix}^2 = \begin{pmatrix} 4&4\\0&4\end{pmatrix}$ , en de formule geeft $2^2 = 4$ en $2 \times 2 = 4$ . ✓

Oefening 30.5 ★★

Zij $A = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ en $F_n$ de rij van Fibonacci ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ ). Toon met inductie aan dat voor $n \geq 1$ geldt

A^n = \begin{pmatrix} F_{n-1} & F_n\\ F_n & F_{n+1}\end{pmatrix},

en leid de identiteit $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ af. (Tip: determinanten vermenigvuldigen zich: $\det(MN) = \det M \det N$ , wat je voor $2\times2$ -matrices mag nagaan.)

Oplossing

Oplossing van Oefening 30.5.

Inductie. Voor $n = 1$ : $A^1 = \begin{pmatrix} 0&1\\1&1\end{pmatrix} = \begin{pmatrix} F_0 & F_1\\ F_1 & F_2\end{pmatrix}$ . Onderstel de formule voor $n$ ; dan is

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

Identiteit. Voor $2\times2$ -matrices toont uitwerken dat $\det(MN) = \det M \det N$ ; dus is $\det(A^n) = (\det A)^n = (-1)^n$ , terwijl $\det A^n = F_{n-1}F_{n+1} - F_n^2$ . (Dat is de identiteit van Cassini.)

Oefening 30.6 ★★

Een gerichte graaf op de toppen $\{1, 2, 3\}$ heeft de bogen $1\to2$ , $2\to3$ , $3\to1$ en $1\to3$ .

Schrijf de verbindingsmatrix $M$ op en bereken $M^2$ en $M^3$ .
Hoeveel wandelingen van lengte $3$ gaan van $1$ naar $1$ ? Som ze op.

Oplossing

Oplossing van Oefening 30.6.

1. Met de toppen in de volgorde $1, 2, 3$ :

M = \begin{pmatrix} 0&1&1\\ 0&0&1\\ 1&0&0\end{pmatrix}, \quad M^2 = \begin{pmatrix} 1&0&1\\ 1&0&0\\ 0&1&1\end{pmatrix}, \quad M^3 = \begin{pmatrix} 1&1&1\\ 1&0&1\\ 1&0&1 \end{pmatrix}.

2. $\bigl(M^3\bigr)_{11} = 1$ : er is precies één gesloten wandeling van lengte $3$ in top $1$ , namelijk $1 \to 2 \to 3 \to 1$ . (De wandeling $1 \to 3 \to 1$ heeft slechts lengte $2$ , en $1 \to 3$ , dan $3\to1$ , dan $1\to3$ eindigt in $3$ .)

Oefening 30.7 ★★

Een autodeelbedrijf verplaatst voertuigen tussen twee steden $A$ en $B$ . Elke week blijft $80\%$ van de auto’s in $A$ in $A$ en verhuist $20\%$ naar $B$ ; van de auto’s in $B$ verhuist $30\%$ naar $A$ en blijft $70\%$ ter plaatse. Zij $a_n$ en $b_n$ de aandelen van het wagenpark in elke stad.

Schrijf $X_{n+1} = MX_n$ met $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ en bepaal $M$ .
Zoek de evenwichtsaandelen (los $MX = X$ op met $a + b = 1$ ).
Toon aan dat $c_n = a_n - 0.6$ voldoet aan $c_{n+1} = 0.5\,c_n$ , en besluit dat de verdeling van het wagenpark naar het evenwicht convergeert.

Oplossing

Oplossing van Oefening 30.7.

1. $a_{n+1} = 0.8a_n + 0.3b_n$ en $b_{n+1} = 0.2a_n + 0.7b_n$ : $M = \begin{pmatrix} 0.8 & 0.3\\ 0.2 & 0.7\end{pmatrix}$ .

2. $MX = X$ geeft $0.8a + 0.3b = a$ , dat wil zeggen $0.3b = 0.2a$ , dus $b = \frac23 a$ ; met $a + b = 1$ : $a = 0.6$ en $b = 0.4$ .

3. Met $b_n = 1 - a_n$ : $a_{n+1} = 0.8a_n + 0.3(1 - a_n) = 0.5a_n + 0.3$ , dus

c_{n+1} = a_{n+1} - 0.6 = 0.5a_n + 0.3 - 0.6 = 0.5(a_n - 0.6) = 0.5\,c_n .

Bijgevolg is $c_n = 0.5^n c_0 \to 0$ : $a_n \to 0.6$ en $b_n \to 0.4$ , wat de beginverdeling ook is.

Oefening 30.8 ★★★

Zij $A = \begin{pmatrix} 3 & 1\\ 1 & 3 \end{pmatrix}$ en $P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}$ .

Bereken $P^{-1}$ , daarna $D = P^{-1}AP$ , en ga na dat $D$ diagonaal is.
Leid een gesloten formule voor $A^n$ af en vergelijk met Voorbeeld 30.10.

Oplossing

Oplossing van Oefening 30.8.

1. $\det P = -2$ , dus $P^{-1} = -\frac12\begin{pmatrix} -1 & -1\\ -1 & 1\end{pmatrix} = \frac12\begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ . Vervolgens

AP = \begin{pmatrix} 4 & 2\\ 4 & -2 \end{pmatrix}, \qquad D = P^{-1}AP = \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} \begin{pmatrix} 4&2\\4&-2\end{pmatrix} = \begin{pmatrix} 4 & 0\\ 0 & 2\end{pmatrix}.

2. Uit $A = PDP^{-1}$ geeft een onmiddellijke inductie $A^n = PD^nP^{-1}$ met $D^n = \begin{pmatrix} 4^n & 0\\ 0 & 2^n\end{pmatrix}$ , dus

A^n = P D^n P^{-1} = \begin{pmatrix} 4^n & 2^n\\ 4^n & -2^n\end{pmatrix}\cdot \frac12\begin{pmatrix} 1&1\\1&-1\end{pmatrix} = \frac12\begin{pmatrix} 4^n + 2^n & 4^n - 2^n\\ 4^n - 2^n & 4^n + 2^n\end{pmatrix}.

$A^n$ toepassen op $X_0 = \begin{pmatrix} u_0\\v_0\end{pmatrix}$ levert precies de formules van Voorbeeld 30.10 op.

30.5 Opgave: de matrix die Fibonacci kent (en het weer)

Probleem 30.1

Weekendopgave — één $2 \times 2$ -matrix draagt heel Fibonacci, een matrix van Markov voorspelt het weer op lange termijn, en een eigenvector is een miljard dollar waard

Een matrix is een machine die een toestand opeet en de volgende teruggeeft — en haar machten bevatten dus hele toekomsten. Deze opgave opent met de verbluffende matrix waarvan de machten de getallen van Fibonacci opsommen (en hun identiteiten elk in één regel bewijzen), laat daarna het weer als een keten van Markov naar zijn stationaire toestand lopen, en sluit af met de eigenvector waarop een zoekmachine gebouwd werd (Stelling 30.12, Methode 30.9).

Deel I — Vlotheid.

Bereken met $A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ en $B = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ de producten $AB$ en $BA$ . Oordeel over de commutativiteit?
Inverteer $\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ (Propositie 30.6) en los met die inverse $2x + y = 4$ , $5x + 3y = 7$ op.
Zij $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : bereken $N^2$ en leid $(I + N)^n = I + nN$ af voor elke $n$ .
De driehoeksgraaf (drie toppen, alle paren verbonden): schrijf zijn verbindingsmatrix $A$ op, bereken $A^3$ , en duid de ingangen op de diagonaal (Stelling 30.12).
Geef voor $D = \begin{pmatrix} 2 & 0\\ 0 & \frac12 \end{pmatrix}$ de matrix $D^n$ en haar gedrag wanneer $n \to \infty$ .

Deel II — De matrix van Fibonacci. Zij $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ en zij $F_1 = F_2 = 1, F_3 = 2, \dots$ de getallen van Fibonacci uit Probleem 13.1.

Bereken $F^2$ , $F^3$ en $F^4$ en vermoed de algemene vorm van $F^n$ in termen van de getallen van Fibonacci.
Bewijs het vermoeden $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$ met inductie.
Neem in beide leden de determinant (de determinant van een product is het product van de determinanten — ga het na op $2 \times 2$ -matrices als je het nooit gezien hebt): leid de identiteit van Cassini $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ af — de motor van het verdwijnende vierkantje, in één regel bewezen.
Lees in $F^{m+n} = F^m F^n$ de ingangen rechtsboven af en leid de somformule

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

af. Ga ze na voor $m = n = 3$ .
Leid uit de somformule af (inductie op $k$ ) dat $F_n$ het getal $F_{kn}$ deelt, en ga dat na voor $F_3 \mid F_6$ en $F_3 \mid F_9$ .
Om $F_{100}$ te berekenen hoef je geen $100$ matrices te vermenigvuldigen: kwadrateer herhaaldelijk ( $F^2, F^4, F^8, \dots$ ) en combineer. Hoeveel matrixvermenigvuldigingen volstaan er, en welke aloude vermenigvuldigingstruc uit het onderbouwvolume is dit, bevorderd tot matrices?

Deel III — De weermachine. In een zekere stad geldt: na een zonnige dag is de volgende zonnig met kans $0.8$ ; na een regendag is ze zonnig met kans $0.4$ . Codeer de verdeling van de dag als een kolom $\binom{p_{\text{zon}}}{p_{\text{regen}}}$ en de evolutie door

M = \begin{pmatrix} 0.8 & 0.4\\ 0.2 & 0.6 \end{pmatrix}.

Ga na dat elke kolom van $M$ als som $1$ heeft, en zeg waarom elke weermachine die eigenschap moet hebben.
Vandaag is het zonnig. Bereken de voorspelling voor morgen en voor overmorgen.
Zoek de stationaire toestand: de verdeling $v$ met $Mv = v$ (en met som $1$ ). Welk aandeel van de dagen is op lange termijn zonnig?
Vertrek van een regendag, $\binom01$ , en pas $M$ vier keer toe, waarbij je bij elke stap de afstand tot de stationaire toestand bijhoudt. Met welke factor krimpt de kloof per stap — en om welk soort convergentie gaat het?
PageRank in het klein: drie pagina’s, met de verwijzingen $A \to B$ , $A \to C$ , $B \to C$ en $C \to A$ . Een willekeurige surfer volgt uniform willekeurig een uitgaande verwijzing. Schrijf de overgangsmatrix op, zoek de stationaire toestand, en rangschik de pagina’s.
Duid de rangschikking: waarom scoort $C$ even hoog als $A$ hoewel het van minder pagina’s een verwijzing krijgt — wat meet de stationaire toestand eigenlijk? (De echte PageRank voegt een dempingsfactor toe voor doodlopende paden en sprongen; het idee van de eigenvector is precies dit.)

Deel IV — Het rendement van de diagonaal.

Twee gekoppelde grootheden voldoen aan $u_{n+1} = 3u_n + v_n$ en $v_{n+1} = u_n + 3v_n$ , dat wil zeggen aan de matrix $A$ van Oefening 30.8. Geef met de diagonalisatie uit die oefening ( $D = \operatorname{diag}(4, 2)$ ) de gesloten formule voor $u_n$ als $u_0 = 1$ en $v_0 = 0$ , en toets ze aan de rechtstreekse berekening voor $n = 1, 2, 3$ .
In een of twee zinnen: wat doet het diagonaliseren met een gekoppeld stelsel — en in welke zin is de stationaire toestand van Markov uit vraag 14 ook een verhaal over eigenvectoren?
Slotstuk — de drie gezichten van de matrix dit weekend: boekhouding (stelsels en inversen), combinatoriek (wandelingen en verwijzingen geteld door machten) en evolutie (Fibonacci, het weer, het web — toekomsten afgelezen op de eigenrichtingen). Telkens één zin, plus de blik vooruit: de lineaire algebra van de universitaire volumes maakt van elk van die gezichten een theorie.

Oplossing

Oplossing van Probleem 30.1.

1. $AB = \begin{pmatrix} 2 & 1\\ 4 & 3\end{pmatrix}$ en $BA = \begin{pmatrix} 3 & 4\\ 1 & 2\end{pmatrix}$ : het vermenigvuldigen van matrices is niet commutatief — $B$ verwisselt rechts de kolommen en links de rijen.

2. Determinant $6 - 5 = 1$ : de inverse is $\begin{pmatrix} 3 & -1\\ -5 & 2\end{pmatrix}$ . Toegepast op $\binom{4}{7}$ : $x = 12 - 7 = 5$ en $y = -20 + 14 = -6$ .

3. $N^2 = 0$ . Dan geeft inductie $(I + N)^n = I + nN$ : $(I + nN)(I + N) = I + (n+1)N + nN^2 = I + (n+1)N$ .

4. $A = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{pmatrix}$ , en $A^3$ heeft $2$ als ingangen op de diagonaal: vanuit elke top precies twee gesloten wandelingen van lengte $3$ (de driehoek met of tegen de wijzers van de klok doorlopen) — de telstelling aan het werk.

5. $D^n = \begin{pmatrix} 2^n & 0\\ 0 & 2^{-n} \end{pmatrix}$ : de ene richting ontploft, de andere sterft uit — op de diagonaal zijn de lotgevallen onafhankelijke meetkundige rijen.

6. $F^2 = \begin{pmatrix} 2 & 1\\ 1 & 1\end{pmatrix}$ , $F^3 = \begin{pmatrix} 3 & 2\\ 2 & 1\end{pmatrix}$ , $F^4 = \begin{pmatrix} 5 & 3\\ 3 & 2\end{pmatrix}$ : overal Fibonacci; het vermoeden luidt zoals aangegeven.

7. Geldt $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1}\end{pmatrix}$ , dan is

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

overerving; het basisgeval $n = 1$ is $F$ zelf, met de afspraak $F_0 = 0$ (die de recursie achterwaarts voortzet).

8. $\det F = -1$ , dus $\det(F^n) = (\det F)^n = (-1)^n$ ; en rechtstreeks is $\det(F^n) = F_{n+1}F_{n-1} - F_n^2$ : Cassini, in één regel. (De productregel voor $2 \times 2$ -determinanten is een aangename uitwerking van vijf minuten.)

9. Rechtsboven in $F^m F^n$ : $F_{m+1}F_n + F_m F_{n-1}$ ; rechtsboven in $F^{m+n}$ : $F_{m+n}$ . Voor $m = n = 3$ : $F_4 F_3 + F_3 F_2 = 3 \times 2 + 2 \times 1 = 8 = F_6$ .

10. Voor $k = 1$ : triviaal. Geldt $F_n \mid F_{kn}$ , dan geeft de somformule met $m = kn$ : $F_{(k+1)n} = F_{kn+1}F_n + F_{kn}F_{n-1}$ , en beide termen zijn veelvouden van $F_n$ . Dus $F_n \mid F_{kn}$ voor alle $k$ : controleer dat $F_3 = 2$ zowel $F_6 = 8$ als $F_9 = 34$ deelt.

11. $F^{100} = F^{64} F^{32} F^4$ : zeven kwadrateringen ( $F^2, F^4, \dots, F^{64}$ ) plus twee combinaties — negen vermenigvuldigingen in plaats van negenennegentig. Het is de verdubbelingstruc van de Egyptische schrijvers, van getallen naar matrices getild: schrijf $100$ in het tweetallig stelsel en vermenigvuldig de verdubbelingen die je nodig hebt.

12. $0.8 + 0.2 = 1$ en $0.4 + 0.6 = 1$ : morgen moet er een of ander weer zijn — elke kolom is een volledige kansverdeling, zodat de kansen behouden blijven.

13. Morgen: $\binom{0.8}{0.2}$ . Overmorgen: $M\binom{0.8}{0.2} = \binom{0.72}{0.28}$ .

14. $Mv = v$ met $v = \binom{s}{r}$ en $s + r = 1$ : $0.8s + 0.4r = s$ geeft $0.4r = 0.2s$ , dus $s = 2r$ : $v = \binom{2/3}{1/3}$ . Op lange termijn zijn twee dagen op drie zonnig — hoe vandaag er ook uitziet.

15. Vanuit $\binom01$ : als zonnecomponenten $0.4$ , $0.56$ , $0.624$ en $0.6496$ ; de kloven tot $\frac23$ zijn $0.267$ , $0.107$ , $0.043$ en $0.017$ — elke stap vermenigvuldigt de kloof met precies $0.4$ (de tweede eigenwaarde van de machine): meetkundige convergentie naar de stationaire toestand.

16. Kolommen (vanuit $A$ , $B$ , $C$ ): $P = \begin{pmatrix} 0 & 0 & 1\\ \frac12 & 0 & 0\\ \frac12 & 1 & 0\end{pmatrix}$ . Stationaire toestand: $v_A = v_C$ , $v_B = \frac{v_A}{2}$ en $v_C = \frac{v_A}{2} + v_B$ ; met som $1$ : $v = \left(\frac25, \frac15, \frac25\right)$ . Rangschikking: $A$ en $C$ delen de eerste plaats, $B$ is laatste.

17. $C$ krijgt al het verkeer van $B$ en de helft van dat van $A$ , en sluist alles terug naar $A$ : de stationaire toestand meet waar de surfer zijn tijd doorbrengt, niet hoeveel verwijzingen er binnenkomen — één verwijzing van een populaire pagina weegt zwaarder dan verscheidene van verlaten pagina’s. Die recursieve weging is precies het stichtingsidee van Google; de demping vangt de spinnenvallen en de doodlopende paden op.

18. $A^n = P D^n P^{-1}$ geeft $u_n = \frac{4^n + 2^n}{2}$ (en $v_n = \frac{4^n - 2^n}{2}$ ). Controle: $u_1 = 3$ , $u_2 = 10$ , $u_3 = 36$ ; en rechtstreeks: $(1,0) \to (3,1) \to (10,6) \to (36, 28)$ : het klopt.

19. Diagonaliseren stapt over op coördinaten waarin het gekoppelde stelsel uiteenvalt in onafhankelijke meetkundige rijen — elke eigenwaarde loopt haar eigen koers. De stationaire toestand van Markov is de eigenvector bij de eigenwaarde $1$ , en de convergentiesnelheid uit vraag 15 is de volgende eigenwaarde: de weermachine was van meet af aan een verhaal over eigenvectoren.

20. Boekhouding: een stelsel is één matrixvergelijking, opgelost door één inverse. Combinatoriek: de machten van de verbindingsmatrix tellen wandelingen, verwijzingen en verbindingen. Evolutie: de machten van de machine dragen toestanden naar hun bestemming, en de eigenrichtingen (de gulden richting van Fibonacci, de stationaire toestand van het weer, de rangschikkingsvector van het web) zijn die bestemmingen. De lineaire algebra, in de universitaire volumes, is precies de wetenschap hiervan.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst