Như các mục trước, cho $V$ là không gian véctơ $n$-chiều trên trường số $\mathbb{K}$.
Trong mục này ta khảo sát bài toán chéo hóa và xem xét một vài ứng dụng của nó.
24.1. Bài toán chéo hóa
Tự đồng cấu $f\in\text{End}(V)$ là chéo hóa được nếu tồn tại cơ sở $S$ của $V$ sao cho $M_S(f)$ là ma trận chéo. Bài toán chéo hóa yêu cầu chỉ ra điều kiện cần và đủ cho sự tồn tại và phương pháp tìm một cơ sở $S$ sao cho $M_S(f)$ là ma trận chéo. Trước hết ta giới thiệu về sự phân rã trên $\mathbb{K}$ và nghiệm bội của đa thức. $\textbf{Định nghĩa 24.1.}\ $
Cho đa thức $p(t)\in\mathbb{K}[t]$.
Bây giờ ta khảo sát mối liên hệ giữa tính chéo hoá được của một tự đồng
cấu tuyến tính và tính phân rã của đa thức đặc trưng của nó.
- Ta nói rằng $p(t)$ phân rã trên $\mathbb{K}$ nếu tồn tại $a,a_1,\dots,a_d\in\mathbb{K}$ (không nhất thiết phân biệt) sao cho $ p(t) = a(t-a_1)\cdots(t-a_d). $
- Một nghiệm $\lambda\in\mathbb{K}$ của $p(t)$ được gọi là $\textbf{nghiệm bội}$ nếu $(t-\lambda)^2$ chia hết $p(t)$. Số nguyên dương lớn nhất $k$ sao cho $(t-\lambda)^k$ chia hết $p(t)$ được gọi là $\textbf{số bội}$ của $\lambda$ và ký hiệu bởi $\mathrm{mult}(p(t),\lambda)$.
$\textbf{Mệnh đề 24.2.} \ $
Cho $f\in\text{End}(V)$ và $\mathcal{P}_f(t)$ là đa thức đặc trưng của $f$.
- Nếu $f$ là chéo hóa được thì $\mathcal{P}_f(t)$ phân rã trên $\mathbb{K}$, tức $\mathcal{P}_f(t)=\pm(t-\lambda_1)\cdots(t-\lambda_n)$ với $\lambda_1,\dots,\lambda_n\in\mathbb{K}$.
- Nếu $\mathcal{P}_f(t)=\pm(t-\lambda_1)\cdots(t-\lambda_n)$ với $\lambda_1,\dots,\lambda_n\in\mathbb{K}$ đôi một khác nhau, thì $f$ là chéo hóa được.
$\textbf{Chứng minh.} \ $
(a)$\ $ Vì $f$ là tự đồng cấu chéo hóa được, nên gọi $S$ là cơ sở sao cho ma trận của $f$ trong $S$ là ma trận chéo
$$
M_S(f) = \begin{bmatrix}
\lambda_1&\dots&0\\
\vdots&\ddots&\vdots\\
0&\dots&\lambda_n\\
\end{bmatrix}.
$$
Khi đó
$$
\mathcal{P}_f(t)=\left|\begin{matrix}
\lambda_1-t&\dots&0\\
\vdots&\ddots&\vdots\\
0&\dots&\lambda_n-t
\end{matrix}\right| =(\lambda_1-t)\cdots(\lambda_n-t).
$$
(b)$\ $ Nếu $\mathcal{P}_f(t)=\pm(t-\lambda_1)\cdots(t-\lambda_n)$
với $\lambda_1,\dots,\lambda_n\in\mathbb{K}$ đôi một khác nhau, thì tự đồng cấu
$f$ có $n$ giá trị riêng đôi một khác nhau theo Bổ đề 23.1,
do đó $f$ là chéo hóa được theo Định lý 22.21.
$\textbf{Ví dụ 24.3.}\ $
Cho $f\in\text{End}(\mathbb{R}^3)$ có ma trận trong cơ sở chính tắc
$\mathcal{E}=\set{\mathbf{e}_1,\mathbf{e}_2,\mathbf{e}_3}$ là
$$
A = \begin{bmatrix}
3&0&0\\ 0&3&4\\ 0&0&4
\end{bmatrix}.
$$
Đa thức đặc trưng của $f$ là
$$
\mathcal{P}_f(t) = \left|\begin{matrix}
3-t&0&0\\ 0&3-t&4\\ 0&0&4-t
\end{matrix}\right| = -(t-3)^2(t-4).
$$
Như vậy $\lambda_1=3$ là giá trị riêng của $f$ với bội 2, và
$\lambda_2=4$ là giá trị riêng của $f$ với bội 1.
Với $\mathbf{x}=[x_1,x_2,x_3]^T$, không gian con riêng
$E_{f,3}$ là tập nghiệm của hệ phương trình
$$
(A-3I_3)\mathbf{x}=\mathbf{0} \;\Leftrightarrow\;
x_3 =0.
$$
Thế nên $E_{f,3} =\langle\mathbf{e}_1,\mathbf{e}_2\rangle_\mathbb{R}$.
Không gian riêng con $E_{f,4}$ là tập nghiệm của hệ phương trình
$$
(A-4I_3)\mathbf{x}=\mathbf{0} \;\Leftrightarrow\;
\begin{cases}
-x_1 &=0\\
-x_2+4x_3 &=0.
\end{cases}
$$
Thế nên $E_{f,4} = \langle\mathbf{v}=\begin{bmatrix}0,4,1\end{bmatrix}^T\rangle_\mathbb{R}$.
Rõ ràng $S=\set{\mathbf{e}_1,\mathbf{e}_2,\mathbf{v}}$ là một cơ sở
của $\mathbb{R}^3$ gồm các véctơ riêng, và $f(\mathbf{e}_i)=3\mathbf{e}_i$ với $i=1,2$
và $f(\mathbf{v})=4\mathbf{v}$. Vậy $f$ là tự đồng cấu chéo hóa được với
$$
M_S(f) = \begin{bmatrix}
3&0&0\\ 0&3&0\\ 0&0&4
\end{bmatrix}.
$$
Theo mệnh đề trên, trường hợp còn lại để làm rõ là $f$ chéo hóa được khi $\mathcal{P}_f(t)$ có nghiệm bội. Ứng với một giá trị riêng $\lambda$ của $f$, chiều của không gian con riêng $E_{f,\lambda}$ liên hệ với số bội $\text{mult}(\mathcal{P}_f(t),\lambda)$ như sau.
$\textbf{Bổ đề 24.4.} \ $
Nếu $\lambda$ là một giá trị riêng của $f\in\text{End}(V)$ thì
$$
1\le \dim(E_{f,\lambda})\le \text{mult}(\mathcal{P}_f(t),\lambda).
$$
$\textbf{Chứng minh.} \ $ Cho $r=\dim(E_{f,\lambda})$ và $S'=\set{\mathbf{v}_1,\dots,\mathbf{v}_r}$ là một cơ sở của $E_{f,\lambda}.$ Rõ ràng $1\le r$, vì $\lambda$ là giá trị riêng của $f$. Ta mở rộng $S'$ thành một cơ sở $S=\set{\mathbf{v}_1,\dots,\mathbf{v}_r,\mathbf{v}_{r+1},\dots,\mathbf{v}_n}$ của $V$. Khi đó $$ A := M_S(f) = \left[ \begin{array}{ccc|c} \lambda& & 0 & \\ &\ddots& & \ast\\ 0 & & \lambda& \\ \hline & O & & A' \end{array} \right] $$ trong đó khối thứ nhất có cấp $r\times r$. Thế nên khai triển định thức $\left\vert A-tI_n\right\vert$ lần lượt theo $r$ cột thứ nhất từ trái qua phải, ta nhận được $ \mathcal{P}_f(t) = (t-\lambda)^r\cdot P_{A'}(t). $ Vì vậy $\dim(E_{f,\lambda})=r\le \text{mult}(\mathcal{P}_f(t),\lambda)$.
Bây giờ ta phát biểu và chứng minh kết quả chính của mục này. $\textbf{Định lý 24.5.} [\textbf{Tiêu chuẩn chéo hóa được}] \ $
Cho tự đồng cấu $f\in\text{End}(V)$. Giả sử $\lambda_1,\dots,\lambda_r$ là
các giá trị riêng phân biệt của $f$.
Khi đó các phát biểu sau đây là tương đương.
- $f$ là chéo hóa được.
- Không gian $V$ có một cơ sở gồm những véctơ riêng của $f$.
- Tồn tại các không gian con bất biến một chiều $V_1,\dots,V_n$ của $f$ sao cho \[ V=V_1\oplus V_2\oplus\dots\oplus V_n. \]
- $\mathcal{P}_f(t)$ phân rã trên $\mathbb{K}$ và $\dim(E_{f,\lambda_i})=\text{mult}(\mathcal{P}_f(t),\lambda_i)$ với $i=1,\dots,r$.
- Không gian $V$ là tổng trực tiếp của các không gian riêng $$ V=E_{f,\lambda_1}\oplus \cdots\oplus E_{f,\lambda_r}. $$
- $\dim V=\dim E_{f,\lambda_1}+\cdots+\dim E_{f,\lambda_r}$.
$\textbf{Chứng minh.} \ $
Trước hết ta chứng minh (a) và (b) là tương đương.
Từ định nghĩa, toán tử $f$ chéo hóa được khi và chỉ khi tồn tại
cơ sở $S=\{\mathbf{v}_1,\dots,\mathbf{v}_n\}$ của $V$
sao cho $M_S(f)$ là ma trận chéo với các phần tử trên đường chéo chính
thuộc vào tập $\{\lambda_1,\dots,\lambda_r\}.$ Điều này tương đương với
việc ứng với mỗi véctơ $\mathbf{v}_i,$ ta tìm được $\lambda_j$ sao cho
$f(\mathbf{v}_i)=\lambda_j\mathbf{v}_i,$ hay tương đương với việc
$S$ là cơ sở gồm các véctơ riêng. Vậy (a) và (b) là tương đương với nhau.
Tiếp theo, ta chứng minh (b) và (c) là tương đương.
Giả sử ta có (b). Gọi $S=\{\mathbf{v}_1,\dots,\mathbf{v}_n\}$
là cơ sở của $V$ trong đó $\mathbf{v}_i$ là các véctơ riêng của $f$.
Khi đó $V_i = \langle\mathbf{v}_i\rangle_{\mathbb{K}}$ là các không gian con bất biến
một chiều của $f$. Do $S$ là cơ sở của $V$ nên mỗi véctơ của $V$
đều được viết duy nhất dưới dạng tổ hợp tuyến tính của các
véctơ~$\mathbf{v}_i$.
Vì vậy $V=V_1\oplus\dots\oplus V_n$.
Ngược lại, giả sử có (c). Với mỗi $i$, lấy $\mathbf{v}_i$ là
cơ sở của $V_i$. Khi đó $\{\mathbf{v}_1,\dots,\mathbf{v}_n\}$
là cơ sở của $V$ gồm các véctơ riêng của $f$.
Từ Mệnh đề 22.19, ta có ngay tổng $E_{f,\lambda_1}+ \cdots+E_{f,\lambda_r}$ là tổng trực tiếp.
Do vậy, vì $V$ là hữu hạn chiều, nên
(e) và (f) là tương đương theo Định lý 14.17.
Để hoàn thành việc chứng minh định lý, ta sẽ chỉ ra
(b)$\Rightarrow$(d)$\Rightarrow$(e)$\Rightarrow$(b).
Trước hết, ta chứng minh $(b)\Rightarrow (d)$.
Giả sử $S$ là cơ sở của $V$ từ những véctơ riêng của~$f$.
Sắp xếp $S = \{\mathbf{v}^{(1)}_1,\dots,\mathbf{v}^{(1)}_{n_1},\dots,
\mathbf{v}^{(r)}_1,\dots,\mathbf{v}^{(r)}_{n_r}\}$ sao cho
$$
\{\mathbf{v}^{(i)}_1,\dots,\mathbf{v}^{(i)}_{n_i}\} = S\cap E_{f,\lambda_i}
\quad i=1,\dots,r.
$$
Rõ ràng $M_S(f)$ là ma trận chéo, nên
$\mathcal{P}_f(t) =\det(M_S(f)-tI_n)$ phân rã trên~$\mathbb{K}$.
Đặt $m_i = \text{mult}(\mathcal{P}_f(t),\lambda_i)$
với $i=1,\dots,r$. Theo Bổ đề 24.4, ta có
$$
n_1+\cdots+n_r = n,\quad m_1+\cdots+m_r = n,\quad
n_i\le \dim( E_{f,\lambda_i})\le m_i.
$$
Do vậy $n_i=\dim( E_{f,\lambda_i})=m_i$ với $i=1,\dots, r$.
Tiếp theo, ta chỉ ra (d)$\Rightarrow$(e).
Đặt $W = E_{f,\lambda_1}+ \cdots+E_{f,\lambda_r}$.
Vì $\lambda_1,\dots,\lambda_r$ đôi một phân biệt,
theo Mệnh đề 22.19, mỗi $\mathbf{w}\in W$ được
biểu diễn duy nhất dạng $\mathbf{w}=\sum_{i=1}^r\mathbf{u}_i$
với $\mathbf{u}_i\in E_{f,\lambda_i}$. Thế nên
$W = E_{f,\lambda_1}\oplus \cdots\oplus E_{f,\lambda_r}$.
Định lý 14.17 suy ra $\dim(W)=m_1+\cdots+m_r=n$,
do vậy $W=V$.
Cuối cùng, ta cần chỉ ra $(e)\Rightarrow (b)$.
Thực vậy, với mỗi $i\in\{1,\dots,r\}$, ta chọn một cơ sở
$\{\mathbf{v}^{(i)}_1,\dots,\mathbf{v}^{(i)}_{n_i}\}$ của
không gian riêng $E_{f,\lambda_i}$, ở đây $n_i=\dim(E_{f,\lambda_i})$.
Đặt $S = \{\mathbf{v}^{(1)}_1,\dots,\mathbf{v}^{(1)}_{n_1},\dots,
\mathbf{v}^{(r)}_1,\dots,\mathbf{v}^{(r)}_{n_r}\}$.
Việc còn lại là chỉ ra hệ véctơ $S$ là độc lập tuyến tính.
Giả sử có $a_1^{(1)},\dots,a_{n_r}^{(r)}\in\mathbb{K}$ sao cho
$$
a^{(1)}_1\mathbf{v}^{(1)}_1+\cdots+a^{(1)}_{n_1}\mathbf{v}^{(1)}_{n_1}
+\cdots +a^{(r)}_1\mathbf{v}^{(r)}_1+\dots+
a^{(r)}_{n_r}\mathbf{v}^{(r)}_{n_r} = \mathbf{0}.
$$
Với mỗi $1\le i\le r$, ta thấy $\mathbf{u}_i:=
\sum_{j=1}^{n_i}a^{(i)}_j\mathbf{v}^{(i)}_j\in E_{f,\lambda_i}$.
Khi đó $\sum_{i=1}^m\mathbf{u}_i=\mathbf{0}$.
Theo Mệnh đề 22.19, ta được $\mathbf{u}_i=\mathbf{0}$
với mọi $1\le i\le r$. Từ định nghĩa của $\mathbf{u}_i$,
ta có ngay $a^{(i)}_j=0$ với mọi $i=1,\dots,r$ và $j=1,\dots,n_i$.
Do vậy, hệ véctơ $S$ là độc lập tuyến tính và (e)$\Rightarrow$(b).
Tiêu chuẩn chéo hóa được (Định lý 24.5) đưa ra câu trả lời đầy đủ cho bài toán chéo hóa giới thiệu đầu bài. Trong đó, nó đưa tới phương pháp tìm cơ sở $S$ của $V$ sao cho $M_S(f)$ là ma trận chéo theo các bước sau:
- Với một cơ sở $S'$ của $V$ và $A:=M_{S'}(f)$, ta tính đa thức đặc trưng $\mathcal{P}_f(t) = \det(A-tI_n)$ của $f$. Kiểm tra $\mathcal{P}_f(t)$ phân rã trên $\mathbb{K}$ hay không. Nếu $\mathcal{P}_f(t)$ không phân rã trên $\mathbb{K}$ thì kết luận $f$ không chéo hóa được. Ngược lại, xác định các nghiệm phân biệt $\lambda_1,\dots,\lambda_r$ của $\mathcal{P}_f(t)$, chúng cũng là các giá trị riêng của $f$ (xem Nhận xét 23.5).
- Với $i=1,\dots,r$, xác định một cơ sở $S_i$ của không gian con riêng $E_{f,\lambda_i}$ thông qua giải hệ phương trình $(A-\lambda_i I_n)\mathbf{x}=\mathbf{0}$. Khi đó kiểm tra \begin{equation} \tag{24.1} \dim(E_{f,\lambda_i}) = \mathrm{mult}(\mathcal{P}_f(t),\lambda_i). \end{equation} Nếu đẳng thức (24.1) không thỏa mãn thì $f$ không chéo hóa được. Ngược lại, khi đẳng thức (24.1) thỏa mãn với mọi giá trị riêng $\lambda_i$, ta kết luận $f$ chéo hóa được. Trong trường hợp này $S=\bigcup_{i=1}^r S_i$ là một cơ sở của $V$ gồm các véctơ riêng của $f$ và $M_S(f)$ là ma trận chéo.
$\textbf{Ví dụ 24.6.}\ $
Cho tự đồng cấu $f\colon\mathbb{R}^3\rightarrow\mathbb{R}^3$ xác định bởi
$$
f\left(\begin{bmatrix}a_1\\ a_2\\ a_3\end{bmatrix}\right)
=
\begin{bmatrix} 2 a_{1} +a_{2} +a_{3} \\
a_{1} +2 a_{2} +a_{3} \\
-a_{1} -a_{2}\end{bmatrix}.
$$
Với cơ sở chính tắc $\mathcal{E}$ của $\mathbb{R}^3$ ta có
$$
A := M_S(f) = \begin{bmatrix}2&1&1\\ 1&2& 1\\ -1&-1&0\end{bmatrix}
$$
và
$$
\mathcal{P}_f(t) =\det(A-tI_3)= -t^3+4t^2-5t+2 = -(t-1)^2(t-2).
$$
Như vậy, $\mathcal{P}_f(t)$ phân rã trên $\mathbb{R}$ và
$f$ có hai giá trị riêng $\lambda_1=1$ và $\lambda_2=2$.
Tiếp theo, ta tìm các cơ sở $S_i$ của không gian riêng $E_{f,\lambda_i}$.
- $\lambda_1=1$: $E_{f,1}$ là không gian nghiệm của hệ phương trình \begin{align*} (A-I_3)\cdot\mathbf{x}=\mathbf{0} & \Leftrightarrow \begin{bmatrix}1&1&1\\ 1&1& 1\\ -1&-1&-1\end{bmatrix}\cdot \begin{bmatrix}x_1\\ x_2\\ x_3\end{bmatrix} = \begin{bmatrix}0\\ 0\\ 0\end{bmatrix}\\ & \Leftrightarrow x_1+x_2+x_3=0. \end{align*} Do vậy $\dim(E_{f,1}) = 2 = \mathrm{mult}(\mathcal{P}_f(t),1)$ và $\set{\mathbf{v}_1=\begin{bmatrix}-1\\0\\ 1\end{bmatrix}, \mathbf{v}_2=\begin{bmatrix}-1\\1\\0\end{bmatrix}}$ là một cơ sở của~$E_{f,1}$.
- $\lambda_2=2$: $E_{f,2}$ là không gian nghiệm của hệ phương trình \begin{align*} (A-2I_3)\cdot\mathbf{x}=\mathbf{0} & \Leftrightarrow\; \begin{bmatrix}0&1&1\\ 1&0& 1\\ -1&-1&-2\end{bmatrix}\cdot \begin{bmatrix}x_1\\ x_2\\ x_3\end{bmatrix} = \begin{bmatrix}0\\ 0\\ 0\end{bmatrix} \\ & \Leftrightarrow\; \begin{cases} x_2+x_3&=0\\ x_1+x_3&=0. \end{cases} \end{align*} Do vậy $\dim(E_{f,2}) = 1 = \mathrm{mult}(\mathcal{P}_f(t),1)$ và $\set{\mathbf{v}_3=\begin{bmatrix}-1\\-1\\ 1\end{bmatrix}}$ là một cơ sở của~$E_{f,2}$.
$\textbf{Ví dụ 24.7.}\ $
Ta kiểm tra tính chéo hóa của ma trận
$$
A = \begin{bmatrix}1 & 0 & 2 \\ -2 & -1 & 4 \\ -1 & -1 & 4\end{bmatrix}.
$$
Đa thức đặc trưng của $A$ là
$$
\mathcal{P}_A(t) = \det(A-tI_3) = -t^3+4t^2-5t+2 = -(t-1)^2(t-2).
$$
Do đó $\mathcal{P}_A(t)$ phân rã trên $\mathbb{K}$ và $A$ có hai giá trị
riêng $\lambda_1=1$ và $\lambda_2=2$ với bội lần lượt là $2$ và $1$.
Với $\lambda_2=2$ ta có $\dim(E_{f,2})=1=\text{mult}(\mathcal{P}_A(t),2)$.
Ta xét trường hợp $\lambda_1=1$. Không gian con riêng $E_{f,1}$
là không gian nghiệm của hệ phương trình $(A-I_3)\cdot\mathbf{x}=\mathbf{0}$,
trong đó
$$
A-I_3= \begin{bmatrix}0 & 0 & 2 \\ -2 & -2 & 4 \\ -1 & -1 & 3\end{bmatrix},\quad
\text{rk}(A-I_3) = 2.
$$
Vì $\dim(E_{f,1})= 3-\text{rk}(A-I_3) = 1 < \text{mult}(\mathcal{P}_A(t),1)$,
nên $A$ không chéo hóa được.
24.2. Một vài ứng dụng
24.2.1. Tính lũy thừa của ma trận chéo hóa được
$\textbf{Ví dụ 24.8.}\ $
Cho $A=\begin{bmatrix}
0&1\\ -6&5
\end{bmatrix} \in\text{Mat}_2(\mathbb{R})$.
Ta chỉ ra rằng $A$ là chéo hóa được và tìm ma trận $C\in\text{Mat}_2(\mathbb{R})$ sao cho
$C^{-1}AC$ là ma trận chéo. Sau đó ta chỉ ra làm sao sử dụng tính chất này để tính
$A^k$ với mọi số nguyên dương $k$.
Trước tiên ta có đa thức đặc trưng của $A$ là
$$
\mathcal{P}_A(t) = \det(A-tI_2) = t^2-5t+6 = (t-2)(t-3).
$$
Do đó $A$ có hai giá trị riêng là $\lambda_1=2$ và $\lambda_2=3$,
và $A$ là chéo hóa được. Với $\lambda_1=2$ ta có
$E_{A,2}$ là không gian nghiệm của
$\begin{bmatrix}-2&1\\ -6&3\end{bmatrix}\begin{bmatrix}x_1\\ x_2\end{bmatrix}=\begin{bmatrix}0\\ 0\end{bmatrix}$,
do đó $E_{A,2}=\langle \begin{bmatrix}1\\ 2 \end{bmatrix}\rangle_\mathbb{R}$.
Tính toán tương tự, ta nhận được
$E_{A,3}=\langle \begin{bmatrix}1\\ 3\end{bmatrix}\rangle_\mathbb{R}$.
Khi đó $S=\set{\begin{bmatrix}1\\ 2\end{bmatrix}, \begin{bmatrix}1\\ 3\end{bmatrix}}$ là một cơ sở của $\mathbb{R}^2$
gồm các véctơ riêng. Cho
$$
C = \begin{bmatrix} 1&1\\ 2&3\end{bmatrix}
$$
là ma trận lập bởi các cột là các véctơ của $S$ (cũng là ma trận
chuyển cơ sở từ cơ sở chính tắc sang $S$).
Khi đó ta có
$$
C^{-1} = \begin{bmatrix} 3 & -1 \\ -2 & 1\end{bmatrix},\quad
D := C^{-1}AC = \begin{bmatrix} 2&0\\ 0&3\end{bmatrix}.
$$
Để tính $A^k$, ta thấy rằng $A=CDC^{-1}$. Vì vậy
\begin{align*}
A^k &= (CDC^{-1})^k = (CDC^{-1})(CDC^{-1})\cdots(CDC^{-1})\\
&= CD^kC^{-1} = \begin{bmatrix} 1&1\\ 2&3\end{bmatrix}\cdot \begin{bmatrix} 2^k & 0 \\ 0 & 3^k\end{bmatrix}
\cdot \begin{bmatrix} 3 & -1 \\ -2 & 1\end{bmatrix}\\
&= \begin{bmatrix}3\cdot 2^k -2\cdot 3^k& -2^k+3^k\\
3\cdot2^{k+1}-2\cdot 3^{k+1}&-2^{k+1}+3^{k+1}\end{bmatrix}.
\end{align*}
Như ví dụ trên, nếu $A\in\text{Mat}_n(\mathbb{K})$ là ma trận chéo hóa được, thì để tính $A^k$ với mọi số nguyên $k\ge 1$ ta thực hiện:
- Tính đa thức đặc trưng và tìm giá trị riêng của $A$. Từ đó tìm một cơ sở $S$ của $\mathbb{K}^n$ gồm các véctơ riêng của $A$.
- Lập ma trận $C$ từ cơ sở $S$ và tính $C^{-1}$ và ma trận chéo $D=C^{-1}AC$.
- Tính $A^k$ theo công thức $A^k=CD^kC^{-1}$ với mọi số nguyên $k\ge 1$.
24.2.2. Phương trình đệ quy tuyến tính của dãy số
Các ví dụ tiếp theo sau chỉ ra ứng dụng của bài toán chéo hóa vào tìm công thức tổng quát của dãy số. $\textbf{Ví dụ 24.9.}\ $
Cho dãy số có công thức đệ quy
$$
x_k = 5x_{k-1}-6x_{k-2}
$$
với $k\ge 2$ và giá trị ban đầu là $x_0=1$ và $x_1=0$.
Ta sử dụng lý thuyết chéo hóa để tìm công thức tổng quát của $x_k$
(chỉ phụ thuộc vào $k$).
Viết dãy theo ma trận ta có
$$
\begin{bmatrix}x_k\\ x_{k+1}\end{bmatrix} = \begin{bmatrix} 0&1\\ -6&5 \end{bmatrix}
\cdot \begin{bmatrix} x_{k-1}\\ x_{k} \end{bmatrix}
= \begin{bmatrix} 0&1\\ -6&5 \end{bmatrix}^k\cdot \begin{bmatrix} 1\\ 0 \end{bmatrix}.
$$
Đặt $A=\begin{bmatrix}0&1\\ -6&5\end{bmatrix}$. Theo Ví dụ 24.8, với $k\ge 1$
ta biết rằng
$$
A^k = \begin{bmatrix} 3\cdot 2^k -2\cdot 3^k& -2^k+3^k\\
3\cdot2^{k+1}-2\cdot 3^{k+1}&-2^{k+1}+3^{k+1}\end{bmatrix}.
$$
Do đó
$$
\begin{bmatrix} x_k\\ x_{k+1}\end{bmatrix} =A^k\cdot \begin{bmatrix} 1\\ 0\end{bmatrix} =
\begin{bmatrix} 3\cdot 2^k -2\cdot 3^k\\
3\cdot2^{k+1}-2\cdot 3^{k+1}\end{bmatrix}.
$$
Vậy $x_k = 3\cdot 2^k -2\cdot 3^k$ với mọi $k\ge 0$.
$\textbf{Ví dụ 24.10.}\ $
Cho các dãy số thỏa mãn hệ phương trình đệ quy tuyến tính
$$
\begin{cases}
x_k &= 5x_{k-1}+4y_{k-1}\\
y_k &= -3x_{k-1}-3y_{k-1}
\end{cases}
$$
với $n\ge 1$ và $x_0=4$ và $y_0=0$.
Ta sẽ tìm công thức tổng quát của $x_k$ và $y_k$.
Trước hết, ta viết hệ phương trình trên dưới dạng ma trận
$$
\begin{bmatrix}
x_k\\ y_k
\end{bmatrix}
=
\begin{bmatrix} 5&4\\ -3&-3 \end{bmatrix}\cdot
\begin{bmatrix} x_{k-1}\\ y_{k-1} \end{bmatrix}
\quad \mbox{ với } \quad
\begin{bmatrix} x_0\\ y_0 \end{bmatrix}
=
\begin{bmatrix} 4\\ 0\end{bmatrix}.
$$
Đặt $A = \begin{bmatrix} 5&4\\ -3&-3 \end{bmatrix}$. Khi đó
\begin{align*}
\mathcal{P}_A(t) &= \det
\left\vert \begin{matrix}
5-t&4\\ -3&-3-t
\end{matrix} \right\vert \\
&= (5-t)(-3-t)+12 = t^2-2t -3 = (t+1)(t-3).
\end{align*}
Do đó $A$ có hai giá trị riêng $\lambda_1 = -1$ và $\lambda_2=3$.
Tiếp theo, ta tính các không gian riêng tương ứng và nhận được
$E_{A,-1} = \langle \begin{bmatrix}2\\ -3\end{bmatrix}\rangle_\mathbb{R}$ và
$E_{A,3} = \langle \begin{bmatrix}2\\ -1\end{bmatrix}\rangle_\mathbb{R}$.
Tìm $a,b\in\mathbb{R}$ sao cho
$$
\begin{bmatrix}
4\\ 0
\end{bmatrix}
= a\begin{bmatrix}
2\\ -3
\end{bmatrix} +b
\begin{bmatrix}
2\\ -1
\end{bmatrix}
= \begin{bmatrix}
2a+2b \\ -3a-b
\end{bmatrix}.
$$
Giải hệ trên ta nhận được $a=-1$ và $b=3$.
Điều này suy ra
$$
\begin{bmatrix}
4\\ 0
\end{bmatrix}
= -1\begin{bmatrix}
2\\ -3
\end{bmatrix} +3
\begin{bmatrix}
2\\ -1
\end{bmatrix}.
$$
Bây giờ ta tính
\begin{align*}
\begin{bmatrix}
x_k\\ y_k
\end{bmatrix}
&=
A\cdot
\begin{bmatrix}
x_{k-1}\\ y_{k-1}
\end{bmatrix}
= A^k\cdot
\begin{bmatrix}
4\\0
\end{bmatrix}
= -A^k \begin{bmatrix}
2\\ -3
\end{bmatrix} +3 A^k
\begin{bmatrix}
2\\ -1
\end{bmatrix} \\
&= -(-1)^k\begin{bmatrix}
2\\ -3
\end{bmatrix} +3\cdot 3^k
\begin{bmatrix}
2\\ -1
\end{bmatrix}
= \begin{bmatrix}
2(3^{k+1} + (-1)^{k+1})\\
-3^{k+1}+3(-1)^k
\end{bmatrix}
\end{align*}
Cuối cùng ta có công thức tổng quát của phương trình đệ quy tuyến tính
là $x_k = 6\cdot 3^k - 2\cdot (-1)^k$
và $y_k = -3\cdot 3^k +3 \cdot(-1)^k$ với mọi $k\ge 0$.
$\textbf{Ví dụ 24.11.}\ $
Có một mảnh đất hình chữ nhật có kích thước $2\times 8$.
Một người muốn dùng gạch có kích thước $1\times 2$ với màu đen hoặc trắng
để lát toàn bộ mảnh đất trên, minh họa như hình dưới đây.
Trước khi lát mảnh đất, người đó tìm hiểu về số cách khác nhau để lát gạch
và khẳng định có 8704 cách. Dưới đây, chúng ta tìm hiểu khẳng định
trên đúng hay sai. Gọi $x_n$ là số cách khác nhau để lát gạch cho mảnh đất
hình chữ nhật có kích thước $2\times n$.
Giá trị ban đầu của nó là $x_1=2$ và $x_2=8$.
Ta tìm công thức đệ quy cho~$x_n$.
Với $n\ge 3$, ta có thể lát mảnh đất
kích thước $2\times n$ theo hai trường hợp tương ứng với số gạch ít nhất từ phía phải.
Trường hợp một là xoay viên gạch cuối đứng dọc và trước nó là mảnh đất đã lát kích thước
$2\times(n-1)$, trường hợp hai là hai viên gạch cuối nằm ngang và trước chúng là
mảnh đất đã lát kích thước $2\times(n-2)$, như hình sau:
Vì gạch chỉ có thể là trắng hoặc đen, nên trường hợp một chỉ có 2 cách chọn
để lát viên gạch cuối (trắng hay đen), trong khi có 4 cách chọn
(trắng/trắng, trắng/đen, đen/trắng, đen/đen)
để lát hai viên gạch cuối trong trường hợp 2.
Lập luận này dẫn đến công thức đệ quy
$$
x_n = 2x_{n-1}+4x_{n-2}\quad \mbox{với $n\ge 3$}.
$$
Cụ thể, với $n=1,\dots, 10$ ta có
Thế nên $x_8 = 8704$ và khẳng định của người trên là đúng.
Bây giờ ta xác định công thức tổng quát của $x_n$. Ta có
$$
\begin{bmatrix}
x_{n-1}\\ x_{n}
\end{bmatrix}
=
\begin{bmatrix}
0&1\\ 4&2
\end{bmatrix}\cdot
\begin{bmatrix}
x_{n-2}\\ x_{n-1}
\end{bmatrix}
= A^{n-2} \cdot
\begin{bmatrix}
2\\ 8
\end{bmatrix}
\quad \mbox{ với } \quad
A =
\begin{bmatrix}
0&1\\ 4&2
\end{bmatrix}.
$$
Đa thức đặc trưng của $A$ là
$$
\mathcal{P}_A(t)= \left\vert \begin{matrix}
-t&1\\ 4&2-t
\end{matrix}\right\vert = -t(2-t)-4 = t^2-2t-4.
$$
Vì biệt thức $\Delta=(-2)^2-4\cdot(-4)=20>0$, nên
$\mathcal{P}_A(t)$ có hai nghiệm $\lambda_1 = 1+\sqrt{5}$
và $\lambda_2= 1-\sqrt{5}$, và chúng là giá trị riêng của $A$.
Hai không gian con riêng tương ứng là
$$
E_{A,\lambda_1} = \langle \begin{bmatrix} 1\\ \lambda_1 \end{bmatrix}\rangle_\mathbb{R},\quad
E_{A,\lambda_2} = \langle \begin{bmatrix} 1\\ \lambda_2 \end{bmatrix}\rangle_\mathbb{R}.
$$
Hơn nữa, ta có biểu diễn
$
\begin{bmatrix}
2\\ 8
\end{bmatrix}
= \dfrac{3+\sqrt{5}}{\sqrt{5}}
\begin{bmatrix}
1\\ \lambda_1
\end{bmatrix}
+\dfrac{-3+\sqrt{5}}{\sqrt{5}}
\begin{bmatrix}
1\\ \lambda_2
\end{bmatrix}.
$
Do đó
\begin{align*}
\begin{bmatrix}
x_{n-1}\\ x_{n}
\end{bmatrix}
&= \frac{3+\sqrt{5}}{\sqrt{5}}
A^{n-2} \cdot
\begin{bmatrix}
1\\ \lambda_1
\end{bmatrix}
-\frac{3-\sqrt{5}}{\sqrt{5}}
A^{n-2} \cdot
\begin{bmatrix}
1\\ \lambda_2
\end{bmatrix} \\
&= \frac{2+\lambda_1}{\sqrt{5}}
\lambda_1^{n-2} \cdot
\begin{bmatrix}
1\\ \lambda_1
\end{bmatrix}
-\frac{2+\lambda_2}{\sqrt{5}}
\lambda_2^{n-2} \cdot
\begin{bmatrix}
1\\ \lambda_2
\end{bmatrix}.
\end{align*}
Từ các đẳng thức $\lambda_i^2 -2\lambda_i-4=0$ với $i=1,2$
ta nhận được
$$
x_n = \frac{(2+\lambda_1)\lambda_1^{n-1}-
(2+\lambda_2)\lambda_2^{n-1}}{\sqrt{5}}
= \frac{1}{2\sqrt{5}}(\lambda_1^{n+1}-\lambda_2^{n+1}).
$$
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $x_n$ | 2 | 8 | 24 | 80 | 256 | 832 | 2688 | 8704 | 28160 | 91136 |
24.2.3. Thuật toán sắp xếp thứ hạng trang web
Larry Page và Sergey Brin đã phát minh ra cách xếp hạng các trang web dựa theo mức độ quan trọng. Họ thành lập công ty Google dựa trên thuật toán của họ. Sau đây là một phiên bản đơn giản cách nó hoạt động. Mỗi trang web có một mức quan trọng tương ứng gọi là thứ hạng. Đây là một con số dương. Thứ hạng này được xác định bởi quy tắc sau. Giả sử mạng lưới internet có $n$ trang web. Nếu trang web $P$ liên kết với $n$ trang web khác $W_1, W_2,\ldots, W_n$ thì mỗi trang web $W_i$ có $\frac{1}{n}$ mức quan trọng của $P$. Ta sắp xếp thứ hạng trang web theo các bước sau:- Bước 1. Ma trận mức độ quan trọng là ma trận $M$ cấp $n\times n$ trong đó $m_{ij}$ là mức quan trọng của trang web $j$ dành cho trang web $i$.
Chẳng hạn, xét trường hợp đơn giản mạng lưới internet chỉ có 4 trang web. Các liên kết được biểu diễn bởi các mũi tên như hình sau.
Theo quy tắc về mức quan trọng ở trên, ta có:
- Trang web $A$ có $3$ liên kết, nên nó nhường $\frac{1}{3}$ mức quan trọng của nó cho các trang web $B, C, D$.
- Trang web $B$ có $2$ liên kết, nên nó nhường $\frac{1}{2}$ mức quan trọng của nó cho các trang web $C, D$.
- Trang web $C$ có $0$ liên kết, nên nó không nhường mức quan trọng của nó cho trang web nào cả.
- Trang web $D$ có $2$ liên kết, nên nó nhường $\frac{1}{2}$ mức quan trọng của nó cho các trang web $A, C$.
- Bước 2. Sau đó, ta hiệu chỉnh ma trận mức quan trọng bằng cách thay mỗi cột không bằng một cột với các thành phần đều bằng $\frac{1}{n}$ trong đó $n$ là số trang web. Ma trận hiệu chỉnh của ma trận $M$ cho bởi: $$ M'=\begin{bmatrix} 0 &0 &\frac{1}{4} &\frac{1}{2}\\ \frac{1}{3} &0 &\frac{1}{4} &0\\ \frac{1}{3} &\frac{1}{2} &\frac{1}{4} &\frac{1}{2}\\ \frac{1}{3} &\frac{1}{2} &\frac{1}{4} &0 \end{bmatrix}. $$
- Bước 3. Tìm ma trận Google. Giả sử $M$ là ma trận mức quan trọng cho mạng internet gồm $n$ trang và $M'$ là ma trận hiệu chỉnh của nó. Khi đó ma trận Google của $M$ với xác suất $p$ là ma trận $$ G=(1-p)M'+pN $$ trong đó $N$ là ma trận cấp $n\times n$ với tất cả các vị trí đều bằng $\frac{1}{n}$. Với trường hợp cụ thể trên, ma trận Google của ma trận $M$ với $p=0.15$ là \begin{align*} G &=0.85\begin{bmatrix} 0 &0 &\frac{1}{4} &\frac{1}{2}\\ \frac{1}{3} &0 &\frac{1}{4} &0\\ \frac{1}{3} &\frac{1}{2} &\frac{1}{4} &\frac{1}{2}\\ \frac{1}{3} &\frac{1}{2} &\frac{1}{4} &0 \end{bmatrix}+0.15\begin{bmatrix} \frac{1}{4} &\frac{1}{4} &\frac{1}{4} &\frac{1}{4}\\ \frac{1}{4} & \frac{1}{4}&\frac{1}{4} &\frac{1}{4}\\ \frac{1}{4} &\frac{1}{4} &\frac{1}{4} &\frac{1}{4}\\ \frac{1}{4} &\frac{1}{4} &\frac{1}{4} &\frac{1}{4} \end{bmatrix} \\ &=\begin{bmatrix} 0,037500 &0,0375 &0,2500&0,4625\\ 0,320833 & 0,0375&0,2500 &0,0375\\ 0,320833 &0,4625 &0,2500&0,4625 \\ 0,320833 &0,4625 &0,2500 &0,0375 \end{bmatrix}. \end{align*}
- Bước 4. Véctơ thứ hạng trang web là véctơ riêng của ma trận Google. Tính toán ta được véctơ riêng $\mathbf{v}=\begin{bmatrix} 0.423702688196764\\ 0.338654283027386\\ 0.687679853472486\\ 0.482582353314025\\ \end{bmatrix}$. Trang web $C$ quan trọng nhất với thứ hạng $0.687679853472486$, trang web $B$ xếp cuối cùng với thứ hạng $0.338654283027386$.
Sử dụng Maple
Chúng ta thấy rằng Tiêu chuẩn chéo hóa được (Định lý 24.5) đưa tới một thuật toán để kiểm tra cũng như thực hiện quá trình chéo hóa một một tự đồng cấu $f\in \mathrm{End}(V)$. Với các lệnh tính toán được trình bày ở mục Sử dụng $\texttt{Maple}$ ở hai bài phía trước, ta thực hiện chéo hóa đối với Ví dụ 24.6 theo từng bước dưới đây. Đầu tiên lập ma trận $A$ của tự đồng cấu và tính đa thức đặc trưng cũng như tìm nghiệm với số bội của đa thức đặc trưng:$\hspace{0cm}\texttt{> with(LinearAlgebra):}$
$\hspace{0cm}\texttt{> A := Matrix([[2,1,1],[1,2,1],[-1,-1,0]]):}$
$\hspace{0cm}\texttt{> Pa := CharacteristicPolynomial(A,t);}$
$\hspace{0.5cm}\texttt{ Pa := t^3-4*t^2+5*t-2}$
$\hspace{0cm}\texttt{> solve(Pa, t);}$
$\hspace{0.5cm}\texttt{ 2, 1, 1}$
Ta có $\mathcal{P}_A(t) = -(t^3-4t^2+5t-2)$ phân rã trên $\mathbb{R}$
với nghiệm $\lambda_1=2$ với bội 1 và nghiệm $\lambda_2=1$ với bội 2.
Ứng với các giá trị riêng $\lambda_1,\lambda_2$ của $A$,
ta cần tìm cơ sở của các không gian riêng của $A$.
Cơ sở của $E_{A,1}$ được tính bởi
$\hspace{0cm}\texttt{> NullSpace(A-IdentityMatrix(3));}$
với kết quả là $\set{\mathbf{v}_1=[-1,0,1]^T,\mathbf{v}_2=[-1,1,0]^T}$,
còn cơ sở của $E_{A,2}$ được tính bởi
$\hspace{0cm}\texttt{> NullSpace(A-2*IdentityMatrix(3));}$
và kết quả là $\set{\mathbf{v}_2=[-1,-1,1]^T}$.
Điều kiện về chiều không gian riêng và số bội được thỏa mãn nên $A$ chéo hóa được.
Với $C=\begin{bmatrix}\mathbf{v}_1,\mathbf{v}_2,\mathbf{v}_3\end{bmatrix}\in\text{Mat}_{3}(\mathbb{R})$,
$C^{-1}AC$ là ma trận chéo với phần tử trên đường chéo chính lần lượt là $1,1,2$.
Bây giờ, ta tính toán véctơ riêng trong Thuật toán sắp xếp thứ hạng trang web
được trình bày ở trên với $\texttt{Maple}:$
$\hspace{0cm}\texttt{> M := Matrix([[0,0,1/4,1/2],[1/3,0,1/4,0],}$
$\hspace{0.5cm}\texttt{ [1/3,1/2,1/4,1/2],[1/3,1/2,1/4,0]]):}$
$\hspace{0cm}\texttt{> N := Matrix(4, 4, fill = 1/4):}$
$\hspace{0cm}\texttt{> p:= 0.15:}$
$\hspace{0cm}\texttt{> G := (1-p)*M+p*N;}$
$\hspace{0cm}\texttt{> Eigenvalues(G);}$
Ta nhận được ma trận $G$ như trên và giá trị riêng của nó là
$$
\begin{bmatrix} 0.999978075837565\\ -0.268095536334335+0.233301727781345\cdot i \\
-0.268095536334335-0.233301727781345 \cdot i\\ -0.101287003168894\end{bmatrix}
$$
trong đó có hai giá trị riêng thực. Véctơ riêng ứng với giá trị riêng thực thứ nhất
($\sim 1$) là véctơ $\mathbf{v}$ trình bày ở trên, còn véctơ riêng ứng với giá
trị riêng thực thứ hai có giá trị âm nên không được dùng để so sánh thứ hạng.
Comments
Post a Comment