Tài liệu (Luận văn thạc sĩ) Về phương pháp ma trận cho bài toán tổ hợp và hình học

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ THU HƢƠNG VỀ PHƢƠNG PHÁP MA TRẬN CHO BÀI TOÁN TỔ HỢP VÀ HÌNH HỌC LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2018 ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------- NGUYỄN THỊ THU HƢƠNG VỀ PHƢƠNG PHÁP MA TRẬN CHO BÀI TOÁN TỔ HỢP VÀ HÌNH HỌC Chuyên ngành: Phƣơng pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Nguyễn Thanh Sơn THÁI NGUYÊN - 2018 i Mục lục Bảng ký hiệu ii Mở đầu 1 Chương 1. Ma trận và một số kiến thức 1.1 Ma trận và các phép toán ma trận . 1.2 Định thức của ma trận . . . . . . . . 1.3 Giá trị riêng, véctơ riêng . . . . . . . 1.4 Chéo hóa ma trận . . . . . . . . . . . 1.5 Chuẩn của ma trận . . . . . . . . . . 1.6 Phân tích SVD của ma trận . . . . . chuẩn . . . . . . . . . . . . . . . . . . . . . . . . Chương 2. Phương pháp ma trận trong tổ hợp 2.1 Ma trận của đồ thị . . . . . . . . . . . . . . 2.2 Đếm đường đi: phương pháp ma trận chuyển 2.3 Đếm số cây bao trùm . . . . . . . . . . . . . 2.4 Đếm chu trình Euler . . . . . . . . . . . . . Chương 3. Phương pháp ma trận trong hình 3.1 Quay không gian con . . . . . . . . . . . . 3.2 Giao của các nhân . . . . . . . . . . . . . 3.3 Góc giữa các không gian . . . . . . . . . . 3.4 Giao của các không gian con . . . . . . . . bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . liệt kê . . . . . . . . . . . . . . . . . . . . học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 7 11 13 17 18 . . . . 28 28 31 37 42 . . . . 47 47 50 53 58 Kết luận 61 Tài liệu tham khảo 62 ii Bảng ký hiệu K Trường số M (m × n, K) Không gian ma trận cỡ m × n trong trường K A Ma trận A AT Ma trận chuyển vị của ma trận A In Ma trận đơn vị cấp n tr(A) Vết của ma trận A sgn(σ) Dấu của phép hoán vị σ det(A) Định thức của ma trận A pA (x) Đa thức đặc trưng của ma trận A kAkR Chuẩn Frobenius của ma trận A kAkp Chuẩn p của ma trận A diag Ma trận đường chéo ker(A) Hạt nhân của ma trận A span(v1 , v2 , . . . , vn ) Không gian véctơ sinh bởi {v1 , v2 , . . . , vn } im(A) Ảnh của ma trận A A(k, :) Hàng thứ k của ma trận A A(:, k) Cột thứ k của ma trận A G(V, E) Đồ thị G có tập đỉnh V và tập cạnh E deg(u) Bậc của đỉnh u indeg(u) Bậc vào của đỉnh u outdeg(u) Bậc ra của đỉnh u A(G) Ma trận kề của đồ thị G M (G) Ma trận liên thuộc của đồ thị G L(G) Ma trận Laplacian của đồ thị G Lv (G) → − L (G) Phần phụ đại số chính của L(G) CG (n) Số đường đi đóng có độ dài n trong G cG Sô cây bao trùm của đồ thị G c(G, v) Sô cây bao trùm có gốc tại v của đồ thị G SVD Phân tích kỳ dị của ma trận Ma trận Laplacian của đồ thị có hướng G 1 Mở đầu Trong toán học, lý thuyết về ma trận trong đại số tuyến tính là nội dung rất cơ bản, quan trọng và có nhiều rất nhiều ứng dụng. Ngày nay, ma trận được ứng dụng vào hàng loạt lĩnh vực khác nhau, từ giải tích tới hình học vi phân và lý thuyết đồ thị, từ cơ học vật lý tới kỹ thuật,... Vì thế nó đã trở thành trọng tâm nội dung học tập cơ sở cho việc đào tạo ở các bậc đại học và sau đại học thuộc các chuyên ngành khoa học cơ bản và công nghệ trong tất cả các trường đại học. Về mặt lịch sử, trong tác phẩm “Nghiên cứu số học” (Disquisitiones Arithmeticae, năm 1801), để xác định một phép biến đổi tuyến tính, Gauss đã đưa ra một ký hiệu dưới dạng bảng, đó chính là ma trận. Ông cũng định nghĩa tích của hai ma trận. Điều này gợi ý cho Cauchy ([5]) đi tới định lý về tích của hai định thức. Vào giữa thế kỷ 19, Cayley và Silvester đã phát triển lý thuyết ma trận. Các khái niệm ma trận và định thức ngày càng quen thuộc hơn với các nhà toán học, chúng góp phần làm chín dần những ý niệm về không gian n chiều. Trong lý thuyết đồ thị, một cây đồ thị là một tập hợp các mối quan hệ giữa các đỉnh và các cạnh của đồ thị. Mối quan hệ này có được biểu diễn dưới dạng danh sách các cạnh kề hoặc dưới dạng ma trận. Từ đó việc khảo sát các tính chất đặc trưng của cây đồ thị có thể thực hiện thông qua khảo sát ma trận của cây đồ thị và ngược lại. Bài toán đếm cây, đếm nhánh, đếm đường đi trên đồ thị được chuyển thành bài toán tính định thức của ma trận. Ở một khía cạnh khác, nếu coi các cột của ma trận là các véc tơ chỉ phương của các phẳng, thì ma trận mang thông tin về phương của các phẳng đó. Những phép toán giữa các ma trận sẽ biểu hiện những biến đổi hay tương tác mang tính hình học của các phẳng mà thông qua đó, nhiều bài toán hình học được giải quyết. 2 Với mong muốn tìm hiểu sâu hơn về ứng dụng của ma trận trong giải các bài toán tổ hợp và bài toán hình học, chúng tôi lựa chọn đề tài Về phương pháp ma trận cho bài toán tổ hợp và hình học dưới sự hướng dẫn của TS. Nguyễn Thanh Sơn. Mục đích của luận văn là sử dụng một số khái niệm và tính chất của ma trận, như định thức, giá trị riêng, phân tích giá trị kỳ dị của ma trận để giải một số bài toán như quay không gian con, giao nhau của hai không gian, và một số bài toán đếm trong tổ hợp. Ngoài phần Mở đầu, Kết luận và Tài liệu tham khảo, luận văn được chia làm ba chương. Chương 1. Ma trận và một số kiến thức chuẩn bị. Chương này tổng hợp lại định nghĩa, một số tính chất, định lý cơ bản về ma trận, định thức, các phép toán trên ma trận, vết của ma trận, phân tích SVD của ma trận. Chương 2. Phương pháp ma trận trong tổ hợp liệt kê. Chương này trình bày ứng dụng phương pháp ma trận vào bài toán đếm của số học tổ hợp, cụ thể hơn là bài toán đếm cây, đếm chu trình, đếm số đường đi trên đồ thị. Một cây đồ thị được biểu diễn duy nhất dưới dạng một ma trận, từ đó ta có thể suy ra các đặc trưng của cây dựa trên ma trận của cây. Chương 3. Phương pháp ma trận trong hình học. Trong chương này phép phân tích SVD được sử dụng để trả lời các câu hỏi: cho trước hai không gian con, chúng gần nhau như thế nào, chúng có giao nhau hay không, ta có thể “quay” một không gian con thành không gian còn lại không. Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên. Tôi xin bày tỏ lòng biết ơn tới TS. Nguyễn Thanh Sơn, người đã định hướng chọn đề tài và tận tình hướng dẫn, cho tôi những nhận xét quý báu để tôi có thể hoàn thành luận văn. Tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới các thầy cô, những người đã tận tâm giảng dạy và chỉ bảo tác giả trong suốt quá trình học tập và thực hiện luận văn. Tôi cũng xin bày tỏ lòng biết hơn chân thành tới phòng Sau Đại học, khoa Toán - Tin, trường Đại học Khoa học, Đại học Thái Nguyên đã giúp đỡ và tạo điều kiện cho tôi trong suốt quá trình học tập và nghiên cứu khoa học. 3 Cuối cùng tôi xin gửi làm cảm ơn tới gia đình, bạn bè, đồng nghiệp đã động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi khi học tập và nghiên cứu. Thái Nguyên, tháng 10 năm 2018 Người viết luận văn Nguyễn Thị Thu Hương 4 Chương 1 Ma trận và một số kiến thức chuẩn bị Nhằm đạt được tính toàn vẹn nhất định của luận văn và cũng là nhắc lại một số kiến thức cơ bản, chương này tổng hợp lại định nghĩa, một số tính chất, định lý cơ bản về ma trận, định thức, các phép toán trên ma trận, vết của ma trận, phân tích SVD của ma trận. Nội dung của chương được tổng hợp từ giáo trình đại số tuyến tính [1] và quyển sách chuyên khảo về tính toán ma trận [7]. 1.1 Ma trận và các phép toán ma trận Định nghĩa 1.1.1 ([1]). Mỗi bảng có dạng  a11 a12 a  21 a22 A=  · · am1 am2  · · · a1n  · · · a2n   ··· ·  · · · amn trong đó aij ∈ K (1 ≤ i ≤ m, 1 ≤ j ≤ n), được gọi là một ma trận m hàng n cột với các phần tử trong K. Nếu m = n, thì ta nói A là một ma trận vuông cấp n. Véctơ hàng (ai1 , ai2 , . . . , ain ) được gọi là hàng thứ i của ma trận A. Véctơ cột (a1j , a2j , . . . , amj )T được gọi là cột thứ j của ma trận A. 5 Ma trận nói trên thường được ký hiệu gọn là A = (aij )m×n . Tập hợp tất cả các ma trận m hàng, n cột với các phần tử trong K được ký hiệu là M (m×n, K). Ta định nghĩa hai phép toán cộng và nhân với vô hướng trên M (m × n, K) như sau:  a11 a12 a  21 a22   · · am1 am2   · · · a1n b11 b12   · · · a2n   b21 b22 + ··· ·   · · · · · amn bm1 bm2  a11 + b11 a12 + b12 a +b a22 + b22  21 21 =  · · am1 + bm1 am2 + bm2  a11 a12 a  21 a22 a  · · am1 am2   · · · b1n  · · · b2n   ··· ·  · · · bmn  · · · a1n + b1n  · · · a2n + b2n  ,  ··· · · · · amn + bmn  · · · a1n aa11 aa12   · · · a2n   aa21 aa22 = ··· ·   · · · · · amn aam1 aam2  · · · aa1n  · · · aa2n   , (a ∈ K). ··· ·  · · · aamn Cho hai ma trận A = (aij ) ∈ M (m × n, K), B = (bjk ) ∈ M (n × p, K). Định nghĩa 1.1.2 ([1]). Tích AB của ma trận A và ma trận B là ma trận C = (cik ) ∈ M (m × p, K) với các phần tử được xác định như sau cik = n X (1 ≤ i ≤ m, 1 ≤ k ≤ p). aij bjk , j=1 Ví dụ 1.1.3.  a b c  x t   ax + by + cz at + bu + cv       d e f  y u = dx + ey + f z dt + eu + f v  . g h i z v gx + hy + iz gt + hu + iv Ví dụ 1.1.4. "   " # 1 3 1 −2 3  9 15  −1 0 = −1 2 5 7 17 2 4 # " # 2 h 3 i 1 4 −2 = " # 2 8 −4 . 3 12 −6 6 Nhận xét 1.1.5. Điều kiện để định nghĩa được ma trận tích AB là số cột của A bằng số hàng của B. Có thể xảy ra trường hợp tích AB thì định nghĩa được mà tích BA thì không. Ma trận  1 0  I = In =  · 0 0 1 · 0  ··· 0  · · · 0  · · · · ··· 1 được gọi là ma trận đơn vị cấp n. Định nghĩa 1.1.6 ([1]). Ma trận A ∈ M (n × n, K) được gọi là một ma trận khả nghịch (hoặc ma trận không suy biến) nếu có ma trận B ∈ M (n × n, K) sao cho AB = BA = In . Khi đó, ta nói B là nghịch đảo của A và ký hiệu B = A−1 . Nhận xét rằng nếu A khả nghịch thì ma trận nghịch đảo của nó được xác định duy nhất. Thật vậy, giả sử B và B 0 đều là các nghịch đảo của A. Khi đó B = BIn = B(AB 0 ) = (BA)B 0 = In B 0 = B 0 . Trong Mục 1.2, chúng ta sẽ chỉ ra một điều kiện cần và đủ rất đơn giản để cho một ma trận vuông là khả nghịch. Định nghĩa 1.1.7. Cho ma trận A cỡ m × n, nếu ta đổi các hàng của ma trận A thành các cột (và do đó các cột thành các hàng) thì ta được ma trận mới cỡ n × m, gọi là ma trận chuyển vị của ma trận trên A, ký hiệu AT AT = (cij )n×m , cij = aji , i = 1, . . . , n, j = 1, . . . , m. Tính chất 1.1.8. 1. (A + B)T = AT + B T . 2. (kA)T = kAT . 3. (AB)T = B T AT . Định nghĩa 1.1.9. 1. Nếu A = AT thì A được gọi là ma trận đối xứng (A là ma trận vuông có các phần tử đối xứng nhau qua đường chéo thứ nhất). 2. A = −AT thì A được gọi là phản đối xứng (A là ma trận vuông có các phần tử đối xứng và trái dấu qua đường chéo thứ nhất, các phần tử trên đường chéo thứ nhất bằng 0). 7 Định nghĩa 1.1.10. Vết của ma trận vuông A bậc n × n được xác định bằng tổng các phần từ trên đường chéo chính (đường nối từ góc trên bên trái xuống góc dưới bên phải) của A: tr(A) = a11 + a22 + · · · + ann = n X aii . i=1 Tính chất 1.1.11. 1. Vết của ma trận A bằng tổng các giá trị riêng của nó tr(A) = n X λi , i=1 trong đó λi là giá trị riêng của A. 2. Cho A, B là các ma trận vuông cùng cấp và c là hằng số, khi đó tr(A + B) = tr(A) + tr(B), tr(c · A) = c tr(A). 3. Cho A là ma trận m hàng n cột còn B là ma trận n hàng và m cột, thì tr(AB) = tr(BA). 4. Cho A là ma trận vuông cấp n bất kì, AT là ma trận chuyển vị của nó. Ta có tr(A) = tr(AT ). 1.2 Định thức của ma trận Định nghĩa 1.2.1 ([1]). Mỗi song ánh từ tập {1, 2, . . . , n} vào chính nó được gọi là một phép thế bậc n. Tập hợp tất cả các phép thế bậc n được ký hiệu bởi Sn . Sn cùng với phép hợp thành các ánh xạ lập thành một nhóm, được gọi là nhóm đối xứng bậc n. Nhóm này có n! phần tử. Nếu σ ∈ Sn , ta thường biểu thị nó dưới dạng ! 1 2 ··· n σ= . σ(1) σ(2) · · · σ(n) 8 Định nghĩa 1.2.2 ([1]). Dấu của phép thế σ ∈ Sn là số sau đây sgn(σ) = Y σ(i) − σ(j) i−j i6=j ∈ {±1}. Tích này chạy trên mọi cặp số (không có thứ tự) {i, j} ⊂ {1, 2, . . . , n}. Cho ma trận vuông A = (aij )n×n với các phần tử trong trường K. Định nghĩa 1.2.3 ([1]). Định thức của ma trận A, được ký hiệu bởi det(A) hoặc |A|, là phần tử sau đây của trường K det A = |A| = X sgn(σ)aσ(1)1 · · · anσ(n) . σ∈Sn Như vậy định thức của ma trận vuông A = (aij )n×n là tổng tất cả các tích gồm n phần tử trên n hàng ma ở trên n cột khác nhau của ma trận A và nhân với +1 hoặc −1. Nếu A là một ma trận vuông cấp n thì det A được gọi là một định thức cấp n. Ví dụ 1.2.4. Định thức cấp 1: det(a) = a, ∀a ∈ K. Định thức cấp 2: det a11 a12 a21 a22 ! = a11 a22 − a21 a12 . Định thức cấp 3:  a11 a12 a13    det a21 a22 a23  a31 a32 a33 = a11 a22 a33 + a21 a32 a13 + a31 a12 a23 − a11 a32 a23 − a21 a12 a33 − a31 a22 a13 . Trên thực tế người ta không trực tiếp dùng định nghĩa để tính các định thức cấp n > 3, vì việc này quá phức tạp. Dưới đây, chúng ta sẽ tìm hiểu những tính chất cơ bản của định thức. Từ đó, ta sẽ nhận được những phương pháp tính định thức hiệu quả và tiết kiệm hơn so với cách trực tiếp dùng định nghĩa. Định thức có các tính chất cơ bản dưới đây mà chứng minh của chúng có thể tìm thấy trong [1]. 9 Tính chất 1.2.5. Định thức của ma trận là một hàm tuyến tính với mỗi cột của nó, khi cố định các cột khác. Tính chất 1.2.6. Nếu ma trận vuông A có hai cột bằng nhau thì det A = 0. Tính chất 1.2.7. Định thức của ma trận đơn vị bằng 1. Hệ quả 1.2.8. 1. Nếu đổi chỗ hai cột của một ma trận thì định thức của nó đổi dấu. 2. Nếu các véctơ cột của một ma trận phụ thuộc tuyến tính thì định thức của ma trận bằng không. Nói riêng, nếu ma trận có một cột bằng 0 thì định thức của nó bằng 0. 3. Nếu thêm vào một cột của ma trận một tổ hợp tuyến tính của các cột khác thì định thức của nó không thay đổi. Tính chất 1.2.9. 1. det(AT ) = det(A), trong đó AT là ma trận chuyển vị của A. 1 = det(A)−1 . 2. det(A−1 ) = det(A) 3. Với ma trận vuông A và B có cùng kích thước, det(AB) = det(A) det(B). 4. det(cA) = cb det(A) với A là ma trận cỡ n × n. 5. Nếu A là ma trận tam giác, tức là aij = 0 với mọi i > j hoặc ngược lại i < j, thì định thức của nó bằng tích của các phần tử trên đường chéo: det(A) = a11 a22 · · · ann = n Y aii . i=1 Công thức sau đây được gọi là công thức khai triển Laplace biểu diễn định thức của ma trận theo định thức con. Định thức con Mi,j được định nghĩa là định thức của ma trận cỡ (n − 1) × (n − 1) sinh ra từ ma trận A bằng cách bỏ đi hàng thứ i và cột thứ j. Biểu thức (−1)i+j Mi,j được gọi là phần bù đại số. Định thức của ma trận A được xác định bởi det(A) = = n X (−1)i+j Mi,j (với i cố định) j=1 n X (−1)i+j Mi,j (với j cố định). i=1 10 Dựa vào công thức trên, việc tính định thức được khai triển dọc theo một hàng hoặc dọc theo một cột. Ví dụ, khai triển Laplace của ma trận 3 × 3   −2 2 −3  3 , 2 0 −1  A = −1 1 dọc theo cột thứ 2 là       −1 3  −2 −3 −2 −3       det(A) = (−1)2+1 · 2   + (−1)2+2 · 1   + (−1)2+3 · 0    2 −1  2 −1 −1 3  = 18. Tuy nhiên, công thức khai triển Laplace chỉ hiệu quả cho ma trận cỡ nhỏ. Định lý 1.2.10 ([1]). Nếu A khả nghịch thì det A 6= 0 (lúc đó ta nói ma trận A không suy biến). Chứng minh. Ta có AA−1 = E nên det A det A−1 = det AA−1 = det E = 1. 1 6= 0. Do đó det A = det A−1 Định lý 1.2.11 ([1]). Nếu ma trận A = (aij ) ∈ M (n × n, K) có định thức khác 0 thì A khả nghịch và  A −1  ã11 · · · ãn1 1   =  · ··· ·  det A ã1n · · · ãnn trong đó ãij là phần bù đại số của aij . Định lý 1.2.12 (Công thức Binet-Cauchy [5]). Cho A là ma trận cỡ m×n và B là ma trận cỡ n×m, m < n. Ký hiệu [n] = {1, . . . , n}, ký hiệu S ⊆ [n] : |S| = m là một tập con gồm m của [n]. Gọi A[S] là ma trận m × m gồm các cột của A với chỉ số trong S, gọi B[S] là ma trận cỡ m × m gồm các hàng từ B có chỉ số trong S. Khi đó, det AB = X S⊆[n]:|S|=m det A[S] det B[S] 11 " Ví dụ 1.2.13. Lấy m = 2 và n = 3, và ma trận A =  1 1 2 3 1 −1 # và B =  1 1   3 1, theo công thức Binet-Cauchy ta có 0 2          1 1 1 1 1 2  3 1 1 2  1 1          det AB =   +  +   3 1 3 1 1 −1 0 2 3 −1 0 2 " # 4 6 . 6 2 = −28 = det 1.3 Giá trị riêng, véctơ riêng Định nghĩa 1.3.1 ([3]). Giả sử A là một ma trận vuông cỡ n, x 6= 0 là một véctơ trong Cn , và λ là một hằng số trong C. Khi đó ta nói rằng x là một véctơ riêng của A ứng với giá trị riêng λ nếu Ax = λx. Ví dụ 1.3.2. Cho     −10 5    16  , x = −4 . 0 −9 −2 3 0 5  A = 0 22 Tính tích Ax ta được        0 5 −10 5 50 5        Ax = 0 22 16  −4 = −40 = 10 −4 . 0 −9 −2 3 30 3 Trong trường hợp này, x là một véctơ riêng của A ứng với giá trị riêng λ = 10. Định nghĩa 1.3.3. Tập tất cả các giá trị riêng của ma trận A được ký hiệu bởi σ(A) và được gọi là phổ của A. Ta có Ax = λx ⇔ Ax − λIn x = 0 ⇔ (A − λIn )x = 0. 12 Vì vậy với mỗi giá trị riêng λ và véctơ riêng tương ứng x 6= 0, véctơ x là một phần tử khác không của không gian không của A − λIn , trong khi ma trận A − λIn suy biến và do đó có định thức bằng không. Ý tưởng này cho ta một cách hữu hiệu để tìm giá trị riêng của ma trận. Định nghĩa 1.3.4 ([3]). Giả sử A là ma trận vuông cỡ n. Khi đó, đa thức đặc trưng của A là đa thức pA (x) xác định bởi pA (x) = det(A − xIn ). Định lý 1.3.5 ([3]). Giả sử A là một ma trận vuông. Khi đó, λ là một giá trị riêng của A khi và chỉ khi pA (λ) = 0. Chứng minh. Giả sử A có cỡ n. λ là một giá trị riêng của A ⇔ tồn tại x 6= 0 sao cho Ax = λx ⇔ tồn tại x 6= 0 sao cho Ax − λx = 0 ⇔ tồn tại x 6= 0 sao cho Ax − λIn x = 0 ⇔ tồn tại x 6= 0 sao cho (A − λIn )x = 0 ⇔ ma trận A − λIn suy biến ⇔ det(A − λIn ) = 0 ⇔ pA (x) = 0. Ví dụ 1.3.6. Cho ma trận   −13 −8 −4  7 4 . 24 16 7  F =  12 Đa thức đặc trưng của F là pF (x) = −(x − 3)(x + 1)2 . Các nghiệm của đa thức là x = 3 và x = −1. Do đó, theo định lý bên trên, λ = 3 và λ = −1 là hai giá trị riêng của F. Với λ = 3, ta có   −16 −8 −4  4 4 24 16 4  F − 3I3 =  12 13 h i Giải phương trình (F − 3I3 )x = 0, ta được nghiệm x = t −t −2t , t ∈ C. hChọn t = 1i ta được một véctơ riêng ứng với giá trị riêng λ = 3 là x = 1 −1 −2 tự ta h Với λ i= −1, tương h i tìm được các véctơ riêng tương ứng là x = −2 3 0 và x = −1 0 3 . Tính chất 1.3.7 ([3]). Giả sử A là một ma trận vuông, λ là một giá trị riêng của A. Khi đó: 1. αλ là một giá trị riêng của αA. 2. λs là một giá trị riêng của As , s ≥ 0 là số nguyên. 3. Cho q(x) là một đa thức theo biến x. Khi đó q(λ) là một giá trị riêng của q(A). 4. λ1 là một giá trị riêng của ma trận A−1 . 5. λ là một giá trị riêng của ma trận AT . 6. Giả sử A là một ma trận vuông cỡ n. Khi đó đa thức đặc trưng của A có bậc n. 1.4 Chéo hóa ma trận Định nghĩa 1.4.1 ([3]). Giả sử A và B là hai ma trận vuông cấp n. Khi đó A và B được gọi là đồng dạng nếu tồn tại một ma trận S không suy biến cấp n sao cho A = S −1 BS. Ví dụ 1.4.2. Cho   −13 −8 −4   B =  12 7 4 , 24 16 7   1 1 2   S = −2 −1 −3 . 1 −2 0 Ta kiểm tra được S không suy biến và tính A = S −1 BS     −6 −4 −1 −13 −8 −4 1 1 2     = −3 −2 −1  12 7 4  −2 −1 −3 5 3 1 24 16 7 1 −2 0 14   −1 0 0   =  0 3 0 . 0 0 −1 Điều đó dẫn đến A và B là đồng dạng. Nhận xét 1.4.3. Trước khi tiếp tục, ta quan sát hình dạng ma trận A. Một số tính toán liên quan tới ma trận A đặc biệt đơn giản. Ví dụ, định thức của A là det A = (−1)3(−1) = 3. Tương tự, đa thức đặc trưng của A là pA (x) = (−1 − x)(3 − x)(−1 − x) = −(x − 3)(x + 1)2 được suy ra ngay và có sẵn dạng phân tích nhân tử. Từ đó, giá trị riêng của ma trận là tường minh λ = 3, λ = −1. Cuối cùng, các véctơ riêng của A chính là các véctơ đơn vị thông thường. Tính chất 1.4.4 ([3]). Giả sử A, B và C là các ma trận vuông cấp n. Khi đó: 1. A đồng dạng với A (tính phản xạ). 2. Nếu A đồng dạng với B, thì B đồng dạng với A (tính đối xứng). 3. Nếu A đồng dạng với B và B đồng dạng với C, thì A đồng dạng với C (tính bắc cầu). Định lý 1.4.5 ([3]). Giả sử A và B là hai ma trận đồng dạng. Khi đó đa thức đặc trưng của A và B bằng nhau, tức là pA (x) = pB (x). Chứng minh. Giả sử A và B có cùng cấp n và đồng dạng với nhau thông qua ma trận không suy biến S, nên A = S −1 BS. Ta có pA (x) = det(A − xIn ) = det(S −1 BS − xIn ) = det(S −1 BS − xS −1 In S) = det(S −1 (B − xIn )S) = det(S −1 ) det(B − xIn ) det(S) = det(S −1 ) det(S) det(B − xIn ) = det(In ) det(B − xIn ) = det(B − xIn ) = pB (x). Từ chứng minh định lý trên, ma trận đồng dạng không những có cùng tập giá trị riêng mà số bội của các giá trị riêng này cũng bằng nhau. Tuy nhiên 15 điều ngược lại không đúng, hai ma trận có cùng giá trị riêng thì chưa chắc chúng đồng dạng. Ví dụ 1.4.6. Cho " A= # " 1 1 , 0 1 B= # 1 0 0 1 và tính được pA (x) = pB (x) = 1 − 2x + x2 = (x − 1)2 . Cho nên A và B có cùng đa thức đặc trưng. Giả sử A và B đồng dạng thì tồn tại ma trận không suy biến S sao cho A = S −1 BS. Khi đó, A = S −1 BS = S −1 I2 S = S −1 S = I2 6= A điều này mâu thuẫn. Suy ra A và B không đồng dạng. Định nghĩa 1.4.7 ([3]). Giả sử A = (aij ) là ma trận vuông. Khi đó A được gọi là ma trận đường chéo nếu aij = 0 với mọi i 6= j. Định nghĩa 1.4.8 ([3]). Giả sử A là ma trận vuông. Khi đó A được gọi là chéo hóa được nếu A đồng dạng với một ma trận đường chéo. Ví dụ 1.4.9. Xét ma trận   −7 −6 −12  5 7  1 0 4  B= 5 là ma trận chéo hóa được. Thật vậy, tồn tại ma trận không suy biến S sao cho  S −1 −1  −5 −3 −2  2 1 1 1 1  BS =  3     −7 −6 −12 −5 −3 −2   5 7  3 2 1 1 0 4 1 1 1  5   −1 −1 −1 −7 −6 −12 −5 −3 −2     = 2 3 1  5 5 7  3 2 1 −1 −2 1 1 0 4 1 1 1   −1 0 0  1 0 . 0 0 2  = 0 Tức là A đồng dạng với một ma trận đường chéo, hay A chéo hóa được. 16 Định lý 1.4.10 ([3]). Giả sử A là ma trận vuông cấp n. Khi đó A chéo hóa được khi và chỉ khi tồn tại tập các véctơ độc lập tuyến tính S mà chứa n véctơ riêng của A. Hơn nữa, ta thu được ma trận đường chéo mà các giá trị riêng của A suất hiện trên đường chéo theo thứ tự xuất hiện của các véctơ riêng trong S. Ví dụ 1.4.11. Xét ma trận   −13 −8 −4   F =  12 7 4 . 24 16 7 iT h Theo Ví dụ 1.3.6, ta có x = 1 −1 −2 h x = −2 3 0 iT h và x = −1 0 3 iT là một véctơ riêng ứng với λ = 3, là hai véctơ riêng ứng với λ = −1. Xác định ma trận S là ma trận có ba cột là ba véctơ riêng của F ,   1 −2 −1   S = −1 3 0 . −2 0 3 Kiểm tra được S là ma trận không suy biến nên các cột của S là tập độc lập tuyến tính. Theo Định lý 1.4.10 ta biết rằng F chéo hóa được. Ngoài ra, khi tìm ma trận đồng dạng của F thông qua S ta thu được ma trận đường chéo mà các giá trị riêng của F suất hiện trên đường chéo theo thứ tự xuất hiện của các véctơ riêng trong S. Do đó  S −1 −1  −2 −1  3 0 −2 0 3 1  F S = −1    −2 −1 1 −2 −1   3 0  −1 3 0 −2 0 3 −2 0 3 1  −1    −3 −2 −1 1 −2 −1 1 −2 −1     = −1 −1/3 −1/3 −1 3 0  −1 3 0 −2 −4/3 −1/3 −2 0 3 −2 0 3   3 0 0   = 0 −1 0  . 0 0 −1 Định lý 1.4.12 ([3]). Giả sử A là ma trận vuông cấp n có n giá trị riêng phân biệt. Khi đó A chéo hóa được.