Định trị một đại lượng bằng hai cách [5]

Lần này ta chứng minh một định lý kinh điển của đại số: định lý Cayley-Hamilton. Mặc dù có thể phát biểu tổng quát hơn, ta chỉ phát biểu nó cho các trường số thực và phức.

Định lý Cayley-Hamilton: Gọi $A$ là một ma trận vuông thực hoặc phức. Gọi $p(x) = \det(xI-A)$ là đa thức đặc trưng của $A$ . Ta có $p(A) = 0$ .

Ví dụ:

$A = \begin{bmatrix} 2 & 3\\ 1 & 4\end{bmatrix}$
Thì đa thức $p(x)$ , tức là định thức của ma trận $(xI-A)$ là
$p(x) = \det \begin{bmatrix} x-2 & -3\\ -1 & x-4\end{bmatrix} = (x-2)(x-4)-3 = x^2-6x+5$
Thay $x$ bằng ma trận $A$ trong $p(x)$ , dễ dàng xác minh được rằng
$p(A) = A^2 - 6A + 5 = \begin{bmatrix} 2 & 3\\ 1 & 4\end{bmatrix}^2 - 6\begin{bmatrix} 2 & 3\\ 1 & 4\end{bmatrix} + 5\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix} = \begin{bmatrix} 0 & 0\\ 0 & 0\end{bmatrix}$

Tuyệt nhỉ! Chứng minh kiểu đại số hoặc kiểu hình topo của định lý này có thể tìm ở nhiều nơi, bao gồm cái Wikipedia entry tôi liên kết ở trên, hoặc là tìm bên Planet Math, hoặc google ra cả đống. Còn chứng minh bằng định trị hai cách tôi sẽ trình bày dưới đây thì khó tìm hơn. Đây là chứng minh của Straubing hồi 1983.

Trước hết, ta nhớ lại một khai triển rất thường dùng của định thức: công thức Leibniz. Gọi $S_n$ là nhóm các hoán vị của $n$ số $\{1, 2, \dots, n\}$ . Dấu của một hoán vị (sign of a permutation) là $+1$ nếu nó là hoán vị chẵn, và $-1$ nếu nó là hoán vị lẻ. Dùng $s(\pi)$ để ký hiệu dấu của hoán vị $\pi$ . Giả sử $A$ là ma trận $n \times n$ . Công thức Leibniz cho ta:

$\displaystyle{p(x) = \det(xI-A) = \sum_{\pi \in S_n} s(\pi) \prod_{i=1}^n (xI-A)_{i \pi(i)}}$
Đến đây ta tìm cách khai triển cái tích $\displaystyle{\prod_{i=1}^n (xI-A)_{i \pi(i)}}$ ra thành tổ hợp tuyến tính của các lũy thừa của $x$ . Cái tích này là tích của một số thừa số có dạng $(x-a_{ii})$ nếu $\pi(i)=i$ và $-a_{ij}$ nếu $\pi(i)=j$ . Tập hợp các chỉ số $i$ mà $\pi(i)=i$ được gọi là tập hợp các điểm tĩnh (fixed points) của hoán vị $\pi$ . Cụ thể hơn, định nghĩa tập hợp các fixed points của $\pi$ như sau:
$F(\pi) := \{ i \in [n] \ : \ \pi(i) = i \}$
Các thừa số dạng $(x-a_{ii})$ đóng góp hoặc $x$ hoặc $-a_{ii}$ trong khai triển của cái tích trên. Vì thế, có thể viết lại tích này như sau:
$\displaystyle{\prod_{i=1}^n (xI-A)_{i \pi(i)} = \sum_{T \subseteq F(\pi)} (-1)^{n-|T|} x^{|T|}\prod_{i\notin T} a_{i\pi(i)}}$
Trong đẳng thức này, ý nghĩa của $T$ là tập các điểm tĩnh đóng góp $x$ vào khai triển. Viết lại của đẳng thức với $S = [n]-T$ để tiện khai triển tiếp, ta có:
$\displaystyle{\prod_{i=1}^n (xI-A)_{i \pi(i)} = \sum_{[n]-S \subseteq F(\pi)} (-1)^{|S|} x^{n-|S|}\prod_{i\in S} a_{i\pi(i)}}$
Đến đây, ta đã có:
$\displaystyle{p(x) = \det(xI-A) = \sum_{\pi \in S_n} s(\pi) \sum_{[n]-S \subseteq F(\pi)} (-1)^{|S|} x^{n-|S|}\prod_{i\in S} a_{i\pi(i)}}$
Mục tiêu chính là viết toàn bộ đa thức $p(x)$ thành một tổ hợp tuyến tính của các lũy thừa của $x$ . Để làm được điều này, ta phải đổi thứ tự các tổng để “lôi” lũy thừa của $x$ ra. Chú ý: nếu đã thành bậc thầy của kỹ thuật định trị hai cách thì việc đổi thứ tự tổng trở thành bản năng thứ hai!

Thay vì lấy tổng theo các hoán vị $\pi$ trước, ta sẽ lấy tổng theo tập $S$ trước. Sau đó, $\pi$ là các hoán vị “fix” mọi điểm nằm ngoài $S$ . Gọi $P(S)$ là tập tất cả các hoán vị của tập $S$ . Ta có:

$\displaystyle{p(x) = \sum_{S \subseteq [n]} \sum_{\pi \in P(S)} x^{n-|S|}s(\pi) (-1)^{|S|} \prod_{i\in S}a_{i\pi(i)}}$
Chú ý rằng ta đã chỉ lấy $\pi$ là một hoán vị của $S$ vì những điểm nằm ngoài $S$ đều được “fixed” (và những điểm này không đóng góp gì vào dấu của hoán vị). Gọi $c(\pi)$ là tổng số vòng tròn của hoán vị $\pi$ (cycles of permutation). Dễ thấy rằng $s(\pi)(-1)^{|S|} = (-1)^{c(\pi)}$ , vì $\pi$ là hoán vị trên tập $S$ . Do đó, ta có
$\displaystyle{p(x) = \sum_{S \subseteq [n]} \sum_{\pi \in P(S)} x^{n-|S|}(-1)^{c(\pi)} \prod_{i\in S}a_{i\pi(i)}}$
Để chứng minh rằng $p(A) = 0$ , ta chứng minh rằng một entry $ij$ bất kỳ của ma trận $p(A)$ bằng $0$ ; Nghĩa là với $i,j \in [n]$ bất kỳ, ta muốn chứng minh tổng sau đây bằng $0$ :
$\displaystyle{(p(A))_{ij} = \sum_{S \subseteq [n]} \sum_{\pi \in P(S)} (A^{n-|S|})_{ij}(-1)^{c(\pi)} \prod_{t\in S}a_{t\pi(t)}}$ .
Ta sẽ tìm cách hiểu cái tổng này một cách tổ hợp. Gọi $K_n$ là complete directed graph (tiếng Việt?) với $n$ đỉnh. Gọi $\mathcal P^k_{ij}$ là tập tất cả các walks từ đỉnh $i$ đến đỉnh $j$ với chiều dài bằng đúng $k$ . Đặt cân nặng (weight) của cạnh $e = (i,j)$ bất kỳ là $w(e) = a_{ij}$ . Cân nặng của một walk $P \in \mathcal P^k_{ij}$ là tích cân nặng của các cạnh trên $P$ . Nghĩa là $w(P) = \prod_{e \in P}w(e)$ . Đẳng thức sau đây là cách hiểu thông dụng về lũy thừa của một ma trận:
$\displaystyle{(A^{n-k})_{ij} = \sum_{P \in \mathcal P_{ij}^{n-k}} w(P)}$
Như vậy, ta có thể viết lại biểu thức tính $(p(A))_{ij}$ theo nghĩa tổ hợp như sau:
$\displaystyle{(p(A))_{ij} = \sum_{S \subseteq [n]} \sum_{P \in \mathcal P_{ij}^{n-|S|}} \sum_{\pi \in P(S)} (-1)^{c(\pi)} w(P) \prod_{t\in S}a_{t\pi(t)}}$ .

Với bất kỳ một bộ ba $(S,\pi, P)$ thỏa ba điều kiện: (i) $S \subseteq [n]$ , (ii) $\pi \in P(S)$ , (iii) $P \in \mathcal P_{ij}^{n-|S|}$ , định nghĩa cân nặng (weight) của bộ ba

$w(S,\pi,P) = w(P)w(\pi)$
trong đó, $w(\pi) = \prod_{t\in S}a_{t\pi(t)}$ , và định nghĩa “dấu” của bộ ba
$s(S,\pi,P) = (-1)^{c(\pi)}$
Ta có:
$\displaystyle{(p(A))_{ij} = \sum_{(S,\pi,P)} s(S,\pi,P) w(S, \pi, P)}$ .
Tuyệt vời! Bây giờ ta chỉ cần tìm cách nào nhóm các số hạng một-một sao cho các cặp một-một đơn giản lẫn nhau. Ý tưởng này là “trái tim” của kỹ thuật định trị hai cách!

Cụ thể hơn. Với một bộ ba $(S,\pi, P)$ tùy ý, ta cần bắt cặp nó với một bộ ba khác $(S',\pi',P')$ cùng cân nặng nhưng ngược dấu!

Đi dọc theo $P$ . Gọi $v$ là đỉnh đầu tiên (a) hoặc là đã chạm $S$ (nghĩa là $v \in S$ ), (b) hoặc là hoàn tất một cycle trên $P$ (nghĩa là đi một lúc quay lại một đỉnh $v$ đã duyệt qua). Đúng một trong hai trường hợp này phải xảy ra! (Và cả hai không thể xảy ra đồng thời.)

Nếu $v \in S$ . Gọi $C$ là cycle chứa $v$ của hoán vị $\pi$ . Đặt $S' = S-C$ , $\pi' = \pi - C$ , và $P' = P+C$ (thêm $C$ vào ngay sau $v$ trên $P$ ). Dễ thấy rằng $(S',\pi',P')$ cùng cân nặng nhưng ngược dấu với $(S,\pi,P)$ .

Nếu $v$ hoàn tất một cycle $C$ của $P$ , ánh xạ của ta ngược lại: thêm $C$ vào $S$ và $\pi$ , và bỏ $C$ ra khỏi $P$ , để đạt được bộ ba $(S',\pi',P')$ .

6 Comments

AustinN

Posted 25/12/2007 at 2:52 am | Permalink

Bài CM này có dùng đến nhóm hoán vị liên quan đến lý thuyết Nhóm của Đại Số. Anh Hưng bữa nào làm một bài về cái mathematical subjects relating to CS để dummies như em take courses học nhé. Em hiện nay chỉ mới xong có analysis với linear algebra.

tranhoang

Posted 04/04/2008 at 10:28 am | Permalink

xin hoi neu tinh ma tran A mu n dung dinh ly cayley-hamilton thi tinh lam sao, A la ma tran vuong cap 2 bat ky

Ngô Quang Hưng

Posted 04/04/2008 at 11:23 am | Permalink
@Tranhoang: đại khái, lấy
```
A^n
```
chia cho đa thức đặc trưng, lấy phần dư là ra kết quả.
dat

Posted 21/05/2008 at 5:06 am | Permalink

xin chaò! em muốn tìm hạng của một ma trận bất kỳ nào đó bằng cách sử dụng phần mềm Mathematica. nhung em không biết lệnh mà có sẵn trong phần mềm này. thế em xin bạn nào mà biết, bảo cho em ngay nhe!
cảm ơn trước

mathsthiu

Posted 28/12/2009 at 8:09 pm | Permalink

@ anh hung: a co’ the? noi’ ro~ hon cho em biet cak tinh’ A^(n) ko . cho e vd cu the? luon nha

Ngô Quang Hưng

Posted 29/12/2009 at 8:25 am | Permalink

@mathsthiu,

Giả sử đa thức đặc trưng là $x^2 + 1$ , và ta muốn tính $A^5$ . Đầu tiên lấy phần dư của $x^5$ chia cho $x^2+1$ :

$x^5 = (x^2+1)x^3 - x(x^2+1) +x \equiv x \pmod{x^2+1}$

Do đó, $A^5 = A$ .

Định trị một đại lượng bằng hai cách [5]

6 Comments

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý