Matematika Universitas — Tahun 2 · Bachelor Year 2

3Reduksi Endomorfisma

Untuk memahami sebuah endomorfisma, carilah arah yang sekadar diregangkannya. Bab ini membangun perkakasnya — nilai eigen, polinomial karakteristik dan polinomial minimal, lema penguraian kernel — beserta ganjarannya: kriteria diagonalisasi dan trigonalisasi, Cayley–Hamilton, penguraian Dunford, serta perhitungan pangkat dan eksponensial yang kelak menjadi santapan Bab 16. Di sepanjang bab ini, $E$ adalah ruang vektor atas $K$ yang berdimensi hingga ( $K = \R$ atau $\C$ ) dan $u \in \mathcal{L}(E)$ , $n = \dim E$ .

3.1 Nilai eigen dan vektor eigen

Definisi 3.1

$\lambda \in K$ disebut nilai eigen bagi $u$ apabila $u(x) = \lambda x$ untuk suatu $x \neq 0$ (vektor semacam itu disebut vektor eigen); ruang eigennya adalah $E_\lambda(u) = \ker(u - \lambda\,\mathrm{id})$ . Himpunan semua nilai eigen disebut spektrum $\operatorname{Sp}(u)$ . Sebuah subruang $F$ disebut stabil apabila $u(F) \subseteq F$ ; ruang eigen bersifat stabil, dan subruang stabil memungkinkan endomorfisma imbasan $u|_F$ .

Teorema 3.2 (Kebebasan ruang eigen)

Vektor eigen yang berkaitan dengan nilai eigen yang berbeda sepasang demi sepasang membentuk keluarga bebas; setara dengan itu, jumlah ruang eigen $E_{\lambda_1} + \dots + E_{\lambda_r}$ (dengan $\lambda_i$ yang berbeda) bersifat langsung. Khususnya $u$ punya paling banyak $n$ nilai eigen.

Bukti. Dengan induksi pada $r$ . Andaikan $x_1 + \dots + x_r = 0$ dengan $x_i \in E_{\lambda_i}$ , sedangkan pernyataannya sudah diketahui untuk $r - 1$ . Terapkan $u$ lalu kurangkan $\lambda_r$ kali kaitan itu:

\sum_{i=1}^{r-1} (\lambda_i - \lambda_r)\, x_i = 0 ,

jadi menurut induksi setiap $(\lambda_i - \lambda_r)x_i = 0$ , yakni $x_i = 0$ untuk $i < r$ , lalu $x_r = 0$ . Jumlah langsung atas ruang tak nol di dalam ruang berdimensi $n$ paling banyak punya $n$ suku. ∎

Matriks A = psmallmatrix2 & 1\\ 1 & 2 psmallmatrix yang bekerja pada bidang: vektor umum e_1 terpental dari garisnya, sedangkan arah eigen v_1 = (1,1) dan v_2 = (1,-1) sekadar diregangkan — masing-masing oleh 3 dan oleh 1 (jadi Av_2 = v_2: peta putus-putusnya berimpit dengan v_2). Diagonalisasi tak lain pergantian ke basis (v_1, v_2), tempat A menjadi diag(3, 1). — Matriks $A = \left(\begin{smallmatrix}2 & 1\\ 1 & 2\end{smallmatrix}\right)$ yang bekerja pada bidang: vektor umum $e_1$ terpental dari garisnya, sedangkan arah eigen $v_1 = (1,1)$ dan $v_2 = (1,-1)$ sekadar diregangkan — masing-masing oleh $3$ dan oleh $1$ (jadi $Av_2 = v_2$ : peta putus-putusnya berimpit dengan $v_2$ ). Diagonalisasi tak lain pergantian ke basis $(v_1, v_2)$ , tempat $A$ menjadi $\operatorname{diag}(3, 1)$ .

Definisi 3.3 (Polinomial karakteristik)

$\chi_u(X) = \det(X\,\mathrm{id} - u)$ — yang dihitung pada basis mana pun sebagai $\det(XI_n - A)$ , sebuah polinomial monik berderajat $n$ yang awet terhadap keserupaan (Teorema 2.17). Akarnya di $K$ persis semua nilai eigen ( $\lambda$ nilai eigen $\iff u - \lambda\,\mathrm{id}$ tidak injektif $\iff \chi_u(\lambda) = 0$ ), dan

\chi_u(X) = X^n - (\operatorname{tr} u)\, X^{n-1} + \dots + (-1)^n \det u .

Multiplisitas aljabar $m_\lambda$ sebuah nilai eigen adalah multiplisitasnya sebagai akar $\chi_u$ ; sedangkan multiplisitas geometrik adalah $\dim E_\lambda$ , dan $1 \leq \dim E_\lambda \leq m_\lambda$ .

Bukti fakta yang dinyatakan. Tentang koefisiennya: uraikan $\det(XI - A)$ dengan rumus permutasi; permutasi identitas menyumbang $\prod_i (X - a_{ii}) = X^n - (\sum a_{ii})X^{n-1} + \dots$ , sedangkan setiap permutasi lain membiarkan tetap paling banyak $n - 2$ kedudukan diagonal, sehingga menyumbang derajat $\leq n - 2$ : jadi dua koefisien teratasnya seperti dinyatakan; lalu $X = 0$ memberi suku tetap $\det(-A) = (-1)^n\det A$ .

Geometrik $\leq$ aljabar: misalkan $d = \dim E_\lambda$ lalu lengkapi basis $E_\lambda$ menjadi basis $E$ ; matriks $u$ menjadi segitiga atas berblok dengan blok kiri atas $\lambda I_d$ , sehingga $\chi_u(X) = (X - \lambda)^d\, \chi_{\text{(blok bawah)}}(X)$ : jadi multiplisitas $\lambda$ sedikitnya $d$ . ∎

Contoh 3.4 ( $\chi$ yang sama, geometri yang berbeda)

Kedua matriks

\begin{pmatrix}2 & 0\\ 0 & 2\end{pmatrix} \qquad\text{dan}\qquad \begin{pmatrix}2 & 1\\ 0 & 2\end{pmatrix}

berbagi polinomial karakteristik $(X - 2)^2$ , trace, determinan, dan spektrum — namun keduanya tidak serupa: yang pertama punya $E_2$ berdimensi $2$ (multiplisitas geometrik $2$ ), yang kedua berdimensi $1$ . Polinomial karakteristik hanya melihat multiplisitas aljabar; dimensi ruang eigen adalah invarian yang lebih halus, dan polinomial minimal yang memutuskan ( $X - 2$ lawan $(X - 2)^2$ ). Pelajaran bagi semua pembahasan tentang keterdiagonalan: $\chi$ menyaring calonnya, tetapi kernel yang memberikan suara.

Definisi 3.5 (Dapat didiagonalkan, dapat ditrigonalkan)

$u$ disebut dapat didiagonalkan apabila $E$ punya basis berisi vektor eigen (untuk matriks: serupa dengan matriks diagonal); dan dapat ditrigonalkan apabila matriksnya pada suatu basis berupa segitiga atas.

Teorema 3.6 (Kriteria keterdiagonalan)

Pernyataan berikut setara:

$u$ dapat didiagonalkan;
$E = \bigoplus_{\lambda \in \operatorname{Sp} u} E_\lambda$ ;
$\chi_u$ terurai lengkap atas $K$ dan $\dim E_\lambda = m_\lambda$ untuk setiap nilai eigen;
(syarat cukup, bukan syarat perlu) $\chi_u$ punya $n$ akar berbeda di $K$ .

Bukti. (1 $\iff$ 2): sebuah basis berisi vektor eigen tersortir menjadi basis tiap $E_\lambda$ , dan sebaliknya menyambung basis suku-suku jumlah langsungnya memberi basis $E$ (Teorema 3.2 membuat jumlahnya langsung; kesamaan dimensi membuatnya seluruh ruang).

(2 $\iff$ 3): pada basis diagonalnya, $\chi_u = \prod (X - \lambda)^{\dim E_\lambda}$ terurai lengkap dengan multiplisitas yang cocok. Sebaliknya, andaikan $\chi_u$ terurai lengkap dengan $\dim E_\lambda = m_\lambda$ di mana-mana; maka jumlah langsung ruang eigennya (langsung menurut Teorema 3.2) berdimensi

\sum_{\lambda}\dim E_\lambda = \sum_{\lambda} m_\lambda = \deg\chi_u = n ,

sebab kesamaan di tengah berlaku karena derajat polinomial yang terurai lengkap sama dengan jumlah multiplisitas akarnya: jadi jumlahnya seluruh $E$ . Perhatikan tempat tiap hipotesis bekerja: keteruraiannya mengisi derajatnya, kesamaan multiplisitasnya mengisi dimensinya.

(4 $\Rightarrow$ 1): $n$ nilai eigen yang berbeda memberi $n$ vektor eigen yang bebas (Teorema 3.2), yakni sebuah basis. ∎

Metode 3.7 (Memutuskan keterdiagonalan)

Dalam praktik, ujilah dengan urutan berikut — tiap langkahnya bisa saja langsung merampungkan pekerjaan. (1) Adakah polinomial penganihilasi berakar sederhana dan terurai lengkap yang langsung tampak ( $u^2 = \mathrm{id}$ , $u^2 = u$ , $u^k = \mathrm{id}$ )? Jika ada: dapat didiagonalkan, tanpa perhitungan (Akibat 3.17 di bawah). (2) Hitung $\chi_u$ ; jika ia punya $n$ akar berbeda di $K$ : dapat didiagonalkan (Teorema 3.6 (4)). (3) Jika tidak, hanya untuk tiap akar berulang $\lambda$ , bandingkan $\dim\ker(u - \lambda\,\mathrm{id})$ dengan multiplisitas $m_\lambda$ : kekurangan sekecil apa pun mematikan keterdiagonalannya, sedangkan kesamaan di mana-mana membuktikannya. Jangan pernah menghitung ruang eigen akar sederhana (dimensinya sudah pasti $1$ ), dan jangan pernah mentrigonalkan hanya untuk memutuskan.

Contoh 3.8 (Diagonalisasi dalam kerja)

Ambil $A = I + J = \left(\begin{smallmatrix}2 & 1 & 1\\ 1 & 2 & 1\\ 1 & 1 & 2\end{smallmatrix}\right)$ , dengan $J$ matriks yang semua unsurnya satu: dari $\operatorname{Sp}(J) = \{3, 0\}$ (Contoh 2.19) diperoleh $\operatorname{Sp}(A) = \{4, 1\}$ , dengan ruang eigen $\R(1,1,1)$ dan bidang $\{x + y + z = 0\}$ : dimensinya $1 + 2 = 3$ , jadi dapat didiagonalkan (Teorema 3.6 (2)). Pangkatnya pun terhitung tanpa matriks pergantian basis: dengan $\Pi = J/3$ sebagai proyektor pada $\R(1,1,1)$ ,

A = 4\,\Pi + 1\cdot(I - \Pi) \quad\Longrightarrow\quad A^k = 4^k\,\Pi + (I - \Pi) = \frac{4^k - 1}{3}\,J + I .

(Periksa $k = 1$ : $\frac{4-1}3 J + I = A$ .) Pelajaran penutupnya: ketika ruang eigennya kasatmata, proyektor spektral menghitung pangkat lebih cepat daripada $PDP^{-1}$ mana pun — dan rumusnya memperlihatkan dinamikanya: $A^k$ tumbuh seperti $4^k$ sepanjang $(1,1,1)$ dan diam saja pada bidang ortogonalnya.

Teorema 3.9 (Trigonalisasi)

$u$ dapat ditrigonalkan atas $K$ bila dan hanya bila $\chi_u$ terurai lengkap atas $K$ . Khususnya setiap endomorfisma ruang vektor atas $\C$ dapat ditrigonalkan.

Bukti. ( $\Rightarrow$ ) Polinomial karakteristik sebuah matriks segitiga adalah $\prod(X - t_{ii})$ : terurai lengkap.

( $\Leftarrow$ ) Induksi pada $n$ . Karena $\chi_u$ terurai lengkap, ia punya akar $\lambda$ : pilihlah vektor eigen $e_1$ . Pada basis yang diawali $e_1$ , matriksnya menjadi $\begin{pmatrix} \lambda & \ast\\ 0 & B\end{pmatrix}$ , dan $\chi_u = (X - \lambda)\chi_B$ : jadi $\chi_B$ pun terurai lengkap. Menurut hipotesis induksi yang diterapkan pada matriks berukuran $(n-1) \times (n-1)$ , yakni $B$ , ada $Q$ berinvers dengan $Q^{-1}BQ$ segitiga atas; mengonjugasikan seluruh matriks itu dengan $\begin{pmatrix}1 & 0\\ 0 & Q\end{pmatrix}$ membuatnya segitiga. ∎

Contoh 3.10 (Mentrigonalkan dengan tangan)

Ambil $B = \begin{pmatrix}3 & -1\\ 1 & 1\end{pmatrix}$ : di sini $\chi_B = X^2 - 4X + 4 = (X - 2)^2$ , dan $\ker(B - 2I) = \ker\left(\begin{smallmatrix}1 & -1\\ 1 & -1\end{smallmatrix}\right)$ adalah garis yang direntang $e_1' = (1, 1)$ : satu nilai eigen dengan ruang eigen berdimensi satu — jadi tidak dapat didiagonalkan, tetapi dapat ditrigonalkan (Teorema 3.9). Lengkapi basisnya dengan $e_2' = (1, 0)$ lalu hitung:

u(e_1') = (2, 2) = 2e_1', \qquad u(e_2') = (3, 1) = 1\cdot e_1' + 2\, e_2' ,

sehingga pada basis $(e_1', e_2')$ matriksnya menjadi $T = \left(\begin{smallmatrix}2 & 1\\ 0 & 2\end{smallmatrix}\right)$ . Pelajaran penutupnya: diagonal $T$ sudah terpaksa (kedua unsurnya wajib berupa nilai eigen ganda $2$ ); hanya unsur pojoknya yang bergantung pada pilihan $e_2'$ , dan menskalakan $e_2'$ dapat membuatnya bernilai tak nol apa pun — “ $1$ ” yang membandel itu adalah bayangan bagian nilpoten yang kelak dipisahkan Dunford.

3.2 Polinomial sebuah endomorfisma

Definisi 3.11

Untuk $P = \sum a_k X^k \in K[X]$ , tetapkan $P(u) = \sum a_k u^k \in \mathcal{L}(E)$ . Pemetaan $P \mapsto P(u)$ adalah morfisma aljabar $K[X] \to \mathcal{L}(E)$ (Definisi 1.33); kernelnya $\{P : P(u) = 0\}$ merupakan ideal $K[X]$ yang tak nol (sebab keluarga $(\mathrm{id}, u, \dots, u^{n^2})$ saling terkait di dalam ruang berdimensi $n^2$ , yaitu $\mathcal{L}(E)$ ), jadi ia dibangun oleh sebuah polinomial monik tunggal $\mu_u$ : itulah polinomial minimal (Teorema 1.26).

Proposisi 3.12

$P(u) = 0 \iff \mu_u \mid P$ ; nilai eigen $u$ adalah akar setiap polinomial penganihilasi, dan akar $\mu_u$ persis semua nilai eigen.
Jika $F$ stabil, maka $\mu_{u|_F} \mid \mu_u$ .

Bukti. (1) Keterbagiannya tak lain definisi sebuah pembangun. Jika $u(x) = \lambda x$ dengan $x \neq 0$ , maka $0 = P(u)(x) = P(\lambda)x$ , jadi $P(\lambda) = 0$ : nilai eigen adalah akar polinomial penganihilasi, khususnya akar $\mu_u$ . Sebaliknya, jika $\lambda$ sebuah akar, maka $\mu_u = (X - \lambda)Q$ dengan $Q(u) \neq 0$ (sebab derajat $\mu_u$ minimal): pilih $y$ dengan $Q(u)(y) \neq 0$ ; maka $(u - \lambda)(Q(u)(y)) = \mu_u(u)(y) = 0$ memperlihatkan vektor eigen $Q(u)(y)$ .

(2) Kita punya $\mu_u(u|_F) = \mu_u(u)|_F = 0$ , lalu terapkan (1) pada $u|_F$ . ∎

Contoh 3.13 (Polinomial minimal yang dicari dengan tangan)

Polinomial minimal dihitung dengan menguji derajat berturut-turut. Untuk matriks $J \in \mathcal{M}_3(\R)$ yang semua unsurnya satu: $J \neq \lambda I$ (jadi derajat $1$ tersingkir), dan $J^2 = 3J$ , sehingga

\mu_J = X^2 - 3X = X(X - 3) :

derajatnya $2$ , terurai lengkap, berakar sederhana — jadi $J$ dapat didiagonalkan dengan spektrum $\{0, 3\}$ (Akibat 3.17 di bawah), yang menegaskan Contoh 2.19 tanpa satu pun determinan. Untuk matriks penukar $A$ pada Contoh 3.15: dari $A \neq \pm I$ dan $A^2 = I$ diperoleh $\mu_A = X^2 - 1$ . Pada kedua kasus polanya sama: tebaklah kesamaan berderajat rendah dari strukturnya (rank satu memaksa $J^2 = (\operatorname{tr}J)\,J$ ; sebuah involusi memaksa $A^2 = I$ ), lalu periksa bahwa tak ada pembagi sejatinya yang menganihilasi. Polinomial minimal biasanya ditemukan, bukan dihitung dari $\chi$ .

Teorema 3.14 (Lema penguraian kernel)

Jika $P = P_1 P_2 \cdots P_r$ dengan $P_i$ saling prima sepasang demi sepasang, maka

\ker P(u) = \ker P_1(u) \oplus \dots \oplus \ker P_r(u),

dan proyeksi pada tiap sukunya berupa polinomial dalam $u$ .

Bukti. Cukuplah menangani $r = 2$ lalu berinduksi. Bézout di $K[X]$ (Teorema 1.26) memberi $U P_1 + V P_2 = 1$ , sehingga untuk setiap $x$ ,

x = \underbrace{U(u)P_1(u)(x)}_{=:\,x_2} + \underbrace{V(u)P_2(u)(x)}_{=:\,x_1}.

Jika $x \in \ker P(u)$ : maka $P_2(u)(x_2) = U(u)\,P(u)(x) = 0$ (polinomial dalam $u$ saling komutatif), jadi $x_2 \in \ker P_2(u)$ , dan setangkup dengan itu $x_1 \in \ker P_1(u)$ : jadi jumlahnya mengisi $\ker P(u)$ ; kedua sukunya berada di dalam $\ker P(u)$ (sebab $P_i \mid P$ ). Kelangsungannya: $x \in \ker P_1(u) \cap \ker P_2(u)$ memberi $x = U(u)P_1(u)x + V(u)P_2(u)x = 0$ . Rumus untuk $x_1, x_2$ tadi memperlihatkan proyeksinya sebagai $V(u)P_2(u)$ dan $U(u)P_1(u)$ . ∎

Contoh 3.15 (Lema kernel dengan proyektor yang gamblang)

Misalkan $A = \left(\begin{smallmatrix}0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1\end{smallmatrix}\right)$ (yang menukar dua koordinat pertama). Maka $A^2 = I$ : polinomial $X^2 - 1 = (X - 1)(X + 1)$ menganihilasi $A$ , faktornya saling prima, dan Bézout-nya gamblang:

\frac{1}{2}(X + 1) - \frac12(X - 1) = 1 .

Dengan mengikuti bukti Teorema 3.14, proyeksi pada $\ker(A - I)$ dan $\ker(A + I)$ adalah polinomial dalam $A$ berikut:

\pi_+ = \frac{A + I}{2} = \frac12\begin{pmatrix} 1 & 1 & 0\\ 1 & 1 & 0\\ 0 & 0 & 2\end{pmatrix}, \qquad \pi_- = \frac{I - A}{2} = \frac12\begin{pmatrix} 1 & -1 & 0\\ -1 & 1 & 0\\ 0 & 0 & 0\end{pmatrix}.

Periksa: $\pi_+ + \pi_- = I$ , $\pi_+\pi_- = 0$ , $\pi_\pm^2 = \pi_\pm$ , dan petanya adalah bidang $\{x = y\}$ (vektor setangkup, bernilai eigen $1$ ) dan garis $\R(1, -1, 0)$ (antisetangkup, bernilai eigen $-1$ ). Lema kernel bukan sekadar pernyataan keberadaan: koefisien Bézout adalah rumus proyektornya.

Contoh 3.16 (Proyektor menghitung eksponensial juga)

Matriks penukar yang sama, satu panen lebih jauh. Karena $A = \pi_+ - \pi_-$ dengan proyektor yang ortogonal dalam arti aljabar ( $\pi_+\pi_- = 0$ ), setiap pangkatnya menuruti $A^k = \pi_+ + (-1)^k\pi_-$ , dan deret eksponensialnya berkelompok menurut proyektor:

\eu^{tA} = \sum_k \frac{t^k}{k!}\bigl(\pi_+ + (-1)^k\pi_-\bigr) = \eu^{t}\,\pi_+ + \eu^{-t}\,\pi_- = \begin{pmatrix} \cosh t & \sinh t & 0\\ \sinh t & \cosh t & 0\\ 0 & 0 & \eu^{t} \end{pmatrix}.

(Periksa $t = 0$ : identitasnya; turunan di $0$ : $A$ .) Penguraian eigen mengubah deret matriks menjadi dua deret skalar — dan itu persis mekanisme yang kelak dijalankan Bab 16 pada setiap sistem yang dapat didiagonalkan, sekaligus alasan mengapa fungsi hiperbolik menguasai kopling yang setangkup.

Akibat 3.17 (Keterdiagonalan lewat polinomial minimal)

$u$ dapat didiagonalkan $\iff$ $\mu_u$ terurai lengkap atas $K$ dengan akar sederhana $\iff$ ada polinomial penganihilasi $u$ yang terurai lengkap dengan akar sederhana.

Bukti. Jika $P(u) = 0$ dengan $P = \prod_{i}(X - \lambda_i)$ ( $\lambda_i$ berbeda), maka lemanya memberi $E = \ker P(u) = \bigoplus_i \ker(u - \lambda_i)$ : yakni jumlah langsung ruang eigen, jadi $u$ dapat didiagonalkan (Teorema 3.6). Sebaliknya, $u$ yang dapat didiagonalkan ditolkan oleh $\prod_{\lambda \in \operatorname{Sp}u}(X - \lambda)$ (yang menolkan tiap ruang eigen), dan polinomial itu terurai lengkap dengan akar sederhana; sedangkan $\mu_u$ membaginya sambil berakar sama (Proposisi 3.12): jadi $\mu_u$ tepat sama dengan hasil kali itu. ∎

Contoh 3.18

Proyeksi memenuhi $p^2 = p$ : ditolkan oleh $X(X-1)$ yang terurai lengkap dengan akar sederhana — jadi dapat didiagonalkan dengan spektrum $\subseteq \{0, 1\}$ , dan $E = \ker p \oplus \ker(p - \mathrm{id})$ : itulah telaah geometrik Tahun ke-1, yang dibuktikan ulang dalam satu baris. Simetri ( $s^2 = \mathrm{id}$ , dengan penganihilasi $X^2 - 1$ ) dapat didiagonalkan bila $\operatorname{char} K \neq 2$ , dengan spektrum $\subseteq \{\pm 1\}$ . Adapun endomorfisma dengan $u^3 = u^2$ dan $u^2 \neq u$ ditolkan oleh $X^2(X - 1)$ , dan tidak harus dapat didiagonalkan — kriterianya mendeteksi hal itu (akar ganda $0$ wajib diuji: dapat didiagonalkan bila dan hanya bila lagi-lagi $\ker u^2 = \ker u$ ).

Contoh 3.19 (Lapangannya yang memutuskan: sebuah rotasi di $\R^3$ )

Misalkan $R$ perputaran seperempat mengelilingi sumbu $z$ :

R = \begin{pmatrix} 0 & -1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 1 \end{pmatrix}, \qquad \chi_R = (X - 1)(X^2 + 1).

Atas $\R$ : satu-satunya nilai eigennya $1$ , dengan ruang eigen berupa sumbu $\R e_3$ — satu garis vektor tetap, dan tanpa reduksi lebih jauh: $R$ tidak dapat didiagonalkan maupun ditrigonalkan di $\mathcal{M}_3(\R)$ (sebab $\chi_R$ tidak terurai lengkap). Atas $\C$ : ada tiga nilai eigen berbeda $1, \iu, -\iu$ , jadi $R$ dapat didiagonalkan, dengan vektor eigen $e_3$ dan $e_1 \mp \iu e_2$ . Geometrinya terdengar di dalam aljabarnya: rotasi pada bidang tidak punya arah invarian yang real, dan nilai eigen kompleks $\pm\iu$ yang bermodulus $1$ menyimpan sudut ( $\pm\frac\pi2$ ) yang hanya dapat diungkapkan matriks realnya lewat pencampuran koordinat.

Contoh 3.20 (Minimal lawan karakteristik)

Untuk $D = \operatorname{diag}(2, 2, 3)$ : $\chi_D = (X - 2)^2(X - 3)$ tetapi $\mu_D = (X - 2)(X - 3)$ , sebab $(D - 2I)(D - 3I) = 0$ (periksa pada basis kanoniknya) sementara tak satu pun faktornya sendiri menolkan $D$ . Untuk blok geser $N = \left(\begin{smallmatrix}0 & 1\\ 0 & 0\end{smallmatrix}\right) \oplus (3)$ , yakni $N' = \left(\begin{smallmatrix}0 & 1 & 0\\ 0 & 0 & 0\\ 0 & 0 & 3\end{smallmatrix}\right)$ : di sini $\chi_{N'} = X^2(X - 3)$ dan $\mu_{N'} = X^2(X - 3)$ — akar gandanya sungguh diperlukan karena $N'$ tidak dapat didiagonalkan di sisi $\ker$ -nya ( $N'e_2 = e_1 \neq 0$ ). Pedoman praktis: $\mu$ dan $\chi$ berakar sama (Proposisi 3.12); multiplisitas pada $\mu$ menakar besarnya blok nilpoten terbesar, sedangkan yang pada $\chi$ menakar dimensi total subruang karakteristiknya.

Teorema 3.21 (Cayley–Hamilton)

$\chi_u(u) = 0$ ; akibatnya $\mu_u \mid \chi_u$ , dan $\deg \mu_u \leq n$ .

Bukti. Tetapkan $x \neq 0$ lalu misalkan $d$ terbesar sehingga $(x, u(x), \dots, u^{d-1}(x))$ bebas; tulis

u^d(x) = -a_0 x - a_1 u(x) - \dots - a_{d-1}u^{d-1}(x),

lalu tetapkan $P_x = X^d + a_{d-1}X^{d-1} + \dots + a_0$ , sehingga $P_x(u)(x) = 0$ . Lengkapi keluarga bebas itu menjadi basis $E$ : pada basis itu $u$ berbentuk blok $\begin{pmatrix} C & \ast\\ 0 & D\end{pmatrix}$ dengan $C$ matriks pendamping $P_x$ , yang polinomial karakteristiknya adalah $P_x$ (uraikan $\det(XI - C)$ sepanjang kolom pertama, dengan induksi pada $d$ ). Karenanya $\chi_u = P_x \cdot \chi_D$ , dan

\chi_u(u)(x) = \chi_D(u)\bigl(P_x(u)(x)\bigr) = 0 .

Hujah itu berlaku untuk setiap $x$ : jadi $\chi_u(u) = 0$ . ∎

Contoh 3.22 (Cayley–Hamilton dalam kerja)

Untuk $A = \begin{pmatrix} 1 & 2\\ 3 & 4\end{pmatrix}$ : $\chi_A = X^2 - 5X - 2$ , jadi $A^2 = 5A + 2I$ . Setiap pangkat $A$ menyusut menjadi kombinasi $I$ dan $A$ :

A^4 = (5A + 2I)^2 = 25A^2 + 20A + 4I = 145A + 54I = \begin{pmatrix} 199 & 290\\ 435 & 634\end{pmatrix},

dan inversnya diperoleh cuma-cuma: dari $A(A - 5I) = 2I$ ,

A^{-1} = \tfrac12(A - 5I) = \begin{pmatrix} -2 & 1\\ 3/2 & -1/2\end{pmatrix}.

Pelajaran penutupnya: Cayley–Hamilton memampatkan seluruh aljabar $K[A]$ menjadi $\operatorname{Vect}(I, A, \dots, A^{n-1})$ — $\dim K[A] = \deg\mu_A \leq n$ , sebesar apa pun pangkat yang diperlukan.

Catatan 3.23 (Jebakan yang sering muncul)

(i) Nilai eigen tidak menjumlah: $\operatorname{Sp}(A + B)$ bukan $\operatorname{Sp}A + \operatorname{Sp}B$ , dan jumlah dua matriks yang dapat didiagonalkan belum tentu dapat didiagonalkan — $\left(\begin{smallmatrix}1 & 1\\ 0 & 0\end{smallmatrix}\right) + \left(\begin{smallmatrix}0 & 0\\ 0 & 1\end{smallmatrix}\right) = \left(\begin{smallmatrix}1 & 1\\ 0 & 1\end{smallmatrix}\right)$ adalah jumlah dua matriks yang dapat didiagonalkan (masing-masing bernilai eigen berbeda) dan hasilnya tidak dapat didiagonalkan; hanya keluarga yang komutatif yang berkelakuan baik (Latihan 3.9). (ii) “ $\chi_u$ terurai lengkap” adalah hipotesis tentang lapangannya: rotasi bidang punya $\chi = X^2 - 2\cos\theta\,X + 1$ , yang terurai lengkap atas $\C$ tetapi tidak atas $\R$ — jadi dapat didiagonalkan di $\mathcal{M}_2(\C)$ , tidak dapat ditrigonalkan di $\mathcal{M}_2(\R)$ . (iii) Ketaksamaannya berjalan geometrik $\leq$ aljabar, tak pernah sebaliknya; menguji $\dim E_\lambda \geq 1$ saja tidak membuktikan apa pun tentang keterdiagonalan. (iv) $\mu_u$ bukan $\chi_u$ : keduanya sama persis ketika tiap nilai eigen punya satu rantai blok tunggal (misalnya matriks pendamping, lihat soal akhir pekan bab ini); memakai $\chi$ di tempat $\mu$ diperlukan hanya menggelembungkan setiap perhitungan pangkat. (v) Adapun $d$ dan $\nu$ milik Dunford berupa polinomial dalam $u$ — penguraian $u = d' + \nu'$ yang bersifat benar tetapi $d'\nu' \neq \nu'd'$ bukanlah Dunford dan tak pernah tunggal.

Catatan 3.24 (Di mana bab ini dipakai)

Reduksi adalah kuda beban bagi sisa buku ini: pangkat dan eksponensial matriks menggerakkan sistem persamaan diferensial linear pada Bab 16; teorema spektral pada Bab 12 tak lain diagonalisasi yang dibuat ortogonal; fungsi pembangkit (Bab 23) menurunkan ulang asimtotik rekurensi pada soal akhir pekan bab ini secara analitis. Pada jilid Tahun ke-3 program yang sama berjalan dalam dimensi tak hingga: teori spektral atas operator kompak yang swa-adjoin, tempat barisan nilai eigen menggantikan spektrum hingga, dan teori Perron–Frobenius atas matriks positif, yang menjelaskan mengapa nilai eigen dominan pada masalah pencacahan selalu positif dan sederhana.

3.3 Nilpoten dan penguraian Dunford

Proposisi 3.25 (Endomorfisma nilpoten)

Untuk $u$ yang $\chi_u$ -nya terurai lengkap, pernyataan berikut setara: $u^n = 0$ ; $u^k = 0$ untuk suatu $k$ ; $\operatorname{Sp}(u) = \{0\}$ ; $\chi_u = X^n$ ; $u$ dapat ditrigonalkan dengan diagonal nol. Endomorfisma nilpoten punya $\mu_u = X^{\text{(indeks kenilpotenan)}}$ , dengan indeks $\leq n$ .

Bukti. Dari $u^k = 0$ setiap nilai eigen menjadi akar $X^k$ : jadi spektrumnya $\{0\}$ (tak kosong ketika $\chi$ terurai lengkap — atas $\C$ selalu demikian). Maka $\chi_u = X^n$ (semua akarnya nol) dan Cayley–Hamilton memberi $u^n = 0$ ; sedangkan trigonalisasi (Teorema 3.9) menaruh nol pada diagonalnya (sebab diagonal mengusung nilai eigennya). Sebaliknya, misalkan $A$ segitiga atas tegas: $a_{ij} = 0$ untuk $j \leq i$ . Kita tunjukkan secara induktif bahwa

(A^k)_{ij} = 0 \qquad \text{setiap kali } j \leq i + k - 1,

yakni tiap pangkatnya mendorong daerah nolnya satu diagonal lebih tinggi. Untuk $k = 1$ inilah hipotesisnya. Adapun langkah induksinya,

(A^{k+1})_{ij} = \sum_{\ell} (A^k)_{i\ell}\,a_{\ell j} ,

dan tiap sukunya lenyap: entah $\ell \leq i + k - 1$ (faktor pertamanya $0$ menurut induksi) atau $\ell \geq i + k$ , dan dalam hal itu $j \leq i + k \leq \ell$ menolkan faktor keduanya. Pada $k = n$ syarat $j \leq i + n - 1$ berlaku untuk setiap $i, j \leq n$ : jadi $A^n = 0$ . Polinomial minimalnya membagi $X^n$ dan penolkannya mendefinisikan indeksnya. ∎

Teorema 3.26 (Penguraian Dunford)

Andaikan $\chi_u$ terurai lengkap atas $K$ (yang otomatis untuk $K = \C$ ). Maka ada tepat satu pasangan $(d, \nu)$ dengan

u = d + \nu, \qquad d \text{ dapat didiagonalkan}, \quad \nu \text{ nilpoten}, \quad d\nu = \nu d ,

dan lebih lanjut $d$ dan $\nu$ berupa polinomial dalam $u$ .

Bukti. Keberadaan. Tulis $\chi_u = \prod_{i=1}^{r} (X - \lambda_i)^{m_i}$ (dengan $\lambda_i$ berbeda) lalu tetapkan $N_i = \ker(u - \lambda_i)^{m_i}$ , yaitu subruang karakteristiknya. Menurut Cayley–Hamilton dan lema kernel (Teorema 3.14),

E = N_1 \oplus \dots \oplus N_r ,

dengan proyeksi $\pi_i$ berupa polinomial dalam $u$ ; tiap $N_i$ bersifat stabil (polinomial dalam $u$ komutatif dengan $u$ ). Tetapkan $d = \sum_i \lambda_i \pi_i$ : sebuah polinomial dalam $u$ yang dapat didiagonalkan (ia bekerja sebagai $\lambda_i$ pada $N_i$ , jadi $E$ terurai menjadi ruang eigennya). Maka $\nu = u - d$ juga polinomial dalam $u$ (sehingga komutatif dengan $d$ ), dan pada tiap $N_i$ ia bekerja sebagai $u - \lambda_i$ dengan $(u - \lambda_i)^{m_i} = 0$ di sana: jadi $\nu^{\max m_i} = 0$ pada tiap suku, sehingga $\nu$ nilpoten.

Ketunggalan. Misalkan $u = d' + \nu'$ pasangan lain yang seperti itu. Karena $d'$ dan $\nu'$ saling komutatif, keduanya komutatif dengan $u = d' + \nu'$ , jadi komutatif dengan setiap polinomial dalam $u$ — khususnya dengan $d$ dan $\nu$ . Maka $d - d'$ dapat didiagonalkan (dua pemetaan komutatif yang dapat didiagonalkan dapat didiagonalkan serentak: Latihan 3.9) dan sama dengan $\nu' - \nu$ , yang nilpoten: jika $\nu^k = 0$ dan $\nu'^{k'} = 0$ , kekomutatifannya mengizinkan penguraian binomial

(\nu' - \nu)^{k + k' - 1} = \sum_{j=0}^{k+k'-1}\binom{k + k' - 1}{j} \,\nu'^{\,j}\,(-\nu)^{k + k' - 1 - j} ,

yang di dalamnya setiap suku mati: entah $j \geq k'$ (faktor pertamanya nol) atau $k + k' - 1 - j \geq k$ (faktor keduanya nol), dan salah satu dari keduanya selalu berlaku. Sedangkan nilpoten yang dapat didiagonalkan pastilah nol (spektrumnya $\{0\}$ dan ia diagonal pada suatu basis): jadi $d = d'$ dan $\nu = \nu'$ . ∎

Contoh 3.27 (Pangkat dan eksponensial)

Untuk $A = \begin{pmatrix} 3 & 1\\ -1 & 1\end{pmatrix}$ : $\chi_A = X^2 - 4X + 4 = (X-2)^2$ , satu nilai eigen $2$ , dengan ruang eigen berdimensi $1$ : jadi tidak dapat didiagonalkan. Dunford: $D = 2I$ , $N = A - 2I = \begin{pmatrix} 1 & 1\\ -1 & -1\end{pmatrix}$ , $N^2 = 0$ . Maka

A^k = (2I + N)^k = 2^k I + k\,2^{k-1} N , \qquad \eu^{tA} = \eu^{2t}(I + tN),

berturut-turut menurut teorema binomial untuk unsur komutatif dan menurut deret eksponensial (Bab 16) yang terpecah pada suku komutatif. Reduksi mengubah dinamika matriks menjadi dinamika skalar.

Catatan 3.28 (Pandangan ke depan di dalam jilid ini)

Reduksi adalah simpul; berikut empat jari-jari yang perlu disimak. Pada Bab 5, norma yang diselaraskan mengubah “semua nilai eigen bermodulus $< 1$ ” menjadi “suatu norma operator $< 1$ ”, sehingga spektrum menguasai kekonvergenan pangkat dan deret. Pada Bab 16, resep pada Contoh 3.27 menjadi penyelesaian umum $X' = AX$ : Dunford memecah $\eu^{tA}$ menjadi blok berupa polinomial dikali eksponensial, dan kestabilannya terbaca dari bagian real nilai eigennya. Pada Bab 12, sebuah hasil kali skalar memaksa apa yang tak sanggup dipaksa aljabar linear semata: matriks setangkup menjadi dapat didiagonalkan secara ortogonal, tanpa bagian nilpoten sama sekali. Dan pada Bab 23, asimtotik nilai eigen dominan pada soal akhir pekan bab ini muncul kembali secara analitis, sebagai singularitas terkecil sebuah fungsi pembangkit — dua bahasa untuk satu laju tumbuh.

3.4 Latihan

Latihan 3.1 ★

Diagonalkan (nilai eigen, basis ruang eigen, matriks berinvers $P$ ):

A = \begin{pmatrix} 1 & 2\\ 2 & 1 \end{pmatrix}, \qquad B = \begin{pmatrix} 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 0 \end{pmatrix}.

Solusi

Solusi Latihan 3.1.

$A$ : $\chi_A = X^2 - 2X - 3 = (X - 3)(X + 1)$ . Vektor eigennya: untuk $3$ : $(1,1)$ ; untuk $-1$ : $(1,-1)$ . Jadi $P = \begin{pmatrix} 1 & 1\\ 1 & -1\end{pmatrix}$ memberi $P^{-1}AP = \operatorname{diag}(3, -1)$ .

$B = J - I$ dengan $J$ matriks yang semua unsurnya satu. Matriks $J$ berank $1$ dengan $Jv = 3v$ untuk $v = (1,1,1)$ dan $Jw = 0$ pada bidang $x + y + z = 0$ : jadi spektrum $B$ adalah $\{2, -1\}$ dengan ruang eigen $\operatorname{Vect}(1,1,1)$ (berdimensi $1$ ) dan $\{x + y + z = 0\}$ (berdimensi $2$ , dengan basis $(1,-1,0), (1,0,-1)$ ). Maka $P$ yang berkolomkan ketiganya memberi $P^{-1}BP = \operatorname{diag}(2, -1, -1)$ .

Latihan 3.2 ★

Tunjukkan bahwa $C = \begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}$ tidak dapat didiagonalkan, dengan dua cara: lewat ruang eigen, dan lewat polinomial minimal.

Solusi

Solusi Latihan 3.2.

Lewat ruang eigen: $\chi_C = (X-1)^2$ , dengan satu nilai eigen $1$ ; $\ker(C - I) = \ker\begin{pmatrix} 0&1\\ 0&0\end{pmatrix}$ adalah garis $\operatorname{Vect}(e_1)$ , berdimensi $1 < 2 = m_1$ , jadi tidak dapat didiagonalkan (Teorema 3.6).

Lewat polinomial minimal: $\mu_C$ membagi $(X-1)^2$ dan $C \neq I$ , jadi $\mu_C = (X-1)^2$ : akarnya ganda, sehingga tidak dapat didiagonalkan (Akibat 3.17).

Latihan 3.3 ★

Misalkan $u$ memenuhi $u^2 - 5u + 6\,\mathrm{id} = 0$ . Buktikan bahwa $u$ dapat didiagonalkan, tentukan spektrum yang mungkin, lalu hitung $u^k$ sebagai kombinasi $\mathrm{id}$ dan $u$ .

Solusi

Solusi Latihan 3.3.

$X^2 - 5X + 6 = (X-2)(X-3)$ : terurai lengkap dengan akar sederhana, jadi $u$ dapat didiagonalkan (Akibat 3.17), dengan $\operatorname{Sp}(u) \subseteq \{2, 3\}$ . Spektrum yang mungkin: $\{2\}$ (yaitu $u = 2\,\mathrm{id}$ ), $\{3\}$ (yaitu $u = 3\,\mathrm{id}$ ), atau $\{2, 3\}$ .

Pangkatnya: carilah $u^k = a_k\,\mathrm{id} + b_k\,u$ . Pada ruang eigennya, syarat itu berbunyi $2^k = a_k + 2b_k$ dan $3^k = a_k + 3b_k$ ; setelah diselesaikan, $b_k = 3^k - 2^k$ dan $a_k = 3\cdot2^k - 2\cdot 3^k$ :

u^k = (3\cdot 2^k - 2\cdot 3^k)\,\mathrm{id} + (3^k - 2^k)\, u .

(Berlaku untuk ketiga spektrumnya: kesamaannya berlaku nilai eigen demi nilai eigen.)

Latihan 3.4 ★★

Misalkan $u$ dapat didiagonalkan dan $F$ subruang yang stabil. Buktikan bahwa $u|_F$ dapat didiagonalkan (batasi sebuah polinomial penganihilasi yang terurai lengkap dengan akar sederhana).

Solusi

Solusi Latihan 3.4.

Karena $u$ dapat didiagonalkan, $P = \prod_{\lambda}(X - \lambda)$ atas spektrumnya menganihilasi $u$ , terurai lengkap, dan berakar sederhana. Maka $P(u|_F) = P(u)|_F = 0$ : pembatasannya dianihilasi oleh polinomial terurai lengkap yang berakar sederhana, jadi ia dapat didiagonalkan (Akibat 3.17).

Latihan 3.5 ★★

(Fibonacci) Misalkan $A = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix}$ . Diagonalkan $A$ atas $\R$ , lalu turunkan rumus Binet untuk barisan Fibonacci ( $F_0 = 0$ , $F_1 = 1$ , $F_{n+1} = F_n + F_{n-1}$ ):

F_n = \frac{\varphi^n - \psi^n}{\sqrt 5}, \qquad \varphi = \frac{1 + \sqrt5}{2},\ \psi = \frac{1 - \sqrt5}{2}.

Solusi

Solusi Latihan 3.5.

Di sini $\chi_A = X^2 - X - 1$ , dengan akar $\varphi$ dan $\psi$ yang berbeda: jadi dapat didiagonalkan, dengan vektor eigen $(\varphi, 1)$ dan $(\psi, 1)$ . Rekurensinya memberi $\begin{pmatrix} F_{n+1}\\ F_n \end{pmatrix} = A^n \begin{pmatrix}1\\ 0\end{pmatrix}$ . Uraikan $(1, 0)$ pada vektor eigennya: $(1,0) = \frac{1}{\varphi - \psi}\bigl((\varphi, 1) - (\psi, 1)\bigr)$ dengan $\varphi - \psi = \sqrt5$ . Menerapkan $A^n$ mengalikan tiap komponen eigennya dengan pangkat ke- $n$ nilai eigennya; setelah koordinat keduanya dibaca:

F_n = \frac{\varphi^n - \psi^n}{\sqrt 5} .

(Periksa: $n = 1$ memberi $\frac{\varphi - \psi}{\sqrt5} = 1$ .)

Latihan 3.6 ★★

Misalkan $u \in \mathcal{L}(E)$ dengan $u^2$ dapat didiagonalkan dan $u$ punya invers ( $K = \C$ ). Buktikan bahwa $u$ dapat didiagonalkan. Berilah contoh penyangkal ketika $u$ tidak punya invers.

Solusi

Solusi Latihan 3.6.

Misalkan $P = \prod_i (X - \mu_i)$ menganihilasi $u^2$ , terurai lengkap dengan akar sederhana $\mu_i$ (yaitu spektrum $u^2$ ). Karena $u$ punya invers, $0$ bukan nilai eigen $u^2$ (sebab $\det u^2 = (\det u)^2 \neq 0$ ), jadi semua $\mu_i \neq 0$ . Maka

Q(X) = \prod_i (X^2 - \mu_i) = \prod_i (X - \sqrt{\mu_i})(X + \sqrt{\mu_i})

menganihilasi $u$ : $\;Q(u) = \prod_i (u^2 - \mu_i\,\mathrm{id}) = P(u^2) = 0$ . Akarnya $\pm \sqrt{\mu_i}$ (yakni akar kuadrat kompleks) berbeda sepasang demi sepasang karena $\mu_i$ berbeda dan tak nol (sebab $\sqrt{\mu_i} = -\sqrt{\mu_j}$ akan memberi $\mu_i = \mu_j$ ). Terurai lengkap dan berakar sederhana: jadi $u$ dapat didiagonalkan.

Contoh penyangkal tanpa keterbalikan: $u = \begin{pmatrix} 0 & 1\\ 0 & 0\end{pmatrix}$ : di sini $u^2 = 0$ dapat didiagonalkan, $u$ tidak.

Latihan 3.7 ★★

Hitung penguraian Dunford, $A^k$ , dan $\eu^{tA}$ untuk

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

Solusi

Solusi Latihan 3.7.

$A = 2I + N$ dengan $N$ geseran ( $N e_2 = e_1$ , $Ne_3 = e_2$ ), $N^3 = 0$ , $N^2 = E_{13}$ : inilah tepat penguraian Dunfordnya ( $2I$ diagonal, $N$ nilpoten, dan keduanya komutatif; ketunggalannya menjadikannya satu-satunya). Binomial atas suku yang komutatif memberi

A^k = 2^k I + k 2^{k-1} N + \binom k2 2^{k-2} N^2 = \begin{pmatrix} 2^k & k2^{k-1} & \binom k2 2^{k-2}\\ 0 & 2^k & k2^{k-1}\\ 0 & 0 & 2^k \end{pmatrix},

\eu^{tA} = \eu^{2t}\Bigl(I + tN + \frac{t^2}{2}N^2\Bigr) = \eu^{2t}\begin{pmatrix} 1 & t & t^2/2\\ 0 & 1 & t\\ 0 & 0 & 1 \end{pmatrix}.

Latihan 3.8 ★★

Misalkan $A \in \mathcal{M}_n(\C)$ dengan $A^k = I$ untuk suatu $k \geq 1$ . Buktikan bahwa $A$ dapat didiagonalkan dan nilai eigennya adalah akar ke- $k$ dari satu. Turunkan bahwa matriks kompleks berinvers dan berorde hingga yang serupa dengan matriks segitiga berdiagonal satu adalah identitas.

Solusi

Solusi Latihan 3.8.

$X^k - 1$ menganihilasi $A$ dan terurai lengkap atas $\C$ dengan $k$ akar berbeda $\eu^{2\iu\pi j/k}$ : jadi $A$ dapat didiagonalkan (Akibat 3.17) dan nilai eigennya, sebagai akar $X^k - 1$ , adalah akar ke- $k$ dari satu.

Jika lagi-lagi $A$ serupa dengan matriks segitiga berdiagonal satu: semua nilai eigennya sama dengan $1$ , dan $A$ yang dapat didiagonalkan dengan nilai eigen tunggal $1$ pastilah $P\,I\,P^{-1} = I$ .

Latihan 3.9 ★★★

(Diagonalisasi serentak) Misalkan $u, v$ dapat didiagonalkan dan saling komutatif. Buktikan bahwa keduanya dapat didiagonalkan serentak: ada basis yang mendiagonalkan keduanya. (Tiap ruang eigen $u$ stabil terhadap $v$ ; diagonalkan pembatasan $v$ di sana, dengan memakai Latihan 3.4.)

Solusi

Solusi Latihan 3.9.

Tulis $E = \bigoplus_\lambda E_\lambda(u)$ (Teorema 3.6). Tiap $E_\lambda(u)$ stabil terhadap $v$ : untuk $x \in E_\lambda$ berlaku $u(v(x)) = v(u(x)) = \lambda v(x)$ . Pembatasan $v$ pada $E_\lambda(u)$ dapat didiagonalkan (Latihan 3.4): pilihlah basis $E_\lambda(u)$ yang terdiri atas vektor eigen $v$ . Menyambung basis-basis itu atas semua $\lambda$ memberi basis $E$ yang vektornya adalah vektor eigen bagi keduanya, yakni $u$ (lewat keanggotaan di $E_\lambda(u)$ ) dan $v$ (menurut konstruksinya).

Latihan 3.10 ★★★

Misalkan $u \in \mathcal{L}(\C^n)$ . Buktikan bahwa $u$ dapat didiagonalkan bila dan hanya bila setiap subruang yang stabil terhadap $u$ punya subruang pelengkap yang juga stabil terhadap $u$ . (Untuk $\Leftarrow$ : terapkan sifat itu pada $F = \sum_\lambda E_\lambda(u)$ , jumlah semua ruang eigen; jika pelengkap stabil $G$ tak nol, mentrigonalkan $u|_G$ akan menghasilkan vektor eigen $u$ di dalam $G$ — yang bertentangan dengan $G \cap F = \{0\}$ .)

Solusi

Solusi Latihan 3.10.

( $\Rightarrow$ ) Misalkan $u$ dapat didiagonalkan dan $F$ stabil. Maka $u|_F$ dapat didiagonalkan (Latihan 3.4): jadi $F$ punya basis berisi vektor eigen, yang di dalam tiap ruang eigen global $E_\lambda$ dapat diperluas menjadi basis $E_\lambda$ (lewat teorema basis tak lengkap di dalam $E_\lambda$ , berawal dari bagian basis $F$ yang terletak di sana — perhatikan $F = \bigoplus_\lambda (F \cap E_\lambda)$ sebab $u|_F$ dapat didiagonalkan). Vektor yang ditambahkan tadi merentang pelengkap yang stabil (masing-masing terletak di suatu $E_\lambda$ , jadi rentangnya stabil terhadap $u$ ).

( $\Leftarrow$ ) Misalkan $F = \sum_\lambda E_\lambda(u)$ (sebuah subruang stabil) dan $G$ pelengkapnya yang stabil. Jika $G \neq \{0\}$ , maka $\chi_{u|_G}$ terurai lengkap atas $\C$ , sehingga $u|_G$ punya vektor eigen $x \in G$ (Teorema 3.9, atau langsung lewat keberadaan akarnya); tetapi setiap vektor eigen $u$ terletak di $F$ , jadi $x \in F \cap G = \{0\}$ : kontradiksi. Karenanya $G = \{0\}$ dan $E = F$ : ruang eigennya mengisi $E$ , yakni $u$ dapat didiagonalkan.

Latihan 3.11 ★★★

(Jari-jari spektral ala Gelfand ringan, cicipan analisis pada $2\times2$ ) Misalkan $A \in \mathcal{M}_2(\C)$ dengan kedua nilai eigennya bermodulus $< 1$ . Buktikan bahwa $A^k \to 0$ unsur demi unsur ketika $k \to \infty$ . (Trigonalkan: $A = P(T)P^{-1}$ dengan $T$ segitiga atas; hitung $T^k$ secara gamblang — bedakan nilai eigen yang sama dan yang berbeda — lalu batasi.)

Solusi

Solusi Latihan 3.11.

Trigonalkan: $A = PTP^{-1}$ , $T = \begin{pmatrix} \lambda & c\\ 0 & \mu\end{pmatrix}$ , dengan $\abs\lambda, \abs\mu < 1$ . Maka $A^k = PT^kP^{-1}$ , sehingga cukuplah menunjukkan $T^k \to 0$ .

Nilai eigen berbeda: induksi memberi

T^k = \begin{pmatrix} \lambda^k & c\,\dfrac{\lambda^k - \mu^k}{\lambda - \mu}\\[4pt] 0 & \mu^k \end{pmatrix},

dan tiap unsurnya menuju $0$ (sebab $\abs{\lambda}^k, \abs\mu^k \to 0$ ).

Nilai eigen sama ( $\mu = \lambda$ ): di sini $T = \lambda I + cE_{12}$ dan $T^k = \lambda^k I + k\lambda^{k-1}cE_{12}$ ; unsur $k\lambda^{k-1} \to 0$ karena $\abs\lambda < 1$ (geometri mengalahkan polinomial). Pada kedua kasusnya $T^k \to 0$ unsur demi unsur, sehingga $A^k = PT^kP^{-1} \to 0$ (perkalian matriks oleh $P, P^{-1}$ yang tetap bersifat kontinu pada unsurnya — tiap unsur hasil kalinya adalah kombinasi linear yang tetap).

Latihan 3.12 ★★

Misalkan $u \in \mathcal{L}(\C^n)$ dengan $\operatorname{rk} u = 1$ ( $n \geq 2$ ). Tunjukkan bahwa $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ , dan bahwa $u$ dapat didiagonalkan bila dan hanya bila $\operatorname{tr} u \neq 0$ . (Ingat kembali dari Latihan 2.5 bahwa $u^2 = (\operatorname{tr} u)\,u$ .)

Solusi

Solusi Latihan 3.12.

Kernel $\ker u$ berdimensi $n - 1$ (rank–nulitas), jadi $0$ adalah nilai eigen bermultiplisitas geometrik $n - 1$ , dan $\chi_u$ habis dibagi $X^{n-1}$ (Definisi 3.3: geometrik $\leq$ aljabar). Tulis $\chi_u = X^{n-1}(X - \alpha)$ ; karena koefisien $X^{n-1}$ adalah $-\operatorname{tr} u$ , diperoleh $\alpha = \operatorname{tr} u$ , yakni $\chi_u = X^{n-1}(X - \operatorname{tr} u)$ .

Jika $\operatorname{tr} u \neq 0$ : nilai eigen $\operatorname{tr} u$ adalah akar $\chi_u$ , jadi ia mengusung vektor eigen; ruang eigen untuk $0$ dan untuk $\operatorname{tr} u$ berdimensi $n - 1$ dan $\geq 1$ , yang berjumlah $\geq n$ : keduanya mengisi $E$ , sehingga $u$ dapat didiagonalkan (Teorema 3.6). Jika $\operatorname{tr} u = 0$ : menurut Latihan 2.5, $u^2 = (\operatorname{tr} u)u = 0$ padahal $u \neq 0$ , jadi $u$ nilpoten tak nol, sedangkan nilpoten yang dapat didiagonalkan pastilah nol (Proposisi 3.25): jadi tidak dapat didiagonalkan.

3.5 Soal: Rekurensi Linear dan Matriks Pendamping

Rekurensi linear $u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_0 u_n$ tak lain pangkat matriks yang menyamar, dan reduksi mengubahnya menjadi rumus tertutup, laju tumbuh, dan taksiran galat. Soal akhir pekan ini mengembangkan kamusnya — matriks pendamping di satu sisi, operator geser pada ruang barisan di sisi lain — membuktikan teorema dasar rekurensi linear (penyelesaian umumnya $\sum_i Q_i(n)\lambda_i^n$ atas akar polinomial karakteristiknya), lalu membelanjakan panennya untuk penghampiran Diophantus atas $\sqrt2$ , untuk pencacahan jalan dan kata, serta untuk sebuah cincin barisan berkopling yang hanya dapat diurai oleh diagonalisasi serentak.

Soal 3.1

Soal akhir pekan — teorema dasar rekurensi linear

Tetapkan $k \geq 1$ , skalar $a_0, \dots, a_{k-1} \in \C$ dengan $a_0 \neq 0$ , polinomial monik $P = X^k - a_{k-1}X^{k-1} - \dots - a_1 X - a_0$ , dan rekurensi

(\mathcal R)\colon\quad u_{n+k} = a_{k-1}u_{n+k-1} + \dots + a_1 u_{n+1} + a_0 u_n \qquad (n \geq 0).

Matriks pendamping bagi $P$ adalah

C = \begin{pmatrix} 0 & 1 & & \\ & \ddots & \ddots & \\ & & 0 & 1\\ a_0 & a_1 & \cdots & a_{k-1} \end{pmatrix} \in \mathcal{M}_k(\C).

Bagian I — Kamus pendamping.

Tunjukkan bahwa sebuah barisan $(u_n)$ memenuhi $(\mathcal R)$ bila dan hanya bila vektor $v_n = (u_n, u_{n+1}, \dots, u_{n+k-1})^{\mathsf T}$ memenuhi $v_{n+1} = Cv_n$ , sehingga $v_n = C^n v_0$ .
Buktikan bahwa $\chi_C = P$ (uraikan $\det(XI - C)$ sepanjang kolom pertama lalu berinduksi pada $k$ ), lalu bahwa $\mu_C = P$ juga (beralihlah ke $C^{\mathsf T}$ , yang $e_1$ -nya siklik, dan perhatikan bahwa sebuah matriks dan transposnya punya polinomial minimal yang sama).
Tunjukkan bahwa untuk tiap akar $\lambda$ pada $P$ , vektor $(1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ merentang ruang eigen $C$ bagi $\lambda$ ; lalu turunkan bahwa setiap ruang eigen $C$ berdimensi $1$ , dan bahwa $C$ dapat didiagonalkan bila dan hanya bila $P$ punya $k$ akar yang berbeda.
Andaikan $P$ punya akar berbeda $\lambda_1, \dots, \lambda_k$ . Tunjukkan bahwa barisan geometri $(\lambda_i^n)_n$ membentuk basis ruang penyelesaian $(\mathcal R)$ , sehingga setiap penyelesaiannya berbentuk $u_n = \sum_i c_i\lambda_i^n$ untuk konstanta $c_i$ yang tunggal.
Selesaikan seluruhnya: $u_{n+2} = u_{n+1} + 6u_n$ , $u_0 = 1$ , $u_1 = 8$ .

Bagian II — Operator geser dan teorema dasarnya. Misalkan $\mathcal{S}$ ruang vektor atas $\C$ yang berisi semua barisan kompleks dan $S \in \mathcal{L}(\mathcal{S})$ operator geser, $S\bigl((u_n)_n\bigr) = (u_{n+1})_n$ .

Tunjukkan bahwa himpunan penyelesaian $(\mathcal R)$ adalah $\ker P(S)$ , dan bahwa dimensinya tepat $k$ (petakan sebuah penyelesaian ke nilai awalnya).
Jelaskan mengapa lema penguraian kernel (Teorema 3.14) berlaku bagi $S$ pada $\mathcal{S}$ yang berdimensi tak hingga tanpa perubahan apa pun, lalu tuliskan penguraian $\ker P(S)$ yang dihasilkannya untuk $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ (dengan $\lambda_i$ berbeda dan semuanya tak nol karena $a_0 \neq 0$ ).
Untuk $\lambda \neq 0$ dan $m \geq 1$ , tunjukkan bahwa

$\ker\,(S - \lambda\,\mathrm{id})^m = \bigl\{\,\bigl(Q(n)\,\lambda^n\bigr)_n : Q \in \C_{m-1}[X]\,\bigr\},$

yang berdimensi $m$ . (Hitung $(S - \lambda)\bigl(Q(n)\lambda^n\bigr) = \lambda^{n+1}(\Delta Q)(n)$ dengan $\Delta Q = Q(X + 1) - Q(X)$ , lalu pakai kenyataan bahwa $\Delta$ menurunkan derajatnya; untuk dimensinya, batasi dengan $m$ lewat nilai awalnya.)
(Teorema dasar rekurensi linear) Simpulkan: jika $P = \prod_{i=1}^{r}(X - \lambda_i)^{m_i}$ dengan $\lambda_i$ berbeda dan tak nol, maka penyelesaian $(\mathcal R)$ persis semua barisan

$u_n = \sum_{i=1}^{r} Q_i(n)\,\lambda_i^n, \qquad Q_i \in \C_{m_i - 1}[X],$

dengan polinomial $Q_i$ yang tertentu secara tunggal.
Selesaikan seluruhnya: $u_{n+2} = 4u_{n+1} - 4u_n$ , $u_0 = 1$ , $u_1 = 0$ , lalu periksa jawabannya pada $u_2$ .

Bagian III — Akar dominan dan panen Diophantus.

Andaikan akarnya sederhana dengan $\abs{\lambda_1} > \abs{\lambda_i}$ untuk $i \geq 2$ , dan $u_n = \sum_i c_i \lambda_i^n$ dengan $c_1 \neq 0$ . Tunjukkan $u_n \sim c_1\lambda_1^n$ dan $u_{n+1}/u_n \to \lambda_1$ .
(Pell) Tetapkan $a_{n+1} = a_n + 2b_n$ , $b_{n+1} = a_n + b_n$ , $a_0 = b_0 = 1$ . Tunjukkan bahwa $q(a, b) = a^2 - 2b^2$ memenuhi $q(a_{n+1}, b_{n+1}) = -q(a_n, b_n)$ , sehingga $a_n^2 - 2b_n^2 = (-1)^{n+1}$ ; lalu kaitkan hal itu dengan determinan $M = \left(\begin{smallmatrix}1 & 2\\ 1 & 1\end{smallmatrix}\right)$ .
Turunkan taksiran galat

$\Bigl|\frac{a_n}{b_n} - \sqrt2\Bigr| = \frac{1}{b_n\,(a_n + \sqrt2\,b_n)} \leq \frac{1}{2b_n^2},$

lalu tunjukkan bahwa galat itu meluruh secara geometri dengan rasio $3 - 2\sqrt2$ (carilah nilai eigen $M$ dan laju tumbuh $b_n$ ).
(Laju tumbuh umum) Dari pertanyaan 9, buktikan: (a) jika setiap akarnya memenuhi $\abs{\lambda_i} \leq \rho$ , maka $\abs{u_n} \leq C\,n^{m-1}\rho^n$ dengan $m = \max_i m_i$ ; (b) jika ada satu akar tunggal $\lambda_1$ yang modulusnya maksimal dan $Q_1 \neq 0$ , maka $u_{n+1}/u_n \to \lambda_1$ — periksalah hal itu pada penyelesaian pertanyaan 10.

Bagian IV — Mencacah jalan dan kata. Untuk sebuah graf hingga dengan himpunan simpul $\{1, \dots, N\}$ , matriks ketetanggaan $A$ punya $A_{ij} = 1$ bila $ij$ sebuah rusuk, dan $0$ bila bukan.

Buktikan bahwa $(A^n)_{ij}$ adalah banyaknya jalan berpanjang $n$ dari $i$ ke $j$ (rangkaian $n$ rusuk, tiap langkahnya menyusuri sebuah rusuk).
(Segitiga) Untuk graf lengkap atas $3$ simpul, berlaku $A = J - I$ : dengan memakai spektrum $J$ (Contoh 2.19), tunjukkan

$(A^n)_{ii} = \frac{2^n + 2(-1)^n}{3}, \qquad (A^n)_{ij} = \frac{2^n - (-1)^n}{3} \quad (i \neq j),$

lalu periksa keduanya pada $n = 2$ dengan mendaftar jalannya.
(Kata tanpa $11$ ) Misalkan $w_n$ banyaknya kata biner berpanjang $n$ yang tidak punya dua angka $1$ berurutan. Sandikan katanya menurut huruf terakhirnya untuk memperoleh matriks transfer, tunjukkan $w_{n+2} = w_{n+1} + w_n$ , turunkan $w_n = F_{n+2}$ (Fibonacci, Latihan 3.5), lalu berikan laju tumbuhnya $\lim w_{n+1}/w_n$ .
(Lintasan) Untuk graf lintasan $1 - 2 - 3$ , tunjukkan bahwa nilai eigen $A$ adalah $\sqrt2, 0, -\sqrt2$ dengan vektor eigen $(1, \pm\sqrt2, 1)$ dan $(1, 0, -1)$ , lalu turunkan bahwa banyaknya jalan berpanjang $n$ dari ujung ke ujung adalah $\bigl((\sqrt2)^n + (-\sqrt2)^n\bigr)/4$ : nol untuk $n$ ganjil, dan $2^{\,n/2 - 1}$ untuk $n$ genap. Periksalah pada $n = 4$ .
(Rumus trace) Tunjukkan bahwa banyaknya seluruh jalan tertutup berpanjang $n$ (dari semua titik awal) adalah $\operatorname{tr}(A^n) = \sum_i \lambda_i^n$ , lalu periksalah pada segitiga.

Bagian V — Sebuah cincin barisan: diagonalisasi serentak. Tetapkan $k \geq 3$ , misalkan $\omega = \eu^{2\iu\pi/k}$ , dan misalkan $W \in \mathcal{M}_k(\C)$ geseran siklik: $W e_i = e_{i+1}$ (indeks modulo $k$ , dengan kolom berindeks $0, \dots, k-1$ ).

Tunjukkan bahwa $W^{\mathsf T}$ adalah matriks pendamping bagi $X^k - 1$ , lalu turunkan $\chi_W = \mu_W = X^k - 1$ , dan bahwa $W$ dapat didiagonalkan dengan $k$ nilai eigen sederhana $\omega^j$ beserta vektor eigen $f_j = (1, \omega^{-j}, \omega^{-2j}, \dots, \omega^{-(k-1)j})^{\mathsf T}$ .
Matriks sirkulan adalah $C = c_0 I + c_1 W + \dots + c_{k-1}W^{k-1}$ . Tunjukkan bahwa semua sirkulan saling komutatif, bahwa basis $(f_0, \dots, f_{k-1})$ mendiagonalkan semuanya serentak, dan bahwa nilai eigen $C$ adalah $\widehat c(\omega^j) = \sum_m c_m \omega^{jm}$ , $j = 0, \dots, k-1$ .
Turunkan $\det C = \prod_{j=0}^{k-1} \widehat c(\omega^j)$ , lalu periksa bahwa $k = 3$ memulihkan pemfaktoran pada Latihan 2.8.
(Rata-rata kalung) Misalkan $x^{(n+1)} = Mx^{(n)}$ dengan $M = \frac12(W + W^{-1})$ : masing-masing dari $k$ bilangan yang tersusun melingkar diganti dengan rata-rata kedua tetangganya. Tunjukkan bahwa nilai eigen $M$ adalah $\cos(2\pi j/k)$ , dan bahwa koefisien $x^{(0)}$ pada $f_0$ adalah rata-rata $\frac1k\sum_m x^{(0)}_m$ (jumlahkan koordinat tiap $f_j$ ).
Simpulkan: untuk $k$ ganjil, $x^{(n)}$ konvergen ke vektor konstan yang nilainya rata-rata nilai awalnya; sedangkan untuk $k = 4$ , tunjukkan nilai eigen yang bertanggung jawab atas ketakkonvergenannya beserta halangannya yang tepat (yaitu koefisien rata-rata berselang-seling yang wajib nol).
(Rangkuman) Dengan satu kalimat untuk masing-masing: bagaimana matriks pendamping mengubah telaah $(\mathcal R)$ menjadi reduksi; di mana lema penguraian kernel sama sekali tidak memerlukan dimensi hingga; mengapa nilai eigen dominan menguasai laju tumbuh dan galat Diophantus; mengapa pangkat matriks ketetanggaan mencacah jalan; dan apa yang dibeli oleh matriks yang saling komutatif. Sebutkan kedua puncaknya: teorema dasar rekurensi linear, dan — untuk matriks positif pada Bagian IV, di jilid Tahun ke-3 — teorema Perron–Frobenius.

Solusi

Solusi Soal 3.1.

1. Sebanyak $k - 1$ koordinat pertama pada $Cv_n$ adalah $u_{n+1}, \dots, u_{n+k-1}$ (karena superdiagonalnya menggeser), dan yang terakhir adalah $a_0 u_n + \dots + a_{k-1}u_{n+k-1}$ . Jadi $v_{n+1} = Cv_n$ berlaku untuk setiap $n$ bila dan hanya bila koordinat terakhirnya cocok untuk setiap $n$ , yakni bila dan hanya bila $(\mathcal R)$ berlaku. Dengan mengiterasikannya, $v_n = C^nv_0$ .

2. Uraikan $D_k(X) = \det(XI_k - C)$ sepanjang kolom pertama: kedua unsurnya yang tak nol adalah $X$ (pada kedudukan $(1,1)$ ) dan $-a_0$ (pada kedudukan $(k,1)$ ). Minor pertamanya berbentuk $D_{k-1}$ untuk koefisien $a_1, \dots, a_{k-1}$ ; minor keduanya segitiga atas dengan diagonal $-1$ , jadi determinannya $(-1)^{k-1}$ , dengan tanda $(-1)^{k+1}$ dari kedudukannya. Induksi pada $k$ (dengan pangkal $k = 1$ : $X - a_0$ ) memberi

D_k(X) = X\bigl(X^{k-1} - a_{k-1}X^{k-2} - \dots - a_1\bigr) - a_0 = P(X).

Untuk $\mu_C$ : karena $Q(C^{\mathsf T}) = Q(C)^{\mathsf T}$ untuk setiap polinomial, $C$ dan $C^{\mathsf T}$ punya penganihilasi yang sama, jadi punya polinomial minimal yang sama. Untuk $C^{\mathsf T}$ : kolomnya berbunyi $C^{\mathsf T}e_1 = e_2$ , …, $C^{\mathsf T}e_{k-1} = e_k$ , sehingga $(e_1, C^{\mathsf T}e_1, \dots, (C^{\mathsf T})^{k-1}e_1)$ tak lain basis kanoniknya: bebas. Maka polinomial $Q \neq 0$ berderajat $< k$ punya $Q(C^{\mathsf T})e_1 \neq 0$ (sebab ia kombinasi tak trivial atas vektor basis), jadi $\deg\mu \geq k$ . Karena $\mu \mid \chi = P$ dengan $\deg P = k$ : $\mu_C = P$ .

3. Untuk $v = (1, \lambda, \dots, \lambda^{k-1})^{\mathsf T}$ : baris $1$ sampai $k-1$ pada $Cv$ memberi $\lambda, \lambda^2, \dots, \lambda^{k-1}$ , yakni $\lambda$ kali $k - 1$ unsur pertama $v$ ; sedangkan baris terakhirnya memberi $\sum_m a_m\lambda^m = \lambda^k - P(\lambda) = \lambda^k = \lambda\cdot\lambda^{k-1}$ . Jadi $Cv = \lambda v$ . Sebaliknya, persamaan $(Cx)_i = \lambda x_i$ untuk $i < k$ berbunyi $x_{i+1} = \lambda x_i$ : jadi setiap vektor eigen sebanding dengan $v$ — artinya tiap ruang eigen berdimensi tepat $1$ . Dapat didiagonalkan bila dan hanya bila dimensi ruang eigennya berjumlah $k$ (Teorema 3.6), bila dan hanya bila ada $k$ nilai eigen berbeda, bila dan hanya bila $P$ punya $k$ akar berbeda (sebab nilai eigennya adalah akar $\chi_C = P$ ).

4. Tiap $(\lambda_i^n)_n$ menyelesaikan $(\mathcal R)$ , sebab $\lambda_i^{n+k} = \lambda_i^n\,\lambda_i^k = \lambda_i^n\sum_m a_m\lambda_i^m$ . Kebebasannya: kombinasi yang nol, $\sum_i c_i\lambda_i^n = 0$ untuk $n = 0, \dots, k-1$ , merupakan sistem Vandermonde (Latihan 2.11) pada $c_i$ : jadi semua $c_i = 0$ . Ruang penyelesaiannya berdimensi $k$ (pertanyaan 6, yang buktinya dasar dan berdiri sendiri): jadi $k$ penyelesaian bebas membentuk basis, dan koordinatnya tunggal.

5. $P = X^2 - X - 6 = (X - 3)(X + 2)$ : penyelesaian umumnya $u_n = A\,3^n + B(-2)^n$ . Syarat awalnya: $A + B = 1$ , $3A - 2B = 8$ , jadi $A = 2$ dan $B = -1$ :

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

(Periksa: $u_2 = u_1 + 6u_0 = 14$ dan $2\cdot9 - 4 = 14$ .)

6. $P(S)\bigl((u_n)\bigr)$ adalah barisan $n \mapsto u_{n+k} - a_{k-1}u_{n+k-1} - \dots - a_0u_n$ : ia nol bila dan hanya bila $(\mathcal R)$ berlaku, jadi himpunan penyelesaiannya adalah $\ker P(S)$ , sebuah subruang. Pemetaan $\ker P(S) \to \C^k$ , $u \mapsto (u_0, \dots, u_{k-1})$ , bersifat linear, injektif (sebab rekurensinya menentukan $u_{k}, u_{k+1}, \dots$ dari $k$ nilai pertamanya, secara induktif) dan surjektif (tetapkan $u_n$ secara rekursif dari data awal apa pun): jadi dimensinya $k$ .

7. Bukti Teorema 3.14 hanya memakai kesamaan Bézout di $\C[X]$ serta kenyataan bahwa polinomial dalam satu endomorfisma tetap saling komutatif. Tak satu pun menyinggung dimensi ruang sekitarnya: jadi lemanya berlaku kata demi kata bagi $S \in \mathcal{L}(\mathcal{S})$ . Karenanya

\ker P(S) = \bigoplus_{i=1}^{r} \ker\,(S - \lambda_i\,\mathrm{id})^{m_i}.

8. Untuk $Q \in \C[X]$ : barisan $(S - \lambda)\bigl(Q(n)\lambda^n\bigr)_n$ bersuku ke- $n$ $Q(n{+}1)\lambda^{n+1} - \lambda Q(n)\lambda^n = \lambda^{n+1}(\Delta Q)(n)$ , dengan $\Delta Q = Q(X{+}1) - Q(X)$ berderajat $\deg Q - 1$ (sebab suku utamanya saling coret). Dengan mengiterasikannya, $(S - \lambda)^m\bigl(Q(n)\lambda^n\bigr) = \bigl(\lambda^{n+m}(\Delta^m Q)(n)\bigr)_n$ , dan $\Delta^m Q = 0$ bila $\deg Q \leq m - 1$ : jadi himpunan di ruas kanan termuat di kernelnya. Kernel itu subruang berdimensi $m$ : barisan $(n^j\lambda^n)_n$ , $0 \leq j < m$ , bersifat bebas, sebab $\sum_j c_j n^j\lambda^n = 0$ untuk setiap $n$ memaksa (setelah dibagi $\lambda^n \neq 0$ ) polinomial $\sum_j c_jX^j$ bernilai nol di setiap $n \in \N$ , jadi memaksanya menjadi nol. Sebaliknya $\dim\ker(S - \lambda)^m \leq m$ : setelah $(S - \lambda)^m = \sum_j \binom mj(-\lambda)^{m-j}S^j$ diuraikan, persamaan $(S - \lambda)^m u = 0$ menjadi rekurensi linear berorde $m$ (dengan koefisien utama $1$ ), sehingga $u$ ditentukan oleh $u_0, \dots, u_{m-1}$ seperti pada pertanyaan 6. Kesamaan dimensinya merampungkan buktinya.

9. Gabungkan pertanyaan 7 dan 8: setiap penyelesaian terurai secara tunggal sebagai jumlah unsur $\ker(S - \lambda_i)^{m_i}$ , yakni $u_n = \sum_i Q_i(n)\lambda_i^n$ dengan $\deg Q_i \leq m_i - 1$ ; polinomial $Q_i$ itu tunggal karena penguraiannya langsung dan, di dalam tiap sukunya, koefisien $Q_i$ adalah koordinat pada basis $(n^j\lambda_i^n)_j$ (pertanyaan 8). Pemeriksaan kewarasan pada dimensinya: $\sum_i m_i = k$ .

10. $P = X^2 - 4X + 4 = (X - 2)^2$ : penyelesaiannya $(a + bn)2^n$ . Data awalnya: $a = 1$ , $2(a + b) = 0$ , jadi $b = -1$ :

u_n = (1 - n)\,2^n .

Periksa: $u_2 = 4u_1 - 4u_0 = -4$ , dan $(1 - 2)\cdot4 = -4$ .

11. Tulis $u_n = \lambda_1^n\bigl(c_1 + \sum_{i\geq2} c_i(\lambda_i/\lambda_1)^n\bigr)$ ; tiap rasionya bermodulus $< 1$ , jadi kurungnya menuju $c_1 \neq 0$ : karenanya $u_n \sim c_1\lambda_1^n$ . Khususnya $u_n \neq 0$ untuk $n$ yang besar, dan

\frac{u_{n+1}}{u_n} = \lambda_1\,\frac{c_1 + o(1)}{c_1 + o(1)} \longrightarrow \lambda_1 .

12. Hitunglah:

q(a_{n+1}, b_{n+1}) = (a_n + 2b_n)^2 - 2(a_n + b_n)^2 = -a_n^2 + 2b_n^2 = -q(a_n, b_n).

Karena $q(a_0, b_0) = 1 - 2 = -1$ , diperoleh $a_n^2 - 2b_n^2 = (-1)^{n+1}$ . Secara struktural: $q(a, b) = (a - \sqrt2\,b)(a + \sqrt2\,b)$ dan pemetaan linear $M$ mengalikan faktor $a + \sqrt2 b$ dengan $1 + \sqrt2$ serta faktor $a - \sqrt2 b$ dengan $1 - \sqrt2$ (hitunglah: $a_{n+1} + \sqrt2 b_{n+1} = (1 + \sqrt2)(a_n + \sqrt2 b_n)$ ); jadi hasil kalinya dikalikan $(1 + \sqrt2)(1 - \sqrt2) = -1 = \det M$ pada tiap langkah.

13. Karena $a_n^2 - 2b_n^2 = (a_n - \sqrt2 b_n)(a_n + \sqrt2 b_n) = (-1)^{n+1}$ , berlaku

\Bigl|\frac{a_n}{b_n} - \sqrt2\Bigr| = \frac{\abs{a_n^2 - 2b_n^2}}{b_n(a_n + \sqrt2 b_n)} = \frac{1}{b_n(a_n + \sqrt2 b_n)} \leq \frac1{2b_n^2},

dengan memakai $a_n \geq b_n \geq 1$ (secara induktif keduanya naik) sehingga $a_n + \sqrt2 b_n \geq (1 + \sqrt2)b_n \geq 2b_n$ . Nilai eigen $M$ : $\chi_M = X^2 - 2X - 1$ , dengan akar $1 \pm \sqrt2$ ; karena $(a_0, b_0)$ punya komponen tak nol pada vektor eigen dominannya (semua unsurnya positif), berlaku $b_n \sim c(1 + \sqrt2)^n$ dengan $c > 0$ (pertanyaan 11). Karenanya galatnya $\asymp (1 + \sqrt2)^{-2n} = (3 + 2\sqrt2)^{-n}$ : peluruhan geometri dengan rasio $1/(3 + 2\sqrt2) = 3 - 2\sqrt2 \approx 0.172$ .

14. (a) Dari pertanyaan 9: $\abs{u_n} \leq \sum_i \abs{Q_i(n)}\abs{\lambda_i}^n \leq \bigl(\sum_i \abs{Q_i(n)}\bigr)\rho^n$ , dan tiap $\abs{Q_i(n)} \leq C_i n^{m_i - 1} \leq C_i n^{m-1}$ untuk $n \geq 1$ : jumlahkan konstantanya. (b) Misalkan $\rho' = \max_{i \geq 2}\abs{\lambda_i} < \abs{\lambda_1}$ dan $d = \deg Q_1$ dengan koefisien utama $c \neq 0$ . Maka $u_n = Q_1(n)\lambda_1^n + R_n$ dengan $\abs{R_n} \leq Cn^{m-1}\rho'^n$ , dan

\frac{R_n}{Q_1(n)\lambda_1^n} = O\Bigl(n^{m-1-d} \bigl(\rho'/\abs{\lambda_1}\bigr)^n\Bigr) \longrightarrow 0

(sebab geometri mengalahkan polinomial). Jadi

u_n \sim Q_1(n)\,\lambda_1^n \sim c\,n^d\lambda_1^n, \qquad \frac{u_{n+1}}{u_n} \longrightarrow \lambda_1 \quad\text{(sebab } Q_1(n{+}1)/Q_1(n) \to 1\text{)}.

Periksa pada pertanyaan 10: untuk $u_n = (1-n)2^n$ rasionya adalah

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

15. Induksi pada $n$ . Untuk $n = 1$ , $A_{ij}$ mencacah jalan berpanjang $1$ . Langkahnya: jalan berpanjang $n + 1$ dari $i$ ke $j$ adalah jalan berpanjang $n$ dari $i$ ke suatu simpul $\ell$ yang disusul rusuk $\ell j$ :

\#\{\text{jalan}\} = \sum_{\ell} (A^n)_{i\ell}A_{\ell j} = (A^{n+1})_{ij}.

16. Di sini $J = 3\Pi$ dengan $\Pi = J/3$ proyeksi pada $\operatorname{Vect}(1,1,1)$ sepanjang bidang $x + y + z = 0$ (sebab $\Pi^2 = \Pi$ karena $J^2 = 3J$ ). Maka $A = J - I = 2\Pi - (I - \Pi)$ , dan karena $\Pi$ dan $I - \Pi$ merupakan proyeksi yang saling melengkapi,

A^n = 2^n\,\Pi + (-1)^n (I - \Pi), \qquad\text{yakni}\qquad (A^n)_{ij} = \frac{2^n}3 + (-1)^n\Bigl(\delta_{ij} - \frac13\Bigr),

sehingga diperoleh kedua rumus yang tertulis tadi. Pada $n = 2$ : diagonalnya $(4 + 2)/3 = 2$ (yaitu jalan $i \to \ell \to i$ lewat kedua tetangga $\ell$ ); di luar diagonal $(4 - 1)/3 = 1$ (yaitu satu-satunya jalan $i \to \ell \to j$ lewat simpul ketiga).

17. Misalkan $w_n^{(0)}, w_n^{(1)}$ mencacah kata yang sah dan berpanjang $n$ , berturut-turut yang berakhiran $0$ dan $1$ . Menambahkan satu huruf: angka $0$ boleh menyusul apa saja, angka $1$ hanya boleh menyusul $0$ :

\begin{pmatrix} w_{n+1}^{(0)}\\ w_{n+1}^{(1)}\end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0\end{pmatrix} \begin{pmatrix} w_n^{(0)}\\ w_n^{(1)}\end{pmatrix}.

Setelah dijumlahkan, $w_{n+2} = w_{n+1} + w_n$ (atau: syaratkan huruf pertamanya). Dengan $w_1 = 2$ , $w_2 = 3$ : secara induktif $w_n = F_{n+2}$ (sebab $F_3 = 2$ , $F_4 = 3$ , dengan rekurensi yang sama). Laju tumbuhnya: akar $X^2 - X - 1$ adalah $\varphi > \abs\psi$ (Latihan 3.5), dan komponen $\varphi$ -nya tak nol (sebab $w_n$ positif dan $\psi^n \to 0$ ), jadi pertanyaan 11 memberi $w_{n+1}/w_n \to \varphi = \frac{1 + \sqrt5}2$ .

18. Di sini $A = \left(\begin{smallmatrix} 0&1&0\\ 1&0&1\\ 0&1&0\end{smallmatrix}\right)$ . Periksa:

A(1, \pm\sqrt2, 1)^{\mathsf T} = (\pm\sqrt2, 2, \pm\sqrt2)^{\mathsf T} = \pm\sqrt2\,(1, \pm\sqrt2, 1)^{\mathsf T}, \qquad A(1, 0, -1)^{\mathsf T} = 0 :

sehingga nilai eigennya $\sqrt2, -\sqrt2, 0$ ( $= 2\cos\frac\pi4, 2\cos\frac{3\pi}4, 2\cos\frac\pi2$ ). Uraikan $e_1$ pada basis eigennya lalu baca koordinat ketiganya, atau pakailah kesetangkupan: dengan $v_\pm = (1, \pm\sqrt2, 1)$ , $v_0 = (1, 0, -1)$ , terperiksa $e_1 = \frac14 v_+ + \frac14 v_- + \frac12 v_0$ , sehingga untuk $n \geq 1$

(A^n)_{13} = \Bigl(\tfrac14(\sqrt2)^n v_+ + \tfrac14(-\sqrt2)^n v_- + 0\Bigr)_{\!3} = \frac{(\sqrt2)^n + (-\sqrt2)^n}{4},

yang nol untuk $n$ ganjil (grafnya bipartit: kedua ujungnya berjarak genap), dan $2\cdot 2^{n/2}/4 = 2^{n/2 - 1}$ untuk $n$ genap. Pada $n = 4$ : $2^{1} = 2$ , yang cocok dengan kedua jalan $1\,2\,1\,2\,3$ dan $1\,2\,3\,2\,3$ .

19. Jalan tertutup berpanjang $n$ dari $i$ berjumlah $(A^n)_{ii}$ ; menjumlahkannya atas $i$ memberi $\operatorname{tr}(A^n)$ . Setelah $A$ ditrigonalkan (atas $\C$ ), $A^n$ menjadi segitiga dengan diagonal $\lambda_i^n$ : jadi $\operatorname{tr}(A^n) = \sum_i\lambda_i^n$ . Untuk segitiganya: $\operatorname{tr}(A^n) = 3\,\frac{2^n + 2(-1)^n}3 = 2^n + 2(-1)^n = 2^n + (-1)^n + (-1)^n$ , yakni spektrum $\{2, -1, -1\}$ , yang selaras dengan pertanyaan 16.

20. Kolom $W^{\mathsf T}$ : $W^{\mathsf T}e_i = e_{i-1}$ untuk $i \geq 1$ dan $W^{\mathsf T}e_0 = e_{k-1}$ ; setelah dinamai ulang menurut urutan $e_0, e_1, \dots$ inilah persis matriks pendamping bagi $X^k - 1$ (dengan $a_0 = 1$ dan $a_m = 0$ untuk yang lain). Menurut pertanyaan 2: $\chi_{W} = \chi_{W^{\mathsf T}} = X^k - 1 = \mu_{W}$ . Akarnya $\omega^j$ ( $j = 0, \dots, k-1$ ) adalah $k$ akar ke- $k$ dari satu yang berbeda: jadi $W$ dapat didiagonalkan (pertanyaan 3, atau Latihan 3.8: sebab $W^k = I$ ). Vektor eigennya: $Wf_j = \sum_m \omega^{-jm}e_{m+1} = \sum_{m'}\omega^{-j(m'-1)}e_{m'} = \omega^j f_j$ .

21. Sirkulan adalah polinomial dalam $W$ , dan polinomial dalam satu matriks tetap saling komutatif. Tiap $f_j$ merupakan vektor eigen bagi setiap pangkatnya: $W^m f_j = \omega^{jm}f_j$ , jadi

Cf_j = \sum_m c_m\omega^{jm} f_j = \widehat c(\omega^j)\,f_j :

maka basis $(f_0, \dots, f_{k-1})$ (bebas: Vandermonde atas $\omega^{-j}$ yang berbeda, Latihan 2.11) mendiagonalkan setiap sirkulan sekaligus, dengan nilai eigen seperti dinyatakan tadi.

22. Determinannya adalah hasil kali nilai eigennya (diagonalkan saja): $\det C = \prod_{j}\widehat c(\omega^j)$ . Untuk $k = 3$ , dengan $c_0 = a$ , $c_1 = b$ , $c_2 = c$ dan $\omega = j = \eu^{2\iu\pi/3}$ :

\det C = (a + b + c)(a + bj + cj^2)(a + bj^2 + cj^4),

dan $j^4 = j$ : jadi persis pemfaktoran pada Latihan 2.8.

23. $M = \frac12(W + W^{-1})$ adalah sirkulan (sebab $W^{-1} = W^{k-1}$ ), dengan nilai eigen $\frac12(\omega^j + \omega^{-j}) = \cos\frac{2\pi j}k$ pada basis $f_j$ yang sama. Koordinatnya: tulis $x^{(0)} = \sum_j \alpha_j f_j$ . Koordinat $f_j$ berjumlah $\sum_m \omega^{-jm}$ , yang bernilai $k$ untuk $j = 0$ dan $0$ selain itu (jumlah geometri dengan rasio $\omega^{-j} \neq 1$ ). Menjumlahkan koordinat $x^{(0)}$ : $\sum_m x^{(0)}_m = \alpha_0\,k$ , jadi $\alpha_0 = \frac1k\sum_m x^{(0)}_m$ , yakni rata-ratanya.

24. Di sini $x^{(n)} = M^nx^{(0)} = \sum_j \alpha_j\cos^n\bigl(\tfrac{2\pi j}k\bigr)f_j$ . Untuk $k$ ganjil, $\abs{\cos(2\pi j/k)} < 1$ bagi setiap $j \neq 0$ (sebab sudutnya tak pernah $0$ atau $\pi$ ), jadi semua sukunya kecuali $j = 0$ menuju $0$ : $x^{(n)} \to \alpha_0 f_0$ , yakni vektor konstan yang sama dengan rata-ratanya — perataan pada cincin ganjil menyeragamkan. Untuk $k = 4$ nilai eigennya $1, 0, -1, 0$ : suku $j = 2$ , yakni $\alpha_2(-1)^nf_2$ dengan $f_2 = (1, -1, 1, -1)^{\mathsf T}$ , berayun selamanya. Halangannya adalah rata-rata berselang-seling: setelah koordinat $x^{(0)}$ dikalikan $(-1)^m$ lalu dijumlahkan, perhitungan jumlah geometri yang sama memberi $\sum_m (-1)^mx^{(0)}_m = 4\alpha_2$ : jadi prosesnya konvergen bila dan hanya bila $x^{(0)}_0 - x^{(0)}_1 + x^{(0)}_2 - x^{(0)}_3 = 0$ , dan ketika itu ia konvergen ke rata-ratanya.

25. Matriks pendamping mengubah rekurensi skalar berorde $k$ menjadi rekurensi vektor berorde satu, sehingga rumus tertutupnya menjadi pernyataan tentang $C^n$ — yakni kandang reduksi sendiri (pertanyaan 1–5). Lema penguraian kernel murni aljabar polinomial (Bézout ditambah kekomutatifan), jadi ia memecah $\ker P(S)$ walaupun $\mathcal{S}$ berdimensi tak hingga (pertanyaan 7–9). Nilai eigen dominan menguasai laju tumbuh karena setiap sumbangan lain terabaikan secara geometri setelah dinormalkan — dan itu pula sebabnya galat Pell meluruh secepat kuadrat akar dominannya (pertanyaan 11–14). Pangkat matriks ketetanggaan mencacah jalan karena perkalian matriks menjumlah atas simpul antaranya, sehingga spektrumnya mencacah jalan tertutup (pertanyaan 15–19). Matriks yang komutatif berbagi basis eigen, dan satu basis Fourier lalu mendiagonalkan seluruh aljabar sirkulan dalam satu tarikan (pertanyaan 20–24). Puncaknya: teorema dasar rekurensi linear (pertanyaan 9); dan untuk matriks tak negatif, alasan mengapa akar dominan seperti $\varphi$ atau $1 + \sqrt2$ otomatis real, positif dan sederhana adalah teorema Perron–Frobenius, yang dibuktikan pada jilid Tahun ke-3.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium