Hình đa diện Birkhoff

Bài này viết về địnhlý Birkhoff cho đại số ma trận, các định lý khác xem Định lý Birkhoff (định hướng)

Hình đa diện Birkhoff là một vấn đề được tìm ra năm 1946, tuy nhiên, kết quả đầu tiên của nó đã được tìm ra từ năm 1916 bởi Dénes König và sau đó được bổ sung bởi nhà toán học Mỹ John von Newmann vào năm 1953. Giống như định lý König, định lý này có thể được diễn dịch qua một dòng chảy mạng (network flow) trở thành một công thức cho lập trình tuyến tính (xem Lý thuyết đối ngẫu (lập trình tuyến tính)).

Các khái niệm

• Ma trận ngẫu nhiên kép là ma trận mà các số hạng của nó là không âm và tổng số của các số hạng trên mỗi hàng hay mỗi cột đều bằng 1.
• Ma trận hoán vị là ma trận mà mỗi hàng hay mỗi cột của nó chỉ có duy nhất một số hạng có giá trị bằng 1, còn lại các số hạng khác đều bằng 0.

Phát biểu vấn đề

Mọi ma trận ngẫu nhiên kép đều là một tổ hợp lồi của các ma trận hoán vị

Xem thêm

• Định lý Carathéodory

Liên kết ngoài

• Birkhoff polytope Web site by Dennis Pixton and Matthias Beck, with links to articles and volumes.