HOW and WHAT makes your life!: Lấy người mình yêu và định lý Birkoff

Khi bé, bạn đi nhà trẻ. Lớn lên, bạn phải lấy vợ. Kiểu gì cũng không tránh được, trừ các vĩ nhân.
Chuyện lấy vợ ngày xưa rất đơn giản. Một ngày đẹp trời, bố khề khà nói với…mẹ “Tôi xem con Sứt con ông phó cối đầu ngõ chăm chỉ đáo để….” Thế là vài tháng sau bạn sẽ là chồng của cô Sứt, và ngày ngày đóng cối….
Chuyên bây giờ không đơn giản như thế nữa. Bạn có tự do, có quyền theo đuổi tình yêu, chắp cánh bay xa, vv. Phải lấy người mình yêu, chà !
Trớ trêu, người bạn yêu (như Angelina Jolie) thì vô số bạn khác cũng yêu. Thế mới cáu. Nhưng không sao, chuyện này các ông Tây cũng đã nghĩ tới, chẳng phải vì cô Angelina là Tây, mà ở bên Tây luật một vợ một chồng có sớm hơn ta, nên các bác ấy phải đi trước một bước, âu cũng là cực chẳng đã.
Các ông Tây giải quyết vấn đề như sau: Thay vì mỗi Angelina, mỗi ông lên một danh sách gồm các cô có thể đưa vào tầm ngắm. Danh sách này sẽ ngắn dài gầy béo tùy theo khả năng và sở thích mối người. Câu hỏi đặt ra là: Khi nào bạn có thể lấy được một
người trong danh sách của bạn mà không dẫn đến một cuộc đọ súng đọ kiếm hay đọ một cái gì với các bạn khác ?
Điều kiện cần của bài toán tương đối dễ xác định. Tưởng tượng cô Mít và cô Đào rất “hot”, và là ý trung nhân của các anh Mai, Thuổng và Xẻng. Thế là hai thục nữ nhưng những ba anh hùng, kiếu gì cũng không ổn. Nói tổng quát, nếu danh sách của $k$ chàng tổng cộng lại chỉ có $\le k-1$ nàng, thì thế nào cũng dẫn đến mâu thuẫn khó giải quyết. Vậy điều kiện cần của bài toán Lấy (một trong những) Người Mình Yêu là:
(1) Vơi mọi $k$ , danh sách của bât kỳ $k$ chàng trai nào tổng cộng lai phải có ít nhất $k$ cô gái.
Định lý Lấy Người Mình Yêu của Hall (Hall Marriage’s thẻoem) nói rằng đây cũng là điều kiện đủ.
Định lý Hall (1) là điều kiện đủ.
Đjinh lý này có thể phảt biểu dươi dạng đồ thị. Ta biểu diễn các chàng trai bằng chấm màu đỏ và các cô gái bằng chấm màu xanh. Đồ thị $G$ có các cạnh giữa chấm xanh và chấm đỏ, $A$ nối với $B$ nếu nàng $B$ ở trong danh sách của chàng $A$ . Một “perfect matching” là một tập các cạnh không dính nhau phủ hết các đỉnh đỏ.
Định lý Hall. $G$ có perfect matching khi và chỉ khi vơi mọi $k$ , với mọi tập đỏ $S$ với $k$ phần tử, số đỉnh xanh nối vởi $S$ ít nhất là $k$ .
Định lý Hall chứng minh không khó, bạn có thể thử dưới dạng bài tập. Trong phần còn lại của bài, ta sẽ dùng định lý Hall để chứng minh một trong những định lý quan trọng nhất trong đại số tuyến tính: định lý Birkoff. Để phát biếu định lý này, ta cần một khái niệm. Một ma trận $n \times n$ được gọi là doubly stochastic nếu các phần tử là số không âm và tổng mối hàng và mỗi cột là một. Nếu ta biếu diễn ma trận đưới dạng một điểm trong không gian $R^{n^2}$ thì các ma trận DS tạo thành một tập lồi; chính xác hơn, một đa diện lồi $S$ . Câu hỏi đặt ra là: tìm đỉnh của đa diện này. Câu hỏi này quan trọng, vì trong rất nhiều bài toán cực trị, giá trị cực trị được đạt được trên các đỉnh.
Birkoff tìm ra câu trả lời rất đẹp cho câu hỏi này. Một ma trận DS được gọi là “permutation matrix” nếu mỗi hàng và mỗi cột có chính xác một số một (còn lại là không). Bạn có thể dễ dàng thấy rằng mối PM tương đương với một phần tử $\sigma$ của nhóm giao hoán $S_n$ . Bạn cũng có thể dễ dàng chứng minh các PM là đỉnh của đa diện $S$ . Birkoff chứng minh rằng ngoài ra không còn đỉnh nào khác.
Định lý Birkoff. Tập PM là các đỉnh duy nhất của đa diện $S$ .
Giả sử $A$ là một ma trận với phần tử $a_{ij}$ . Với mỗi giao hoán $\sigma$ , ta gọi dãy $a_{1 \sigma (1)}, \dot, a_{n \sigma n}$ là một diagonal của $A$ . Bạn có thể dùng định lý Hall để chứng minh bổ đề sau
{ Bổ đề.} Nếu mỗi diagonal của $A$ có ít nhất một số $0$ thì $A$ có một $k \times l$ ma trận con với các phần tử đều bằng $0$ và $k+l > n$ .
Chứng minh định lý Birkoff. Giả sử $A$ là một điểm trong $S$ . Ta sẽ chứng minh $A$ có thể viết đưới dạng $\sum_{i=1}^m \lambda_i M_i$ , với $\sum_I \lambda_i=1, \lambda_i \ge 0$ và $M_i$ là PM. Ta qui nạp theo số phần tử dương của $A$ . Nếu $A$ có $n$ phần tử dương thì nó là một PM. Giả sử $A$ có $m \ge n+1$ phần tử dương. Bạn có thể dễ dàng kiểm tra là một ma trận DS không thể có một ma trận con như trong bổ đề (bài tập). Như vậy, ta có một diagonal gồm toàn số dương. Diagonal này gắn với một phép giao hoán $\sigma$ , và qua đó, một PM $P$ . Gọi $a$ là giá trị (dương) nhỏ nhất trong diagonal trên và $B: = \frac{A- aP}{1-a}.$
$B$ cũng là một DS matrix. Ngoài ra sồ phần tử dương của nó $\le m-1$ . Vậy $B$ có thể biểu diến dưới dạng $\sum_{i=1}^m \lambda_i M_i$ . Nhưng, $A = (1-a) B + aP$ . QED

Homework for combinatorics 1 (part 2)

(1) Let $S$ be a set of at least $n+2$ points in $R^n$ . Prove that $S$ can be partitioned into two subsets whose convex hulls intersect.
(2) Let $C_1, \dots, C_m$ be convex sets in $R^n$ such that any $n+1$ of them intersect. Prove that all of them intersect.
(3) Let $p$ be a fixed prime. Construct a family of $\Omega (n^3)$ subsets of $\{1, \dots, n \}$ such that each has cardinality $p^3$ but any two has intersection
either 0, 1, $p$ or $p^2$ .
(4)* Let $F$ be a family of subsets of $\{1, \dots, n \}$ such that the intersection of any three is even. Prove that for all sufficiently large $n$ , $|F| \le 2^{n/2}$ .
(*) is a bonus problem, it does not count if you cannot do it, but if you can, I am willing to hear the solution.

HOW and WHAT makes your life!

Chủ Nhật, 25 tháng 3, 2012

Lấy người mình yêu và định lý Birkoff

Homework for combinatorics 1 (part 2)

Không có nhận xét nào:

Đăng nhận xét

Trang