Birkhoff Polytope

定义 Definition

Birkhoff 多面体（也常称为置换矩阵多面体）是由所有 \(n\times n\) 双随机矩阵（每个元素非负、每一行与每一列的和都等于 1）构成的凸多面体。它的极点正好是所有 \(n\times n\) 的置换矩阵；这一事实与 Birkhoff–von Neumann 定理密切相关。

发音 Pronunciation

/ˈbɝːk.hɔːf/ /ˈpɑː.li.toʊp/

例句 Examples

The Birkhoff polytope is the set of all doubly stochastic matrices of size \(n\).
Birkhoff 多面体是由所有 \(n\) 阶双随机矩阵组成的集合。

In assignment problems, optimizing a linear objective over the Birkhoff polytope often yields a permutation matrix as an optimal extreme point.
在指派问题中，在 Birkhoff 多面体上对线性目标进行优化时，最优解常常出现在某个置换矩阵这一极点上。

词源 Etymology

该术语以美国数学家 Garrett Birkhoff（加勒特·伯克霍夫）命名；“polytope”源自希腊语，意为“多面体”。Birkhoff 多面体的核心性质通常通过 Birkhoff–von Neumann 定理表述：任意双随机矩阵都可以表示为置换矩阵的凸组合。

相关词 Related Words

• Assignment
• Birkhoff–von Neumann Theorem
• Convex
• Doubly Stochastic Matrix
• Extreme Point
• Linear Programming
• Permutation Matrix
• Polytope

文学与著作中的用例 Literary Works

• Brualdi, Combinatorial Matrix Classes：讨论双随机矩阵与置换矩阵的结构时常涉及 Birkhoff 多面体。
• Schrijver, Combinatorial Optimization: Polyhedra and Efficiency：在多面体方法与指派问题的章节中出现 Birkhoff（置换）多面体。
• Papadimitriou & Steiglitz, Combinatorial Optimization: Algorithms and Complexity：以指派问题/线性规划松弛为背景，常提到双随机矩阵与对应的多面体观点。