5
$\begingroup$

Given the following polyhedron: All the $n\times n$ matrices $\boldsymbol{X}$ with elements $x_{ij}\in(0,1)$ such that $$\boldsymbol{X}\cdot\boldsymbol{1}=\boldsymbol{r}, \boldsymbol{1}^T\boldsymbol{X}=\boldsymbol{c}^T$$

For some given vectors $\boldsymbol{r}$ and $\boldsymbol{c}$.

Can I calculate the volume of this polyhedron? Can I calculate it's surface?

$\endgroup$
11
$\begingroup$

When $\boldsymbol{r}=\boldsymbol{c}=(1,1,\dots,1)$ the polytope $X$ is the Birkhoff polytope of $n\times n$ doubly-stochastic matrices. Computing its $(n-1)^2$-dimensional volume is a well-known difficult problem. An answer is given by De Loera, Liu, and Yoshida in http://arxiv.org/abs/math/0701866, but it is quite a complicated formula. For generalizing it to $\boldsymbol{r}$ and $\boldsymbol{c}$ and to higher dimension, see De Loera's survey at http://arxiv.org/pdf/1307.0124.pdf. For additional information in the case of the Birkhoff polytope, see OEIS A078524, A078525, A037302.

$\endgroup$
1
$\begingroup$

The volume can be approximated by MCMC algorithms, see https://arxiv.org/abs/1312.2873 for estimations for $n\leq 15$. Also see https://arxiv.org/abs/0705.2422 for an asymptotic formula.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.