Min. Birkhoff Decomposition

The Minimum Birkhoff Decomposition problem seeks to express a doubly stochastic matrix as a minimal convex combination of permutation matrices. This problem arises in various applications including assignment problems, scheduling, and quantum physics.

Problem Description

Definitions:

• A doubly stochastic matrix $D \in \mathbb{R}^{n \times n}$ has non-negative entries where all rows and columns sum to one
• A permutation matrix $P_i$ is a doubly stochastic matrix with binary entries
• Let $P_1, \ldots, P_{n!}$ denote all possible $n \times n$ permutation matrices

Optimization Problem:

For a given doubly stochastic matrix $D$, find:

$$ \underset{\lambda_i \in [0,1]}{\text{minimize}} \qquad \sum_{i=1}^{n!} |\lambda_i|^0 $$

subject to: $$ D = \sum_{i=1}^{n!} \lambda_i P_i, \qquad \sum_{i=1}^{n!} \lambda_i = 1 $$

where $0^0 = 0$ by convention.

Goal: Find the smallest number of permutation matrices whose convex combination equals $D$.