3
$\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$
9
$\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$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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