Định trị một đại lượng bằng hai cách [5]
Ngô Quang Hưng | 22 tháng 12, 2007 | 
Bản để in
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
là một ma trận vuông thực hoặc phức. Gọi
là đa thức đặc trưng của
.
Ví dụ:
Thì đa thức
, tức là định thức của ma trận 
là
Thay
bằng ma trận trong , dễ dàng xác minh được rằng
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 
là nhóm các hoán vị của 
số 
. Dấu của một hoán vị (sign of a permutation) là 
nếu nó là hoán vị chẵn, và 
nếu nó là hoán vị lẻ. Dùng 
để ký hiệu dấu của hoán vị 
. Giả sử là ma trận 
. Công thức Leibniz cho ta:
Đến đây ta tìm cách khai triển cái tích
ra thành tổ hợp tuyến tính của các lũy thừa của . Cái tích này là tích của một số thừa số có dạng 
nếu 
và 
nếu 
. Tập hợp các chỉ số 
mà được gọi là tập hợp các điểm tĩnh (fixed points) của hoán vị . Cụ thể hơn, định nghĩa tập hợp các fixed points của như sau:![F(\pi) := \{ i \in [n] \ : \ \pi(i) = i \}](/blog/latexrender/pictures/a3bc3edbcf8db4762c56f40d6e105cc2.gif "F(\pi) := \{ i \in [n] \ : \ \pi(i) = i \}")
Các thừa số dạng
đóng góp hoặc hoặc 
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:
Trong đẳng thức này, ý nghĩa của
là tập các điểm tĩnh đóng góp vào khai triển. Viết lại của đẳng thức với ![S = [n]-T](/blog/latexrender/pictures/850814a8e6e6d10a6aa45e072f774e03.gif "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)}}](/blog/latexrender/pictures/19210fc4431963f04eeca49eae5f92a3.gif "\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)}}](/blog/latexrender/pictures/7a158482f910e722bcc00c69f892cf6b.gif "\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
thành một tổ hợp tuyến tính của các lũy thừa của . Để 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 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ị trước, ta sẽ lấy tổng theo tập 
trước. Sau đó, là các hoán vị “fix” mọi điểm nằm ngoài . Gọi 
là tập tất cả các hoán vị của tập . 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)}}](/blog/latexrender/pictures/b580bcda7bcaf682ae82a577e60df399.gif "\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
là một hoán vị của vì những điểm nằm ngoài đề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 
là tổng số vòng tròn của hoán vị (cycles of permutation). Dễ thấy rằng 
, vì là hoán vị trên tập . 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)}}](/blog/latexrender/pictures/e68d015047aa37b9e90265c043dce25b.gif "\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
, ta chứng minh rằng một entry 
bất kỳ của ma trận 
bằng 
; Nghĩa là với ![i,j \in [n]](/blog/latexrender/pictures/4cadba9539e5ec1be1886ecae3a795d1.gif "i,j \in [n]")
bất kỳ, ta muốn chứng minh tổng sau đây bằng :![\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)}}](/blog/latexrender/pictures/0bd2ec16de2749a4863800e5ed4c5a63.gif "\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
là complete directed graph (tiếng Việt?) với đỉnh. Gọi 
là tập tất cả các walks từ đỉnh đến đỉnh 
với chiều dài bằng đúng 
. Đặt cân nặng (weight) của cạnh 
bất kỳ là 
. Cân nặng của một walk 
là tích cân nặng của các cạnh trên 
. Nghĩa là 
. Đẳ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:
Như vậy, ta có thể viết lại biểu thức tính
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)}}](/blog/latexrender/pictures/f7d8cde22f19a296018bea0fd2898038.gif "\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 
thỏa ba điều kiện: (i) ![S \subseteq [n]](/blog/latexrender/pictures/8eb4b4344cf2283b2624c68ac769fba6.gif "S \subseteq [n]")
, (ii) 
, (iii) 
, định nghĩa cân nặng (weight) của bộ ba
trong đó,
, và định nghĩa “dấu” của bộ ba
Ta có:
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 tùy ý, ta cần bắt cặp nó với một bộ ba khác 
cùng cân nặng nhưng ngược dấu!
Đi dọc theo . Gọi 
là đỉnh đầu tiên (a) hoặc là đã chạm (nghĩa là 
), (b) hoặc là hoàn tất một cycle trên (nghĩa là đi một lúc quay lại một đỉnh đã 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 . Gọi 
là cycle chứa của hoán vị . Đặt 
, 
, và 
(thêm vào ngay sau trên ). Dễ thấy rằng cùng cân nặng nhưng ngược dấu với 
.
Nếu hoàn tất một cycle của , ánh xạ của ta ngược lại: thêm vào và , và bỏ ra khỏi , để đạt được bộ ba .
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.
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
@Tranhoang: đại khái, lấy
chia cho đa thức đặc trưng, lấy phần dư là ra kết quả.
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