Vĩnh thức

Nghiên cứu trình bày Vĩnh Thức, định thức, và định thức Pfaff là các đa thức đa biến trên các ma trận. Chúng có liên hệ mật thiết với nhau, và có ứng dụng trong Vật Lý thống kê, Kinh tế học, toán Tổ hợp, độ phức tạp tính toán, lý thuyết đồ thị, và thuật toán. Bài viết này điểm qua lịch sử và chứng minh của một số kết quả liên kết các đối tượng Tổ hợp kỳ thú này. Mời các bạn tham khảo!
Nội dung trích xuất từ tài liệu:
Vĩnh thức VĨNH THỨC NGÔ QUANG HƯNG (Đại học Buffalo, Mỹ) Tóm tắt nội dung Vĩnh Thức, định thức, và định thức Pfaff là các đa thức đa biến trên các ma trận. Chúng có liên hệ mật thiết với nhau, và có ứng dụng trong Vật Lý thống kê, Kinh tế học, toán Tổ hợp, độ phức tạp tính toán, lý thuyết đồ thị, và thuật toán. Bài viết này điểm qua lịch sử và chứng minh của một số kết quả liên kết các đối tượng Tổ hợp kỳ thú này.1. Vĩnh ThứcGọi A = (aij ) là một ma trận vuông n × n. Vĩnh Thức1 của A đượcđịnh nghĩa như sau: XY n Perm(A) = aiπ(i) , π∈Sn i=1trong đó Sn là tập tất cả các hoán vị của [n]. Như vậy, công thứctính vĩnh thức rất giống công thức Leibniz để tính định thứccủa A, chỉ khác ở điểm duy nhất là ta không nhân sgn(π) vàomỗi số hạng trong tổng trên.Hàm vĩnh thức có nhiều ứng dụng. Ví dụ, một vấn đề cơ bảntrong toán Tổ hợp là tìm số cách lát một hình chữ nhật với cácquân đô-mi-nô kích thước 2 × 1. Mỗi cách lát hoàn hảo tươngứng với một bắt cặp hoàn hảo2 của đồ thị lưới tương ứng. (Xemhình 3.1.) Làm thế nào để ta đếm tổng số cách bắt cặp hoànhảo của đồ thị lưới? Dễ thấy đồ thị lưới là đồ thị hai phần3 . Giả 1 Permanent. Sau thảo luận với các anh Phạm Hi Đức và Phùng Hồ Hải,tôi quyết định chọn từ vĩnh thức để dịch permanent. 2 Perfect matching. Còn được gọi là cặp ghép hoàn hảo (ban Biên tập). 3 Bipartite graph. 29 Tạp chí Epsilon, Số 03, 06/2015.sử đồ thị hai phần này có n đỉnh bên trái và n đỉnh bên phải.(Nếu một bên có số đỉnh ít hơn thì ta thêm vào cách đỉnh đơn lẻcho hai bên bằng nhau.) Sau đó, ta xây dựng ma trận A = (aij )trong đó aij = 1 nếu đỉnh i bên trái có cạnh đến đỉnh j bên phải;và aij = 0 nếu không có cạnh ij trong đồ thị. Khi đó, Perm(A)bằng đúng tổng số các cách bắt cặp hoàn hảo của đồ thị – vànó cũng là số cách lát đô-mi-nô mà ta cần tìm.Hình 3.1: Lợp hình chữ nhật 8 × 5 bằng các hình đô-mi-nô 2 × 1,và bắt cặp hoàn hảo tương ứng của đồ thị lưới.Vấn đề tìm số cách lát đô-mi-nô không phải là bài toán giải tríhoặc Tổ hợp thông thường. Đây là một vấn đề cơ bản trong Vậtlý thống kê và Hoá học trạng thái rắn [17, 16, 18]. Chúng ta sẽquay lại với mô hình dimer trong Vật lý dưới đây.Vĩnh Thức khởi nguyên năm 1812, do các nhà Toán học ngườiPháp Jacques Philippe Marie Binet và Augustin-Louis Cauchyđịnh nghĩa. Trong thế kỷ 19 đã có khoảng chục nhà toán họcnghiên cứu các đẳng thức và bất đẳng thức liên quan đến vĩnhthức, bao gồm Arthur Cayley và Thomas Muir của Vương QuốcAnh. Cái tên “permanent” có lẽ bắt nguồn từ Cauchy (1812),nhưng người đầu tiên thật sự dùng và làm “chết tên” nó làMuir (1882). Tuy nhiên, các nghiên cứu về vĩnh thức chỉ thậtsự “nóng” lên từ những năm 1960 do các đóng góp của toánhọc Hà Lan.1.1. Giả định van der WaerdenNăm 1926, nhà Toán học người Hà Lan Bartel Leendert van derWaerden đặt một câu hỏi là vĩnh thức nhỏ nhất của một ma 30Tạp chí Epsilon, Số 03, 06/2015.trận ngẫu nhiên kép4 là bao nhiêu [35]. Trực quan cho thấy matrận Jn = n1 J có lẽ là ma trận có vĩnh thức cực tiểu. (Ma trận Jlà ma trận vuông n × n gồm toàn các số 1.) Từ đó, bất đẳng thứcsau đây được gọi là giả định van der Waerden5 : n! Perm(A) ≥ (3.1) nn với mọi ma trận ngẫu nhiên kép A kích thước n × n.Van Lint [37] kể rằng, năm 1969 có một lần van der Waerdenđến dự một buổi hội thảo về toán Tổ hợp. Ông vốn là dân Đạisố, hầu như ít làm toán tổ hợp. Một diễn giả trẻ lên báo báomột vấn đề liên quan đến giả định van der Waerden. Van derWaerden giơ tay lên hỏi “giả định đó nói gì vậy?” Cuối buổi diễngiả xuống ... xem bảng tên người đặt câu hỏi.Van Lint, vốn là một nhà toán học cừ khôi cũng người HàLan, đã truy vấn van der Waerden xem giả định này có xuấtphát điểm từ đâu. Van der Waerden nhớ lại rằng hồi 1926,ông nói chuyện với O. Schreier, và Schreier cho ông biết G. A.Miller có chứng minh rằng có một hệ đại diện chung6 cho cáclớp kề7 trái và các lớp kề phải của một nhóm con H của mộtnhóm hữu hạn G.Van der Waerden quan sát rằng bộ các lớp kề trái là một phânhoạch (R1 , . . . , Rn ) của G, trong đó R1 ∪ · · · ∪ Rn = G, và |Ri | =|G|/n với mọi i ∈ [n]. Bộ các lớp kề phải là một phân hoạch(C1 , . . . , Cn ) của G, cũng thoả |Cj | = |G|/n với mọi j ∈ [n]. Hệ đạidiện chung cho hai bộ phân hoạch này là một bộ các phần tửS = {g1 , . . . , gn } ⊆ G sao cho |Ri ∩S| = |Cj ∩S| = 1, với mọi i, j ∈ [n].Bây giờ nếu ta xây dựng ma trận A = (aij ) trong đó aij = |Ri ∩ Cj |thì sự tồn tại của hệ đại diện chung tương đương với phát biểuPerm(A) > 0. Do tổng của các hàng và các cột của A đều bằng |Ri ∩Cj ||G|/n, ta “thường hoá”8 A bằng cách đặt aij = |G|/n . Khi đó Alà ma trận ngẫu nhiên kép. Ta có thể chứng minh Perm(A) > 0dễ dàng bằng định lý K¨onig-Hall. Nhưng một câu hỏi khác cũng 4 Doubly stochastic matrix. Một ma trận vuông gọi là “ngẫu nhiên kép”nếu nó không âm, và tổng mỗi hàng và mỗi cột đều bằng 1. 5 Van der Waerden conjecture 6 Common system of representatives. 7 Coset. 8 Normalize. 31 Tạp chí Epsilon, Số 03, 06/2015.tự nhiên không kém là giá trị nhỏ nhất Perm(A) có thể đạt tớilà bao nhiêu. Đây chính là nguồn gốc của giả định van derWaerden.Trong quyển “Permanents” (1978 [23]), Henryk Minc ghi rằnghồi ông nộp một số bài báo về vĩnh thức giữa thế kỷ 20 thì cóm ...