🔙 Quay lại trang tải sách pdf ebook Tạp Chí Epsilon Số 3 Ebooks Nhóm Zalo x x Vĩnh thức Ngô Quang Hưng Ma trận ngẫu nhiên Vũ Hà Văn Thư của Kapitsa về khoa học Đàm Thanh Sơn (dịch) Cubic Rubik Trần Nam Dũng (dịch và tổng hợp) 90 x Tự học là tốt nhưng có thầy tốt hơn Nguyễn Tiến Dũng Định lí bướm kép đối với tứ giác. Nguyễn Ngọc Giang Trịnh Huy Vũ 90 90 x VÀ CÁC CHUYÊN MỤC KHÁC 45 HENRYK MINC ghi rằng hồi ông nộp một số bài báo về vĩnh thức giữa thế kỷ 20 thì có một bình duyệt viên nói rằng “chế ra cái tên gì lố bịch thế”? t h ứ c - N g ô 135 1/3x h Vĩ n - g n ư H Q u a n g No Nếu bạn muốn con bạn thông minh, hãy đọc cho chúng nghe truyện cổ tích. Nếu bạn muốn con bạn thông minh hơn, hãy đọc cho chúng nhiều truyện cổ tích hơn. Albert Einstein 13 Jun 2015 ngày 13 tháng 06 năm 2015 Tạp chí online của cộng đồng những người yêu Toán Số 3Chủ biên: TRẦN NAM DŨNG Biên tập viên: VÕ QUỐC BÁ CẨN TRẦN QUANG HÙNG LÊ PHÚC LỮ NGUYỄN TẤT THU ĐẶNG NGUYỄN ĐỨC TIẾN LỜI NGỎ Ban biên tập Epsilon Epsilon số 2 ra mắt bạn đọc đúng hạn vào ngày 13/4 đã làm cho Epsilon không thuộc vào đội ngũ các Tạp chí 1 số. Tức là những tạp chí dồn công sức ra được số đầu rất hay, rất tốt nhưng cũng là duy nhất. Có số 2 tức là sẽ hy vọng có số 3. Và bạn đọc đang đọc số 3 của tạp chí Epsilon – tạp chí online của những người yêu toán. Qua 2 số đầu tiên, chúng ta vui mừng vì người đọc Epsilon đang nhiều lên, người biết đến và ủng hộ Epsilon nhiều lên, người viết bài cho Epsilon cũng nhiều lên. Trong buổi uống bia trưa 10/6 tại quán Hải Xồm gần Viện Toán học, chúng tôi cảm thấy vui vui khi mọi người nhắc đến Epsilon. “Hôm trước gặp hội anh Nguyễn Thành Nam, có nói chú vừa ra tờ Epsilon. Trước đó Ngô Bảo Châu cũng có nói anh rảnh thì viết bài cho Epsilon” – GS Phạm Hữu Tiệp, người vừa trình bày chuyên đề ở Viện toán nói với tôi. “Anh rảnh viết cho em luôn bài Random walk đi anh”, “Chưa biết anh có viết được bài đó không, nhưng chắc sau trận bia này anh với chú đi ramdon walk về viện Toán”. Thấy mọi người bàn tán rôm rả về Epsilon, PGS trẻ Phạm Hoàng Hiệp, người vừa được giải thưởng Tạ Quang Bửu, còn nói đùa “Có khi anh Dũng phải đổi tên tạp chí thành 1/epsilon cũng nên”. Nói vui là thế, chứ công việc của Epsilon thực sự là công việc đi gom những li ti để tạo nên một sản phẩm nhỏ mà ý nghĩa, để người đọc luôn có thể tìm được một điều gì đó cho mình qua một số tạp chí. Với suy nghĩ như vậy, chúng tôi mong muốn, trân trọng và ghi nhận mọi sự đóng góp đến từ các tác giả. Epsilon hy vọng sự có mặt của mình sẽ làm cho mọi người chịu khó viết bài hơn. Các GS thì cố gắng nghiên cứu cách viết đơn giản, dễ hiểu để có thể đến với số đông. Các bạn học sinh, sinh viên cũng cố gắng viết bài có chất lượng hơn, có định hướng hơn, bước đầu làm quen 3 Tạp chí Epsilon, Số 03, 06/2015. với phong cách nghiên cứu và trình bày bài báo khoa học. Các thầy giáo cũng có động lực hơn trong việc tổng kết các chuyên đề một cách hệ thống hơn, thay vì các bài viết nhỏ với các ý tưởng đơn lẻ. Epsilon số 3 lần này quy tụ 14 bài viết chính với các chủ đề phong phú: Các bài viết của Vũ Hà Văn “Ma trận ngẫu nhiên” và Ngô Quang Hưng “Vĩnh thức và định thức Pfaff” sẽ giới thiệu với bạn đọc những vấn đề nóng hổi của toán học hiện đại. Mục lịch sử toán học sẽ dành các trang viết của mình cho các nhà Vật lý qua bài “Những triết lý sống của Einstein” do BBT sưu tầm và “Thư của Kapitsa về khoa học” do GS Đàm Thanh Sơn dịch và giới thiệu. Mục Giảng dạy toán học lần này có bài của GS Nguyễn Tiến Dũng “Tự học là tốt nhưng có thầy tốt hơn”. Nguyễn Quốc Khánh tiếp tục chuyên mục điểm sách đầy hấp dẫn của mình qua bài “Đêm trước của những bản thảo sắp in”. Đặng Nguyễn Đức Tiến thì tạm gác chủ đề về những chiếc mũ để giới thiệu về một trong những nhà truyền bá toán học nổi tiếng nhất thế giới – Martin Gardner. Chuyên mục Các vấn đề cổ điển và hiện đại sẽ giới thiệu chuỗi bài toán đếm tam giác (dành cho học sinh tiểu học và THCS) và chuỗi bài toán về khối vuông Rubik (từ trò chơi đến lý thuyết nhóm). Mảng toán sơ cấp, như thường lệ vẫn rất rôm rả với bài viết rất công phu “Cực trị tập hợp” của thầy Trần Minh Hiền, một tiểu phẩm xinh xinh của thầy Nguyễn Duy Liên xung quanh một bài toán thi IMO 2001. Các học sinh chuyên toán đang chuẩn bị cho các kỳ thi HSG của năm học sau chắc chắn sẽ tìm được nhiều điều bổ ích qua bài bình luận về 4 bài còn lại trong kỳ thi chọn đội tuyển Việt Nam 2015 của thầy Trần Nam Dũng. Đặc biệt mảng hình học lần này sẽ giới thiệu một chùm hoa đẹp gồm ba bài viết do các thành viên của nhóm Bài toán hay – Lời giải đẹp – Đam mê toán học (Vũ Thanh Tùng, Nguyễn Chương Chí, Nguyễn Ngọc Giang) phối hợp cùng biên tập viên Trần Quang Hùng và các học trò (Nguyễn Bảo Ngọc, Trịnh Huy Vũ). Những bài toán và định lý xinh xắn, những chứng minh như ảo thuật chắc chắc sẽ làm hài lòng những độc giả yêu thích hình học, còn những người chưa thích sẽ bắt đầu... thích. Làm cho những người đã thích toán thêm thích toán. Làm cho những người chưa thích toán bắt đầu thấy thích toán. Nếu hoàn 4 Tạp chí Epsilon, Số 03, 06/2015. thành được 10% nhiệm vụ đó thì những người làm Epsilon quá đỗi vui mừng. Và sẽ lại có năng lượng để bước tiếp. Đi nhiều người, bạn sẽ đi rất xa ... 5 Tạp chí Epsilon, Số 03, 06/2015. 6 MỤC LỤC 1 Lời ngỏ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Ma trận ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Vũ Hà Văn 3 Vĩnh thức . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 Ngô Quang Hưng 4 Tự học là tốt nhưng có thầy tốt hơn . . . . . . . . . . . . . . . . . . 61 Nguyễn Tiến Dũng 5 Thư của Kapitsa về khoa học . . . . . . . . . . . . . . . . . . . . . . . . . 71 Đàm Thanh Sơn 6 Những triết lý sống của Einstein . . . . . . . . . . . . . . . . . . . . . 81 Ban biên tập Epsilon 7 Lời giải và bình luận đề thi TST 2015 . . . . . . . . . . . . . . . . 89 Trần Nam Dũng 8 Martin Gardner - Người làm vườn của toán học . . . 105 Đặng Nguyễn Đức Tiến 9 Cực trị tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 Trần Minh Hiền 10 Một bài toán số học hay với nhiều cách giải . . . . . . . . 175 Nguyễn Duy Liên 7 Tạp chí Epsilon, Số 03, 06/2015. 11 Định lý Carnot và ứng dụng . . . . . . . . . . . . . . . . . . . . . . . . . 181 Vũ Thanh Tùng, Nguyễn Chương Chí 12 Về một bài toán hình học từ diễn đàn AoPS . . . . . . . . 193 Trần Quang Hùng, Nguyễn Bảo Ngọc 13 Định lý bướm kép đối với tứ giác . . . . . . . . . . . . . . . . . . . . 205 Nguyễn Ngọc Giang (TP. Hồ Chí Minh) Trịnh Huy Vũ (THPT Chuyên KHTN Hà Nội) 14 Đêm trước những bản thảo sắp in . . . . . . . . . . . . . . . . . . 211 Nguyễn Quốc Khánh 15 Các vấn đề cổ điển và hiện đại . . . . . . . . . . . . . . . . . . . . . . 223 Trần Nam Dũng 8 MA TRẬN NGẪU NHIÊN VŨ HÀ VĂN (Đại học Yale, Mỹ) Lời giới thiệu Lý thuyết ma trận ngẫu nhiên có mục tiêu chính là đưa ra những hiểu biết sâu sắc về các tính chất đa dạng của các ma trận mà các thành phần của chúng được chọn ngẫu nhiên từ các phân phối xác suất khác nhau. Từ khi ra đời đến nay, lý thuyết ma trận ngẫu nhiên đã có những phát triển mạnh mẽ, thúc đẩy bởi những ứng dụng trong Thống kê và Giải tích số, Khoa học máy tính, Điều khiển tối ưu, và đặc biệt là các ứng dụng trong Vật lý hạt nhân. Ở Việt Nam, lý thuyết ma trận ngẫu nhiên là một khái niệm tương đối mới. Năm 2009, người viết lời giới thiệu này, khi đang dạy cho đội tuyển Olymic Toán của Việt Nam chuẩn bị cho kỳ thi toán quốc tế IMO 2009, đã dẫn toàn bộ đội tuyển đến dự bài nói chuyện của GS Vũ Hà Văn về Ma trận ngẫu nhiên. Thú thực là mặc dù thầy và trò đều chỉ hiểu lõm bõm về những điều GS Văn nói, nhưng tất cả đều rất ấn tượng khi hàng loạt các giả thuyết đã được Vũ Hà Văn cùng Terence Tao chứng minh được với tốc độ chóng mặt. Trong Epsilon số 3 này, được sự đồng ý của tác giả, chúng tôi trích giới thiệu nội dung 3 chương đầu trong bài báo cáo của GS Vũ Hà Văn tại Đại hội Toán học Thế giới 2014 (ICM 2014). Để giúp độc giả có thể nắm bắt được nội dung chính, chúng tôi cố gắng chú giải chi tiết nhất có thể, đồng thời đăng nguyên bản tiếng Anh để đối chiếu. Vì đây là lĩnh vực mới, ít có tài liệu tiếng Việt nên trong dịch thuật có thể có những chỗ chưa chuẩn, rất mong nhận được ý kiến đóng góp của bạn đọc để các phần sau được dịch tốt hơn. Ban Biên tập. 9 Tạp chí Epsilon, Số 03, 06/2015. Tóm tắt nội dung Trong bài viết này, chúng ta sẽ trao đổi về một số bài toán trong lý thuyết ma trận ngẫu nhiên có bản chất tổ hợp. 1. Mở đầu Lý thuyết ma trận ngẫu nhiên là một mảnh đất màu mỡ trong toán học. Bên cạnh những vấn đề nội tại thú vị, ma trận ngẫu nhiên đóng một vai trò quan trọng trong nhiều lĩnh vực như Thống kê, Vật lý Toán, Tổ hợp, Khoa học Máy tính... Trong khảo sát này, chúng tôi tập trung vào các bài toán có bản chất tổ hợp. Các bài toán này đặc biệt thú vị khi các ma trận được lấy mẫu từ một phân phối rời rạc. Các mô hình thông dụng nhất là: • (Bernoulli) Mn: ma trận ngẫu nhiên bậc n mà các thành phần là các biến ngẫu nhiên độc lập đồng nhất theo phân phối Bernoulli (nhận các giá trị ±1 với xác suất 1/2). Ma trận này đôi khi còn được gọi là ma trận dấu ngẫu nhiên1. Tổng cộng có tất cả N = 2n2 ma trận với tất cả các thành phần là ±1, mỗi ma trận có xác suất 1/N. • (Bernoulli đối xứng2) Msym n: ma trận đối xứng ngẫu nhiên bậc n mà các thành phần trên và trong đường chéo là các biến ngẫu nhiên độc lập đồng nhất theo phân phối Bernoulli. Số ma trận đối xứng với thành phần ±1 là M = 2n(n+1)/2 và mỗi ma trận có xác suất 1/M. • Ma trận kề của một đồ thị ngẫu nhiên. Với mỗi đồ thị ta có một ma trận kề định nghĩa như sau: Giả sử đồ thị G có n đỉnh {1, 2.., n}. Ma trận kề của G là một ma trận đối xứng và tại vị trí ij ta viết 1 nếu ij là cạnh của G và 0 trong trường hợp ngược lại. Về các mô hình đồ thị ngẫu nhiên. Trong bài viết này, chúng tôi xét trên hai mô hình: Erdos-Rényi và đồ thị đều ngẫu nhiên. ¨ Chi tiết hơn về các mô hình này, xem [6, 35]. 1Random sign matrix. Toàn bộ chú thích trong bài này đều của Ban Biên tập. 2Symmetric Bernoulli. 10 Tạp chí Epsilon, Số 03, 06/2015. • (Erdos-Rényi) Ta ký hiệu ¨ G(n, p) là đồ thị ngẫu nhiên trên n đỉnh, được sinh ra bằng cách vẽ cạnh nối hai điểm bất kỳ với xác suất p một cách độc lập. • (Đồ thị đều ngẫu nhiên3) Đồ thị đều ngẫu nhiên có n đỉnh với bậc d thu được bằng cách chọn ngẫu nhiên với xác suất đều trên tập hợp tất cả các đơn đồ thị đều bậc d4trên tập các đỉnh {1, 2, . . . , n}. Ta ký hiệu đồ thị này là Gn,d. Có một chú ý quan trọng là các cạnh của Gn,d không độc lập5. Vì vậy, mô hình này thường khó nghiên cứu hơn mô hình G(n, p). Ta ký hiệu A(n, p) là ma trận kề của đồ thị ngẫu nhiên Erdos- ¨ Rényi G(n, p), và An,d là ma trận kề của Gn,d tương ứng. Về ký hiệu: Trong suốt bài này, n luôn được giả sử là rất lớn. Các ký hiệu tiệm cận6 như o, O, Θ đều được hiểu khi n tiến tới vô cùng. Ta viết A B nếu A = o(B). c ký hiệu cho hằng số chung7. Tất cả các logarit đều là logarit tự nhiên nếu không nói khác đi. 2. Xác suất suy biến Bài toán tổ hợp nổi tiếng nhất về ma trận ngẫu nhiên có lẽ là bài toán suy biến8. Gọi pn là xác suất ma trận Mn suy biến (một ma trận vuông suy biến nếu định thức bằng 0). Hiển nhiên là: pn ≥ 2−n vì vế phải là xác suất để hai dòng đầu của ma trận bằng nhau9. Vì ta có thể chọn hai dòng (cột) bất kỳ (thay vì chỉ chọn 2 dòng đầu) và có thể thay dấu bằng bởi dấu bằng khi cùng nhân với 3Random regular graph. 4Đồ thị đều bậc d (d-regular graph) là đồ thị mà mọi đỉnh đều có bậc bằng d. Ví dụ đồ thị đều bậc 0 có mọi đỉnh đều là đỉnh cô lập, đồ thị đầy đủ Kn là đồ thị đều bậc n − 1. 5Nghĩa là xác suất tồn tại của các cạnh của Gn,d không độc lập với nhau, trong khi xác suất ở các cạnh của G(n, p) là độc lập. 6Asymptotic notation. 7Universal constant. Đôi khi vẫn được dịch là hằng số phổ dụng hay hằng số độc lập. 8Singularity problem. 9Ma trận có 2 dòng bất kỳ bằng nhau có định thức bằng 0. 11 Tạp chí Epsilon, Số 03, 06/2015. ±110, ta có được cận dưới tốt hơn một chút: pn ≥ (4 − o(1)) n 2 2−n = (12+ o(1))n(2.1) Một giả thuyết được đặt ra là: Giả thuyết 2.1. [Giả thuyết về suy biến] pn = ( 12 + o(1))n. Giả thuyết 2.1 vẫn là bài toán mở, nhưng ta có thể phát biểu những giả thuyết chính xác hơn (xem [4]), dựa vào những "niềm tin" sau: Hiện tượng I.11 Lý do chủ yếu để một ma trận ngẫu nhiên suy biến là sự phụ thuộc của một số ít hàng/cột. Thực sự thì ngay cả việc chứng minh pn = o(1) đã là không đơn giản. Kết quả này lần đầu tiên được chứng minh bởi Komlós [38] vào năm 1967 (trong phần 3 của bài này, chúng tôi sẽ đưa ra một chứng minh ngắn gọn cho định lý Komlós). Sau đó Komlós (xem [6]) tìm được chứng minh mới cho cận trên: pn = O(n−1/2). Trong một bài báo quan trọng, Kahn, Komlós và Szemerédi [37] lần đầu tiên đã đưa ra được cận trên theo hàm mũ: Định lý 2.2. pn ≤ .999n. Lập luận của Kahn, Komlós và Szemerédi đã được đơn giản hóa bởi Tao và Vũ trong bài báo [66] năm 2004, dẫn đến một cận trên tốt hơn 1 chút O(.958n). Sau đó ít lâu, các tác giả này [67] kết hợp cách tiếp cận trong [37] với ý tưởng của các định lý đảo (xem [71, chương 7] hay [53]) đã đạt kết quả rất quan trọng: Định lý 2.3. pn ≤ (3/4 + o(1))n. Không dừng lại ở đó, Bourgain, Vũ và Wood ở bài báo [9] đã dùng thêm một ý tưởng về không gian có chiều phân số để tiếp tục cải thiện cận trên: Định lý 2.4. pn ≤ ( √12+ o(1))n. 10Nghĩa là ta có thể chọn 2 dòng (hoặc cột) bất kỳ có cùng trị tuyệt đối thay vì bằng nhau. 11Ở đây tác giả dùng "Phenomenon" nên chúng tôi đối dịch là "Hiện tượng". Đây là một cách dùng lạ, vì nó mang tính trực giác nhiều cho vấn đề đang xét. 12 Tạp chí Epsilon, Số 03, 06/2015. Hai phương pháp trên [67, 9] cho phép chúng ta thu được các cận trên của pn trực tiếp từ các ước tính lượng giác đơn giản. Ví dụ cận trên 3/4 có được từ: | cos x| ≤ 34+14cos 2x, trong khi cận 1/√2 thu được từ | cos x|2 =12+12cos 2x. Định lý 2.2 ở [9] đã đưa ra một mối liên hệ hình thức giữa các ước lượng suy biến và các ước lượng lượng giác. Các liên hệ này mặc dù chưa thể dùng để giải bài toán suy biến tổng quát, nhưng có thể sử dụng để ước tính khá chính xác các cận trên trong một số trường hợp, chẳng hạn như xác suất suy biến của ma trận ngẫu nhiên với các thành phần (0, ±1). Để kết thúc mục này, chúng tôi đề cập đến một công cụ rất hữu ích: định lý Littlewood-Offord-Erdos. Gọi ¨ v = {v1, . . . , vn} là tập hợp gồm n số thực khác 0 và ξ1, . . . , ξn là các biến ngẫu nhiên Bernoulli độc lập phân bố đồng nhất. Định nghĩa S := Pni=1 ξivi và pv(a) = P(S = a) và pv = supa∈Z pv(a). Vào những năm 1940, Littlewood và Offord đã đưa ra cách ước tính pv (ở [45]) như thành tố kỹ thuật chính trong các nghiên cứu của họ về nghiệm thực của đa thức ngẫu nhiên. Erdos, ¨ bằng cách cải thiện kết quả của Littlewood và Offord, đã chứng minh định lý sau mà chúng ta gọi là bất đẳng thức quả bóng nhỏ Erdos-Littlewood-Offord (xem [ ¨ 53] để rõ hơn về cái tên này). Định lý 2.5. (Bất đẳng thức quả bóng nhỏ) Giả sử v1, . . . , vn là các số thực khác 0 và ξ1, . . . , ξn là các biến ngẫu nhiên Bernoulli độc lập phân bố đồng nhất. Khi đó: n bn/2c pv ≤ 2n= O(n−1/2). Định lý 2.5 là một kết quả kinh điển trong tổ hợp và có rất nhiều những mở rộng và hệ quả sâu xa (xem [7, 34, 53], [71, Chương 7] và các tài liệu tham khảo ở đó). 13 Tạp chí Epsilon, Số 03, 06/2015. Để độc giả có thể cảm nhận được làm sao bất đẳng thức quả bóng nhỏ có thể có ích trong việc đánh giá pn, ta xếp các dòng của Mn từng dòng một từ trên xuống dưới. Giả sử rằng n − 1 dòng đầu là độc lập và tạo thành một siêu phẳng với véc-tơ pháp tuyến v = (v1, . . . , vn). Khi đó, xác suất để Mn suy biến là: P(X · v = 0) = P(ξ1v1 + · · · + ξnvn = 0), trong đó X = (ξ1, . . . , ξn) là dòng cuối cùng. Trong phần 3, độc giả sẽ thấy một ứng dụng của định lý 2.5 dẫn đến kết quả gốc của Komlós: pn = o(1). Để thu được các đánh giá mạnh hơn các kết quả ở định lý 2.3 và 2.4, ta cần thiết lập các định lý Littlewood-Offord đảo, dựa trên nguyên lý tổng quát sau: Hiện tượng II. Nếu P(X · v = 0) là tương đối lớn thì các hệ số v1, . . . , vn có một cấu trúc cộng tính mạnh. Các định lý này được thúc đẩy bởi các định lý đảo kiểu Freiman trong tổ hợp cộng tính12 mà việc thảo luận nằm ngoài phạm vi của khảo sát này. Độc giả quan tâm có thể xem chi tiết ở [53]. 3. Một chứng minh đơn giản của định lý Komlós pn = o(1) Ta hãy bắt đầu từ một tính chất đơn giản. Từ đây về sau véc-tơ Bernoulli được hiểu là véc-tơ với tọa độ ±1. Tính chất 3.1. Cho H là không gian con 1 ≤ d ≤ n chiều. Khi đó H chứa nhiều nhất 2d véc-tơ Bernoulli. Để thấy điều này, ta chú ý rằng trong không gian con d chiều, tồn tại một tập hợp d tọa độ xác định các tọa độ còn lại13. Tính chất này suy ra: pn ≤Xn−1 i=1 P(Xi+1 ∈ Hi) ≤Xn−1 i=1 2i−n ≤ 1 −22n. 12Additive Combinatorics. 13Trong không gian d chiều, có thể dùng d véc-tơ cơ sở để biểu diễn mọi véc-tơ trong không gian đó. 14 Tạp chí Epsilon, Số 03, 06/2015. Rất không hay là điều này đối nghịch với kết quả chúng ta muốn chứng minh, nhưng đừng vội nản chí, màn hay hãy còn ở phần sau! Để thu được cận trên o(1) mong muốn, ta cần chứng minh rằng tổng của một số hạng tử cuối, chẳng hạn log log n, không vượt quá (chẳng hạn) 1 log1/3 n. Để chứng minh điều này, ta sẽ sử dụng tính chất Hi được sinh bởi các véc-tơ ngẫu nhiên. Bổ để sau sẽ suy ra định lý Komlós thông qua định lý cận hợp14: Bổ đề 3.1. Cho H là không gian con sinh bởi d véc-tơ ngẫu nhiên, trong đó d ≥ n−log log n. Khi đó với xác suất ít nhất 1−1n, H chứa nhiều nhất 2n log1/3 nvéc-tơ Bernoulli. Ta nói rằng tập hợp S gồm d véc-tơ là k-phổ dụng nếu với bất kỳ tập k chỉ số khác nhau 1 ≤ i1, . . . , ik ≤ n và bất kỳ tập dấu 1, . . . , n ( i = ±1) nào, tồn tại một véc-tơ v thuộc S sao cho dấu của tọa độ thứ ij của v bằng j , với mọi 1 ≤ j ≤ k. Tính chất 3.2. Nếu d ≥ n/2 thì 1 −1nlà xác suất thấp nhất cho tập hợp gồm d véc-tơ ngẫu nhiên là k-phổ dụng với k := log n/10. Để chứng minh điều này, ta chú ý rằng xác suất thất bại, theo định lý cận hợp, sẽ không vượt quá n k (1 −12k)d ≤ nk(1 −12k)n/2 ≤ n−1. Nếu S là k-phổ dụng, thì một véc-tơ v khác 0 trong phần bù trực giao của không gian con sinh bởi S sẽ có nhiều hơn k véc tơ khác 0 (nếu không, sẽ có một véc-tơ trong S có tích trong15 14Union bound. Còn được gọi bất đẳng thức Boole, phát biểu rằng với mọi tập hữu hạn hoặc đếm được thì xác suất để ít nhất một sự kiện xảy ra nhỏ hơn tổng xác suất của tất cả các sự kiện, nghĩa là nếu E1, E2, . . . En, . . . là các sự kiện thì: P{∃i : Ei xảy ra} = P{[∞ i=1 Ei} ≤ X∞ i=1 P{Ei} Ở một số tài liệu union bound còn được gọi là định lý tổng xác suất. 15Inner product. 15 Tạp chí Epsilon, Số 03, 06/2015. dương với v). Nếu ta cố định véc-tơ v này và giả sử X là véc-tơ ngẫu nhiên Bernoulli thì theo định lý 2.5 P(X ∈ Span(S)) ≤ P(X · v = 0) = O(1k1/2) ≤1 log1/3 n, và bổ đề 3.1 cùng định lý được chứng minh. * * * Phần bài viết sẽ được tiếp tục giới thiệu ở các số Epsilon tiếp theo. Chúng tôi cũng đính kèm bản gốc tiếng Anh để bạn đọc tiện theo dõi ở phần sau. 16 (Van H. Vu)∗ Keywords. General mathematics, collection of articles. Abstract. In this survey, we discuss several problems in Random Matrix theory of combinatorial nature. 1. Introduction The theory of random matrices is a very rich topic in mathematics. Beside being interesting in its own right, random matrices play fundamental role in various areas such as statistics, mathematical physics, combinatorics, theoretical computer science, etc. In this survey, we focus on problems of combinatorial nature. These problems are most interesting when the matrix is sampled from a discrete distribution. The most popular models are: • (Bernoulli) Mn: random matrix of size n whose entries are i.i.d. Bernoulli random variables (taking values ±1 with probability 1/2). This is sometimes referred to as the random sign matrix. • (Symmetric Bernoulli) Msym n: random symmetric matrix of size n whose (upper triangular) entries are i.i.d. Bernoulli random variables. • Adjacency matrix of a random graph. This matrix is symmetric and at position ij we write 1 if ij is an edge and zero otherwise. • Laplacian of a random graph. Model of random graphs. We consider two models: Erd¨os-R´enyi and random reg ular graphs. For more information about these models, see [6, 35]. • (Erd¨os-R´enyi) We denote by G(n, p) a random graph on n vertices, generated by drawing an edge between any two vertices with probability p, indepen dently. ∗Yale University. 2 • (Random regular graph) A random regular graph on n vertices with degree d is obtained by sampling uniformly over the set of all simple d-regular graphs on the vertex set {1, . . . , n}. We denote this graph by Gn,d. It is important to notice that the edges of Gn,d are not independent. Because of this, this model is usually harder to study, compared to G(n, p). We denote by A(n, p) (L(n, p)) the adjacency (laplacian) matrix of the Erd¨os-R´enyi random graph G(n, p) and by An,d (Ln,d) the adjacency (laplacian) matrix of Gn,d, respectively. Notation. In the whole paper, we assume that n is large. The asymptotic notation such as o, O, Θ is used under the assumption that n → ∞. We write A B if A = o(B). c denotes a universal constant. All logarithms have natural base, if not specified otherwise. 2. The singular probability The most famous combinatorial problem concerning random matrices is perhaps the ”singularity” problem. Let pn be the probability that Mn is singular. Trivially, pn ≥ 2−n, as the RHS is the probability that the first two rows are equal. By choosing any two rows (columns) and also replacing equal by equal up to sign, one can have a slightly better lower bound pn ≥ (4 − o(1)) n 2 2−n = (12+ o(1))n. (1) It has been conjectured, for quite sometime, that Conjecture 2.1. [Singularity Conjecture] pn = ( 12 + o(1))n. Conjecture 2.1 is still open, but one can formulate even more precise conjectures (see [4]), based on the following belief Phenomenon I. The dominating reason for singularity is the dependency between a few rows/columns. It is already non-trivial to prove that pn = o(1). This was first done by Koml´os [38] in 1967 and in Section 3, we will give a short proof of this fact. Later, Koml´os 3 (see [6]) found a new proof which gave quantitative bound pn = O(n−1/2). In an important paper, Kahn, Koml´os and Szemr´edi [37] proved the first exponential bound. Theorem 2.2. p(n) ≤ .999n. Their arguments were simplified by Tao and Vu in 2004 [66], resulting in a slightly better bound O(.958n). Shortly afterwards, these authors [67] combined the ap proach from [37] with the idea of inverse theorems (see [71, Chapter 7] or [53] for surveys) to obtained a more significant improvement Theorem 2.3. p(n) ≤ (3/4 + o(1))n. With an additional twist, Bourgain, Vu and Wood [9] improved the bound further Theorem 2.4. p(n) ≤ ( √12+ o(1))n. The method from [67, 9] enables one to deduce bounds on pn directly from simple trigonometrical estimates. For instance, the 3/4-bound comes from the fact that | cos x| ≤ 34+14cos 2x, while the 1/√2 bound come from | cos x|2 =12+12cos 2x. [9, Theorem 2.2] provides a formal connection between singularity estimates and trigonometrical estimates of this type, which, while not yet solve the Singularity Conjecture, does lead to sharp bounds in other situations, such as singularity of random matrices with (0, ±1) entries). To conclude this section, let us mention a very useful tool, the Littlewood-Offord Erd¨os theorem. Let v = {v1, . . . , vn} be a set of n non-zero real numbers and ξ1, . . . , ξn be i.i.d random Bernoulli variables. Define S := Pni=1 ξivi and pv(a) = P(S = a) and pv = supa∈Z pv(a). The problem of estimating pv came from a paper of Littlewood and Offord in the 1940s [45], as a key technical ingredient in their study of real roots of random polynomials. Erd¨os, improving a result of Littlewood and Offord, proved the following theorem, which we will refer to as the Erd¨os-Littlewood-Offord small ball inequality; see [53] for an explanation of this name. Theorem 2.5. (Small ball inequality) Let v1, . . . , vn be non-zero numbers and ξi be i.i.d Bernoulli random variables. Then n bn/2c pv ≤ 2n= O(n−1/2). 4 Theorem 2.5 is a classical result in combinatorics and have many non-trivial ex tensions with far reaching consequences (see [7, 34, 53], [71, Chapter 7] and the references therein). To give the reader a feeling about how small ball estimates can be useful in esti mating pn, let us expose the rows of Mn one by one from top to bottom. Assume that the first n−1 rows are independent and form a hyperplane with normal vector v = (v1, . . . , vn). Conditioned on these rows, the probability that Mn is singular is P(X · v = 0) = P(ξ1v1 + · · · + ξnvn = 0), where X = (ξ1, . . . , ξn) is the last row. In Section 3, the reader will see an application of Theorem 2.5 that leads to Koml´os’ original result pn = o(1). In order to obtain the stronger estimates in Theorems 2.3 and 2.4, one needs to ebstablish Inverse (or structural) Littlewood-Offord theorems, based on the following general principle Phenomenon II. If P(X ·v = 0) is relatively large, then the coefficients v1, . . . , vn posses a strong additive structure. These theorems are motivated by inverse theorems of Freiman type in Additive Combinatorics, the discussion of which is beyond the scope of this survey. The interested reader is referred to [53] for a detailed discussion. 3. A simple proof of Koml´os’ Theorem Let us start with a simple fact. Here and later Bernoulli vectors mean vectors with coordinates ±1. Fact 3.1. Let H be a subspace of dimension 1 ≤ d ≤ n. Then H contains at most 2d Bernoulli vectors. To see this, notice that in a subspace of dimension d, there is a set of d coordinates which determine the others. This fact implies pn ≤ nX−1 i=1 P(Xi+1 ∈ Hi) ≤ nX−1 i=1 2i−n ≤ 1 −22n. While this bound is quite the opposite of what we want to proof, notice that the loss comes at the end. Thus, to obtain the desired upper bound o(1), it suffices to 5 show that the sum of the last (say) log log n terms contribute at most (say) 1 log1/3 n. To do this, we will exploit the fact that the Hi are spanned by random vectors. The following lemma implies the theorem via the union bound. Lemma 3.1. Let H be the subspace spanned by d random vectors, where d ≥ n − log log n. Then with probability at least 1 −1n, H contains at most 2n Bernoulli vectors. log1/3 n We say that a set S of d vectors is k-universal if for any set of k different indices 1 ≤ i1, . . . , ik ≤ n and any set of signs 1, . . . , n ( i = ±1), there is a vector v in S such that the sign of the ij th coordinate of v matches j , for all 1 ≤ j ≤ k. Fact 3.2. If d ≥ n/2, then with probability at least 1−1n, a set of d random vectors is k-universal, for k := log n/10. To prove this, notice that the failure probability is, by the union bound, at most n k (1 −12k)d ≤ nk(1 −12k)n/2 ≤ n−1. It S is k-universal, then any non-zero vector v in the orthogonal complement of the subspace spanned by S should have more than k non-zero vectors (otherwise, there would be a vector in S having positive inner product with v). If we fix such v and let X be a random Bernoulli vector, then by Theorem 2.5, P(X ∈ Span(S)) ≤ P(X · v = 0) = O(1 k1/2) ≤1 log1/3n, proving Lemma 3.1 and the theorem. Tạp chí Epsilon, Số 03, 06/2015. Tài liệu tham khảo [1] N. Alon, Eigenvalues and expanders, Combinatorica 6(1986), no. 2, 83-96. [2] N. Alon and V. Milman, λ1- isoperimetric inequalities for graphs, and supercon- centrators, J. Combin. Theory Ser. B 38 (1985), no. 1, 73-88. [3] N. Alon and J. Spencer, The probabilistic method, 3rd ed., John Wiley & Sons Inc., Hoboken, NJ, 2008. [4] R. Arratia and S. DeSalvo, On the singularity of ran dom Bernoulli matricesNnovel integer partitions and lower ˜ bound expansions, Ann. Comb. 17 (2013), no. 2, 251-274. [5] Z. Bai and J. Silverstein, Spectral analysis of large dimen sional random matrices. Second edition. Springer Series in Statistics. Springer, New York, 2010. [6] B. Bollobás, Random graphs. Second edition, Cambridge Studies in Advanced Mathematics, 73. Cambridge Univer sity Press, Cambridge, 2001. [7] B. Bollobás, Combinatorics. Set systems, hypergraphs, families of vectors and combinatorial probability. Cam bridge University Press, Cambridge, 1986. [8] C. Bordenave, M. Lelarge, and J. Salez, The rank of diluted random graphs, Ann. Probab. 39 (2011), no. 3, 1097-1121. [9] J. Bourgain, V. Vu and P. M. Wood, On the singularity probability of discrete random matrices, J. Funct. Anal. 258 (2010), no. 2, 559–603. [10] S. Brooks and E. Lindenstrauss, Non-localization of eigen functions on large regular graphs, Israel J. Math. 193 (2013), no. 1, 1–14 [11] Chung, F. R. K.; Graham, R. L.; Wilson, R. M. Quasi random graphs. Combinatorica 9 (1989), no. 4, 345–362. [12] F. Chung, Spectral graph theory, CBMS series, no. 92 (1997). 22 Tạp chí Epsilon, Số 03, 06/2015. [13] K. Costello, Bilinear and quadratic variants on the Littlewood-Offord problem,Israel J. Math. 194 (2013), no. 1, 359–394. [14] K. Costello and V. Vu, The ranks of random graphs. Ran dom Structures and Algorithm. 33 (2008), 269-285 [15] K. Costello and V. Vu, The rank of sparse random matrices, Combin. Probab. Comput. 19 (2010), no. 3, 321–342. [16] K. Costello, T. Tao and V. Vu, Random symmetric matrices are almost surely singular, Duke Math. J. 135 (2006), no. 2, 395–413. [17] Y. Dekel, J. Lee, and N. Linial. Eigenvectors of ran dom graphs: Nodal domains.Approx- imation, Randomiza tion, and Combinatorial Optimization. Algorithms and Tech niques, pages 436-448, 2008. [18] I. Dimitriu and S. Pal, Sparse regular random graphs: spectral density and eigenvectors, Ann. Probab. 40 (2012), no. 5, 2197–2235. [19] A. Edelman, E. Kostlan and M. Shub, How many eigen values of a random matrix are real? J. Amer. Math. Soc. 7 (1994), no. 1, 247–267. [20] A. Edelman, Eigenvalues and condition numbers of ran dom matrices, SIAM J. Matrix Anal. Appl. 9 (1988), 543– 560. [21] P. Erdos, On a lemma of Littlewood and Offord, ¨ Bull. Amer. Math. Soc. 51 (1945), 898–902. [22] L. Erdos, A. Knowles, H-T. Yau and J. Yin, Spectral statis- ¨ tics of Erd?s-RvZnyi graphs I: Local semicircle law, Ann. Probab. 41 (2013). [23] L. Erdos, A. Knowles, H-T. Yau and J. Yin, Spectral statis- ¨ tics of Erd?s-RvZnyi Graphs II: Eigenvalue spacing and the extreme eigenvalues, Comm. Math. Phys. 314 (2012), no. 3, 587–640. 23 Tạp chí Epsilon, Số 03, 06/2015. [24] L. Erdos, B. Schlein and H-T. Yau, Wegner estimate and ¨ level repulsion for Wigner random matrices, Int. Math. Res. Not. IMRN 2010, no. 3, 436–479. [25] L. Erdos and H-T. Yau, Universality of local spectral statis- ¨ tics of random matrices, Bull. Amer. Math. Soc. (N.S.) 49 (2012), no. 3, 377–414. [26] J. Friedman. On the second eigenvalue and random walks in random d-regular graphs. Technical Report CX-TR-172- 88, Princeton University, August 1988. [27] J. Fiedman, A proof of Alon’s second eigenvalue conjec ture and related problems. (English summary)Mem. Amer. Math. Soc. 195 (2008), no. 910, viii+100 pp. [28] J. Friedman and D-E. Kohler, The Relativized Second Eigenvalue Conjecture of Alon, preprint. [29] Z. Furedi and J. Komlós, The eigenvalues of random sym- ¨ metric matrices,Combinatorica 1 (1981), no. 3, 233-241. [30] V. L. Girko, A refinement of the central limit theorem for random determinants. (Russian) Teor. Veroyatnost. i Primenen. 42 (1997), no. 1, 63–73; translation in Theory Probab. Appl. 42 (1997), no. 1, 121–129 (1998) [31] V. L. Girko, A central limit theorem for random determi nants. Teor. Veroyatnost. i Mat. Statist. 21 (1979), 35–39, 164. [32] A. Guionnet and O. Zeitouni, Concentration of the spec tral measure for large matrices, Electron. Comm. Probab. 5 (2000), 119–136. [33] H. Golstein and J. von Neumman, Numerical inverting of matrices of high order, Bull. Amer. Math. Soc. 53 (1947), 1021-1099. [34] G. Halász, Estimates for the concentration function of com binatorial number theory and probability, Period. Math. Hungar. 8 (1977), no. 3-4, 197–211. [35] S. Janson, T. Luczak and A. Rucinski, Random Graphs,Wiley-Interscience (2000) 24 Tạp chí Epsilon, Số 03, 06/2015. [36] J. Kahn and E. Szemerédi, STOC 1989. [37] J. Kahn, J. Komlós, E. Szemerédi, On the probability that a random ±1 matrix is singular, J. Amer. Math. Soc. 8 (1995), 223–240. [38] J. Komlós, On the determinant of (0, 1) matrices, Studia Sci. Math. Hungar. 2 (1967) 7-22. [39] J. Komlós, On the determinant of random matrices,Studia Sci. Math. Hungar. 3 (1968) 387–399. [40] M. Krivelevich and B. Sudakov, Pseudo-random graphs.More sets, graphs and numbers, 199-262, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006. [41] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs, Combinatorica, 8(3):261-277, 1988. [42] G.A. Margulis , Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators [in Russian] . Prob lemy Peredachi Informatsii 24 (1988), pp. 51-60. [43] B.D. McKay. The expected eigenvalue distribution of a large regular graph.Linear Algebra and its Applications, 40:203- 216, 1981. [44] P. Mitra, Entrywise bounds for eigenvectors of random graphs. Electron. J. Combin. 16 (2009), no. 1, Research Paper 131, [45] J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation. III. Rec. Math. [Mat. Sbornik] N.S. 12 , (1943). 277–286. [46] A. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), no. 2, 491– 523. [47] A. Marcus, D. Spielman and N. Srivastava, Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees, preprint. 25 Tạp chí Epsilon, Số 03, 06/2015. [48] K. Maples, Symmetric random matrices over finite fields announcement, April 15, 2013, preprint. [49] A. Nilli, On the second eigenvalue of a graph, Discrete Math ematics 91 (1991), 207-210. [50] A. Nilli, Tight estimates for eigenvalues of regular graphs, Electronic J. Combinatorics 11 (2004), N9, 4pp. [51] H. Nguyen, On the least singular value of random symmet ric matrices, Electron. J. Probab. 17 (2012), no. 53. [52] H. Nguyen, Inverse Littlewood-Offord problems and the singularity of random symmetric matrices, Duke Math. J. 161 (2012), no. 4, 545–586. [53] H. Nguyen and V. Vu, Small probability, inverse theorems, and applications, Erdos’ 100th Anniversary Proceeding, Bolyai Society Mathematical Studies, Vol. 25 (2013). [54] H. Nguyen and V. Vu, Random matrices: Law of the deter minant, Annals of Probability (2014), Vol. 42, No. 1, 146- 167. [55] M. Rudelson, Invertibility of random matrices: norm of the inverse, Ann. of Math. (2) 168 (2008), no. 2, 575–600. [56] M. Rudelson, Lecture notes on non-aymptotic random ma trix theory, notes from the AMS Short Course on Random Matrices, 2013. [57] M. Rudelson and R. Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. [58] M. Rudelson and R. Vershynin, Delocalization of eigen vectors of random matrices with independent entries, preprint. [59] O. N. Feldheim and S. Sodin, A universality result for the smallest eigenvalues of certain sample covariance matri ces, Geom. Funct. Anal. 20 (2010), no. 1, 88–123. [60] A. Sárkozy and E. Szemerédi, Uber ein Problem von Erd ¨ os¨ und Moser, Acta Arithmetica, 11 (1965) 205-208. 26 Tạp chí Epsilon, Số 03, 06/2015. [61] D. Spielman and S-H. Teng, D. Spielman, S.-H. Teng, Smoothed analysis of algorithms, Proceedings of the Inter national Congress of Mathematicians, Vol. I (Beijing, 2002), 597–606, Higher Ed. Press, Beijing, 2002. [62] B. Sudakov and V. Vu, Local resilience of graphs, Random Structures Algorithms 33 (2008), no. 4, 409–433. [63] T. Tao and V. Vu, A central limit theorem for the deter minant of a Wigner matrix, Adv. Math. 231 (2012), no. 1, 74–101. [64] T. Tao and V. Vu, Random matrices: universal properties of eigenvectors, Random Matrices Theory Appl. 1 (2012), no. 1. [65] T. Tao and V. Vu, Random matrices: Universality of the local eigenvalues statistics pdf file Acta Math. 206 (2011), no. 1, 127–204. [66] T. Tao and V. Vu, On random ±1 matrices: Singularity De terminant,Random Structures Algorithms 28 (2006), no. 1, 1–23. [67] T. Tao and V. Vu, On the singularity probability of random Bernoulli matrices, J. Amer. Math. Soc. 20 (2007), no. 3, 603–628. [68] T. Tao and V. Vu, Inverse Littlewood-Offord theorems and the condition number of random matrices, Annals of Math. 169 (2009), 595-632 [69] T. Tao and V. Vu, On the permanent of random Bernoulli matrices,Advances in Mathematics 220 (2009), 657-669. [70] T. Tao and V. Vu, Random matrices: Universality of local spectral statistics of non-Hermitian matrices, to appear in Annals of Probability. [71] T. Tao and V. Vu, Additive Combinatorics,Cambridge Univ. Press, 2006. [72] T. Tao and V. Vu, Random matrices: The Universality phe nomenon for Wigner ensembles, preprint, to appear in AMS lecture notes on Random Matrices, 2013. 27 Tạp chí Epsilon, Số 03, 06/2015. [73] T. Tao and V. Vu, Random matrices: the distribution of the smallest singular values, Geom. Funct. Anal. 20 (2010), no. 1, 260–297. [74] T. Tao and V. Vu, Random matrices: universal properties of eigenvectors, Random Matrices Theory Appl. 1 (2012), no. 1. [75] L. Tran, V. Vu and K. Wang, Sparse random graphs: Eigen values and Eigenvectors, Random Structures Algorithms 42 (2013), no. 1, 110–134. [76] R. Vershynin, Invertibility of symmetric random matrices, Random Structures and Algorithms 44 (2014), 135–182 [77] E.P. Wigner. On the distribution of the roots of certain symmetric matrices.Annals of Mathematics, 67(2):325-327, 1958. [78] N.C. Wormald, Models of random regular graphs,In Sur veys in Combinatorics, 1999, J.D. Lamb and D.A. Preece, eds, pp. 239-298. [79] V. Vu and K. Wang, Random projection, random quadratic forms, and random eigenvectors, to appear in Random Structures and Algorithms. [80] M. Wood, The distribution of sandpile groups of random graphs, preprint. 28 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ức Gọ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: Perm(A) = X π∈Sn Yn i=1 aiπ(i), trong đó Sn là tập tất cả các hoán vị của [n]. Như vậy, công thức tính vĩnh thức rất giống công thức Leibniz để tính định thức của A, chỉ khác ở điểm duy nhất là ta không nhân sgn(π) vào mỗ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ản trong toán Tổ hợp là tìm số cách lát một hình chữ nhật với các quâ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. (Xem hình 3.1.) Làm thế nào để ta đếm tổng số cách bắt cặp hoàn hảo của đồ thị lưới? Dễ thấy đồ thị lưới là đồ thị hai phần3. Giả 1Permanent. 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. 2Perfect matching. Còn được gọi là cặp ghép hoàn hảo (ban Biên tập). 3Bipartite 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ật lý 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ười Phá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ọc nghiên cứu các đẳng thức và bất đẳng thức liên quan đến vĩnh thức, bao gồm Arthur Cayley và Thomas Muir của Vương Quốc Anh. 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ật sự “nóng” lên từ những năm 1960 do các đóng góp của toán học Hà Lan. 1.1. Giả định van der Waerden Năm 1926, nhà Toán học người Hà Lan Bartel Leendert van der Waerden đặt một câu hỏi là vĩnh thức nhỏ nhất của một ma 30 Tạp chí Epsilon, Số 03, 06/2015. trận ngẫu nhiên kép4là bao nhiêu [35]. Trực quan cho thấy ma trận Jn =1nJ có lẽ là ma trận có vĩnh thức cực tiểu. (Ma trận J là ma trận vuông n × n gồm toàn các số 1.) Từ đó, bất đẳng thức sau đây được gọi là giả định van der Waerden5: Perm(A) ≥n!nn(3.1) 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 Đại số, hầu như ít làm toán tổ hợp. Một diễn giả trẻ lên báo báo một vấn đề liên quan đến giả định van der Waerden. Van der Waerden giơ tay lên hỏi “giả định đó nói gì vậy?” Cuối buổi diễn giả 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ất phá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ác lớp kề7trái và các lớp kề phải của một nhóm con H của một nhó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ân hoạ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ệ đại diệ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ểu Perm(A) > 0. Do tổng của các hàng và các cột của A đều bằng |G|/n, ta “thường hoá”8 A bằng cách đặt aij =|Ri∩Cj | |G|/n . Khi đó A là ma trận ngẫu nhiên kép. Ta có thể chứng minh Perm(A) > 0 dễ dàng bằng định lý Konig-Hall. Nhưng một câu hỏi khác cũng ¨ 4Doubly 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. 5Van der Waerden conjecture 6Common system of representatives. 7Coset. 8Normalize. 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ới là bao nhiêu. Đây chính là nguồn gốc của giả định van der Waerden. Trong quyển “Permanents” (1978 [23]), Henryk Minc ghi rằng hồi ông nộp một số bài báo về vĩnh thức giữa thế kỷ 20 thì có một bình duyệt viên nói rằng “chế ra cái tên gì lố bịch thế”? Giả thiết van der Waerden cuối cùng cũng được chứng minh, năm 1981, độc lập bởi hai bài báo khác nhau của G. P. Ego rychev [8] và của D. I. Falikman [9]. Cả hai đều dùng một bất đẳng thức hình học gọi là bất đẳng thức Alexandroff-Fenchel [1]. Egorychev và Falikman được giải Fulkerson năm 1982 về bài này. Năm 2006, Leonid Gurvits [11] chứng minh một bất đẳng thức rất tổng quát với chứng minh ngắn gọn, bao gồm một hệ quả là Định lý van der Waerden. 1.2. Giả định Minc Giả định van der Waerden nói về chặn dưới của vĩnh thức của một lớp các ma trận nhất định. Về chặn trên thì năm 1963 Minc [22] có một giả định như sau. Gọi A là một ma trận 01, nghĩa là aij ∈ {0, 1} với mọi i, j ∈ [n]. Gọi mi là số số 1 trên hàng i của ma trận, thì ta có Perm(A) ≤Qni=1(mi!)1/mi. Năm 1973 Lev M. Brègman [4] chứng minh được giả định này, và bây giờ nó thường được gọi là Định lý Brègman.9 Năm 1977, một nhà toán học lỗi lạc khác người Hà Lan, Alex Schrijver, trình bày một chứng minh cực gọn và thanh lịch [28]. Ngoài ra, Schrijver cũng tổng quát hoá định lý cho các ma trận nguyên không âm. Dưới đây chúng ta ghi lại chứng minh cho trường hợp ma trận 01 của Schrijver. Định lý 1.1 (Định lý Brègman). Gọi A là ma trận 01 kích thước n × n. Gọi mi là số các số 1 trên hàng i của A. Ta có, Perm(A) ≤Yn i=1 (mi!)1/mi. (3.2) Chứng minh. Cho một cặp i, j ∈ [n], gọi Aij là ma trận đạt được bằng cách bỏ hàng i và cột j ra khỏi A. Từ định nghĩa (và từ giả 9Đây cũng chính là Brègman của phân kỳ Brègman (Bregman divergence) trong xác suất thống kê. 32 Tạp chí Epsilon, Số 03, 06/2015. thiết A là ma trận 01), dễ thấy Perm(A) = X j:aij=1 Perm(Aij ), với mọi i ∈ [n]. (3.3) (Khai triển này giống như khai triển Laplace tính định thức.) Do vế phải của (3.2) là một cái tích, ta thử chặn Perm(A) bằng cách chuyển vế phải của (3.3) thành một cái tích của các hàm của Perm(Aij ), rồi sau đó áp dụng quy nạp. Cách tự nhiên nhất để chặn trên tổng bằng tích là dùng bất đẳng thức Jensen. Cụ thể hơn, từ tính lồi của hàm x ln x trên miền x > 0, bất đẳng thức Jensen cho ta biết t1 + · · · + tm m ln t1 + · · · + tm m ≤t1 ln t1 + · · ·tm ln tm m, miễn là ti > 0 với mọi i ∈ [m]. Từ đó, ta chặn được tổng bằng tích: (t1 + · · · + tm)t1+···+tm ≤ mt1+···+tmtt11· · ·ttm m . Và cũng dễ thấy rằng bất đẳng thức này đúng với mọi ti ≥ 0, chứ không cần ti > 0 như trước nữa. Áp dụng vào (3.3), ta được một chặn trên cho Perm(A) mà vế phải là một tích: Perm(A)Perm(A) ≤ mPerm(A) i Y j:aij=1 Perm(Aij )Perm(Aij ). (3.4) Bất đẳng thức (3.4) đúng với mọi i ∈ [n]. Bước tự nhiên kế tiếp là ta nhân chúng với nhau để có vế phải đối xứng, và để cho các vế phải “trung hoà” lẫn nhau khi kích thước chúng khác nhau. Nói cách khác, ta dùng trung bình nhân của các vế phải: Perm(A)nPerm(A) ≤ Yn i=1 mPerm(A) i ! ·  Yn i=1 Y j:aij=1 Perm(Aij )Perm(Aij )   . (3.5) Phát triển tự nhiên kế đến là áp dụng bất đẳng thức (3.2) cho Perm(Aij ) bên vế phải. Tuy nhiên, điều phiền phức là có cả Perm(Aij ) trên số mũ – áp dụng vào sẽ làm loạn vế phải. Cho nên, ta tìm cách viết lại thừa số thứ hai bên vế phải của (3.5) một chút. Định nghĩa, S = π ∈ Sn | aiπ(i) = 1 33 Tạp chí Epsilon, Số 03, 06/2015. Sij = π ∈ S | π(i) = j . Từ định nghĩa của vĩnh thức, dễ thấy rằng |S| = Perm(A) và |Sij | = Perm(Aij ) nếu aij = 1. Đây là một “diễn giải tổ hợp” của hàm vĩnh thức. Ngoài ra, nếu aij = 0 thì |Sij | = 0. Do đó, ta có thể viết lại thừa số thứ hai bên vế phải của (3.5) như sau: Yn i=1 Y j:aij=1 Perm(Aij )Perm(Aij ) =Yn i=1 =Yn i=1 Y j:aij=1 Y j:aij=1 Perm(Aij )|Sij | Perm(Aij )|Sij | Y j:aij=0 Perm(Aij )|Sij | =Yn i=1 Yn j=1 Perm(Aij )|Sij | Đến đây ta dùng cái mẹo “định trị một đại lượng bằng hai cách” cực kỳ phổ dụng trong toán Tổ hợp. Trong vế phải ở đẳng thức trên, với mỗi cặp (i, j) thì Perm(Aij ) xuất hiện |Sij | lần. Bây giờ tưởng tượng ta xây dựng một đồ thị hai phần mà các đỉnh bên trái là các cặp (i, j), và các đỉnh bên phải là các hoán vị π ∈ S. Sau đó, ta nối đỉnh (i, j) bên trái với đỉnh π bên phải nếu và chỉ nếu π(i) = j. Với mỗi cạnh như vậy ta cho “cân nặng” bằng Perm(Aij ), thì cái tích Qni=1Qnj=1 Perm(Aij )|Sij | chính là tích của cân nặng của các cạnh tưởng tượng nọ nhóm theo các đỉnh bên trái của đồ thị hai phần. Thế thì, một cách khác để nhóm cái tích các cân nặng này lại với nhau là nhóm theo các đỉnh π ∈ S bên phải. Với mỗi đỉnh π ta lấy n cạnh kề với nó, đó là các cạnh nối π với cách đỉnh (i, π(i)) bên trái. Như vậy ta suy ra Yn i=1 Yn j=1 Perm(Aij )|Sij | =Y π∈S Yn i=1 Perm(Aiπ(i)). Còn thừa số đầu tiên của vế phải của (3.5) thì dễ viết lại thành Yn i=1 i =Yn mPerm(A) i=1 i =Y m|S| π∈S Yn i=1 mi. Đến đây, ta có thể viết lại toàn bộ bất đẳng thức (3.5) ở dạng dễ chịu hơn nhiều: Perm(A)nPerm(A) ≤Y π∈S Yn i=1 mi· Perm(Aiπ(i)). (3.6) 34 Tạp chí Epsilon, Số 03, 06/2015. Vế phải của (3.6) đã rất cân đối, đến lúc ta áp dụng giả thiết quy nạp được rồi: Yn i=1 Perm(Aiπ(i)) ≤Yn i=1  Y k6=i akπ(i)=1 ((mk − 1)!)1/(mk−1) Y k6=i akπ(i)=0 (mk!)1/mk   . (3.7) Vế phải của bất đẳng thức này trông có vẻ kinh dị, nhưng lại có dạng rất đơn giản. Nó là tích “cân nặng” của các cặp i 6= k. Cân nặng này bằng ((mk − 1)!)1/(mk−1) nếu akπ(i) = 1, và bằng (mk!)1/mk nếu akπ(i) = 0. Vế phải của (3.7) nhóm các tích này theo i. Ta cũng có thể nhóm nó theo k (nhớ dùng cái đồ thị hai phần tưởng tượng – bên trái là i, bên phải là k, và nối (i, k) nếu i 6= k). Nhóm theo k thì có cái lợi là cân nặng của một cặp i 6= k chỉ phụ thuộc vào k. Lưu ý rằng π ∈ S, do đó akπ(k) = 1. Do đó, số các i sao cho i 6= k và akπ(i) = 1 chính là mk − 1, và số các i sao cho i 6= k và akπ(i) = 0 chính là n − mk. Do đó, vế phải của (3.7) bằng Yn k=1 (mk − 1)! · (mk!)n−mk mk . Kết hợp với (3.6) nữa thì ta có Perm(A)nPerm(A) ≤Y π∈S =Y "Yn i=1 Yn mi # · "Yn k=1 ! (mk − 1)! · (mk!)n−mk mk . #! π∈S Yn k=1 (mk!)n/mk !nPerm(A) = k=1 (mk!)1/mk . Đó là chứng minh tuyệt vời của Alex Schrijver. 1.3. Độ phức tạp tính toán Từ thế kỷ 18, Gauss đã cho chúng ta biết cách tính định thức trong thời gian O(n3). Chỉ khác nhau ở cái dấu, nhưng vĩnh thức khó tính hơn định thức nhiều. Năm 1979, Leslie Valiant định nghĩa lớp độ phức tạp #P và chứng minh rằng vấn đề 35 Tạp chí Epsilon, Số 03, 06/2015. tính Perm(A) của một ma trận 01 là vấn đề #P-khó [33]. Đây là một trong những công trình cột mốc mang đến giải Turing năm 2010 cho Valiant. Ông có hai con trai là Greg Valiant (giáo sư khoa Máy tính ở Stanford), và Paul Valiant (giáo sư khoa Máy tính ở Brown). Ở đây chúng ta chỉ mô tả rất nôm na kết quả của Valiant. Một vấn đề quyết định10 là vấn đề mà câu trả lời là có hoặc không tồn tại lời giải. Lớp P là lớp các vấn đề quyết định mà ta có thể tìm lời giải hoặc trả lời không tồn tại lời giải trong thời gian đa thức. Ví dụ, cho một đồ thị G = (V, E), vấn đề bắt cặp lớn nhất11 hỏi G có tập cạnh không giao nhau có kích thước ít nhất k hay không. Đây là vấn đề quyết định, và thuật toán trổ hoa12 của Edmonds năm 1965 giải nó trong thời gian O(|V |4) [7]. Lớp NP là lớp các vấn đề quyết định mà việc xác minh một lời giải có thật sự là lời giải hay không có thể làm nhanh được trong thời gian đa thức, nhưng việc tìm ra lời giải thì chưa chắc. Ví dụ, nếu ai đó tô màu một đồ thị G và nói “đây là một tô màu hợp lệ dùng 3 màu” thì ta dễ dàng kiểm tra được trong thời gian đa thức xem người đó có thành thật hay không. Nhưng nếu cho trước đồ thị G thì ta không biết cách nào để trả lời câu hỏi “có tồn tại cách tô G dùng 3 màu hay không?” trong thời gian đa thức. Dễ thấy rằng P ⊆ NP, nhưng chứng minh P 6= NP là một câu hỏi triệu đô. Hiện nay, để chứng minh một vấn đề quyết định nào đó là khó (nghĩa là khó có khả năng tồn tại thời gian đa thức để giải nó) thì thường là ta chứng minh rằng nó khó hơn tất cả các vấn đề trong NP. Cụ thể hơn một chút, ta có thể chứng minh rằng nếu trả lời được câu hỏi “G có tô bằng 3 màu được không?” một cách hiệu quả thì tất cả các vấn đề trong NP đều có thuật toán hiệu quả để giải. Vì thế, vấn đề tô 3 màu là vấn đề NP-khó. Các vấn đề quyết định là các vấn đề tính toán 1 bit thông tin: bit 0 (trả lời không) hoặc bit 1 (trả lời có). Đây là giải pháp kỹ thuật để chứng minh độ khó. Nhưng tất nhiên các vấn đề thực tế không chỉ là các vấn đề mà output chỉ có 1 bit thông tin. Ví dụ ta cần tính xác suất mà một mạng máy tính là liên thông, cho biết trước xác suất lỗi của các kết nối. Bài toán này gọi là 10Decision problem. 11Maximum matching. Còn được gọi là cặp ghép cực đại (ban Biên tập). 12Blossom algorithm. 36 Tạp chí Epsilon, Số 03, 06/2015. vấn đề độ tin cậy13 của một mạng. Hoặc, ta cần tính Perm(A) của một ma trận A cho trước. Rõ ràng là trên thực tế có hàng tỉ các vấn đề như vậy. Lớp #P được Valiant định nghĩa để nắm bắt độ khó của việc tính một con số (thay vì chỉ một bit thông tin): #P là lớp các vấn đề mà câu trả lời là số lời giải của một vấn đề NP. Ví dụ, vấn đề tìm số cách tô đồ thị dùng 3 màu hay vấn đề tìm số tập cạnh không giao nhau với kích thước n/2 là các vấn đề trong lớp #P. Rõ ràng là nếu ta đếm được số lời giải, thì ta sẽ quyết định được là có lời giải hay không. Do đó, các vấn đề trong #P khó hơn các vấn đề tương ứng trong NP. Đếm số cách tô 3 màu khó hơn xác minh xem có cách tô 3 màu hay không. Đếm số cách bắt cặp hoàn hảo khó hơn xác minh xem có cách bắt cặp hoàn hảo hay không. Tương tự như NP-khó, #P-khó là lớp các vấn đề mà – nếu ta giải được bất kỳ vấn đề nào trong lớp này một cách hiệu quả, thì ta giải được tất cả các vấn đề trong lớp #P một cách hiệu quả, và do đó ta cũng giải được tất cả các vấn đề trong NP một cách hiệu quả. Tóm lại, một thuật toán thời gian đa thức cho bất kỳ vấn đề #P-khó nào sẽ dẫn đến hệ quả là P = NP. Trong ngữ cảnh của bài viết này thì điều này có nghĩa là rất khó có khả năng tồn tại một thuật toán tính Perm(A) trong thời gian đa thức – cho dù ma trận A là ma trận 01. Không tính được hiệu quả thì ta có hai chọn lựa tự nhiên: một là tìm thuật toán xấp xỉ nó (trong thời gian đa thức), hai là tìm lớp các ma trận A mà vẫn tồn tại thuật toán hiệu quả. Chọn lựa thứ hai dẫn ta đến câu hỏi của Pólya và khái niệm định thức Pfaff. Tuy nhiên, trước khi thảo luận câu hỏi của Pólya và định thức Pfaff, ta cần chuẩn bị một ít kiến thức nền về hoán vị. 2. Vài quan sát cơ bản về hoán vị Cho hoán vị π ∈ Sn. Ta có thể biểu diễn π thành dạng một đồ thị có hướng, với tập đỉnh [n], và cạnh (i, π(i)). Đồ thị này là một tập hợp các chu trình không giao nhau, và các chu trình này phủ toàn bộ [n]. (Xem hình 3.2.) 13Reliability. 37 2 5 Tạp chí Epsilon, Số 03, 06/2015. 3 1 7 6 4 8 π = (8 3 6 1 2 5 7 4) Hình 3.2: Hoán vị và cấu trúc chu trình của nó. Hoán vị này có một chu trình chẵn. Một nghịch thế14 của π là một cặp (i, j) sao cho i < j và π(i) > π(j). Gọi Inv(π) là tổng số các nghịch thế của π. Dấu của π được định nghĩa là sgn(π) = (−1)Inv(π). Một chuyển vị kề15 là hoán vị π = (1 · · · i − 1 i + 1 i i + 2 · · · n) với i ∈ [n − 1] nào đó; hoán vị này thường được viết là (i i + 1). Nếu ta hợp thành π và một chuyển vị kề (i i + 1) thì ta được hoán vị σ = π ◦ (i i + 1) = (π(1)· · · π(i − 1) π(i + 1) π(i) π(i + 2)· · · π(n)). Mọi hoán vị σ tuỳ ý đều có thể đạt đến từ một hoán vị π tuỳ ý bằng cách áp dụng nhiều chuyển vị kề. Điều này tương đương với thuật toán sắp xếp bong bóng16. Trong thuật toán sắp xếp bong bóng, ta dùng chuyển vị kề để phần tử nhỏ nhất trong một dãy số cho trước “nổi” lên đầu tiên, rồi phần tử nhỏ nhì nổi lên vị trí thứ nhì, vân vân. Nghĩa là mọi hoán vị đều chuyển về hoán vị đơn vị được bằng chuyển vị kề. Và như thế thì mọi hoán vị đều chuyển về hoán vị khác được dùng chuyển vị kề. Dễ thấy rằng sgn(σ) = −sgn(π) nếu σ là hợp thành của π và một chuyển vị kề. Còn chuyển vị kề thay đổi cấu trúc chu trình của một giao hoán π như thế nào? Nếu i và i + 1 nằm trên cùng một chu trình của π, thì sau khi chuyển vị chu trình này sẽ bị bẻ thành hai chu trình. Nếu i và i + 1 nằm trên hai chu trình khác nhau thì hai chu trình này sẽ được trộn thành một chu trình. 14Inversion. Còn được dịch là cặp trật tự ngược (ban Biên tập). 15Adjacent transposition. 16Bubble sort. Còn được gọi là sắp xếp nổi bọt (ban Biên tập). 38 Tạp chí Epsilon, Số 03, 06/2015. Các khẳng định vừa rồi cũng đúng cho chuyển vị bất kỳ (i j), không nhất thiết là chuyển vị kề. Từ đó, ta chứng minh được bài tập sau đây, là một bài tập cơ bản của toán Tổ hợp đếm. Bài tập 2.1. Chứng minh rằng sgn(π) = (−1)e(π), trong đó e(π) là số các chu trình chẵn trong cấu trúc chu trình của π. (Chu trình chẵn là một chu trình có một số chẵn các đỉnh.) Một tính chất thú vị nữa của các hoán vị là hai hoán vị liên hợp có cấu trúc chu trình giống hệt nhau. Cụ thể hơn, hoán vị π và σ gọi là hai hoán vị liên hợp17 nếu π = τ ◦σ ◦τ−1 với τ là một hoán vị nào đó. Ví dụ, nếu π = (i i + 1) ◦ σ ◦ (i i + 1)−1thì cấu trúc chu trình của π và cấu trúc chu trình của σ giống y nhau, chỉ đổi chỗ i và i + 1. Hình 3.3 minh hoạ điều này. 2 7 3 6 5 1 4 8 Hình 3.3: Cấu trúc chu trình của σ = (5 7) ◦ π ◦ (5 7)−1, π là hoán vị ở Hình 3.2 3. Câu hỏi của Pólya Năm 1913, George Pólya [24] quan sát rằng det a b c d = Perm a b −c d , nghĩa là với mọi ma trận 2 × 2 thì có cách đổi dấu một (vài) phần tử của ma trận để biến vĩnh thức thành định thức. Pólya thắc mắc là điều này có đúng với mọi ma trận hay không? Cụ thể hơn, câu hỏi của Pólya như sau. Cho trước một ma trận A = (aij ). Có tồn tại một ma trận B = (bij ) sao cho bij = ±aij , với mọi i, j ∈ [n], và, với mọi hoán vị π ∈ Sn ta có Yn i=1 aiπ(i) = sgn(π)Yn i=1 biπ(i). (3.8) 17Conjugate permutations. 39 Tạp chí Epsilon, Số 03, 06/2015. Trong đó, sgn(π) ∈ {+1, −1} là dấu của hoán vị π, đã định nghĩa trong phần trước. Theo khai triển Leibniz thì det(B) = X π∈Sn sgn(π)Yn i=1 bij . Do đó, nếu tồn tại ma trận B như trên thì Perm(A) = det(B). Từ nay, ma trận B thoả tính chất này sẽ được gọi là ma trận Pólya của ma trận A. Cũng trong năm đó, Gábor Szego˝18 [31] trả lời là không, vì với mọi n ≥ 3 luôn tồn tại một ma trận n×n không có ma trận Pólya tương ứng. Bài tập 3.1. Gọi J3 là ma trận 3 × 3 gồm toàn các số 1. Chứng minh rằng J3 không có ma trận Pólya. Dựa vào đó, chứng minh rằng với mọi n ≥ 3, tồn tại ma trận n×n không có ma trận Pólya tương ứng. Câu hỏi tự nhiên tiếp theo, cũng là câu hỏi chính của phần này của bài viết, như sau: Câu hỏi 3.2 (Câu hỏi của Pólya). Ma trận A phải như thế nào thì mới có ma trận Pólya cho nó? Giả sử A có ma trận Pólya B. Thì ta có thể viết B = A ◦ L là tích Hadamard của A và một ma trận L = (`ij ). Trong đó bij = aij `ij với mọi i, j ∈ [n], `ij ∈ {−1, 0, 1}, và `ij 6= 0 nếu aij 6= 0. Từ (3.8) Qta suy ra ma trận L phải thoả mãn tính chất sau đây. Nếu n i=1 aiπ(i) 6= 0 thì sgn(π)Yn i=1 `iπ(i) = 1, (3.9) nghĩa là tất cả các số hạng khác 0 trong khai triển Leibniz của định thức của L đều bằng 1. Một ma trận L với các phần tử trong tập {−1, 0, 1} được gọi là ma trận không kỳ dị về dấu19 nếu nó thoả điều kiện là tất cả các số hạng khác 0 trong khai triển định thức của L đều có cùng dấu, và tồn tại ít nhất một số hạng khác 0. Tập các cặp (i, j) sao cho aij 6= 0 được gọi là giàn tựa20 của A. Phân tích vừa rồi cho thấy câu hỏi của Pólya tương đương với câu hỏi sau đây: 18Pólya thì không cần phải giới thiệu. Bản thân Szego cũng là một nhà ˝ Toán học lớn người Hungary, đã từng kèm thêm cho John von Neumann. 19Sign nonsingular. 20Support. 40 Tạp chí Epsilon, Số 03, 06/2015. Câu hỏi 3.3. Cho trước một ma trận A, khi nào thì tồn tại một ma trận L có cùng giàn tựa như A, và L là ma trận không kỳ dị về dấu. Một điều rất thú vị là đây là câu hỏi có ứng dụng trong Kinh Tế học, được chính Paul Samuelson (Nobel Kinh tế, 1970) đặt ra trong quyển “Nền tảng của phân tích Kinh Tế” năm 1947 [27]. Để tìm cách trả lời câu hỏi 3.3, ta sắp xếp nó lại thành một bài toán Tổ hợp. Trước hết, xây dựng một đồ thị hai phần G = (R ∪ C, E), trong đó R = [n] là tập các hàng của A, C = [n] là tập các cột của A, và có một cạnh (i, j) ∈ E trong đồ thị G nếu và chỉ nếu aij 6= 0. Mỗi ma trận L có cùng giàn tựa như A tương ứng với một phép gán các hệ số {−1, +1} vào các cạnh của đồ thị G. Bất kể ta gán hệ số như thế nào, khai triển định thức của L có một số hạng khác 0 nếu và chỉ nếu tồn tại một bắt cặp hoàn hảo trong đồ thị G; tại vì mỗi số hạng khác 0 trong khai triển định thức tương ứng với một bắt cặp hoàn hảo. Như vậy, không mất tính tổng quát ta có thể giả sử là G có ít nhất một bắt cặp hoàn hảo. Bắt cặp hoàn hảo (nếu có) của một đồ thị hai phần G có thể tính được bằng nhiều thuật toán, ví dụ như thuật toán nới dài đường dẫn21 hoặc thuật toán Hopcroft–Karp [12] với thời gian chạy là Op|V (G)||E(G)| = On5/2 . Gọi π ∈ Sn là một bắt cặp hoàn hảo của G, nghĩa là các cạnh (i, π(i)) thuộc về bắt cặp này. Nếu ta xáo trộn các hàng hoặc các cột của một ma trận L thì ta không thay đổi tính chất không kỳ dị về dấu của nó. Do đó, không mất tính tổng quát ta có thể giả sử π(i) = i bằng cách đánh số lại các đỉnh trong tập R. Còn nữa, khi ta nhân một hàng hoặc một cột bất kỳ của L với giá trị −1 thì ta cũng không thay đổi tính chất không kỳ dị về dấu của L. Do đó, ta có thể giả sử rằng phép gán hệ số vào các cạnh của G gán số 1 cho tất cả các cạnh (i, i) của G. Tiếp tục với hành trình sắp xếp lại bài toán. Bây giờ ta xây dựng một đồ thị có hướng D = ([n], E(D)) bằng hai bước: (1) định hướng tất cả các cạnh (i, j) ∈ E(G), i ∈ R, j ∈ C, bằng cách đổi nó thành một mũi tên từ i đến j; và (2) sau đó nhập đỉnh i ∈ R và đỉnh i ∈ C của G làm một. Sau khi làm điều này thì đồ thị D có n đỉnh, mỗi đỉnh i có một cái vòng22 là một mũi tên trỏ 21Augmenting path algorithm. Còn được gọi là Thuật toán tìm đường tăng (luồng) (ban Biên tập). 22Loop 41 Tạp chí Epsilon, Số 03, 06/2015. từ i đến i. Tại vì, ở trong G thì có mũi tên từ i ∈ R vào i ∈ C. Ngoài ra, mọi hoán vị π ∈ Sn sao cho (i, π(i)) ∈ E(G), ∀i ∈ [n], tương ứng với một bộ các chu trình không giao nhau của đồ thị D, và các chu trình này phủ toàn bộ các đỉnh của D. Một tập các chu trình (có hướng) như vậy của D được gọi là một phủ chu trình23 của D. Tóm lại, bài toán của ta đã chuyển từ gán hệ số {−1, 1} vào các cạnh vô hướng của G thành việc gán hệ số w : E(D)˜o{−1, 1} vào các cạnh có hướng của D. Với phủ chu trình π, định nghĩa “cân nặng” của nó là w(π) = sgn(π)Yn i=1 w(i, π(i)). (Ở đây ta lạm dụng ký hiệu, và dùng luôn w để ký hiệu hàm cân nặng của các phủ chu trình.) Và ta muốn tìm một phép gán hệ số sao cho w(π) = 1, với mọi phủ chu trình π của D. Thật ra bài toán chỉ đòi hỏi các số hạng này cùng dấu, nhưng vì π(i) = i là một trong các phủ chu trình, và cân nặng của nó bằng 1, nên ta biết tất cả các cân nặng của các phủ chu trình đều phải bằng 1. Mặc dù đã chuyển vấn đề từ ma trận về vấn đề đồ thị phần nào dễ hình dung hơn, chúng ta vẫn tuyệt nhiên không biết cách nào để (bằng thuật toán) kiểm tra xem có phép gán hệ số như mong muốn hay không. Vazirani và Yannakakis [40] lại sắp xếp tiếp bài toán này. Bổ đề 3.4 (Vazirani-Yannakakis, 1988). Cho một đồ thị có hướng D = ([n], E) với n vòng (i, i) ∈ E. Tồn tại một phép gán hệ số w : Eo˜{−1, 1} sao cho tất cả các phủ chu trình của D đều có cân nặng bằng 1 nếu và chỉ nếu tồn tại một phép gán hệ số w : Eo˜{−1, 1} sao cho, với mỗi chu trình C của D, thì có một số lẻ các cạnh của C với hệ số bằng 1. Chứng minh. Giả sử tồn tại phép gán hệ số sao cho mỗi chu trình C của D đều có một số lẻ các cạnh với hệ số bằng 1. Như vậy, một chu trình lẻ có một số chẵn các hệ số −1; và một chu trình chẵn có một số lẻ các hệ số −1. Gọi π là một phủ chu trình 23Cycle cover. 42 Tạp chí Epsilon, Số 03, 06/2015. bất kỳ của D. Từ Bài tập 2.1, ta biết sgn(π) = (−1)ctrong đó c là số các chu trình chẵn của π. Từ đó, dễ thấy w(π) = 1. Ngược lại, giả sử tồn tại một phép gán hệ số sao cho tất cả các phủ chu trình đều có cân nặng là 1. Gọi C là một chu trình bất kỳ của D. Nếu ta lấy C, cùng với các vòng (i, i) với mọi i /∈ C, thì ta có một phủ chu trình π. Nếu C là chu trình lẻ, thì sgn(π) = 1 – do π không có chu trình chẵn. Vì thế, phải có một số chẵn các hệ số −1 trên chu trình C. Ngược lại, nếu C là chu trình chẵn thì sgn(π) = −1. Vì thế, phải có một số lẻ các hệ số −1 trên C. Đến đây thì vấn đề rõ ràng hơn một chút. Tuy nhiên, kể cả khi ai đó cho ta một phép gán hệ số thì ta cũng không biết cách nào để kiểm tra một cách hiệu quả xem phép gán hệ số đó có tốt hay không. Tại vì, tổng số các chu trình của một đồ thị cho trước có thể làm hàm mũ. Ta không thể đi kiểm tra từng chu trình một được. Đó là chưa nói đến chuyện phải đi qua tất cả các phép gán hệ số {−1, 1}. Định nghĩa 3.5. Một đồ thị có hướng D được gọi là đồ thị chẵn nếu, với mọi phép gán hệ số {−1, 1} vào các cạnh của D, luôn tồn tại một chu trình của D có một số chẵn các hệ số 1. Bổ đề Vazirani-Yannakakis ở trên đã cho ta biết câu hỏi của Pólya tương đương với câu hỏi kiểm tra xem một đồ thị có hướng có phải đồ thị chẵn hay không. Năm 1987, Paul Seymour và Carsten Thomassen [29] nghiên cứu các ma trận không kỳ dị về dấu, và đã chứng minh rằng, tồn tại một đồ thị có hướng H sao cho D là đồ thị chẵn nếu và chỉ nếu H có một chu trình với một số chẵn các cạnh. Và H có thể xây dựng được từ D trong thời gian đa thức. Như vậy, ta có Định lý 3.6. Câu hỏi của Pólya tương đương về mặt thuật toán với bài toán xác minh xem một đồ thị có hướng H có một chu trình với sỗ chẵn các cạnh hay không. Chứng minh định lý trên không tầm thường, mặc dù cũng không phải quá khó. Xem thêm phần Chú Thích ở cuối bài và các tham khảo từ đó. Câu hỏi của Pólya đã trở thành một câu hỏi rất rõ ràng về mặt tổ hợp, nhưng ta vẫn hoàn toàn không biết cách trả lời câu hỏi trong thời gian đa thức. Cuối cùng, đến năm 1999 thì Robertson, Seymour, và Thomas [26] thiết kế thuật toán trả lời câu hỏi này trong thời gian đa 43 Tạp chí Epsilon, Số 03, 06/2015. thức. Bài báo này ở tờ Annals of Mathematics. Như vậy là sau 86 năm, câu hỏi của Pólya đã được trả lời thoả đáng. Không những thế, như sẽ được đề cập ở phần tới của bài, câu hỏi này có liên quan mật thiết đến một đối tượng đại số tuyến tính khác – định thức Pfaff – quyến rũ không kém định thức và vĩnh thức. 4. Định thức Pfaff Cũng như vĩnh thức và định thức, định thức Pfaff là một đa thức đa biến, với các biến là các phần tử của một ma trận vuông. Trong phần này của bài viết, tôi sẽ giải thích tại sao Định thức Pfaff liên quan đến định thức, đến tổng số cách bắt cặp hoàn hảo của một đồ thị cho trước, và đo đó liên đới đến vĩnh thức. 4.1. Định thức Pfaff Gọi n là một số nguyên dương chẵn. Gọi Fn là tập tất cả các phân hoạch của [n] thành n/2 cặp số. Như vậy, mỗi thành viên F ∈ Fn là một tập n/2 cặp (i, j), i < j, sao cho tất cả các số trong [n] điều thuộc về một cặp nào đó của F. Hai cặp (i, j),(i0, j0) ∈ F được gọi là hai cặp cắt nhau24 nếu i < i0 < j < j0. Đơn giản là nếu ta vẽ hai cung từ i đến j và từ i0 đến j0thì chúng cắt nhau, như hình sau đây. i i0 j j0 Gọi χ(F) là tổng số cặp cắt nhau trong F. Định thức Pfaff được định nghĩa như sau. Gọi A = (aij ) là một ma trận phản xứng25, nghĩa là A = −AT, thì định thức Pfaff của A, ký hiệu là Pf(A), được định nghĩa là aij . (3.10) 24Crossing. Pf(A) = X F ∈Fn (−1)χ(F) Y (i,j)∈F 25Anti-symmetric, cũng gọi là skew-symmetric 44 Tạp chí Epsilon, Số 03, 06/2015. Bài tập 4.1. Có một cách khác để định nghĩa “dấu” của một thành viên F ∈ Fn. Giả sử F = {i1, j1}, · · · {in/2, jn/2} , trong đó i` < j` với mọi ` ∈ [n/2]. Gọi π là hoán vị sau đây π = 1 2 3 4 · · · n − 1 n i1 j1 i2 j2 · · · in/2 jn/2 Chứng minh rằng (−1)χ(F) = sgn(π). (Trong một số sách bạn đọc sẽ thấy họ dùng sgn(π) thay vì (−1)χ(F) để định nghĩa định thức Pfaff.) Theo quyển “Chứng minh và khẳng định”26 của David M. Bres soud [5] thì các tổng dạng định thức Pfaff xuất hiên đầu tiên từ một bài báo của Johann Friedrich Pfaff từ năm 1815. Ông mô tả một phương pháp giải một hệ 2n phương trình vi phân bậc nhất bằng cách dùng biến và phương trình phụ trợ. Các phương trình phụ trợ này gồm tổng của một số tỉ lệ mà tử số là các định thức Pfaff. Lúc đó Pfaff đã gần 50 tuổi, và công trình của ông cũng không được đọc rộng rãi cho đến khi Carl Gustav Jacob Jacobi viết một bài về phương pháp của Pfaff. Định thức Pfaff liên hệ mật thiết đến các ma trận phản xứng. Các người khổng lồ Poisson, Lagrange, Laplace, và Monge đã làm việc với các ma trận này trong nửa đầu thế kỷ 18. Nhưng phải đến Ja cobi mới nhận ra được liên hệ giữa định thức Pfaff và định thức của một ma trận. Mà kể cả như vậy, thì cũng phải chờ đến Arthur Cayley (1847) thì người ta mới biết đến đẳng thức quan trọng det(A) = Pf(A)2. Trên Wikipedia thì nói đẳng thức này do Thomas Muir chứng minh trong quyển sách của ông về định thức năm 1882. Nhưng tôi tin Bressoud đúng! Duyệt nhanh qua quyển sách của Muir thì hơi khó khẳng định vì ông không viết theo kiểu ai đã chứng minh cái gì. Chúng ta chứng minh đẳng thức này ở đây dùng phương pháp tổ hợp của John Stembridge [30]; đây là một bài báo thật sự là tuyệt hảo trong toán tổ hợp đếm. Định lý 4.2 (Cayley, 1847). Gọi A là một ma trận phản xứng n × n với n chẵn. Ta có, det(A) = Pf(A)2. 26Proofs and confirmations 45 Tạp chí Epsilon, Số 03, 06/2015. Chứng minh của John Stembridge. Trước hết, chúng ta viết lại vế trái của đẳng thức trên dùng thêm kiến thức là A là ma trận phản xứng. Khi ta khai triển định thức det(A) = X π∈Sn sgn(π)Yn i=1 aiπ(i) thì sẽ có nhiều cặp số hạng bù trừ lẫn nhau vì A là ma trận phản xứng. Cụ thể hơn, giả sử có một chu trình C của π là chu trình lẻ (như chu trình (1 8 4) trong Hình 3.2). Gọi π0là hoán vị có các chu trình giống hệt như π, ngoại trừ chu trình lẻ C bị đảo chiều. Khi đó, sgn(π) = sgn(π0), và Qni=1 aiπ(i) = −Qni=1 aiπ0(i). Như vậy hai số hạng tương ứng với π và π0 bù trừ lẫn nhau. Ta có thể bắt cặp các hoán vị trong Sn bằng cách này. Nếu π có một chu trình lẻ, thì ta lấy chu trình lẻ có chứa số bé nhất trong các chu trình lẻ, rồi đảo chiều chu trình lẻ này để lấy π0. Đây là một bắt cặp hoàn hảo giữa các hoán vị có (ít nhất một) chu trình lẻ. Do đó, gọi En ⊆ Sn là tập tất cả các hoán vị của [n] với toàn chu trình chẵn, ta có det(A) = X π∈En (−1)e(π)Yn i=1 aiπ(i). (3.11) (Nhớ rằng, như đã định nghĩa trong Bài tập 2.1, e(π) là số chu trình chẵn của π.) Bây giờ ta viết lại vế phải của đẳng thức cần chứng minh. Pf(A)2 =  X (−1)χ(F) Y aij   ·  X (−1)χ(F0) Y ai0j0   F ∈Fn (i,j)∈F  F0∈Fn   (i0,j0)∈F0  =X (F,F0)∈Fn×Fn (−1)χ(F)+χ(F0) Y (i,j)∈F aij  · Y (i0,j0)∈F0 ai0j0  =X (F,F0)∈Fn×Fn (−1)χ(F)+χ(F0) Y (i,j)∈F ∪F0 aij . Kế hoạch là tìm một song ánh giữa En và Fn × Fn sao cho, với mỗi π ∈ En có duy nhất một cặp (F, F0) tương ứng (và ngược lại) để có đẳng thức sau đây là xong: (−1)e(π)Yn i=1 aiπ(i) = (−1)χ(F)+χ(F0) Y (i,j)∈F ∪F0 46 aij . (3.12) Tạp chí Epsilon, Số 03, 06/2015. Tìm một song ánh giữa En và Fn × Fn là điều rất dễ hàng. Một cặp (F, F0) ∈ Fn × Fn là một cặp (có thứ tự) bắt cặp hoàn hảo các số trong [n]. Ta gọi các cạnh của F là cạnh xanh và cạnh của F0là cạnh đỏ. Có tất cả n/2 cạnh xanh, n/2 cạnh đỏ, và tập các cạnh cùng màu là một bắt cặp hoàn hảo. Khi ta vẽ cả các cạnh xanh và đỏ vào cùng một đồ thị với [n] là tập đỉnh, thì mỗi đỉnh có bậc bằng đúng 2. Cụ thể hơn thì mỗi đỉnh kề với một cạnh xanh và một cạnh đỏ. Do đó, tập n cạnh này tạo thành một phủ chu trình của [n]. Mỗi chu trình trong phủ chu trình này có chiều dài chẵn, vì nếu ta đi vòng theo mỗi chu trình ta gặp các màu xanh và đỏ luân phiên nhau. Cho đến đây thì ta vẫn chưa được một hoán vị vì phủ chu trình này chưa có hướng. Để định hướng cho mỗi chu trình thì ta bắt đầu từ đỉnh nhỏ nhất của chu trình, và đi theo cạnh xanh trước. Dễ thấy đây là song ánh, vì cho trước một phủ chu trình π ∈ En, ta làm ngược lại: đi từ đỉnh nhỏ nhất của mỗi chu trình, và tô màu xanh đỏ thay phiên nhau cho các cạnh. Hình 3.4 minh họa song ánh này. Ta gọi song ánh này là song ánh Stem bridge. 1 2 3 4 5 6 7 8 Tương ứng với hoán vị π = (5 4 1 2 7 6 8 3) Hình 3.4: Song ánh giữa En và Fn × Fn Như vậy, điều duy nhất còn lại để chứng minh là chứng minh rằng sgn(π) có cùng “dấu” với cặp ảnh (F, F0) của nó trong song ánh Stembridge. Với π ∈ En, gọi r(π) = {i | π(i) < i} thì đẳng thức cần chứng minh (3.12) tương đương với e(π) + r(π) = χ(F) + χ(F0) (mod 2). (3.13) Ví dụ, đẳng thức này tất nhiên là đúng với π = (2 1 4 3 . . . n n−1) vì khi đó e(π) = n/2 và r(π) = n/2. Bây giờ giả sử (3.13) đúng với một hoán vị π nào đó, ta chứng minh là nó cũng đúng với hoán vị liên hợp σ = (i i + 1) ◦ π ◦ (i i + 1)−1. Gọi (F, F0) là ảnh của π. Ta phân biệt hai trường hợp: 47 Tạp chí Epsilon, Số 03, 06/2015. • Nếu i và i+1 nằm kề nhau trong cùng một chu trình của π, thì hoán chuyển i và i + 1 ta sẽ thay đổi r(π) mod 2, nhưng giữ nguyên e(π). Không khó để thấy rằng ta cũng thay đổi hoặc là χ(F) mod 2 hoặc là χ(F0) mod 2, nhưng không thay đổi cả hai. Ví dụ, nếu giữa i và i+1 có một cạnh màu xanh, thì hoán chuyển vị trí của i và i + 1 sẽ không thay đổi số điểm cắt nhau của các cạnh màu xanh. Còn i và i + 1 sẽ kề với hai cạnh màu đỏ khác nhau. Nếu chúng không cắt nhau thì sẽ cắt nhau sau khi hoán chuyển, và nếu chúng đã cắt nhau thì sẽ không cắt nhau sau khi hoán chuyển. • Nếu i và i+1 không nằm kề nhau trong cùng một chu trình của π thì hoán chuyển i và i + 1 sẽ giữ r(π) (và e(π)) nguyên trạng; nhưng lần này cả χ(F) và χ(F0) đều thay đổi. Như vậy, để chứng minh (3.13) đúng cho π, ta chỉ cần chứng minh (3.13) đúng cho σ – miễn là ta có thể chuyển π thành σ bằng (nhiều lần) đổi chỗ hai số nguyên liên tiếp. Mà bằng cách đổi chỗ hai số nguyên liên tiếp thì ta có thể chuyển π thành một hoán vị mà chu trình thứ nhất C1 chứa các số nguyên nhỏ nhất {1, 2, . . . , |C1|}, chu trình thứ hai chứa các số nguyên kế tiếp, theo cùng thứ tự, vân vân. Dễ thấy rằng (3.13) đúng với σ thoả tính chất này. 4.2. Định hướng Pfaff Gọi A = (aij ) là ma trận kề27 của một đồ thị vô hướng G = (V, E), nghĩa là aij = 1 nếu ij là một cạnh. Mỗi số hạng (−1)χ(F) Qij∈Faij của khai triển định thức Pfaff của A khác 0 nếu và chỉ nếu F là một bắt cặp hoàn hảo của G. Tiếc là A là ma trận đối xứng chứ không phải ma trận phản xứng. Năm 1961, các nhà Vật lý Pieter Kasteleyn [14, 15] (người Hà Lan), Harold Neville Vazeille Temperley và Michael Fisher [32] (người Anh) nhận ra một ý tưởng đơn giản. Giả sử ta định hướng các cạnh ij của G, và gán aij = 1 nếu ioj˜ còn aij = −1 nếu joi˜ , thì ma trận A của định hướng của G là ma trận phản xứng. Khi đó, nếu tồn tại một định hướng của G sao cho tất cả các số hạng khác 0 của khai triển định thức Pfaff của A đều có cùng dấu, thì khi đó Định Lý 4.2 sẽ cho ta cách đếm nhanh số các bắt cặp hoàn hảo của đồ thị G dùng định thức! Một định hướng của G thoả tính chất 27Adjacency matrix. 48 Tạp chí Epsilon, Số 03, 06/2015. này gọi là định hướng Pfaffian của đồ thị. Và, thuật toán này bây giờ ta gọi là thuật toán FKT. Hai câu hỏi ta cần trả lời là: • Khi nào thì tồn tại một định hướng Pfaff cho G? • Nếu biết định hướng Pfaff tồn tại, thì làm thế nào để tìm nó một cách hiệu quả? Để tìm cách trả lời các câu hỏi này, ta tìm một miêu tả mang tính tổ hợp hơn của định hướng Pfaff. Một chu trình C của G là một chu trình tốt nếu nó có số chẵn các đỉnh và có một bắt cặp hoàn hảo trong đồ thị G − C. Cho một định hướng −→G của G thì chu trình C được gọi là chu trình định hướng lẻ nếu đi vòng quanh C theo một chiều nhất định thì số mũi tên xuôi chiều ta thấy là số lẻ. Tất nhiên, vì C chẵn nên khi ta đi theo chiều ngược lại thì số mũi tên xuôi chiều cũng là số lẻ. Bổ đề 4.3. Cho −→G là một định hướng của G, thì −→G là định hướng Pfaff nếu và chỉ nếu tất cả các chu trình tốt của G đều được −→G định hướng lẻ. Chứng minh. Gọi A là ma trận kề của −→G, nghĩa là aij = 1 nếu (i, j) ∈ E(−→G), aij = −1 nếu (j, i) ∈ E(−→G), ngoài ra thì aij = 0. Gọi F và F0là hai bắt cặp hoàn hảo của G, thì −→G là định hướng Pfaff nếu và chỉ nếu (−1)χ(F) Y (i,j)∈F aij = (−1)χ(F0) Y (i0,j0)∈F0 ai0j0, với mọi cặp (F, F0). Đẳng thức này tương đương với (−1)χ(F)+χ(F0) Y (i,j)∈F ∪F0 aij = 1. (3.14) Lưu ý rằng F, F0 ∈ Fn, và nếu (i, j) ∈ F ∪F0thì i < j. Gọi π là ảnh của (F, F0) trong song ánh Stembridge. Từ đẳng thức (3.13), ta suy ra (3.14) tương đương với (−1)e(π)+r(π) Y (i,j)∈F ∪F0 aij = 1. (3.15) Đến đây, ta bắt đầu chứng minh chiều thuận của bổ đề. Giả sử −→G là một định hướng Pfaff của G. Gọi C là một chu trình 49 Tạp chí Epsilon, Số 03, 06/2015. tốt. Gọi M là một bắt cặp hoàn hảo của G − C. Ta có thể tách C ra thành hai bắt cặp C1 và C2 bằng cách đi vòng theo C, bỏ một cạnh vào C1, cạnh kế vào C2, luân phiên nhau. Định nghĩa F = M ∪ C1 và F0 = M ∪ C2, thì F và F0là hai bắt cặp hoàn hảo của G. Gọi π là ảnh của cặp (F, F0) qua song ánh Stembridge, thì như phân tích ở trên đẳng thức (3.15) được thoả mãn. Gọi V (C) là tập các đỉnh của C, và E(C) là tập các cạnh. Định nghĩa r(C) = |{i ∈ V (C) | π(i) < i}|. Dễ thấy rằng e(π) = |M| + 1 r(π) = |M| + r(C). Định nghĩa s(i, j) = ( 1 i < j −1 j ≥ i. Do A là ma trận phản xứng, nếu i < j ta có aij = s(i, j)aij và nếu j < i ta có aji = s(i, j)aij . Vì thế, Y (i,j)∈F ∪F0 =Y ij∈E(C) i