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

Chia sẻ: Đặng Thị Tràn | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

116
lượt xem 3
download

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

Bài viết Ước chung lớn nhất của các ma trận vuông làm rõ định nghĩa UCLN của các ma trận vuông, chứng minh sự tồn tại UCLN của các ma trận vuông trên miền chính, trình bày chi tiết phương pháp tìm UCLN của hai ma trận vuông với các phần tử là các số nguyên và chứng minh một số tính chất của ước và UCLN các ma trận vuông,... Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: Ước chung lớn nhất của các ma trận vuông

TDMU, số 2 (27) 2016 Tạp chí Khoa học–TDMU ISSN: 1859 - 4433 Ước chungSố lớn2(27) nhất–của cácTháng ma trận 2016, 4 –vuông 2016 ƢỚC CHUNG LỚN NHẤT CỦA CÁC MA TRẬN VUÔNG Nguyễn Thị Khánh Hòa − Nguyễn Thị Kiều Trinh Trường Đại học Thủ Dầu Một TÓM TẮT Dựa trên những kiến thức đã có về ước chung lớn nhất (UCLN) của các số nguyên, kết hợp sử dụng một số kết quả về ma trận trên miền chính, bài viết làm rõ định nghĩa UCLN của các ma trận vuông, chứng minh sự tồn tại UCLN của các ma trận vuông trên miền chính, trình bày chi tiết phương pháp tìm UCLN của hai ma trận vuông với các phần tử là các số nguyên và chứng minh một số tính chất của ước và UCLN các ma trận vuông. Từ khóa: ước chung, lớn nhất, ma trận, miền chính ma trận cũng không được thể hiện một 1 GIỚI THIỆU cách tường minh. Để góp phần làm sáng tỏ Trên vành số nguyên , d là UCLN vấn đề này, chúng tôi sẽ đưa ra một điều của các số nguyên a1, a2, …, an khi và chỉ kiện vành R là một miền chính (bổ đề 2) khi iđêan sinh bởi {a1, a2, …, an} cũng và từ đó có thể khẳng định UCLN của các chính là iđêan sinh bởi d. Vì là miền ma trận vuông trên miền chính luôn tồn tại chính nên luôn tồn tại UCLN của các số (định lý 1). Chúng tôi cũng sẽ trình bày nguyên và dựa vào phép chia có dư trong chi tiết phương pháp tìm UCLN của hai , chúng ta có phương pháp tìm UCLN ma trận vuông với các phần tử là các số chính là thuật toán Ơclit. nguyên (định lý 2, định lý 3) và chứng Khái niệm “ước chung lớn nhất” của minh một số tính chất của ước và UCLN các ma trận đã được Éugene Cahen định các ma trận vuông. nghĩa tương tự như UCLN của các số nguyên[4]. Tuy nhiên, giữa vành số 2. KIẾN THỨC CƠ BẢN nguyên và vành các ma trận M mn  R  2.1 Bổ đề 1 (định lí 6.1, trang 218, [8]): Cho R là miền chính và M là môđun con với R là vành tùy ý, là có sự khác biệt. của R- môđun R n . Khi đó M là môđun tự Chẳng hạn, phép nhân các số nguyên có do với hạng không vượt quá n. tính giao hoán nhưng phép nhân các ma trận thì không, trong vành số nguyên có 2.2 Bổ đề 2 (bài tập 17 chương 15, phép chia có dư nhưng trong vành ma trận trang 203, [9]): Cho R là miền chính. I là thì chưa có, vành số nguyên là miền iđêan trái của Mn(R). Khi đó I là iđêan trái chính nhưng với R là vành tùy ý thìvành chính của Mn(R). M n  R  không chắc là miền chính. Do đó, 3. MỘT SỐ KẾT QUẢ khi R là vành tùy ý thì sự tồn tại của Trong phần này, ta luôn giả sử R là UCLN của các ma trận không được đảm miền chính. bảo và phương pháp tìm UCLN của hai 3.1. Các định nghĩa ma trận cũng không thể làm tương tự như Éugene Cahen định nghĩa ước cho các thuật toán Ơclit được. Éugene Cahen cũng ma trận với cấp tùy ý[4]. Trong phạm vi chưa đề cập đến vấn đề rằng UCLN của của bài viết này, chúng tôi chỉ đề cập đến các ma trận vuông có luôn tồn tại hay ước và UCLN của các ma trận vuông. không[4]. Phương pháp tìm UCLN của các 68 TDMU, số 2 (27) – 2016 Nguyễn Thị Khánh Hòa, Nguyễn Thị Kiều Trinh của C. Chứng minh: VìA là ước bên phải của B và B là ước bên phải của C nên tồn tại P, Q  M n ( R) để B = PA và C = QB. Suy ra C = (QP)A. Do đó, A là ước bên phải của C. iv) Với A1, A2 ,..., An  M n ( R) , nếu D là ước bên phải của A1, A2 ,..., An thìD là ước bên phải của ( P1 A1  P2 A2  ...  Pn An ) với 3.1.1. Ước của ma trận vuông Định nghĩa: Cho Mn(R) là vành. Giả sử A  M n ( R) , D  M n ( R) , D  O . Ta nói D là ước bên phải (trái) của ma trận A, nếu tồn tại P  M n ( R) sao cho A = PD (tương ứng A = DP). Ví dụ: Trên M 2 ( ) , cho hai ma trận Pi  M n ( R) , i  1, n. 0 1  0 1  , D A  , D O.  1 0  0 0 D là ước bên phải của A vì tồn tại 1 0  P   M 2 ( ) để A = PD. 0 0  Chứng minh: VìD là ước bên phải của Ai, i  1, n nên tồn tại các ma trận Qi  M n ( R) , i  1, n sao cho Ai  Qi D. Khi đó: P1 A1  P2 A2  ...  Pn An Tính chất: i) A là ước bên phải, trái của ma trận đơn vị I n khi và chỉ khi A là ma trận khả nghịch. Chứng minh: () Giả sử A là ma trận khả nghịch.  P1 (Q1D)  P2 (Q2 D)  ...  Pn (Qn D)  ( PQ 1 1  P2Q2  ...  PnQn ) D. 3.1.2 Ước chung của các ma trận vuông Định nghĩa: Trên M n ( R) , ma trận D được gọi là ước chung bên phải (trái) của các ma trận A1,A2,…,An nếu D là ước bên phải (trái) đồng thời của mỗi ma trận đó. Ví dụ: 1 1 Trên M 2 ( ) , D    là ước chung 1 1 Suy ra tồn tại B là ma trận nghịch đảo của A sao cho I n  AB . Do đó A vừa là ước bên phải, vừa là ước bên trái của I n . () Giả sử A là ước bên phải, trái của I n . Suy ra tồn tại ma trận B sao cho I n  BA . 2 2 3 3 và B    . 3 3 1 1  bên phải của A   Khi đó: det B.det A  det I n  1 . Suy ra A khả nghịch. Chứng minh tương tự cho A là ước bên trái của In. ii) (Mục 368, chương 19, [4]) A là ước (bên phải và bên trái ) của A. Chứng minh: Hiển nhiên, bởi vì tồn tại ma trận đơn vị I n để A  I n A  AI n . Vì tồn tại các ma trận M   1 2 , 2 1  2 0 N   để A=MD và B=ND. 0 1 3.1.3 UCLN của các ma trận vuông Định nghĩa: Trên Mn(R), cho D là một ước chung bên phải (trái) của các ma trận A1,A2,…,An. iii) Nếu A là ước bên phải của B và B là ước bên phải của C thìA là ước bên phải 69 TDMU, số 2 (27) – 2016 Ước chung lớn nhất của các ma trận vuông Nếu mọi ước chung bên phải (trái) của A1,A2,…,An đều là ước bên phải (trái) của D thìD được gọi là ước chung lớn nhất bên phải (trái) của các ma trận đó. Sau đây, ta chỉ xét ước chung lớn nhất Ví dụ:  4 3 1 2 Trên M 2 ( ) , cho A   , B   2 1 .    3 4  bên phải của các ma trận và ta viết tắt ước chung lớn nhất của A1,A2,…,An là UCLN  A1, A2 ,..., An  . 1 2  Khi đó, D    là UCLN(A,B). 0 1  4 3  4 5 1 2  và   .   2 1  2 3 0 1 1 2 1 0  1 2  Thật vậy, ta có:   .  3 4 3 2 0 1 nên D là ước chung bên phải của A và B. 1 2  1 0  1 2 0 0  4 3 Hơn nữa, ta có:      . 0 1  2 2 3 4 1 0  2 1 1 0  0 0  hay D=XA+YB với X   và Y     .  2 2 1 0  Do đó, nếu D1 là ước chung bên phải của A và B, tức là A  A1.D1 ; B  B1.D1 thì D  ( XA1 ) D1  (YB1 ) D1  ( XA1  YB1 ) D1 , tức là D1 là ước bên phải của D. Nhận xét: 1) Nếu D và D ' là UCLN  A1, A2 ,..., An  thìD và D ' sai khác nhau một ma trận khả nghịch, nghĩa là tồn tại U, V  M n ( R) khả nghịch sao cho D  UD ' và D '  VD . Chứng minh: VìD, D ' là UCLN  A1, A2 ,..., An  nên D là ước bên phải của D ' , D ' là ước bên phải của D. Do đó tồn tại U, V  M n ( R) để D  UD ' và D '  VD . Khi đó D  UD '  UVD . Suy ra det D  det U .det V .det D . VìR là miền nguyên nên det U .det V  1 . Suy ra U, V khả nghịch. 2) Theo nhận xét 1, ta có thể kết luận UCLN  A1, A2 ,..., An  là không duy nhất. 3.2 Sự tồn tại và phƣơng pháp tìm UCLN của các ma trận vuông 3.2.1 Sự tồn tại UCLN của các ma trận vuông Định lí 1: Giả sử R là miền chính. Khi đó, luôn tồn tại UCLN bên phải (trái) của các ma trận vuông thuộc S  M n ( R). Chứng minh: Giả sử A1, A2, …, An là các ma trận tùy ý thuộc Mn(R), ta sẽ chứng minh luôn tồn tại UCLN(A1, A2, …, An). − Xét M  SA1  SA2  ...  SAn  D1 A1  D2 A2  ...  Dn An | D1, D2 ,....Dn  S . − Ta thấy M là iđêan trái của S. − Theo bổ đề 2 (mục 2.2), vìR là miền chính nên mọi iđêan trái của S đều là iđêan trái chính. Suy ra tồn tại D  S sao cho: M  SD  K .D | K  S . − Ta chứng minh D là UCLN  A1, A2 ,..., An  . Hệ quả: Trên M n ( R) , nếu D là UCLN  A1, A2 ,..., An  thì tồn tại các ma trận 70 TDMU, số 2 (27) – 2016 Nguyễn Thị Khánh Hòa, Nguyễn Thị Kiều Trinh U1,U 2 ,...,U n  M n ( R) sao cho D  U1 A1  U 2 A2  ...  U n An . Đị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 M n  R  .  A Đặt C    là ma trận cấp 2n  n . Nếu tồn tại ma trận khả nghịch V sao cho B 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  . P Đặt n cột đầu của V 1 là   thì A  PD ; B  QD. Q  iii) Đặt n dòng đầu của V là  X Y  thì XA  YB  D. Chứng minh: X Y   P  D Giả sử V   ; V 1   ; H   trong đó X , Y , P, Q, D là các       2 n2 n Q  2 n2 n  O  2nn ii) ma trận vuông cấp n . − Theo giả thiết VC  H mà V khả nghịch nên C  V 1H .  A  P   D  Do đó C     V 1H      . Điều này cho ta A  PD và B  QD. B Q   O  Có nghĩa D là ước chung bên phải của A và B.  X Y   A  D  − Cũng từ VC  H ta suy ra         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 P, Q  M n  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 đó Ek ...E1.C  H . Đặt V  Ek ...E1 . Ta sẽ chứng minh V khả nghịch. Nếu Ei 1  i  k  là ma trận sơ cấp có được do đổi dòng thì det Ei   det I m  1 . Nếu Ei 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 Ei  det I m  1 . Do đó det V  1 . 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: 71 TDMU, số 2 (27) – 2016 Ước chung lớn nhất của các ma trận vuông Thuật toán tìm UCLN của hai ma trận vuông A, B trên vành M n  Với A, B  M n    A  .  B  2nn  . Đặt C   Đư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 để ckj  0 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ử cij  i  k  bằng cách cộng vào dòng i một bội qi của dòng j . Trong đó : cij  qi .c jj  ri ; 0  ri  c jj , qi , ri  . 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  . 1 2  4 3 Ví dụ: Tìm UCLN của hai ma trận vuông A và B ,biết A   và B    . 3 4   2 1 1 2  3 4  . Ta tiến hành đưa ma trận C về dạng bậc thang. Đặt C   4 3   2 1 Bước 1: Ta có c11  1  0 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ử c11 của C. − Để khử c21  3 , ta cộng vào dòng 2 một bội q1  3 dòng 1. Ta được: 1 2  1 2   0 2  0 2    . C1  . Khử phần tử c31  4 và c41  2 thu được ma trận: C2   4 3  0 5     2 1  0 3 Bước 3: Lặp lại bước 1 và bước 2 cho cột 2 của ma trận C2 . Ta có c22  2  0 là phần tử có giá trị tuyệt đối nhỏ nhất trên cột 2 của ma trận C2 . − Để khử c32  5 , ta cộng vào dòng 3 một bội q4  3 dòng 2. Ta được: 1 2   0 2  . C3   0 1    0 3 Vì c32  1  0 là phần tử có giá trị tuyệt đối nhỏ nhất trên cột 2 của ma trận C3 , nên ta thực hiện phép đổi chỗ d2  d3 của C3 . − Ta tiếp tục khử phần tử c32  2 và c42  3 tương tự như trên. 72