Ước chung lớn nhất của các ma trận vuông

Suy ra tồn tại D S sao cho:  . |M SD K D K S   . 
− Ta chứng minh D là  1 2, ,..., nUCLN A A A . 
Hệ quả: Trên ( )nM R , nếu D là  1 2, ,..., nUCLN A A A thì tồn tại các ma trận 
TDMU, số 2 (27) – 2016 Nguyễn Thị Khánh Hòa, Nguyễn Thị Kiều Trinh 
 71 
1 2, ,..., ( )n nU U U M R sao cho 1 1 2 2 ... n nD U A U A U A    . 
Định lý 2: 
Cho R là vành chính và A, B là các ma trận vuông cấp n trong vành  nM R . 
Đặt 
A
C
B
 
  
 
 là ma trận cấp 2n n . Nếu tồn tại ma trận khả nghịch V sao cho 
VC H là ma trận bậc thang thì các khẳng định sau đây là đúng: 
i) Gọi D là n dòng đầu của H thì D là  ,UCLN A B . 
ii) Đặt n cột đầu của 1V  là 
P
Q
 
 
 
 thì A PD ; .B QD 
iii) Đặt n dòng đầu của V là  X Y thì .XA YB D  
Chứng minh: 
Giả sử 
2 2n n
X Y
V

 
    
; 1
2 2n n
P
V
Q


 
   
; 
2n n
D
H
O

 
  
 
 trong đó , , , ,X Y P Q D là các 
ma trận vuông cấp n . 
− Theo giả thiết VC H mà V khả nghịch nên 1 .C V H 
Do đó C  1
A P D
V H
B Q O

     
           
. Điều này cho ta A PD và .B QD 
Có nghĩa D là ước chung bên phải của A và B. 
− Cũng từ VC H ta suy ra .
X Y A D
XA YB D
B O
     
              
− Giả sử D là ước chung bên phải của A, B nghĩa là tồn tại  , nP Q M R  sao cho 
A P D  ; B Q D  . Khi đó D    .XA YB XP D YQ D XP YQ D           
Suy ra D là ước bên phải của D . Vậy D là  ,UCLN A B . 
Kết quả sau được chứng minh trong trường hợp R  . 
Định lí 3: Bằng cách sử dụng hai phép biến đổi sơ cấp trên dòng (đổi chỗ 2 dòng; 
Cộng vào 1 dòng một bội của dòng khác) ta luôn đưa được một ma trận C bất kỳ về dạng 
bậc thang H và tồn tại một ma trận khả nghịch V sao cho VC=H. 
Chứng minh: 
− Chứng minh: mọi ma trận C bất kỳ đều đưa được về dạng bậc thang H. 
− Chứng minh: tồn tại một ma trận khả nghịch V sao cho VC=H. 
Giả sử H là ma trận bậc thang nhận được sau k phép biến đổi sơ cấp. 
Khi đó 1... .kE E C H . Đặt 1...kV E E . Ta sẽ chứng minh V khả nghịch. 
Nếu iE  1 i k  là ma trận sơ cấp có được do đổi dòng thì det det 1i mE I    . 
Nếu iE  1 i k  là ma trận sơ cấp có được do cộng vào một dòng một bội của dòng 
khác thì det det 1i mE I  . Do đó det 1V   . Có nghĩa là V là ma trận khả nghịch. 
3.2.2 Phương pháp tìm UCLN của các ma trận vuông 
Từ chứng minh của định lý 2 và định lý 3 mục 3.2.1, ta có được thuật toán sau: 
TDMU, số 2 (27) – 2016 Ước chung lớn nhất của các ma trận vuông 
 72 
Thuật toán tìm UCLN của hai ma trận vuông A, B trên vành  nM 
Với  , nA B M . Đặt 
2n n
A
C
B

 
  
 
. 
Đưa ma trận C về dạng bậc thang H bằng hai phép biến đổi sơ cấp trên dòng (phép đổi 
chỗ hai dòng, phép cộng vào dòng này một bội của dòng khác). 
Bước 1: Giả sử j là cột đầu tiên khác 0 của C , sử dụng phép đổi chỗ các dòng để 
0kjc  là phần tử đầu tiên của cột j và là phần tử có giá trị tuyệt đối nhỏ nhất trên cột j . 
Bước 2: Khử các phần tử ijc  i k bằng cách cộng vào dòng i một bội iq của dòng 
j . Trong đó : .ij i jj ic q c r  ; 0 ,i jjr c  ,i iq r  . 
Bước 3: Lặp lại các bước 1 và bước 2 cho các cột kế tiếp của C . 
Bước 4: Ma trận D tạo bởi n dòng đầu của H là  ,UCLN A B . 
Ví dụ: Tìm UCLN của hai ma trận vuông A và B ,biết 
1 2
3 4
A
 
  
 
 và 
4 3
2 1
B
 
  
 
. 
Đặt 
1 2
3 4
4 3
2 1
C
 
 
 
 
 
 
. Ta tiến hành đưa ma trận C về dạng bậc thang. 
Bước 1: Ta có 11 1 0c   là phần tử có giá trị tuyệt đối nhỏ nhất trên cột 1 của .C 
Bước 2: Khử các phần tử (của cột 1) nằm bên dưới phần tử 11c của .C 
− Để khử 21 3c  , ta cộng vào dòng 2 một bội 1 3q   dòng 1. Ta được: 
1
1 2
0 2
4 3
2 1
C
 
 
 
 
 
 
. Khử phần tử 31 4c  và 41 2c  thu được ma trận: 2
1 2
0 2
0 5
0 3
C
 
 
 
 
 
 
. 
Bước 3: Lặp lại bước 1 và bước 2 cho cột 2 của ma trận 2C . 
Ta có 22 2 0c    là phần tử có giá trị tuyệt đối nhỏ nhất trên cột 2 của ma trận 2C . 
− Để khử 32 5c   , ta cộng vào dòng 3 một bội 4 3q   dòng 2. Ta được: 
3
1 2
0 2
.
0 1
0 3
C
 
 
 
 
 
 
 Vì 32 1 0c   là phần tử có giá trị tuyệt đối nhỏ nhất trên cột 2 của ma trận 3C , nên ta 
thực hiện phép đổi chỗ 2 3d d của 3C . 
− Ta tiếp tục khử phần tử 32 2c   và 42 3c   tương tự như trên. 
TDMU, số 2 (27) – 2016 Nguyễn Thị Khánh Hòa, Nguyễn Thị Kiều Trinh 
 73 
Bước 4: Sau bước 3, ma trận C được đưa về dạng bậc thang là 4
1 2
0 1
.
0 0
0 0
C
 
 
 
 
 
 
Vậy  ,UCLN A B là 
1 2
0 1
D
 
  
 
 (D là ma trận tạo bởi 2 dòng đầu của 4C ). 
Phương pháp tìm UCLN của nhiều ma trận: 
Cho  1 2, ,..., n nA A A M . 
Gọi 2D là  1 2, ,UCLN A A 3D là  2 3, ,UCLN D A , nD là  1, .n nUCLN D A 
Khi đó nD là  1 2, ,..., .nUCLN A A A 
Thật vậy, ta thấy rằng mọi ước chung của 1 2, ,..., nA A A đều là ước chung của 
2 3, ,..., nD A A và ngược lại. Vì vậy ta có    1 2 2 3, ,..., , ,...,n nUCLN A A A UCLN D A A . 
Lặp lại lí luận này nhiều lần, ta sẽ được    1 2 2 3, ,..., , ,...,n nUCLN A A A UCLN D A A 
  3 4, ,..., nUCLN D A A  1.... ,n nUCLN D A  
nghĩa là nD là  1 2, ,..., .nUCLN A A A 
3.3 Một số tính chất của UCLN của các ma trận vuông 
1) (Mục 379, chương 19, [4])  nK M R  , nếu D là  1 2, ,..., nUCLN A A A thì DK là 
 1 2, ,..., nUCLN A K A K A K . 
Chứng minh 
− Giả sử D là  1 2, ,..., nUCLN A A A . 
Suy ra tồn tại  1 2, ,..., n nU U U M R để 1 1 2 2 ... n nD U A U A U A    . 
Suy ra      1 1 2 2 ... .n nDK U A K U A K U A K    
Suy ra DK là ước chung bên phải của 1 2, ,..., .nA K A K A K 
− Giả sử E là ước chung bên phải tùy ý của 1 2, ,..., .nA K A K A K . 
Ta có: i iAK X E (  i nX M R , 1,i n  ). 
Khi đó: 
            1 1 2 2 1 1 2 2... ...n n n nDK U X E U X E U X E U X E U X E U X E        
  1 1 2 2 ... n nU X U X U X E    
Suy ra E là ước bên phải của DK . Vậy DK là  1 2, ,..., nUCLN A K A K A K 
2) Cho K là ước chung bên phải của 1 2, ,..., nA A A (tức là tồn tại iK để i iA K K với 
1,i n ). Nếu D là  1 2, ,..., nUCLN K K K thì DK là  1 2, ,..., nUCLN A A A . 
Chứng minh : Tính chất 2 được suy ra trực tiếp từ tính chất 1. 
3)  nK M R  , nếu E là  1 2, ,..., nUCLN A K A K A K thì .E D K với  nD M R . 
Chứng minh: Vì E là  1 2, ,..., nUCLN A K A K A K nên tồn tại các ma trận 
TDMU, số 2 (27) – 2016 Ước chung lớn nhất của các ma trận vuông 
 74 
 1 2, ,..., n nX X X M R sao cho 
     1 1 2 2 ... n nE X A K X A K X A K     1 1 2 2 ... .n nX A X A X A K    
Đặt  1 1 2 2 ... n n nD X A X A X A M R     . Khi đó .E D K . 
4) Cho D là ước chung của 1 2, ,..., nA A A (tức là tồn tại iE để i iA E D với 1,i n ). 
Khi đó, D là  1 2, ,..., nUCLN A A A khi và chỉ khi I là  1 2, ,..., nUCLN E E E . 
Chứng minh: Giả sử D là  1 2, ,..., nUCLN A A A và U là  1 2, ,..., nUCLN E E E . 
Khi đó, theo tính chất 1, ta suy ra UD cũng là  1 2, ,..., nUCLN A A A . 
Do đó, UD là ước của D, tức là tồn tại ma trận V sao cho  D V UD . 
Suy ra  D VU D . Suy ra  det 1 0VU   hay ma trận U khả nghịch. 
Do đó, theo nhận xét 2 (mục 3.1.3), ta có 1U U I  cũng là  1 2, ,..., nUCLN E E E . 
Điều ngược lại được suy ra trực tiếp từ tính chất 1. 
5) Nếu I là  ,UCLN A B và B là ước của AC thì B là ước của C. 
Chứng minh: Vì I là  ,UCLN A B nên tồn tại  , nX Y M R để .I XA YB  
Suy ra   .IC XA YB C  Suy ra .C XAC YBC  
Vì B là ước của AC và B là ước của BC nên B là ước của  .XAC YBC 
Do đó B là ước của C. 
6) Nếu I là  ,UCLN A B và D là  ,UCLN C B thì D là  ,UCLN AC B và ngược lại. 
Chứng minh 
− Giả sử D là ước chung của AC và B. Suy ra D là ước chung của AC và BC. 
Mà theo tính chất 1, vì I là  ,UCLN A B nên C là  ,UCLN AC BC . 
Do đó D là ước của C. Vậy D là ước chung của B và C. 
− Ngược lại, giả sử D là ước chung của C và B. Suy ra D là ước chung của AC và B. 
− Như vậy, tập hợp các ước chung của AC và B trùng với tập hợp các ước chung của C 
và B nên nếu D là  ,UCLN C B thì D là  ,UCLN AC B . 
7) Nếu I là  ,UCLN A B và I là  ,UCLN A C thì I cũng là  ,UCLN A BC . 
Chứng minh : Giả sử D là  ,UCLN A BC , theo tính chất 6, D cũng là  ,UCLN A C . 
Mà I là  ,UCLN A C nên D là ước của I, tức là D khả nghịch. 
Do đó 1D D I  cũng là  ,UCLN A BC . 
GREATEST COMMON DIVISOR OF SQUARE MATRICES 
Nguyễn Thị Khánh Hòa − Nguyễn Thị Kiều Trinh 
ABSTRACT 
Based on existing knowledge about the greatest common divisor of integers in 
combination with matrix results on the primary domain, the article clarifies definition of 
greatest common divisor of square matrices, proving the existence of the greatest common 
divisor of the square matrices on the main domain, detailing how to find the greatest 
TDMU, số 2 (27) – 2016 Nguyễn Thị Khánh Hòa, Nguyễn Thị Kiều Trinh 
 75 
common divisor of two square matrices with elements as integers, and proving some 
properties of the divisor and the greatest common divisor of square matrices. 
TÀI LIỆU THAM KHẢO 
[1] Bùi Xuân Hải (Chủ biên), Đại số tuyến tính, Trường Đại học Khoa học Tự nhiên 
TP.HCM, 2000. 
[2] Donald Knuth -Addison wesleef Longman, Ine - Seminumericalalgorithms (The art of 
computer programming), Third edition, 1997. 
[3] Dương Quốc Việt, Cơ sở lý thuyết module, NXB Đại học Sư phạm, 2008. 
[4] Éugene Cahen, Théorie des nombres, Librairie Sciencetifique A. Hermann & Fils, 1914. 
[5] Hoàng Xuân Sính, Đại số đại cương, NXB Giáo dục, 1999 
[6] Nguyễn Hữu Việt Hưng, Đại số đại cương, NXB Giáo dục, 1998. 
[7] Nguyễn Tiến Tài (Chủ biên), Số học, NXB Giáo dục, 1999. 
[8] Thomas W. Hungerford, Algebra, Springer Science & Business Media, 1974. 
[9] William Brown, Matrices over commutative rings, Marcel Dekker, 1993.