Matematika Sekolah Menengah Atas · Grades 10–12

30Matriks dan Graf

Matriks adalah larik bilangan berbentuk persegi panjang, yang dijumlahkan dan dikalikan menurut kaidah yang dirancang agar aljabar matriksnya mewakili komposisi transformasi linear. Matriks menyelesaikan sistem linear, menggerakkan barisan rekurensi yang berpasangan, dan mencacah jalan pada jaringan — yaitu matematika di balik mesin pencari dan algoritme lintasan terpendek.

30.1 Aljabar matriks

Definisi 30.1 (Matriks)

Suatu matriks $m \times n$ adalah tabel bilangan real dengan $m$ baris dan $n$ kolom: $A = (a_{ij})$ , dengan $a_{ij}$ isian pada baris $i$ , kolom $j$ . Dua matriks yang berukuran sama dijumlahkan isian demi isian, dan $\lambda A = (\lambda a_{ij})$ .

Definisi 30.2 (Hasil kali matriks)

Misalkan $A$ berukuran $m \times n$ dan $B$ berukuran $n \times p$ . Hasil kali $AB$ adalah matriks $m \times p$ yang isian $(i,j)$ -nya

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

(yaitu kaidah “baris $i$ dari $A$ kali kolom $j$ dari $B$ ”).

Contoh 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}$ , sedangkan $\begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix} \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix} = \begin{pmatrix} 3 & 4\\ 4 & 6\end{pmatrix}$ : perkalian matriks tidak komutatif.

Proposisi 30.4 (Kaidah aljabar matriks)

Setiap kali ukurannya membuat hasil kalinya bermakna:

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

dan matriks satuan $I_n$ (berisi satu pada diagonalnya, nol di tempat lain) memenuhi $I_m A = A I_n = A$ untuk $A$ berukuran $m \times n$ .

Bukti. Semuanya pemeriksaan isian demi isian dari Definisi 30.2; keasosiatifannya, satu-satunya yang tak sepele, sama saja dengan menukar dua jumlah berhingga: $\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}$ . ∎

Definisi 30.5 (Balikan)

Matriks persegi $A$ berukuran $n$ disebut dapat dibalik jika ada matriks $B$ dengan $AB = BA = I_n$ ; matriks $B$ itu lalu tunggal dan ditulis $A^{-1}$ .

Proposisi 30.6 (Balikan matriks $2\times2$ )

Misalkan $A = \begin{pmatrix} a & b\\ c & d\end{pmatrix}$ dan $\det A = ad - bc$ (yaitu determinan matriks itu). Maka $A$ dapat dibalik jika dan hanya jika $\det A \neq 0$ , dan dalam hal itu

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

Bukti. Perhitungan memberi $A \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} = \begin{pmatrix} d & -b\\ -c & a\end{pmatrix} A = (ad - bc) I_2$ ; jika $ad - bc \neq 0$ , bagilah. Sebaliknya, jika $ad - bc = 0$ , kolom $A$ sebanding, dan begitu pula kolom $AB$ untuk sebarang $B$ ; padahal kolom $I_2$ tidak sebanding, jadi tak ada $B$ yang memenuhi $AB = I_2$ . ∎

Metode 30.7 (Sistem linear)

Sistem $\begin{cases} ax + by = e\\ cx + dy = f \end{cases}$ adalah persamaan matriks $AX = Y$ dengan $X = \begin{pmatrix} x \\ y\end{pmatrix}$ , $Y = \begin{pmatrix} e \\ f\end{pmatrix}$ . Jika $\det A \neq 0$ , penyelesaian tunggalnya adalah $X = A^{-1}Y$ . Formalisme yang sama mengurus $n$ persamaan dengan $n$ bilangan tak diketahui.

30.2 Pangkat matriks dan barisan rekurensi

Definisi 30.8

Untuk matriks persegi $A$ dan $k \in \N$ , $A^k = A \times \dots \times A$ ( $k$ faktor), dengan $A^0 = I$ .

Metode 30.9 (Kasus diagonal-tambah-nilpoten dan kasus terdiagonalkan)

Dua cara baku untuk menghitung $A^k$ :

Jika $A = \lambda I + N$ dengan $N^2 = 0$ , maka teorema binomial (yang berlaku di sini sebab $I$ dan $N$ komutatif) runtuh menjadi dua suku: $A^k = \lambda^k I + k \lambda^{k-1} N$ .
Jika orang menemukan $P$ yang dapat dibalik dengan $A = PDP^{-1}$ dan $D$ diagonal, maka $A^k = P D^k P^{-1}$ , dan $D^k$ dihitung isian demi isian. (Menemukan $P$ semacam itu secara sistematis adalah teori pendiagonalan, yang dikembangkan di universitas; pada tingkat ini $P$ sudah diberikan.)

Contoh 30.10 (Barisan berpasangan)

Misalkan $u_{n+1} = 3u_n + v_n$ dan $v_{n+1} = u_n + 3v_n$ . Dengan mengambil $X_n = \begin{pmatrix} u_n\\ v_n \end{pmatrix}$ dan $A = \begin{pmatrix} 3 & 1\\ 1 & 3\end{pmatrix}$ , kita peroleh $X_{n+1} = AX_n$ , sehingga $X_n = A^n X_0$ . Barisan bantunya $s_n = u_n + v_n$ dan $d_n = u_n - v_n$ memenuhi $s_{n+1} = 4s_n$ dan $d_{n+1} = 2d_n$ , jadi $s_n = 4^n s_0$ , $d_n = 2^n d_0$ dan

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

(Di balik layarnya: $(1,1)$ dan $(1,-1)$ adalah arah vektor eigen $A$ .)

30.3 Graf dan jalan

Definisi 30.11 (Graf, matriks ketetanggaan)

Suatu graf terdiri atas simpul $1, 2, \dots, n$ dan sisi yang menghubungkan pasangan simpul tertentu (pasangan terurut bagi graf berarah). Matriks ketetanggaan dari graf itu adalah matriks $n \times n$ bernama $M$ dengan $m_{ij} = 1$ jika ada sisi dari $i$ ke $j$ , dan $0$ jika tidak. Suatu jalan sepanjang $k$ dari $i$ ke $j$ adalah barisan $k$ sisi berturut-turut yang membawa dari $i$ ke $j$ .

M = pmatrix 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 pmatrix Sebuah graf berarah dan matriks ketetanggaannya (): m_ij = 1 tepat ketika ada sisi dari i ke j. — $M = \begin{pmatrix} 0 & 1 & 1\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix}$ Sebuah graf berarah dan matriks ketetanggaannya (Latihan 30.6): $m_{ij} = 1$ tepat ketika ada sisi dari $i$ ke $j$ .

Teorema 30.12 (Mencacah jalan)

Banyaknya jalan sepanjang $k$ dari simpul $i$ ke simpul $j$ adalah isian $(i,j)$ pada $M^k$ .

Bukti. Induksi pada $k$ . Untuk $k = 1$ inilah definisi $M$ . Andaikan pernyataannya benar untuk $k$ . Jalan sepanjang $k+1$ dari $i$ ke $j$ adalah jalan sepanjang $k$ dari $i$ ke suatu simpul $l$ , lalu diikuti sisi dari $l$ ke $j$ ; menurut asas penjumlahan dan asas perkalian, banyaknya adalah

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

∎

Contoh 30.13

Untuk graf segitiga ( $3$ simpul, semua pasangannya terhubung), $M = \begin{pmatrix} 0&1&1\\ 1&0&1\\ 1&1&0\end{pmatrix}$ dan $M^2 = \begin{pmatrix} 2&1&1\\ 1&2&1\\ 1&1&2\end{pmatrix}$ : jadi dari tiap simpulnya ada $2$ jalan sepanjang $2$ yang kembali ke dirinya (lewat salah satu tetangganya) dan $1$ jalan ke tiap simpul lainnya.

30.4 Latihan

Latihan 30.1 ★

Misalkan $A = \begin{pmatrix} 1 & 2\\ 0 & 1 \end{pmatrix}$ dan $B = \begin{pmatrix} 2 & 0\\ 1 & 1 \end{pmatrix}$ . Hitunglah $A + B$ , $AB$ , $BA$ dan $A^2$ .

Solusi

Solusi Latihan 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}.

Perhatikan bahwa $AB \neq BA$ .

Latihan 30.2 ★

Tentukan apakah matriks berikut dapat dibalik, lalu hitunglah balikannya jika ada:

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

Solusi

Solusi Latihan 30.2.

$\det A = 6 - 5 = 1 \neq 0$ : $A^{-1} = \begin{pmatrix} 3 & -5\\ -1 & 2 \end{pmatrix}$ . $\det B = 12 - 12 = 0$ : jadi $B$ tak dapat dibalik.

Latihan 30.3 ★

Selesaikan lewat pembalikan matriks sistem $\begin{cases} 2x + 5y = 1\\ x + 3y = 2 . \end{cases}$

Solusi

Solusi Latihan 30.3.

Sistemnya adalah $AX = Y$ dengan $A$ seperti pada Latihan 30.2 dan $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 .

Latihan 30.4 ★★

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

Periksalah bahwa $N^2 = 0$ dan bahwa $I$ dan $N$ komutatif.
Simpulkan $A^k$ untuk semua $k \in \N$ lalu periksalah rumusnya untuk $k=2$ lewat perhitungan langsung.

Solusi

Solusi Latihan 30.4.

1. $N^2 = \begin{pmatrix} 0&1\\0&0\end{pmatrix} \begin{pmatrix} 0&1\\0&0\end{pmatrix} = 0$ , dan $I$ komutatif dengan setiap matriks.

2. Karena kedua sukunya komutatif, teorema binomial berlaku dan semua suku yang memuat $N^2$ lenyap:

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

Periksalah untuk $k = 2$ : $A^2 = \begin{pmatrix} 2&1\\0&2\end{pmatrix}^2 = \begin{pmatrix} 4&4\\0&4\end{pmatrix}$ , dan rumusnya memberi $2^2 = 4$ , $2 \times 2 = 4$ . ✓

Latihan 30.5 ★★

Misalkan $A = \begin{pmatrix} 0 & 1\\ 1 & 1\end{pmatrix}$ dan $F_n$ barisan Fibonacci ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+2} = F_{n+1} + F_n$ ). Tunjukkan lewat induksi bahwa untuk $n \geq 1$ ,

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

lalu simpulkan identitas $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ . (Petunjuk: determinan saling mengalikan: $\det(MN) = \det M \det N$ , dan itu boleh kamu periksa untuk matriks $2\times2$ .)

Solusi

Solusi Latihan 30.5.

Induksinya. Untuk $n = 1$ : $A^1 = \begin{pmatrix} 0&1\\1&1\end{pmatrix} = \begin{pmatrix} F_0 & F_1\\ F_1 & F_2\end{pmatrix}$ . Andaikan rumusnya benar untuk $n$ ; maka

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

Identitasnya. Untuk matriks $2\times2$ , penjabarannya menunjukkan $\det(MN) = \det M \det N$ ; karena itu $\det(A^n) = (\det A)^n = (-1)^n$ , sedangkan $\det A^n = F_{n-1}F_{n+1} - F_n^2$ . (Inilah identitas Cassini.)

Latihan 30.6 ★★

Sebuah graf berarah pada simpul $\{1, 2, 3\}$ mempunyai sisi $1\to2$ , $2\to3$ , $3\to1$ dan $1\to3$ .

Tulislah matriks ketetanggaannya $M$ lalu hitung $M^2$ dan $M^3$ .
Ada berapa jalan sepanjang $3$ dari $1$ ke $1$ ? Daftarkanlah.

Solusi

Solusi Latihan 30.6.

1. Dengan mengurutkan simpul $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$ : jadi tepat ada satu jalan tertutup sepanjang $3$ di simpul $1$ , yaitu $1 \to 2 \to 3 \to 1$ . (Jalan $1 \to 3 \to 1$ hanya sepanjang $2$ , sedangkan $1 \to 3$ lalu $3\to1$ lalu $1\to3$ berakhir di $3$ .)

Latihan 30.7 ★★

Sebuah perusahaan berbagi mobil memindahkan kendaraan antara dua kota $A$ dan $B$ . Tiap pekan, $80\%$ mobil di $A$ tinggal di $A$ dan $20\%$ pindah ke $B$ ; lalu $30\%$ mobil di $B$ pindah ke $A$ dan $70\%$ tinggal. Misalkan $a_n, b_n$ adalah bagian armadanya di tiap kota.

Tulislah $X_{n+1} = MX_n$ dengan $X_n = \begin{pmatrix} a_n\\ b_n\end{pmatrix}$ lalu kenalilah $M$ .
Carilah bagian yang setimbang (selesaikan $MX = X$ dengan $a + b = 1$ ).
Tunjukkan bahwa $c_n = a_n - 0.6$ memenuhi $c_{n+1} = 0.5\,c_n$ , lalu simpulkan bahwa distribusi armadanya menuju kesetimbangan itu.

Solusi

Solusi Latihan 30.7.

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

2. $MX = X$ memberi $0.8a + 0.3b = a$ , yaitu $0.3b = 0.2a$ , sehingga $b = \frac23 a$ ; lalu dengan $a + b = 1$ : $a = 0.6$ , $b = 0.4$ .

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

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 .

Jadi $c_n = 0.5^n c_0 \to 0$ : maka $a_n \to 0.6$ dan $b_n \to 0.4$ , berapa pun distribusi awalnya.

Latihan 30.8 ★★★

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

Hitunglah $P^{-1}$ , lalu $D = P^{-1}AP$ , dan periksalah bahwa $D$ diagonal.
Simpulkan rumus tertutup bagi $A^n$ lalu bandingkan dengan Contoh 30.10.

Solusi

Solusi Latihan 30.8.

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

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. Dari $A = PDP^{-1}$ , induksi yang langsung memberi $A^n = PD^nP^{-1}$ dengan $D^n = \begin{pmatrix} 4^n & 0\\ 0 & 2^n\end{pmatrix}$ , sehingga

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

Menerapkan $A^n$ pada $X_0 = \begin{pmatrix} u_0\\v_0\end{pmatrix}$ menghasilkan kembali persis rumus pada Contoh 30.10.

30.5 Soal: Matriks yang hafal Fibonacci (dan cuaca)

Soal 30.1

Soal akhir pekan — satu matriks $2 \times 2$ memikul seluruh Fibonacci, sebuah matriks Markov meramal cuaca jangka panjang, dan sebuah vektor eigen bernilai semiliar dolar

Matriks adalah mesin yang memakan sebuah keadaan lalu mengembalikan keadaan berikutnya — dan pangkatnya karena itu menyimpan seluruh masa depan. Soal ini dibuka dengan matriks mencengangkan yang pangkatnya mendaftar bilangan Fibonacci (dan membuktikan identitasnya masing-masing satu baris), lalu menjalankan cuaca sebagai rantai Markov sampai keadaan mapannya, dan ditutup dengan vektor eigen yang di atasnya sebuah mesin pencari dibangun (Teorema 30.12, Metode 30.9).

Bagian I — Kelancaran.

Dengan $A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ dan $B = \begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$ : hitunglah $AB$ dan $BA$ . Vonis atas kekomutatifannya?
Baliklah $\begin{pmatrix} 2 & 1\\ 5 & 3\end{pmatrix}$ (Proposisi 30.6) lalu pakailah balikannya untuk menyelesaikan $2x + y = 4$ , $5x + 3y = 7$ .
Misalkan $N = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : hitunglah $N^2$ , lalu simpulkan $(I + N)^n = I + nN$ untuk setiap $n$ .
Graf segitiga (tiga simpul, semua pasangannya terhubung): tulislah matriks ketetanggaannya $A$ , hitunglah $A^3$ , lalu tafsirkan isian diagonalnya (Teorema 30.12).
Untuk $D = \begin{pmatrix} 2 & 0\\ 0 & \frac12 \end{pmatrix}$ : berikan $D^n$ dan perilakunya ketika $n \to \infty$ .

Bagian II — Matriks Fibonacci. Misalkan $F = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ dan misalkan $F_1 = F_2 = 1, F_3 = 2, \dots$ adalah bilangan Fibonacci pada Soal 13.1.

Hitunglah $F^2$ , $F^3$ , $F^4$ lalu terkalah bentuk umum $F^n$ dengan bilangan Fibonacci.
Buktikan terkaan $F^n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$ itu lewat induksi.
Ambillah determinan kedua ruasnya (determinan hasil kali adalah hasil kali determinannya — periksalah pada matriks $2 \times 2$ jika kamu belum pernah melihatnya): lalu simpulkan identitas Cassini $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$ — yaitu mesin kuadrat yang lenyap itu, yang terbukti dalam satu baris.
Dari $F^{m+n} = F^m F^n$ , bacalah isian kanan atasnya lalu turunkan rumus penjumlahannya

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

Periksalah untuk $m = n = 3$ .
Simpulkan dari rumus penjumlahan itu (lewat induksi pada $k$ ) bahwa $F_n$ membagi $F_{kn}$ , lalu periksalah pada $F_3 \mid F_6$ dan $F_3 \mid F_9$ .
Untuk menghitung $F_{100}$ , orang tak perlu mengalikan $100$ matriks: kuadratkanlah berulang kali ( $F^2, F^4, F^8, \dots$ ) lalu gabungkan. Berapa kali perkalian matriks yang cukup, dan muslihat perkalian kuno mana dari jilid sekolah menengah pertama yang ini, yang kini naik pangkat ke matriks?

Bagian III — Mesin cuaca. Di sebuah kota: sesudah hari yang cerah, hari berikutnya cerah dengan peluang $0.8$ ; sesudah hari yang hujan, cerah dengan peluang $0.4$ . Sandikan distribusi harinya sebagai satu kolom $\binom{p_{\text{cerah}}}{p_{\text{hujan}}}$ dan perubahannya oleh

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

Periksalah bahwa tiap kolom $M$ berjumlah $1$ , lalu katakan mengapa setiap mesin cuaca harus punya sifat itu.
Hari ini cerah. Hitunglah ramalan untuk besok dan untuk lusa.
Carilah keadaan mapannya: yaitu distribusi $v$ dengan $Mv = v$ (dan isiannya berjumlah $1$ ). Berapa bagian harinya yang cerah dalam jangka panjang?
Mulailah dari hari hujan, $\binom01$ , lalu terapkan $M$ empat kali, sambil melacak jaraknya ke keadaan mapan pada tiap langkahnya. Dengan faktor berapa jurangnya menyusut tiap langkah — dan kekonvergenan macam apa ini?
PageRank dalam ukuran mini: tiga halaman, dengan tautan $A \to B$ , $A \to C$ , $B \to C$ , $C \to A$ . Seorang peselancar acak mengikuti tautan keluar secara acak seragam. Tulislah matriks peralihannya, carilah keadaan mapannya, lalu peringkatkan halamannya.
Tafsirkan peringkatnya: mengapa $C$ bernilai setinggi $A$ padahal menerima tautan dari lebih sedikit halaman — apa yang sebenarnya diukur keadaan mapan itu? (PageRank yang sungguhan menambahkan faktor peredam untuk jalan buntu dan lompatan; gagasan vektor eigennya tepat yang ini.)

Bagian IV — Untung dari diagonalnya.

Dua besaran yang berpasangan menuruti $u_{n+1} = 3u_n + v_n$ , $v_{n+1} = u_n + 3v_n$ , yaitu matriks $A$ pada Latihan 30.8. Dengan memakai pendiagonalan latihan itu ( $D = \operatorname{diag}(4, 2)$ ), berikan rumus tertutup bagi $u_n$ ketika $u_0 = 1$ , $v_0 = 0$ , lalu periksalah terhadap perhitungan langsung untuk $n = 1, 2, 3$ .
Dalam satu atau dua kalimat: apa yang dilakukan pendiagonalan terhadap sistem yang berpasangan — dan dalam arti apa keadaan mapan Markov pada pertanyaan 14 juga sebuah kisah vektor eigen?
Penutup — tiga wajah matriks pada akhir pekan ini: pembukuan (sistem dan balikan), kombinatorika (jalan dan tautan yang tercacah oleh pangkatnya), dan perubahan (Fibonacci, cuaca, jejaring — masa depan yang terbaca dari arah eigennya). Masing-masing satu kalimat, ditambah penunjuk ke depan: aljabar linear di jilid universitas menjadikan tiap wajah itu sebuah teori.

Solusi

Solusi Soal 30.1.

1. $AB = \begin{pmatrix} 2 & 1\\ 4 & 3\end{pmatrix}$ dan $BA = \begin{pmatrix} 3 & 4\\ 1 & 2\end{pmatrix}$ : jadi perkalian matriks tidak komutatif — $B$ menukar kolom bila di kanan, dan menukar baris bila di kiri.

2. Determinannya $6 - 5 = 1$ , jadi balikannya $\begin{pmatrix} 3 & -1\\ -5 & 2\end{pmatrix}$ . Dengan menerapkannya pada $\binom{4}{7}$ : $x = 12 - 7 = 5$ , $y = -20 + 14 = -6$ .

3. $N^2 = 0$ . Maka $(I + N)^n = I + nN$ lewat induksi: $(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}$ , dan $A^3$ berisian diagonal $2$ : jadi dari tiap simpulnya ada tepat dua jalan tertutup sepanjang $3$ (segitiganya ditempuh searah atau berlawanan arah jarum jam) — teorema pencacahan itu sedang beraksi.

5. $D^n = \begin{pmatrix} 2^n & 0\\ 0 & 2^{-n} \end{pmatrix}$ : satu arahnya meledak, arah lainnya mati — nasib diagonalnya adalah barisan ukur yang saling bebas.

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}$ : Fibonacci di mana-mana; terkaannya seperti yang dinyatakan.

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

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

itulah pewarisannya; sedangkan kasus dasarnya $n = 1$ adalah $F$ sendiri, dengan memakai kesepakatan $F_0 = 0$ (yang memperluas rekurensinya ke belakang).

8. $\det F = -1$ , jadi $\det(F^n) = (\det F)^n = (-1)^n$ ; dan secara langsung $\det(F^n) = F_{n+1}F_{n-1} - F_n^2$ : itulah Cassini, dalam satu baris. (Kaidah hasil kali bagi determinan $2 \times 2$ adalah penjabaran lima menit yang menyenangkan.)

9. Kanan atas $F^m F^n$ : $F_{m+1}F_n + F_m F_{n-1}$ ; kanan atas $F^{m+n}$ : $F_{m+n}$ . Untuk $m = n = 3$ : $F_4 F_3 + F_3 F_2 = 3 \times 2 + 2 \times 1 = 8 = F_6$ .

10. Untuk $k = 1$ : sepele. Jika $F_n \mid F_{kn}$ , maka rumus penjumlahannya dengan $m = kn$ memberi $F_{(k+1)n} = F_{kn+1}F_n + F_{kn}F_{n-1}$ : kedua sukunya kelipatan $F_n$ . Jadi $F_n \mid F_{kn}$ untuk semua $k$ : periksalah bahwa $F_3 = 2$ membagi $F_6 = 8$ dan $F_9 = 34$ .

11. $F^{100} = F^{64} F^{32} F^4$ : yaitu tujuh kali pengkuadratan ( $F^2, F^4, \dots, F^{64}$ ) ditambah dua penggabungan — sembilan kali perkalian, bukan sembilan puluh sembilan. Inilah muslihat tabel pelipatduaan para juru tulis Mesir, yang diangkat dari bilangan ke matriks: tulislah $100$ dalam biner, lalu kalikan pelipatduaan yang kamu perlukan.

12. $0.8 + 0.2 = 1$ dan $0.4 + 0.6 = 1$ : besok haruslah suatu cuaca — tiap kolomnya adalah distribusi peluang yang lengkap, sehingga peluangnya kekal.

13. Besok: $\binom{0.8}{0.2}$ . Lusa: $M\binom{0.8}{0.2} = \binom{0.72}{0.28}$ .

14. $Mv = v$ dengan $v = \binom{s}{r}$ , $s + r = 1$ : maka $0.8s + 0.4r = s$ memberi $0.4r = 0.2s$ , jadi $s = 2r$ dan $v = \binom{2/3}{1/3}$ . Dalam jangka panjang, dua hari dari tiga hari cerah — bagaimanapun rupa hari ini.

15. Dari $\binom01$ : komponen cerahnya $0.4$ , $0.56$ , $0.624$ , $0.6496$ ; jurangnya terhadap $\frac23$ : $0.267$ , $0.107$ , $0.043$ , $0.017$ — jadi tiap langkahnya mengalikan jurangnya tepat dengan $0.4$ (yaitu nilai eigen kedua mesinnya): kekonvergenan ukur menuju keadaan mapannya.

16. Kolomnya (dari $A$ , $B$ , $C$ ): $P = \begin{pmatrix} 0 & 0 & 1\\ \frac12 & 0 & 0\\ \frac12 & 1 & 0\end{pmatrix}$ . Keadaan mapannya: $v_A = v_C$ , $v_B = \frac{v_A}{2}$ , $v_C = \frac{v_A}{2} + v_B$ ; lalu dengan berjumlah $1$ : $v = \left(\frac25, \frac15, \frac25\right)$ . Peringkatnya: $A$ dan $C$ seri di tempat pertama, $B$ terakhir.

17. Halaman $C$ menerima seluruh lalu lintas $B$ dan separuh milik $A$ , lalu menyalurkan semuanya kembali ke $A$ : keadaan mapannya mengukur di mana sang peselancar menghabiskan waktunya, bukan berapa banyak tautan yang menunjuk masuk — satu tautan dari halaman populer mengalahkan beberapa tautan dari halaman sepi. Pembobotan rekursif itu justru gagasan pendiri Google; peredamnya mengurus perangkap laba-laba dan jalan buntu.

18. $A^n = P D^n P^{-1}$ memberi $u_n = \frac{4^n + 2^n}{2}$ (dan $v_n = \frac{4^n - 2^n}{2}$ ). Periksalah: $u_1 = 3$ , $u_2 = 10$ , $u_3 = 36$ ; sedangkan secara langsung: $(1,0) \to (3,1) \to (10,6) \to (36, 28)$ , jadi cocok.

19. Pendiagonalan mengganti ke koordinat yang membuat sistem berpasangan itu terurai menjadi barisan ukur yang saling bebas — tiap nilai eigennya berlari dalam lombanya sendiri. Keadaan mapan Markov adalah vektor eigen dengan nilai eigen $1$ , dan laju kekonvergenan pada pertanyaan 15 adalah nilai eigen berikutnya: jadi mesin cuaca itu sejak awal sebuah kisah eigen.

20. Pembukuan: satu sistem adalah satu persamaan matriks, yang diselesaikan oleh satu balikan. Kombinatorika: pangkat matriks ketetanggaan mencacah jalan, tautan, dan hubungan. Perubahan: pangkat mesinnya membawa keadaan menuju nasibnya, dan arah eigennya (yaitu arah emas milik Fibonacci, keadaan mapan cuaca, vektor peringkat milik jejaring) adalah nasib itu sendiri. Aljabar linear, di jilid universitas, adalah ilmu tentang justru hal ini.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium