BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
DƯƠNG PHƯƠNG HOA
MA TRẬN CỦA ĐỒ THỊ VÀ MỘT SỐ ỨNG DỤNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
HÀ NỘI, 2016
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
DƯƠNG PHƯƠNG HOA
MA TRẬN CỦA ĐỒ THỊ VÀ MỘT SỐ ỨNG DỤNG
Chuyên ngành: Toán ứng dụng
Mã số: 60 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. TRẦN MINH TƯỚC
HÀ NỘI, 2016
i
Lời cảm ơn
Luận văn được hoàn thành tại trường Đại học Sư phạm Hà Nội 2 dưới sự
hướng dẫn của TS. Trần Minh Tước.
Tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới TS. Trần Minh Tước –
người đã định hướng chọn đề tài và tận tình hướng dẫn để tác giả hoàn thành
luận văn này.
Tác giả xin gửi lời cảm ơn tới phòng Sau đại học; trường Đại học Sư phạm
Hà Nội 2, các thầy, cô giáo giảng dạy chuyên ngành Toán Ứng dụng đã giúp
đỡ tác giả trong suốt quá trình học tập và hoàn thành luận văn tốt nghiệp.
Tác giả cũng xin được gửi lời cảm ơn chân thành đến gia đình, bạn bè,
người thân đã luôn động viên, cổ vũ, tạo mọi điều kiện thuận lợi cho tác giả
trong quá trình học tập và hoàn thành luận văn
Hà Nội, ngày 25 tháng 11 năm 2016
Dương Phương Hoa
ii
Lời cam đoan
Dưới sự hướng dẫn của TS. Trần Minh Tước, luận văn thạc sỹ chuyên ngành
Toán Ứng dụng với đề tài “Ma trận của đồ thị và một số ứng dụng” được hoàn
thành từ nhận thức của bản thân, không trùng lặp với bất cứ luận văn nào
khác.
Trong khi nghiên cứu luận văn, tôi đã sử dụng những thành tựu của các
nhà khoa học với sự trân trọng và biết ơn.
Hà Nội, tháng 10 năm 2016
Dương Phương Hoa
iii
Mục lục
Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
Lời mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
Chương 1. Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.1. Khái niệm đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2. Ma trận kề. Ma trận trọng số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3. Ma trận liên thuộc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
1.4. Véc tơ riêng, giá trị riêng của ma trận . . . . . . . . . . . . . . . . . . . . . . .
13
Chương 2. Tính chất của ma trận biểu diễn đồ thị . . . . . . . . . . . . . . .
19
2.1. Định lý Kirchhoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.1.1. Ma trận Laplace của đồ thị và một số tính chất cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.1.2. Ma trận Laplace của một cạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.1.3. Phân tích ma trận Laplace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.1.4. Định lý Kirchhoff. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.2. Định lý Perron-Frobenius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.2.1. [10](Định lý (Perron-Frobenius) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.2.2. [10]Định lý Perron-Frobenius cho trường hợp n = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.2.3. [10]Định lý Perron-Frobenius cho ma trận n × n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
Chương 3. Một số ứng dụng của ma trận biểu diễn đồ thị . . . . . . . .
52
3.1. Ứng dụng định lý Kirchhoff tìm số cây bao trùm của đồ thị . . . .
52
iv
3.2. [4][5]Xếp hạng các đội chơi trong 1 giải đấu . . . . . . . . . . . . . . . . .
54
3.2.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
3.2.2. Khung SAS/IML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
3.2.3. Phương pháp xếp hạng thứ tự GeM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
3.2.4. Ma trận trọng số có hướng NFL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
3.2.5. Ma trận GeM G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
1
Lời mở đầu
1. Lý do chọn đề tài
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã hình thành và phát triển từ
khá lâu nhưng lại có nhiều ứng dụng hiện đại. Những tư tưởng cơ bản của lý
thuyết đồ thị được đề xuất từ những năm 30 của thế kỷ XVIII bởi nhà toán
học lỗi lạc người Thụy Sỹ Leonhard Euler. Chính ông là người đã đề xuất mô
hình đồ thị và sử dụng nó để giải bài toán nổi tiếng về bảy cây cầu ở thành
phố K¨ nigsberg. Từ đó, lý thuyết đồ thị ngày càng khẳng định được vị trí
o
quan trọng trong việc áp dụng để giải quyết nhiều bài toán trên mọi lĩnh vực.
Đồ thị mô tả các quan hệ hai ngôi trên tập hợp một cách trực quan sinh
động; giúp chúng ta mô tả các bài toán phức tạp trở nên cụ thể, đơn giản hơn.
Sơ đồ biểu diễn một hệ thống các tuyến bay của một hãng hàng không là một
hình ảnh của đồ thị. Các đối tượng là các sân bay, mỗi đường bay thẳng sẽ
biểu diễn mối liên hệ giữa 2 sân bay đầu cuối của tuyến.
Các tính chất của đồ thị có thể được biểu diễn bằng ngôn ngữ đại số tuyến
tính và những kết quả của đại số tuyến tính sẽ được thể hiện trực quan bằng
đồ thị. Ma trận là một khái niệm của Đại số tuyến tính. Ma trận có ứng dụng
trong hầu hết các lĩnh vực khoa học. Ma trận có vai trò khá quan trọng trong
lý thuyết đồ thị. Có thể nói ma trận là một công cụ kết nối giữa lý thuyết đồ
thị và đại số tuyến tính. Trong phạm vi của luận văn tốt nghiệp thạc sĩ chuyên
ngành Toán ứng dụng, từ sự đề xuất hướng nghiên cứu và trực tiếp hướng dẫn
của TS. Trần Minh Tước, chúng tôi xác định đề tài là
"Ma trận của đồ thị và một số ứng dụng".
2
Với đề tài này, tôi hy vọng rằng sẽ làm rõ mối liên hệ giữa đại số tuyến tính
và lý thuyết đồ thị dựa trên các biểu diễn ma trận của nó, từ đó tìm ra được
ứng dụng. Kết quả của đề tài cũng là sự thể hiện quá trình tập dượt nghiên
cứu của tôi.
2. Mục đích nghiên cứu
Tìm hiểu sự liên hệ giữa ma trận và đồ thị và góp phần làm rõ mối quan
hệ giữa đại số tuyến tính với lý thuyết đồ thị.
3. Nhiệm vụ nghiên cứu
Nhiệm vụ nghiên cứu được đặt ra trong khuôn khổ luận văn này là nghiên
cứu lợi ích khi biểu diễn đồ thị dưới dạng ma trận, từ đó sử dụng các công cụ
đại số nhằm tìm ra các ứng dụng thực tế của ma trận đồ thị. Luận văn được
chia làm 3 chương:
Chương 1: Kiến thức chuẩn bị. Trong chương này, tôi trình bày cách xây
dựng một đồ thị về ma trận đại số và một số kiến thức cơ bản của đại số tuyến
tính nhằm sử dụng chủ yếu cho nội dung trong chương 2
Chương 2: Tính chất của ma trận biểu diễn đồ thị. Trên cơ sở các loại ma
trận của đồ thị hướng đến chứng minh hai định lý chính: định lý Kirchhoff và
định lý Perron – Frobenius. Rõ ràng, việc tính số cây bao trùm của một đồ thị
trực quan thường mất thời gian và dễ gây nhầm lẫn, thiếu xót nhưng với định
lý Kirrchoff, từ công cụ đại số tác giả xây dựng nên cách tính số cây bao trùm
của một đồ thị một cách chính xác và khoa học hơn bằng phần bù đại số của
ma trận Laplace. Định lý Perron – Frobenius cho ta cái nhìn cụ thể hơn về
giá trị riêng và véc tơ riêng của ma trận không âm. Ở đó, nếu các thành phần
của ma trận là dương và tổng các cột bằng 1, định lý và hệ quả cuối cùng cho
ta kết quả là giá trị riêng lớn nhất không âm là 1 và véc tơ riêng tương ứng
3
dương. Đó là nền tảng hình thành nên ứng dụng mang tính thực tiễn cao ở
chương 3.
Chương 3: Một số ứng dụng của ma trận biểu diễn đồ thị. Tác giả trình
bày hai ứng dụng thực tế sử dụng tính chất đã nêu ở chương hai. Ứng dụng
đầu tiên sử dụng định lý Kirchhoff nhằm giải quyết bài toán xây dựng mạng
lưới đường sắt tàu hỏa một cách kinh tế và tối ưu nhất. Ứng dụng thứ hai sử
dụng định lý Perron – Frobenius và hệ quả để đánh giá xếp hạng các đội chơi
trong một giải đấu.
4. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu:
Đối tượng nghiên cứu của luận văn xoay quanh đồ thị hữu hạn và các biểu
diễn của đồ thị dưới dạng ma trận là: ma trận kề, ma trận liên thuộc, ma trận
bậc, ma trận có trọng số và ma trận Laplace
Phạm vi nghiên cứu:
Sử dụng các kiến thức đã được nghiên cứu về đồ thị vô hướng, đồ thị vô
hướng có trọng số; các kiến thức đại số tuyến tính về ma trận của đồ thị
5. Phương pháp nghiên cứu
Phương pháp nghiên cứu lí thuyết sử dụng các công cụ của lý thuyết đồ thị
và đại số tuyến tính.
6. Đóng góp của luận văn
Luận văn làm rõ mối liên hệ giữa tính chất của đồ thị với đại số tuyến tính,
từ đó tìm hiểu hai ứng dụng ma trận của đồ thị. Tác giả cố gắng xây dựng luận
văn thành một tài liệu tham khảo bổ ích cho những ai có nhu cầu tìm hiểu về
ma trận của đồ thị và một số ứng dụng của chúng. Tuy đã có nhiều cố gắng,
song do hạn chế về thời gian và năng lực của bản thân, nên luận văn không
4
tránh khỏi sai xót, rất mong được sự quan tâm góp ý của thầy cô và các bạn.
Tôi xin chân thành cảm ơn!
5
Chương 1
Kiến thức chuẩn bị
Trong chương này, chúng tôi trình bày một số kiến thức cơ sở cho chương sau.
Trước tiên là trình bày khái niệm đồ thị có hướng và đồ thị vô hướng, từ đó
biểu diễn đồ thị dưới dạng ma trận và ý nghĩa. Tiếp theo là định nghĩa về véc
tơ riêng và giá trị riêng. Nội dung trình bày ở chương này và các kiến thức
liên quan khác về lý thuyết đồ thị, đại số tuyến tính và giải tích hàm sử dụng
trong bài được xem ở tài liệu [1][2][3].
1.1. Khái niệm đồ thị
Định nghĩa 1.1. Một đồ thị vô hướng G là một cặp có thứ tự G = (V, E),
ở đây V là một tập hữu hạn; còn E là tập với các phần tử là các tập con hai
phần tử trên V ,
E ⊆ { {u, v} |u, v ∈ V, u = v}
Các phần tử của V được gọi là các đỉnh, tập đỉnh của G được ký hiệu là
V (G). Các phần tử của E được gọi là các cạnh, tập cạnh của đồ thị vô hướng
G được ký hiệu là E(G). Nhưng để đơn giản hơn ta có thể viết “đỉnh v ∈ V ”
hay “cạnh e ∈ E”. Cho a, b ∈ V , nếu tồn tại e ∈ {a, b} thì khi đó e là một
6
cạnh của G với hai đỉnh đầu mút là a, b hay a, b là hai đỉnh liên thuộc với e.
Cạnh e = {a, b} thường được ký hiệu ngắn gọn là ab hay ba. Trong luận văn
này, ta chỉ xét tới đơn đồ thị, không xét tới đồ thị có khuyên và đa đồ thị. Do
vậy khi nhắc đến đồ thị, ta ngầm hiểu là đơn đồ thị vô hướng.
Có thể biểu diễn một đồ thị một cách trực quan như sau: Các đỉnh của V
được biểu diễn bằng các vòng tròn nhỏ (rỗng hoặc đặc), còn các cạnh được
biểu diễn bằng một đường cong (đường thẳng) nối 2 đầu mút của cạnh.
Ví dụ 1.1.1. Cho G = (V, E) với V = {a, b, c, d, f, g};
E = {ab, db, dc, bc, cf, cg, gf }.
Khi đó biểu diễn của đồ thị vô hướng G:
Hình 1.1: Đồ thị G
Giả sử một mạng lưới giao thông gồm các trạm xe bus và đường đi giữa
chúng, giữa 2 trạm luôn chỉ có không quá một đường đi trực tiếp, không có
đường quay vòng từ một trạm tới chính nó. Ta biểu diễn mạng lưới giao thông
này bằng mô hình đồ thị như sau: mỗi trạm đỗ xe là một đỉnh, mỗi đường đi
trực tiếp giữa hai trạm là 1 cạnh.
Ta có hình ảnh chính xác của đồ thị.
7
Hình 1.2: Mạng lưới xe buýt
Các đường giao thông đôi khi chỉ được chạy theo một chiều. Chúng ta có
thể dùng đồ thị có hướng để mô hình hóa những mạng như thế.
Định nghĩa 1.2. Một đồ thị có hướng G là một cặp có thứ tự G = (V, E), ở
đây V là một tạp hữu hạn, còn E là một tập con của tích Đề các V × V .
Các phần tử của V được gọi là các đỉnh, còn các phần tử của E được gọi
là các cung của đồ thị vô hướng G. Nếu (a, b) ∈ E thì (a, b) được gọi là cung
của G với đỉnh đầu là a, đỉnh cuối là b và có hướng từ a tới b. Khi đã cho
G = (V, E) là đồ thị có hướng, cung (a, b) ∈ E thường được ký hiệu ngắn
gọn là ab với a là đỉnh đầu và b là đỉnh cuối; ba là cạnh với b là đỉnh đầu, a là
đỉnh cuối.
Biểu diễn một đồ thị có hướng trên mặt phẳng trực quan tương tự như biểu
diễn đồ thị vô hướng: Các đỉnh của V được biểu diễn bằng các vòng tròn nhỏ
(rỗng hoặc đặc), còn các cung được biểu diễn bằng một đường cong có hướng
(với mũi tên) từ đỉnh đầu tới đỉnh cuối.
Ví dụ 1.1.2. Cho đồ thị có hướng G = (V, E) với V = {a, b, c, d, f, g};
E = {ad, db, dc, bc, cf, cg, gf }.
8
Khi đó biểu diễn của đồ thị có hướng G:
Hình 1.3: Đơn đồ thị G
Định nghĩa 1.3. Đồ thị có hướng hoặc vô hướng G = (V, E) được gọi là đồ
thị có trọng số (hay thường gọi tắt là trọng đồ) nếu có ít nhất một trong hai
hàm:
f : V → WV
và
g : E → WE
được xác định. Ở đây Wv và WE là các tập số. Giá trị f (v) cho v ∈ V được
gọi là trọng số của đỉnh v, còn giá trị g(e) cho e ∈ E được gọi là trọng số của
cung hay cạnh e. Người ta cũng thường ký hiệu trọng đồ bằng G = (V, E, f )
hay hay G = (V, E, f, g) tùy thuộc vào việc chỉ một hàm f , chỉ một hàm g
hay cả hai hàm f và g được xác định.
Trong khuôn khổ luận văn này, chúng ta chỉ sử dụng tới G = (V, E, g).
Biểu diễn một đồ thị G = (V, E, g) có trọng số trên mặt phẳng ta biểu
diễn đồ thị có hướng và gắn giá trị trọng số tương ứng lên trực tiếp sát phía
bên cạnh của cung mang giá trị đó
Ví dụ 1.1.3. Cho đồ thị có hướng có trọng số với V = {a, b, c, d, f, g},
E = {ad, db, dc, bc, cf, cg, gf }, g (ad) = g (dc) = g (gf ) = 3,
g (db) = g (bc) = 2, g(cf ) = g(cg) = 4.
9
Khi đó biểu diễn của đồ thị có trọng lượng G:
Hình 1.4: Đồ thị có trọng số G
1.2. Ma trận kề. Ma trận trọng số
Xét đồ thị vô hướng G = (V, E) với tập đỉnh V = {1, 2, . . . , n} và tập cạnh
E = {e1 , e2 , . . . , em }. Ta gọi ma trận kề của đồ thị G là (0;1)-ma trận
A = {aij : i, j = 1, 2, . . . , n}
với các phần tử được xác định theo quy tắc sau đây
aij = 0, nếu {i, j} ∈ E và aij = 1, nếu {i, j} ∈ E,
/
i, j = 1, 2, . . . , n.
Ví dụ 1.2.1. Cho đồ thị như hình vẽ:
Ma trận kề của đồ thị vô hướng G là:
10
Hình 1.5: Đồ thị vô hướng G và đồ thị có hướng G1
1
1
0
21
31
40
51
6 0
2
1
3
1
4
0
5
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
0
1
1
6
0
0
0
1
1
0
Các tính chất của ma trận kề.
1) Rõ ràng ma trận kề của đồ thị vô hướng là đối xứng, tức là
aij = aji ,
i, j = 1, 2, . . . , n.
Ngược lại mỗi (0,1)-ma trận đối xứng cấp n sẽ tương ứng, chính xác đến cách
đánh số đỉnh (còn nói là: chính xác đến đẳng cấu), với một đồ thị vô hướng n
đỉnh.
2) Tổng các phần tử trên dòng i (cột j) của ma trận kề của đồ thị vô hướng
11
chính bằng bậc của đỉnh i (đỉnh j).
3) Nếu ký hiệu
ap , i, j = 1, 2, . . . , n
ij
là các phần tử của ma trận tích
Ap = A.A...A
p
Khi đó
ap , i, j = 1, 2, . . . , n
ij
cho ta số đường đi khác nhau từ đỉnh i tới đỉnh j qua p − 1 đỉnh trung gian.
Ma trận kề của đồ thị có hướng được định nghĩa hoàn toàn tương tự.
Ví dụ 1.2.2. Đồ thị có hướng G1 cho trong Hình 1.5 có ma trận kề là ma trận
sau
1
1
0
20
30
40
50
6 0
2
1
3
1
4
0
5
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
6
0
0
0
0
1
0
Lưu ý rằng ma trận của đồ thị có hướng chưa chắc là ma trận đối xứng.
Trong trường hợp đồ thị có trọng số cạnh hoặc cung, thay vì ma trận kề,
12
để biểu diễn đồ thị ta sử dụng ma trận trọng số
C = cij : i, j = 1, 2, . . . , n,
với
cij = cji ,
nếu (i, j) ∈ E
cij = θ,
nếu (i, j) ∈ E,
/
và
trong đó số θ, tùy từng trường hợp cụ thể, có thể được đặt bằng một trong các
giá trị sau: 0, −∞, +∞.
Ưu điểm lớn nhất của phương pháp biểu diễn đồ thị bằng ma trận kề (hoặc
ma trận trọng số) là để trả lời câu hỏi: Hai đỉnh u, v có kề nhau trên đồ thị hay
không, chúng ta chỉ phải thực hiện một phép so sánh. Nhược điểm lớn nhất
của phương pháp này là không phụ thuộc vào số cạnh của đồ thị, ta luôn phải
sử dụng n2 đơn vị bộ nhớ để lưu trữ ma trận kề của nó.
1.3. Ma trận liên thuộc
Xét G = (V, E), (V = {1, 2, . . . , n}, E = {e1 , e2 , . . . , em }) , là đồ thị có
hướng. Xây dựng ma trận B = (bij , i = 1, 2, . . . , n, j = 1, 2, . . . , m), trong
đó
1,
bij = −1,
0,
nếu tồn tại {i, j}, i < j
nếu tồn tại {i, j}, i > j
nếu không tồn tại {i, j} .
13
Ma trận B xây dựng như quy tắc vừa nêu được gọi là ma trận liên thuộc đỉnh
cung.
Ví dụ 1.3.1. Xét đồ thị cho trên hình vẽ sau:
Hình 1.6: Đồ thị vô hướng
1 −1 0 0
B = 1 0 −1 0 .
1 0 0 −1
Ma trận liên thuộc là một trong những cách biểu diễn rất hay được sử dụng
trong các bài toán liên quan đến đồ thị có hướng mà trong đó phải xử lý các
cung của đồ thị.
1.4. Véc tơ riêng, giá trị riêng của ma trận
Định nghĩa 1.4. Cho f : V → V là một tự đồng cấu của V và U u là một
không gian vectơ con của V .
14
Ta nói U u là không gian vectơ con bất biến đối với f (hay một không gian
con f - bất biến) nếu f (U u) ⊆ U u.
Ví dụ: Với tự đồng cấu f : V → V bất kỳ, các không gian con sau đây đều
là f - bất biến: {0}, V, Kerf, Imf.
Định nghĩa 1.5. Giả sử f : V → V là một tự đồng cấu của K− không gian
vectơ V . Nếu có vectơ α = 0 của V và vô hướng λ ∈ K sao cho f (α) = λα
thì λ được gọi là một giá trị riêng còn α được gọi là một vectơ riêng của f
ứng với giá trị riêng λ.
Nhận xét rằng, nếu α là một vectơ riêng của f ứng với giá trị riêng λ thì
α ∈ Ker(f − λ, idv ) \ {0}. Ta định nghĩa khái niệm dưới đây.
Định nghĩa 1.6. Giả sử λ là một giá trị riêng của một tự đồng cấu f : V → V .
Khi đó, không gian vectơ Ker(f −λ.idv ) gồm vectơ 0 và tất cả các vectơ riêng
của f ứng với giá trị riêng λ được gọi là không gian con riêng của f ứng với
giá trị riêng λ và được ký hiệu là Pλ .
Giả sử, dimV = n và f có ma trận là A = (aij )n×n đối với một cơ sở
nào đó trong V . Khi đó, đối với cơ sở này, đồng cấu f − X.idv có ma trận là
A − X.En . Khi đó
a11 − X
det(f − X.idv ) = det(A − X.En ) =
a21
a1,2
...
a1,n
a22 − X . . .
a2n
...
...
...
an1
an2
. . . ann − X
Như vậy det(f − X.idv ) là một đa thức bậc n của X.
...
- Xem thêm -