Questions tagged [birkhoff-polytopes]

The Birkhoff polytope is a convex polytope whose points are doubly stochastic matrices and whose vertices are permutation matrices.

Filter by
Sorted by
Tagged with
1
vote
1answer
37 views

Prove that the set of doubly stochastic $3 \times 3$ matrices is a polyhedron

Let $B_3$ be the set of $3 \times 3$ matrices $M$ with non-negative entries whose rows and columns all add up to $1$. Show that $B_3$ is a polyhedron. Hint: represent a matrix $M$ as a vector $x$ ...
7
votes
1answer
90 views

How wide is the Birkhoff Polytope?

Now also posted on Math Overflow. Define the width of a polytope $P \subset \mathbb R^d$ as the minimum length of the interval $\{v \cdot p:p \in P\}$ for $v$ in the unit sphere. In other words the ...
0
votes
0answers
44 views

Proof of Birkhoff-von Neumann theorem using total unimodularity

How to prove the Birkhoff-von Neumann theorem using total unimodularity? Especially the following sufficiency condition (source): $\begin{array}{l}{\text { A matrix } A \text { is totally unimodular ...
2
votes
1answer
172 views

Proof involving the Birkhoff polytope

Setup: Fix $n$. Let $\mathcal{B}$ denote the $n$-dimensional Birkhoff polytope, i.e. the set of all $n \times n$ doubly stochastic matrices. There is a fixed natural number $N(n)$. We drop the ...
2
votes
1answer
55 views

Number of facets of the Birkhoff polytopes $B(n)$.

The wikipedia's page for Birkhoff polytope states that the polytope has $n^2$ facets, determined by the inequalities $x_{ij} \geq 0$, for $1 \leq i,j \leq n$. I've tried different things but can't see ...
0
votes
1answer
71 views

Project an orthogonal matrix onto the Birkhoff Polytope

It is known that the permutation matrices lie at the intersection of the orthogonal group $\mathbb{O}^N$ with the Birkhoff polytope $\mathbb{DS}^N$. It is also known that any non-negative matrix $X\in\...
5
votes
1answer
213 views

$n$-sphere enclosing the Birkhoff polytope

I am not a mathematician by training, so please feel free to correct my logic or descriptions when necessary: Let $P$ denote a $\textit{permutation matrix}$: $$ \begin{equation} P := \{X \in \{0,1\}^{...
5
votes
1answer
82 views

What are the facets of the Birkhoff Polytope when $n=2$?

I've read in several sources that the number of facets of the Birkhoff polytope $\mathcal{B}(n)$ is $n^2$. Is this supposed to hold when $n=2$? Since $\mathcal{B}(2)$ has dimension $1$, the facets ...
1
vote
1answer
194 views

Facets of the Birkhoff polytope

I recently became interested in the geometric structure of the Birkhoff polytope since it's connected to a problem that I'm working on. The Wikipedia article states that the Birkhoff polytope has $n^2$...
0
votes
1answer
62 views

Is there a representational face lattice for the tridiagonal Birkhoff polytope?

Is there a representational face lattice for the tridiagonal Birkhoff polytope of dimension d; i.e., $\Omega^t_{d+1}$? That is, is there a system of representing the faces of $\Omega^t_{d+1}$ so that ...
1
vote
1answer
74 views

Birkhoff decomposition with maximization objective.

Given a doubly-stochastic matrix $\pi$, Birkhoff-von Neumann theorem states that $\pi$ can be written as a convex combination of permutation matrices: $$\pi=\sum_{i\leq k} \alpha_i B_i$$ where $\...
2
votes
0answers
91 views

Why is calculating the volume of the Birkhoff polytope complicated?

It is known that calculating the volume of the Birkhoff polytope in higher dimension is still open. I am not very good at it. I am trying to understand why it is complicated. It would be really ...
0
votes
1answer
112 views

Birkhoff-von Neumann Proof inequality explanation

https://staff.fnwi.uva.nl/n.s.walton/Notes/Hall_Birkhoff.pdf Could someone possible explain how the inequality arises in $(44)$?
2
votes
0answers
510 views

My proof of Birkhoff–von Neumann theorem whit a probabilistic point of view

I have just found a very beautiful and short proof for the birkhoff-von Neuman theorem that gives a new probabilistic approach. Notations : Let, $S_{n}$ be the set of permutations of the set {$1,...,...
8
votes
0answers
143 views

Birkhoff representation of a stochastic matrix

From the Birkhoff theorem, it is known that every doubly stochastic matrix can be written as a convex combination of permutation matrices, although this representation might not be unique. Assume ...
1
vote
1answer
85 views

Count and description of vertices of certain faces - called MTBFs - of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$

For $k \ge 1$, $d \ge 2$ and $k \le d - 1$, let ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ be the intersection of $k - 1$ facets of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$ with equations: $a_{...
1
vote
1answer
96 views

What are the facets of the Tridiagonal Birkhoff $d$-polytope $\Omega^t_{d+1}$?

The Birkhoff $d$-polytope $\Omega_{d+1}$ is the convex polytope in $\mathbb{R}^{d+1}$ $\times$ $\mathbb{R}^{d+1}$ of doubly stochastic matrices: • All matrices contained in $\Omega_{d+1}$ have non-...
3
votes
1answer
563 views

Projection onto Birkhoff Polytope

Suppose we would like to compute the Euclidean projection of an arbitrary matrix $A$ onto the Birkhoff polytope, the set of doubly-stochastic matrices. Under some conditions on $A$, Sinkhorn's ...
10
votes
1answer
1k views

Proof that the set of doubly-stochastic matrices forms a convex polytope?

Does the set of all doubly-stochastic matrices form a convex polytope? In general, I wonder how the proofs of convexity and geometry can be established for sets of matrices of this kind? Anything to ...
8
votes
1answer
2k views

What's the algorithm of finding the convex combination of permutation matrices for a doubly stochastic matrix?

According to Birkhoff, $n$-by-$n$ stochastic matrices form a convex polytope whose extreme points are precisely the permutation matrices. It implies that any doubly stochastic matrix can be written as ...
27
votes
2answers
2k views

Does Birkhoff - von Neumann imply any of the fundamental theorems in combinatorics?

I recently had the occasion to think about Hall's Marriage Theorem for the first time since my undergraduate combinatorics class more than a decade ago. Reading the wikipedia article linked above, I ...
10
votes
3answers
4k views

How do I Generate Doubly-Stochastic Matrices Uniform Randomly?

A doubly-stochastic matrix is an $n\times n$ matrix $P$ such that $\displaystyle\sum_{i=1}^n{p_{ij}}=1$ and $\displaystyle\sum_{j=1}^n{p_{ij}}=1$ where $p_{ij}\ge 0$. Can someone suggest an ...