Wiskunde bovenbouw · Grades 10–12

30Matrices en grafen

Een matrix is een rechthoekige array van getallen, opgeteld en vermenigvuldigd volgens regels zo ontworpen dat matrixalgebra de samenstelling van lineaire transformaties voorstelt. Matrices lossen lineaire stelsels op, drijven gekoppelde recurrente rijen, en tellen paden in netwerken — de wiskunde achter zoekmachines en kortste-padalgoritmen.

30.1 Matrixalgebra

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})$ , waar $a_{ij}$ de ingang in rij $i$ , kolom $j$ is. Twee matrices van dezelfde grootte worden ingang voor ingang opgeteld, en $\lambda A = (\lambda a_{ij})$ .

Definitie 30.2 (Matrixproduct)

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

(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}$ : matrixvermenigvuldiging is niet commutatief.

Propositie 30.4 (Regels van matrixalgebra)

Wanneer de groottes de producten zinvol maken:

(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 grootte $m \times n$ .

Bewijs. Alles is ingang-voor-ingang verificatie uit Definitie 30.2; associativiteit, de enige niet-triviale, 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 grootte $n$ is inverteerbaar als er een matrix $B$ is met $AB = BA = I_n$ ; $B$ is dan uniek, geschreven $A^{-1}$ .

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

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

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$ ; als $ad - bc \neq 0$ , deel. Omgekeerd, als $ad - bc = 0$ , zijn de kolommen van $A$ evenredig, en zo ook de kolommen van $AB$ voor elke $B$ ; maar de kolommen van $I_2$ zijn niet evenredig, dus geen $B$ kan $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}$ , $Y = \begin{pmatrix} e \\ f\end{pmatrix}$ . Als $\det A \neq 0$ , is de unieke oplossing $X = A^{-1}Y$ . Dezelfde formalisme behandelt $n$ vergelijkingen in $n$ onbekenden.

30.2 Matrixmachten en recurrente rijen

Definitie 30.8

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

Methode 30.9 (Diagonaal-plus-nilpotent en diagonaliseerbare gevallen)

Twee standaardmanieren om $A^k$ te berekenen:

Als $A = \lambda I + N$ waar $N^2 = 0$ , stort de binomiaalstelling (geldig hier omdat $I$ en $N$ commuteren) in tot twee termen: $A^k = \lambda^k I + k \lambda^{k-1} N$ .
Als men een inverteerbare $P$ vindt met $A = PDP^{-1}$ en $D$ diagonaal, dan $A^k = P D^k P^{-1}$ , en $D^k$ wordt ingang voor ingang berekend. (Zulke $P$ systematisch vinden is de theorie van diagonalisatie, ontwikkeld op de universiteit; op dit niveau is $P$ gegeven.)

Voorbeeld 30.10 (Gekoppelde rijen)

Laat $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 $s_n = 4^n s_0$ , $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 eigenvectorrichtingen van $A$ .)

30.3 Grafen en paden

Definitie 30.11 (Graaf, adjacentie-matrix)

Een graaf bestaat uit hoekpunten $1, 2, \dots, n$ en kanten die bepaalde paren hoekpunten verbinden (geordende paren voor een gerichte graaf). Haar adjacentie-matrix is de $n \times n$ -matrix $M$ met $m_{ij} = 1$ als er een kant van $i$ naar $j$ is, en $0$ anders. Een pad (of wandeling) van lengte $k$ van $i$ naar $j$ is een rij van $k$ opeenvolgende kanten van $i$ naar $j$ .

M = pmatrix 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 pmatrix Een gerichte graaf en haar adjacentie-matrix (): m_ij = 1 precies wanneer er een kant van i naar j is. — $M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ Een gerichte graaf en haar adjacentie-matrix (Oefening 30.6): $m_{ij} = 1$ precies wanneer er een kant van $i$ naar $j$ is.

Stelling 30.12 (Paden tellen)

Het aantal paden van lengte $k$ van hoekpunt $i$ naar hoekpunt $j$ is de $(i,j)$ -ingang van $M^k$ .

Bewijs. Inductie op $k$ . Voor $k = 1$ is dit de definitie van $M$ . Neem de claim aan voor $k$ . Een pad van lengte $k+1$ van $i$ naar $j$ is een pad van lengte $k$ van $i$ naar enig hoekpunt $l$ , gevolgd door een kant van $l$ naar $j$ ; volgens de optel- en vermenigvuldigingsprincipes 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$ hoekpunten, alle paren verbonden), $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}$ : van elk hoekpunt zijn er $2$ paden van lengte $2$ terug naar zichzelf (via één van beide buren) en $1$ naar elk ander hoekpunt.

30.4 Oefeningen

Oefening 30.1 ★

Laat $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 $AB \neq BA$ .

Oefening 30.2 ★

Bepaal of de volgende matrices inverteerbaar zijn, en bereken de inverses wanneer 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 door matrixinversie het stelsel op $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 . \end{cases}$

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 ★★

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

Controleer dat $N^2 = 0$ en dat $I$ en $N$ commuteren.
Leid $A^k$ af voor alle $k \in \N$ en verifieer de formule voor $k=2$ door directe 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, geldt de binomiaalstelling en verdwijnen alle termen die $N^2$ bevatten:

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$ , $2 \times 2 = 4$ . ✓

Oefening 30.5 ★★

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

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. (Hint: determinanten vermenigvuldigen: $\det(MN) = \det M \det N$ , wat u voor $2\times2$ -matrices mag controleren.)

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}$ . Neem de formule aan voor $n$ ; dan

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 ontwikkelen $\det(MN) = \det M \det N$ ; dus $\det(A^n) = (\det A)^n = (-1)^n$ , en $\det A^n = F_{n-1}F_{n+1} - F_n^2$ . (Dit is de identiteit van Cassini.)

Oefening 30.6 ★★

Een gerichte graaf op hoekpunten $\{1, 2, 3\}$ heeft kanten $1\to2$ , $2\to3$ , $3\to1$ en $1\to3$ .

Schrijf de adjacentie-matrix $M$ en bereken $M^2$ en $M^3$ .
Hoeveel paden van lengte $3$ gaan van $1$ naar $1$ ? Lijst ze.

Oplossing

Oplossing van Oefening 30.6.

1. Hoekpunten $1, 2, 3$ ordenen:

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$ : precies één gesloten pad van lengte $3$ in hoekpunt $1$ , namelijk $1 \to 2 \to 3 \to 1$ . (Het pad $1 \to 3 \to 1$ heeft lengte $2$ alleen, en $1 \to 3$ dan $3\to1$ dan $1\to3$ eindigt in $3$ .)

Oefening 30.7 ★★

Een deelauto-bedrijf 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$ ; $30\%$ van de auto’s in $B$ verhuist naar $A$ en $70\%$ blijft. Laat $a_n, b_n$ de proporties van de vloot in elke stad zijn.

Schrijf $X_{n+1} = MX_n$ met $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ en identificeer $M$ .
Vind de evenwichtsproporties (los $MX = X$ op met $a + b = 1$ ).
Toon dat $c_n = a_n - 0.6$ voldoet aan $c_{n+1} = 0.5\,c_n$ , en concludeer dat de vlootverdeling naar het evenwicht convergeert.

Oplossing

Oplossing van Oefening 30.7.

1. $a_{n+1} = 0.8a_n + 0.3b_n$ , $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$ , d.w.z. $0.3b = 0.2a$ , dus $b = \frac23 a$ ; met $a + b = 1$ : $a = 0.6$ , $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 .

Dus $c_n = 0.5^n c_0 \to 0$ : $a_n \to 0.6$ en $b_n \to 0.4$ , ongeacht de beginverdeling.

Oefening 30.8 ★★★

Laat $A = \begin{pmatrix} 3 & 1\\ 1 & 3 \end{pmatrix}$ , $P = \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}$ .

Bereken $P^{-1}$ , daarna $D = P^{-1}AP$ , en controleer 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}$ . Dan

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}$ reproduceert precies de formules van Voorbeeld 30.10.