ĐẠ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


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ị
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.

.

.
.

.
.
.
.

.
.
.
.

.
.
.
.
.
.

.
.
.
.

.
.
.
.



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


A

p

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

→
−
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

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.


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ả



a11 + b11 a12 + b12
a +b
a22 + b22
 21
21
=

·
·
am1 + bm1 am2 + bm2



a11 a12
a
 21 a22
a
 ·
·
am1 am2





· · · b1n

· · · b2n 



· · · 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
n

cik =

(1 ≤ i ≤ m, 1 ≤ k ≤ p).

aij bjk ,
j=1

Ví dụ 1.1.3.



a b c




1 −2 3 
9 15

−1 0 =
−1 2 5
7 17
2 4
2
3

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 = 

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

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

.
σ(1) σ(2) · · · σ(n)


8

Định nghĩa 1.2.2 ([1]). Dấu của phép thế σ ∈ Sn là số sau đây
sgn(σ) =
i=j

σ(i) − σ(j)
∈ {±1}.
i−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
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,



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:
n

det(A) = a11 a22 · · · ann =

aii .
i=1


3 ,
2 0 −1


A = −1 1
dọc theo cột thứ 2 là
det(A) = (−1)2+1 · 2

−1 3
−2 −3
−2 −3
+ (−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 = 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
= 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à


S⊆[n]:|S|=m


11

1 1 2
3 1 −1

Ví dụ 1.2.13. Lấy m = 2 và n = 3, và ma trận A =



và B =



1 1



3 1, theo công thức Binet-Cauchy ta có
0 2
det AB =

1 1 1 1
1 2 3 1
1 2 1 1
+
+
3 1 3 1

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

⇔ tồn tại x = 0 sao cho Ax − λIn x = 0
⇔ tồn tại x = 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ó






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 .



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) = 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 = 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 = 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
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





−13 −8 −4


F =  12
7
4 .
24 16 7
T

Theo Ví dụ 1.3.6, ta có x = 1 −1 −2
T

x = −2 3 0

là một véctơ riêng ứng với λ = 3,

T

là hai véctơ riêng ứng với λ = −1. Xác

và x = −1 0 3

định ma trận S là ma trận có ba cột là ba véctơ riêng của F ,





F S = −1






−2 −1
1 −2 −1


3
0  −1 3
0
−2 0
3
−2 0
3
1


−1






−3 −2

17

1.5

Chuẩn của ma trận

Vì Rm×n đẳng cấu với Rm·n , định nghĩa của chuẩn ma trận tương đương
với định nghĩa của chuẩn véctơ. Nói riêng, f : Rm×n → R là một chuẩn ma
trận nếu ba tính chất sau thỏa mãn:
f (A) ≥ 0 với mọi A ∈ Rm×n , f (A) = 0 khi và chỉ khi A = 0
f (A + B) ≤ f (A) + f (B), với mọi A, B ∈ Rm×n
f (αA) = |α|f (A), với mọi α ∈ R, A ∈ Rm×n .
Giống như với chuẩn véctơ, ta ký hiệu chuẩn của ma trận A là A . Các chuẩn
ma trận thường được sử dụng trong phương pháp trong đại số tuyến tính là
chuẩn Frobenius,
m

A

n

|aij |2

=

F

i=1 j=1

và chuẩn p


√

n A

2

mn max |aij |
i,j

m

A

A

1

∞

|aij |

= max

1≤j≤n

i=1
n

|aij |

n A 1.


18

1.6

Phân tích SVD của ma trận

Định nghĩa 1.6.1 ([1]). Một tập các véctơ {x1 , . . . , xp } thuộc Rm được gọi là
trực giao nếu xTi xj = 0 với mọi i = j và được gọi là trực chuẩn nếu xTi xj = δij .
Một cách trực quan, các véctơ trực giao khác không là độc lập tuyến tính
vì chúng hướng theo các chiều khác nhau.
Định nghĩa 1.6.2 ([1]). Một họ các không gian con S1 , . . . , Sp thuộc Rm được
gọi là trực giao lẫn nhau nếu xT y = 0 với mọi x ∈ Si và y ∈ Sj với i = j.
Phần bù trực giao của không gian con S ⊆ Rm được định nghĩa bởi
S ⊥ = {y ∈ Rm : y T x = 0 với mọi x ∈ S}
và không khó để chứng minh rằng im(A)⊥ = ker(AT ). Các véctơ v1 , . . . , vk tạo
thành một cơ sở trực chuẩn của không gian con S ⊂ Rm nếu chúng là trực
chuẩn và căng S.
Ma trận Q ∈ Rm×m được gọi là trực giao nếu QT Q = I. Nếu Q = [q1 , . . . , qm ]
là trực giao, khi đó qi tạo thành một cơ sở trực giao của Rm . Ta luôn có thể
mở rộng một cơ sở như trên thành một cơ sở trực chuẩn {v1 , . . . , vm } của Rm .
Chuẩn 2 là bất biến dưới phép biến đổi trực giao vì nếu QT Q = I, thì
Qx 22 = xT QT Qx = xT x = x 22 . Chuẩn 2 và chuẩn Frobenius của ma trận
cũng bất biến dưới phép biến đổi trực giao. Cụ thể, dễ chứng minh được với
tất cả ma trận Q và Z có số chiều thích hợp thì ta có
QAZ

F

, Σ = A 2 , V = 1.
A 2

Ta giả sử SVD tồn tại với ma trận cỡ (m − 1) × (n − 1), tức là mỗi ma trận A˜
cỡ (m − 1) × (n − 1) luôn có phân tích SVD
A˜ = U1 Σ1 V1T .
Chọn v sao cho v 2 = 1 và A
nghĩa của chuẩn ma trận,

2

= Av

A

2

= max Av 2 .

2

> 0. Vectơ v luôn tồn tại theo định

v 2 =1

Av
; đây là một vectơ đơn vị. Ta đặt U = [u, U˜ ] là
Av 2
ma trận trực giao cỡ m × n và V = [v, V˜ ] là ma trận trực giao cỡ n × n. Ta viết
Tiếp theo ta chọn u =


2

≡ σ,

2

và
U˜ T Av = U˜ T u Av

2

= 0.

Ta suy ra uT AV˜ = 0 bởi vì nếu không
σ= A

2

= U T Av

2

[1, 0, . . . , 0]U T AV

2

= [σ|uT AV˜ ]

Đây là một mâu thuẫn. Như vậy

2

> σ.


20

hoặc
A=

1 0
U
0 U1

σ 0
0 Σ1

V

1 0
0 V1

T

.

Định nghĩa 1.6.4. Các cột u1 , u2 , . . . , un của U được gọi là vectơ kì dị trái.
Các cột v1 , v2 , . . . , vn của V được gọi là vectơ kì dị phải và các σi được gọi là
giá trị kì dị.
Nhận xét 1.6.5. Phân tích SVD của một ma trận A = U ΣV T không là duy

Khi đó, phân tích SVD của A là A = U ΣV T , ta có σi = |λi | và vi =
sgn(λi )ui , sgn(0) = 1.
2. Các giá trị riêng của ma trận đối xứng AT A là σi2 , các vectơ kì dị phải vi
là tương ứng với các vectơ riêng trực chuẩn.
3. Các giá trị riêng của ma trận đối xứng AAT là σi2 và m−n phần tử không.
Các vectơ kì dị trái ui là tương ứng của các vectơ riêng trực chuẩn với các
giá trị riêng σi2 . Ta có thể lấy bất kì m − n vectơ trực giao khác nhau như
là vectơ riêng tương ứng với các giá trị riêng bằng không.
0 AT
, trong đó A là ma trận vuông và A = U ΣV T là
4. Cho H =
A 0
khai triển SVD của A. Cho Σ = diag(σ1 , σ2 , . . . , σn ), U = [u1 , u2 , . . . , un ],
V = [v1 , v2 , . . . , vn ]. Khi đó, 2n giá trị riêng của H là ±σi , ứng với vectơ
vi
1
.
riêng đơn vị tương ứng là √
2 ±ui
5. Nếu ma trận A là hạng đầy thì nghiệm minx Ax − b 2 là x = V Σ−1 U T b.
6. A 2 = σ1 . Nếu A là ma trận vuông và không kì dị, thì A−1 −1
2 = σn
σ1
−1
và A 2 A
; giá trị này được gọi là số điều kiện của ma trận.
2 =
σn
7. Giả sử σ1 ≥ σ2 ≥ . . . ≥ σr ≥ σr+1 = . . . = σn = 0 thì hạng của A là r.
Hạt nhân của A là không gian con sinh bởi cột từ r + 1 đến n của V