Luận văn Thạc sĩ Toán học: Về phương pháp ma trận cho bài toán tổ hợp và hình học

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:66

Thêm vào BST

Báo xấu

37
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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,... Mời các bạn cùng tham khảo nội dung luận văn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: 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 chuẩn bị 4 1.1 Ma trận và các phép toán ma trận . . . . . . . . . . . . . . . . 4 1.2 Định thức của ma trận . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Giá trị riêng, véctơ riêng . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Chéo hóa ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Chuẩn của ma trận . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.6 Phân tích SVD của ma trận . . . . . . . . . . . . . . . . . . . . 18 Chương 2. Phương pháp ma trận trong tổ hợp liệt kê 28 2.1 Ma trận của đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Đếm đường đi: phương pháp ma trận chuyển . . . . . . . . . . . 31 2.3 Đếm số cây bao trùm . . . . . . . . . . . . . . . . . . . . . . . . 37 2.4 Đếm chu trình Euler . . . . . . . . . . . . . . . . . . . . . . . . 42 Chương 3. Phương pháp ma trận trong hình học 47 3.1 Quay không gian con . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Giao của các nhân . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.3 Góc giữa các không gian . . . . . . . . . . . . . . . . . . . . . . 53 3.4 Giao của các không gian con . . . . . . . . . . . . . . . . . . . . 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) Phần phụ đại số chính của L(G) → − L (G) Ma trận Laplacian của đồ thị có hướng 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
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 Arith- meticae, 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 · · · a1n · · · a2n  a  21 a22  A=  · · ··· ·   am1 am2 · · · 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 · · · a1n b11 b12 · · · b1n · · · a2n   b21 b22 · · · b2n  a  21 a22    +  · · ··· ·   · · ··· ·    am1 am2 · · · amn bm1 bm2 · · · bmn   a11 + b11 a12 + b12 · · · a1n + b1n · · · a2n + b2n  a +b a22 + b22   21 21 = ,  · · ··· ·  am1 + bm1 am2 + bm2 · · · amn + bmn     a11 a12 · · · a1n aa11 aa12 · · · aa1n · · · a2n   aa21 aa22 · · · aa2n  a  21 a22    a =  , (a ∈ K).  · · ··· ·   · · ··· ·  am1 am2 · · · amn aam1 aam2 · · · 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 n X cik = aij bjk , (1 ≤ i ≤ m, 1 ≤ k ≤ p). 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 i 2 8 −4 1 4 −2 = . 3 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 ··· 0 · · · 0 0 1  I = In =   · · · · · ·  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: n X tr(A) = a11 + a22 + · · · + ann = 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ó n X tr(A) = λ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 Y σ(i) − σ(j) sgn(σ) = ∈ {±1}. i−j i6=j 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 X det A = |A| = 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: ! a11 a12 det = a11 a22 − a21 a12 . a21 a22 Đị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 2. det(A−1 ) = = 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: n Y det(A) = a11 a22 · · · ann = 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 n X det(A) = (−1)i+j Mi,j (với i cố định) j=1 Xn = (−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 A = −1 1 3 ,   2 0 −1 dọc theo cột thứ 2 là