Questions tagged [birkhoff-polytopes]
The Birkhoff polytope is a convex polytope whose points are doubly stochastic matrices and whose vertices are permutation matrices.
35
questions
2
votes
0
answers
23
views
Can Sinkhorn's algorithm reach any point on the Birkhoff polytope?
It is well known that Sinkhorn's algorithm converges to a doubly stochastic matrix given a non-negative square input matrix.
Knowing that Sinkhorn's algorithm always produces a DSM, I am interested in ...
- 210
1
vote
2
answers
59
views
Orthogonal Projection onto the Convex Hull of Permutation Matrix
Given a matrix $\boldsymbol{Y} \in \mathbb{R}^{m \times n}$ where $n \leq m$.
I want to find its projection onto the Convex Hull of Permutation Matrices:
$$ \mathcal{P} = \left\{ \boldsymbol{P} \mid \...
- 9,067
4
votes
1
answer
222
views
The permutation matrices are the doubly stochastic matrices with the highest Frobenius norm
In a 2013 talk, Alexandre d'Aspremont did claim the following:
Among all doubly stochastic matrices, the rotations, hence, the permutation matrices, have the highest Frobenius norm
I had never ...
0
votes
0
answers
129
views
Birkhoff polytope vs permutation polyhedron
I cannot understand a few things about the Birkhoff polytope.
The Birkhoff polytope is defined as a polyhedron of all $n \times n$ doubly stochastic matrices. How is is it polytope then? To transform ...
- 1
1
vote
0
answers
56
views
Is there a short representation for the convex hull of all row and column permutations of a matrix?
Suppose $S$ is the set of all $n\times n$ permutation matrices. For a matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$ define the set $P(\mathbf{A})$ as the set of all equal row and column permutations of ...
- 11
2
votes
0
answers
64
views
Finding all integer solutions for a Linear Program over the Birkhoff Polytope
I have the situation where the Birkhoff Polytope is the space of all valid solutions to a linear function I am interested in maximizing. It is my understanding that, because the vertices of the ...
0
votes
0
answers
159
views
Confusion in one statement related to the Birkhoff polytope
I know that the set of doubly stochastic matrices $(\Omega(n))$ form a polyhedron. I only know about polyhedron is that it is a $3$-dimensional shape with flat polygonal faces, straight edges and ...
2
votes
1
answer
929
views
Prove that a matrix can be written as a sum of permutation matrices
Given a square matrix $A$ of size $n$ whose entries are non-negative integers and where the sum of each column and row is equal to $k$, prove that $A$ can be written as a sum of $k$ permutation ...
- 69
1
vote
1
answer
71
views
The optimal value function over all doubly stochastic matrices
Let $I = J = \{1,\dots,n\}$. Define set $X \subset \Bbb R^{I \times J}$ as all $n \times n$ doubly stochastic matrices $x = (x_{ij})$ satisfying
$$\sum_{j=1}^n x_{ij} = 1, \quad \forall i $$
$$\sum_{i=...
- 131
2
votes
0
answers
54
views
What is the linear description of a transformation of Birkhoff polytope?
Let $I, J$ be finite sets and $|I|=|J|=n$, Let $F$ be a Birkhoff polytope formed by the convex hull of $n\times n$ doubly stochastic matrices:
$$F=\{R^{I\times J}_+: \sum_j x( i,j)=1,\forall i\in I,
...
- 131
0
votes
0
answers
217
views
Finding optimal permutation via minimizing non-convex objective over Birkhoff polytope
Suppose function $f$ is non-convex and non-linear, $P$ is a permutation matrix and $x$ is input data. In this case, we consider a convex relaxation of $P$ by letting $P$ be in the set of doubly ...
- 277
2
votes
0
answers
52
views
Counting the number of facets of the alternating sign matrix polytopes ($ASM_n$).
I’m reading the following definitions and theorem on alternating sign matrices (ASMs).
Definition 1. Alternating sign matrices (ASMs) are square matrices with the following properties:
entries $\in\{...
- 2,317
2
votes
1
answer
520
views
Birkhoff-von Neumann Theorem
I am reading from Linear Algebra in Action by Dym and am working through the proof of the BvN Theorem. For the sake of clarity, ill write up everything until the point where I get lost.
Theorem: Let $...
- 83
0
votes
1
answer
192
views
Can every doubly stochastic be generated by the Sinkhorn Knopp algorithm?
I want to generate doubly stochastic matrices in a way that doesn't exclude any doubly stochastic matrix. At the moment I am generating an $n \times n$ matrix whose components are from a $\text{...
1
vote
1
answer
212
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$ in $\...
- 5,283
7
votes
1
answer
206
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 ...
- 10.5k
2
votes
1
answer
435
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 ...
- 1,491
2
votes
1
answer
174
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 ...
- 2,317
0
votes
1
answer
322
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\...
- 912
7
votes
1
answer
423
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\}^{...
- 912
5
votes
1
answer
200
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 ...
- 4,138
1
vote
1
answer
509
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$...
- 23
0
votes
1
answer
95
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,129
1
vote
1
answer
217
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
0
answers
116
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
1
answer
204
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)$?
- 143
2
votes
1
answer
852
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,...,...
7
votes
0
answers
294
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
1
answer
115
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,129
1
vote
1
answer
115
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-...
- 1,129
7
votes
3
answers
1k
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 ...
- 173
11
votes
1
answer
3k
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 ...
- 1,161
12
votes
2
answers
4k
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 ...
- 4,253
29
votes
2
answers
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 ...
- 98.7k
18
votes
3
answers
7k
views
How do I generate doubly-stochastic matrices uniform randomly?
A doubly-stochastic matrix is an $n \times n$ matrix $P$ such that
$$ \sum_{i=1}^n p_{ij} = \sum_{j=1}^n p_{ij} = 1 $$
where $p_{ij}\ge 0$. Can someone please suggest an algorithm for generating these ...
- 2,058