Volumes of the Birkhoff polytopes

edit · history · discussion · files · long url · combinatorics discrete geometry volume

Numbers

$n$

normalisation

volume

$\operatorname{vol}_{\mathrm{rel}}$:

$\operatorname{Vol}$:

$\operatorname{vol}_{\mathrm{Euc}}$:

$\operatorname{vol}_{\mathrm{rel}}$:

$\operatorname{Vol}$:

$\operatorname{vol}_{\mathrm{Euc}}$:

$\operatorname{vol}_{\mathrm{rel}}$:

1/8

$\operatorname{Vol}$:

$\operatorname{vol}_{\mathrm{Euc}}$:

9/8

$\operatorname{vol}_{\mathrm{rel}}$:

11/11340

$\operatorname{Vol}$:

352

$\operatorname{vol}_{\mathrm{Euc}}$:

176/2835

$\operatorname{vol}_{\mathrm{rel}}$:

188723/836911595520

$\operatorname{Vol}$:

4718075

$\operatorname{vol}_{\mathrm{Euc}}$:

23590375/167382319104

$\operatorname{vol}_{\mathrm{rel}}$:

9700106723/10258736801144832000000

$\operatorname{Vol}$:

14666561365176

$\operatorname{vol}_{\mathrm{Euc}}$:

9700106723/1319281996032000000

$\operatorname{vol}_{\mathrm{rel}}$:

225762910421308831/4709491654300668677115504230400000000

$\operatorname{Vol}$:

17832560768358341943028

$\operatorname{vol}_{\mathrm{Euc}}$:

77436678274508929033/13730296368223523839986892800000000

$\operatorname{vol}_{\mathrm{rel}}$:

5562533838576105333259507434329/264011225709317517739692779219312229551889249730560000000000

$\operatorname{Vol}$:

12816077964079346687829905128694016

$\operatorname{vol}_{\mathrm{Euc}}$:

5562533838576105333259507434329/125890362600954779500814809426933398033089280000000000

$\operatorname{vol}_{\mathrm{rel}}$:

559498129702796022246895686372766052475496691/9269262340995263649896514671280698429605195132920241960610847715334553600000000000000

$\operatorname{Vol}$:

7658969897501574748537755050756794492337074203099

$\operatorname{vol}_{\mathrm{Euc}}$:

559498129702796022246895686372766052475496691/215330276631180889478121101750832506606140689157723348094523801600000000000000

$\operatorname{vol}_{\mathrm{rel}}$:

727291284016786420977508457990121862548823260052557333386607889/828160860106766855125676318796872729344622463533089422677980721388055739956270293750883504892820848640000000000000000

$\operatorname{Vol}$:

5091038988117504946842559205930853037841762820367901333706255223000

$\operatorname{vol}_{\mathrm{Euc}}$:

727291284016786420977508457990121862548823260052557333386607889/828160860106766855125676318796872729344622463533089422677980721388055739956270293750883504892820848640000000

Definition

The Birkhoff polytope $B_n\subset\mathbb{R}^{n\times n}$ is the lattice polytope of $n\times n$ doubly stochastic matrices [2]. The table stores its volume in three normalisations: the relative lattice volume, the normalised lattice volume, and the Euclidean volume in the metric inherited from $\mathbb{R}^{n\times n}$.

Parameters

$n$

— matrix size ($n$ is an integer with $n\geq1$)

normalisation

— volume normalisation (one of relative, normalised, and euclidean)

Formulas

(1)

With $d=(n-1)^2$, $\operatorname{vol}_{\mathrm{rel}}(B_n)=[t^d]H_n(t)$, the leading coefficient of the Ehrhart polynomial $H_n(t)$ of $B_n$.

(2)

With $d=(n-1)^2$, $\operatorname{Vol}(B_n)=d!\,\operatorname{vol}_{\mathrm{rel}}(B_n)=d!\,[t^d]H_n(t)$.

(3)

If $h^*_{B_n}(z)$ is the Ehrhart $h^*$-polynomial, then $h^*_{B_n}(1)=\operatorname{Vol}(B_n)$.

(4)

$\operatorname{vol}_{\mathrm{Euc}}(B_n)=n^{n-1}\operatorname{vol}_{\mathrm{rel}}(B_n)$.

(5)

The covolume of $\Lambda_n$ in the Frobenius inner product is $n^{n-1}$. Identified with the integral cycle lattice of $K_{n,n}$, $\Lambda_n$ has squared covolume equal to the number of spanning trees of $K_{n,n}$, which is $n^{2n-2}$ by the matrix-tree theorem [3].

Comments

(6)

Let $d=(n-1)^2$ be the dimension of $B_n$, and let $\Lambda_n$ be the lattice of integer $n\times n$ matrices whose rows and columns all sum to $0$. The affine hull of $B_n$ is a translate of $\Lambda_n\otimes\mathbb{R}$. The relative volume $\operatorname{vol}_{\mathrm{rel}}(B_n)$ is the $d$-dimensional volume in which a fundamental domain of $\Lambda_n$ has volume $1$. The normalised volume is $\operatorname{Vol}(B_n)=d!\,\operatorname{vol}_{\mathrm{rel}}(B_n)$. The Euclidean volume $\operatorname{vol}_{\mathrm{Euc}}(B_n)$ is the $d$-dimensional volume for the Frobenius inner product $\langle X,Y\rangle=\sum_{i,j}X_{ij}Y_{ij}$.

Programs

(P1)

Sage

# Sage can compute the Euclidean volume directly for small n.
from sage.geometry.polyhedron.library import polytopes

B = polytopes.Birkhoff_polytope(4)
B.volume(measure="induced", engine="internal")  # 176/2835

References

[1]

Matthias Beck and Dennis Pixton, The Ehrhart polynomial of the Birkhoff polytope, Discrete & Computational Geometry 30 (2003), no. 4, 623-637. (arXiv) (doi)

Links

[2]

Wikipedia: Birkhoff polytope

[3]

Wikipedia: Matrix tree theorem

[4]

OEIS A037302: normalized volume of the Birkhoff polytope

[5]

OEIS A078524: numerators of the Euclidean volumes of the Birkhoff polytopes

[6]

OEIS A078525: denominators of the Euclidean volumes of the Birkhoff polytopes

[7]

Beck and Pixton: Ehrhart polynomials for the Birkhoff polytopes

[8]

Beck and Pixton: volumes of the Birkhoff polytopes

Similar tables

Ehrhart polynomials of the Birkhoff polytopes — gives the Ehrhart polynomial whose leading coefficient is the relative volume

Ehrhart $h^*$-polynomials of the Birkhoff polytopes — gives the $h^*$-polynomial whose value at $z=1$ is the normalised volume

Data properties

Entries are of type: rational number

How well the digits are known: exact

Table is complete: no (it holds all three normalisations for every matrix size $n$ with $1\leq n\leq10$; Beck and Pixton computed the Ehrhart polynomial, and hence the volume, of $B_9$ [1] and later announced the volume of $B_{10}$ [8])

How they were obtained:

The normalised volumes are transcribed from OEIS A037302 [4]. The relative volumes are obtained by dividing by $((n-1)^2)!$, and the Euclidean volumes by multiplying the relative volumes by the covolume $n^{n-1}$ in (5).

All ten Euclidean volumes agree with Beck and Pixton's list [8]. OEIS A078524 [5] agrees with the Euclidean numerators, and OEIS A078525 [6] agrees with the Euclidean denominators except at $n=9$. At $n=9$, A078525 keeps the denominator of the unscaled value Beck and Pixton first published before correcting the missing factor $9^8$. The relative volumes for $1\leq n\leq9$ were compared with the leading coefficients of Beck and Pixton's published Ehrhart polynomials [7].