\documentclass[ALCO,Unicode]{cedram}
%-------------------------------------------------------------------
% fonts, encoding etc.
%-------------------------------------------------------------------
%-------------------------------------------------------------------
\hyphenation{Ros-tock Bie-le-feld}
%-------------------------------------------------------------------
% Macros
%-------------------------------------------------------------------
%-------------------------------------------------------------------
% theorem declarations
\newtheorem{introthm}{Theorem}
\renewcommand{\theintrothm}{\Alph{introthm}}
%\newtheorem{lemma}{Lemma}[section]
\equalenv{cor}{coro}
%\newtheorem{cor}[lemma]{Corollary}
%
%\theoremstyle{remark}
%\newtheorem{remark}[lemma]{Remark}
%-------------------------------------------------------------------
% redefined commands
% use the standard ("correct") forms of greek letters:
\newcommand{\eps}{\varepsilon}
\renewcommand{\theta}{\vartheta}
\renewcommand{\rho}{\varrho}
\renewcommand{\phi}{\varphi}
% other (personal preference):
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
%-------------------------------------------------------------------
% math macros
\newcommand{\reals}{\mathbb{R}}
\newcommand{\iso}{\cong} % isomorph
\newcommand{\Sym}[1]{\operatorname{Sym}(#1)} % Symmetric Group
\DeclarePairedDelimiter{\card}{\lvert}{\rvert} % Cardinality of sets
\DeclarePairedDelimiter{\erz}{\langle}{\rangle} % Struc. generated by...
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\AGL}{AGL}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Zentr}{\mathbf{Z}} % Center,
\DeclareMathOperator{\Centrl}{\mathbf{C}} % Centralizer
\DeclareMathOperator{\Norml}{\mathbf{N}}
\DeclareMathOperator{\mat}{\mathbf{M}} %Matrizenring
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\Id}{id} % identity map
\DeclareMathOperator{\sign}{sign}
%-------------------------------------------------------------------
% Metadata
%-------------------------------------------------------------------
\title{A property of the Birkhoff polytope}
\author{\firstname{Barbara} \lastname{Baumeister}}
\address{Universität Bielefeld\\
Postfach 100131\\
33501 Bielefeld\\
Germany}
\email{b.baumeister@math.uni-bielefeld.de}
\author{\firstname{Frieder} \lastname{Ladisch}}
\address{Universität Rostock\\
Institut für Mathematik\\
18051 Rostock\\
Germany}
\email{frieder.ladisch@uni-rostock.de}
\subjclass[2010]{52B15, 05E18, 20B25, 20C15, 52B05, 52B12}
\keywords{Birkhoff polytope, representation polytope,
permutation polytope, combinatorial symmetry}
\thanks{Part of the work was done while the second author visited
Bielefeld University. We wish to thank the CRC~$701$
``\emph{Spectral Structures and Topological Methods in Mathematics}''
for its support.
The second author is also supported by the DFG
through project SCHU~$1503/6-1$.}
%-------------------------------------------------------------------
% set metadata for pdf:
%
%\hypersetup{pdfauthor = {Barbara Baumeister, Frieder Ladisch},
% pdftitle={A property of the Birkhoff polytope},
% pdfkeywords = {Birkhoff polytope, representation polytope,
% permutation polytope, combinatorial symmetry}
% }
%
%-------------------------------------------------------------------
% Beginning of the document
%-------------------------------------------------------------------
\begin{document}
\begin{abstract}
The Birkhoff polytope $B_n$ is the convex hull
of all $n\times n$ permutation matrices in
$\mathbb{R}^{n\times n}$.
We compute the combinatorial symmetry group
of the Birkhoff polytope.
A representation polytope is
the convex hull of some finite matrix group
$G\leq \operatorname{GL}(d,\mathbb{R})$.
We show that the group of permutation matrices
is essentially the only finite matrix group
which yields a representation polytope
with the same face lattice as the Birkhoff polytope.
\end{abstract}
\maketitle
\section{Introduction}
Let $P\colon G= S_n \to \GL(n,\reals)$ be the
standard permutation representation of
the symmetric group~$S_n$ on $n$ letters.
The \emph{Birkhoff polytope} $B_n$ is by definition
the convex hull of all permutation matrices of size $n\times n$:
\[ B_n := \conv\{ P(\sigma) \mid \sigma\in S_n\}.
\]
In this note, we prove a conjecture of
Baumeister, Haase, Nill and Paffenholz~\cite[Conjecture~5.3]{BHNP09}
on the uniqueness of the Birkhoff polytope among
permutation polytopes.
In fact, we prove a slightly stronger result.
To state the result, we need the following notation.
Let $D\colon G\to \GL(d,\reals)$
be a representation over the reals.
The corresponding \emph{representation polytope},
$P(D)$, is the convex hull of the image of $D$:
\[ P(D):= \conv\{ D(g) \mid g\in G
\}.
\]
If $D$ is a permutation representation, then the
representation polytope is called a
\emph{permutation polytope}.
Two representations
$D_i\colon G_i \to \GL(d_i,\reals)$
(where $i=1$, $2$) are called
\emph{effectively equivalent} if there is
a group isomorphism $\phi\colon G_1\to G_2$
such that $D_1$ and $D_2\circ \phi$ are
\emph{stably equivalent},
which means that $D_1$ and $D_2\circ \phi$
have the same nontrivial irreducible constituents
(not necessarily occurring with the same multiplicities).
The representation polytopes of effectively representations are
affinely isomorphic
\cite[Theorem~2.4]{BaumeisterGrueninger15} \cite[\S~2]{BHNP09}.
The converse is not true, for example,
when $D$ is the regular representation of a group,
then $P(D)$ is a simplex of dimension $\card{G}-1$.
Thus groups that are not even isomorphic as abstract groups,
may yield affinely equivalent representation polytopes.
From this viewpoint, the next result is somewhat surprising.
Recall that two polytopes
$P$ and $Q$ are
\emph{combinatorially equivalent}
if there is a bijection between the vertices of $P$
and the vertices of $Q$ which maps faces of $P$
onto faces of $Q$.
Affinely equivalent polytopes are combinatorially equivalent,
but not conversely.
\begin{introthm}\label{main:birkhoff_unique}
Let $D\colon G\to \GL(d,\reals)$ be
a faithful representation such that
the representation polytope~$P(D)$ is combinatorially equivalent
to the Birkhoff polytope~$B_n$.
Then either $n=3$ and $G$ is cyclic of order $6$,
or $D$ and the standard permutation representation
$P\colon S_n \to \GL(n,\reals)$
are effectively equivalent
(in particular, $G\iso S_n$).
\end{introthm}
In the exceptional case $n=3$ and $G$ cyclic, it is easy to see that
$D$ is not stably equivalent to a permutation representation.
It follows also from the classification of permutation polytopes
in small dimensions~\cite[Theorem~4.1]{BHNP09}
that $B_3$ is not combinatorially equivalent
to any other permutation polytope.
In particular, Theorem~\ref{main:birkhoff_unique}
answers ~\cite[Conjecture~5.3]{BHNP09} in the positive.
To prove Theorem~\ref{main:birkhoff_unique},
we use the determination of the
combinatorial symmetry group of the Birkhoff polytope,
which may be of interest in its own right:
\begin{introthm}\label{main:birkhoff_symgrp}
For every combinatorial symmetry $\alpha$ of
the Birkhoff polytope
there are $\sigma$, $\tau\in S_n$ and $\eps\in \{\pm 1\}$
such that $\alpha(\pi)= \sigma \pi^{\eps} \tau$
for all $\pi\in S_n$.
Every combinatorial symmetry comes from an isometry of
the space of $n\times n$ matrices over $\reals$.
\end{introthm}
As we will explain below, this means that for $n\geq 3$,
the combinatorial symmetry group of the Birkhoff polytope
is isomorphic to the wreath product
$S_n \wr C_2 = (S_n \times S_n)\rtimes C_2$.
Although not difficult, this result seems not to be in the literature
yet.
There are, however, two different published proofs
that the above maps
are all the linear maps preserving the Birkhoff
polytope~\cite{LiSpiZobin04,LiTamTsing02}.
Since every linear or affine symmetry of a polytope
induces a combinatorial symmetry,
Theorem~\ref{main:birkhoff_symgrp}
is actually stronger than the old result.
As one would expect, our proof of Theorem~\ref{main:birkhoff_symgrp}
depends on the well known description of
the facets and thus the combinatorial structure
of the Birkhoff polytope.
On the other hand, the combinatorial structure of
representation and permutation polytopes in general
can be quite complicated,
even for cyclic groups, as examples show~\cite{BHNP11pre}.
\section{Preliminaries on permutation actions on a group}
Let $G$ be a finite group.
For each $g\in G$, let $\lambda_g\in \Sym{G}$
be left multiplication with $g$
(so $\lambda_g(x)= gx$),
and $\rho_g$ be right multiplication
with $g^{-1}$, that is, $\rho_g(x)= xg^{-1}$.
Thus $g\mapsto \lambda_g$ and $g\mapsto \rho_g$ are
the left and right regular permutation action.
Also, let $\iota\in \Sym{G}$ be the map that
inverts elements (so $\iota(x)= x^{-1}$ for all $x\in G$).
Let $\Gamma(G)\leq \Sym{G}$ be the group generated by all these
elements:
\[ \Gamma(G):= \erz{\lambda_g, \rho_g, \iota
\mid g\in G}.
\]
To describe $\Gamma(G)$, we need the
\emph{wreath product} $G\wr C_2$
of $G$ with a cyclic group~$C_2=\erz{s}$
of order $2$.
Recall that this is the semidirect product of
$G\times G$ with $C_2$, where $s$ acts on
$G\times G$ by exchanging coordinates:
$(g,h)^s = (h,g)$ for $g$, $h\in G$.
Then:
\begin{lemma}
If $G$ is not an elementary abelian $2$-group,
then $\Gamma(G) \iso (G\wr C_2)/Z$,
where $Z = \{(z,z)\in G \times G \mid z \in \Zentr(G)\}$.
\end{lemma}
\begin{proof}
We have that $\lambda(G)$ and $\rho(G)$ centralize each other,
and $(\lambda_g)^{\iota} = \rho_g$.
Thus sending $(g,h)\in G\times G$ to
$\lambda_g \rho_h$ and $s\in C_2 = \{1,s\}$
to $\iota$ defines a surjective group homomorphism
$G\wr C_2 \to \Gamma(G)$
with $Z$ in the kernel.
Suppose $\lambda_g \rho_h = \Id_G$.
Then $gxh^{-1} = x$ for all $x\in G$.
Taking $x=1$ yields $g=h$,
and it follows that $g\in \Zentr(G)$.
Now assume $\lambda_g \rho_h \iota = \Id$.
Then $gx^{-1}h^{-1} = x$ for all $x\in G$,
and $x=1$ yields $g=h$.
Moreover, we have
$xy = g (xy)^{-1} g^{-1}
= g y^{-1} g^{-1} \, g x^{-1} g^{-1}
= y x$
for all $x$, $y\in G$.
Thus $G$ must be abelian in this case, and
$x^{-1} = x$ for all $x\in G$.
So when $G$ is not an elementary abelian $2$-group,
such an element can not be in the kernel of the action
of $G\wr C_2$ on $G$.
This shows the result.
\end{proof}
In the proof of Theorem~\ref{main:birkhoff_unique},
we need the fact
that $\Gamma(G)$ contains no pair of commuting,
regular subgroups other than $\lambda(G)$
and $\rho(G)$, when $G = S_n$ and $n\geq 4$.
The exception in Theorem~\ref{main:birkhoff_unique}
for $n=3$
comes from the fact that
in $\Gamma(S_3)$, we have other pairs of commuting, regular
subgroups, namely $U=V = C_2 \times C_3$
and $U=V= C_3\times C_2$.
Notice that we do not assume that the commuting, regular subgroups
$U$, $V$
of $\Gamma(G)$ have trivial intersection.
If one assumes $U\cap V=1$, one can give a somewhat
shorter proof that
$\{U,V\} = \{ \lambda(G), \rho(G)\}$
for almost simple groups $G$,
but we need the stronger statement for the proof of
Theorem~\ref{main:birkhoff_unique}.
The most elegant and elementary way to prove
that $\lambda(G)$ and $\rho(G)$ form the only pair
of commuting regular subgroups of $\Gamma(G)$
(when $G= S_n$, $n\geq 4$),
seems to be to use a general argument due to
Chermak and Delgado~\cite{ChermakDelgado89}.
Let $G$ be an arbitrary finite group.
Following Isaacs~\cite[\S~1G]{IsaacsFGT},
we call $m_G(H) := \card{H}\card{\Centrl_G(H)}$
the \emph{Chermak-Delgado measure} of the subgroup
$H\leq G$.
\begin{lemma}\cite[Theorem~1.44]{IsaacsFGT}
\label{l:cdlatt}
Let $G$ be a finite group and let
$\mathcal{L} = \mathcal{L}(G)$ be the set of subgroups
for which the Chermak-Delgado measure is as large as
possible.
Then for $H$, $K\in \mathcal{L}$, we have
$H\cap K\in \mathcal{L}$,
$\erz{H,K} =HK=KH \in \mathcal{L}$,
and $\Centrl_G(H)\in \mathcal{L}$.
\end{lemma}
The \emph{Chermak-Delgado lattice} of $G$ is by definition
the set of all subgroups of $G$ for which
the Chermak-Delgado measure is maximized.
The last result tells us that this is indeed a sublattice
of the lattice of all subgroups of $G$.
We need the following, which is probably well known:
\begin{cor}
Any member of the Chermak-Delgado lattice
of a finite group $G$ is subnormal in $G$.
\end{cor}
\begin{proof}
If $H$ is a member of the Chermak-Delgado lattice of $G$,
then any conjugate $H^g$ is also in the
Chermak-Delgado lattice,
and so $HH^g = H^g H$ by Lemma~\ref{l:cdlatt}.
But subgroups $H\leq G$ with $HH^g = H^gH$ for all $g\in G$
are subnormal~\cite[Theorem~2.8]{IsaacsFGT}.
\end{proof}
\begin{lemma}\label{l:sn_cent_est}
Suppose that $G$ is almost simple
(that is, $G$ has a nonabelian simple
socle).
Then $\card{U}\card{\Centrl_{G}(U)} \leq \card{G}$
for any subgroup $U\leq G$,
and equality holds if and only if
$U = \{1\}$ or $U=G$.
In particular, this holds for
$G= S_n$, $n\geq 5$.
The conclusion is also true for $G=S_4$.
\end{lemma}
\begin{proof}
Suppose that $1\neq H$ is a member of
the Chermak-Delgado lattice.
Then $H$ is subnormal and thus contains the nonabelian
simple socle of $G$.
It follows that $\Zentr(H)=1 = H \cap \Centrl_G(H)$.
Since $\Centrl_G(H)$ is also a member of the Chermak-Delgado lattice,
we must have $\Centrl_G(H)=1$.
Since $\card{H}\card{\Centrl_G(H)} = \card{H} \leq \card{G}$
was supposed to be maximal possible, we see that
$H=G$.
Thus the Chermak-Delgado lattice contains exactly the groups
$1$ and $G$ itself,
and the first assertion follows.
The case $G=S_4$ is a simple verification.
\end{proof}
We will need the following application (for $G=S_n$):
\begin{lemma}\label{l:snwrc2_reg}
Let $G$ be a group such that the Chermak-Delgado lattice of $G$
contains exactly the groups $1$ and $G$.
Then $\lambda(G)$, $\rho(G)$ is the only pair of
commuting, regular subgroups of\/ $\Gamma(G)$.
\end{lemma}
\begin{proof}
Notice that $\Zentr(G)=\{1\}$, since otherwise
$m_G(\Zentr(G))=\card{\Zentr(G)}\card{G} > \card{G} = m_G(1)$.
Thus $\Gamma(G)\iso G\wr C_2$
and $\lambda(G)\rho(G) \iso G\times G$.
We first show that a regular subgroup $U$ of
$\Gamma(G)$ is contained in the normal subgroup
$\lambda(G) \rho(G)$.
Otherwise, $U$
contains an element $u = \lambda_g \rho_h \iota$
sending $x\in G$ to $ g x^{-1} h^{-1}$.
Then $u^2$ sends $x$ to $gh x g^{-1}h^{-1}$,
and in particular fixes $g$.
By regularity, we must have $u^2 = \Id_G$.
This implies
$gh = hg $ and
$gh\in \Zentr(G) = \{1\}$.
Thus $u$ sends $x$ to $g x^{-1}g$,
and so fixes $g$, too,
which contradicts the regularity.
This shows that $U \leq \lambda(G) \rho(G)$.
Since $\lambda(G) \rho(G)\iso G\times G$, we may work
in $G\times G$ from now on.
Suppose that $U$ and $V\leq G\times G$
both have size $\card{G}$,
and commute with each other.
Let $U_L$ be the projection of $U$
onto the first component,
that is, the subgroup of elements
$g\in G$ such that there is an $h\in G$
with $(g,h)\in U$.
Let $U_R$ be the projection of $U$ on the second component.
With this notation,
$\Centrl_{G\times G}(U) = \Centrl_{G}(U_L)\times \Centrl_{G}(U_R)$.
Thus
\[ \card{G}^2
= \card{U}\card{V}
\leq \card{U_L}\card{U_R}
\card{\Centrl_{G}(U_L)}\card{\Centrl_{G}(U_R)}
\leq \card{G}^2,
\]
where the last inequality follows from our assumption
on the Chermak-Delgado lattice of $G$.
Thus equality holds, and it follows also that
$U_L$ and $U_R$ are trivial or the group $G$ itself.
Since both $U$ and $V$ have size $\card{G}$,
it follows that
$\{U,V\} = \{G\times 1, 1\times G\}$.
\end{proof}
\begin{cor}\label{c:normlgamma}
Let $G$ be a group such that the Chermak-Delgado lattice of $G$
contains exactly the groups $1$ and $G$.
Then $\Norml_{\Sym{G}}(\Gamma(G)) = (\Aut G)\Gamma(G)$.
\end{cor}
\begin{proof}
Let $\pi \in \Norml_{\Sym{G}}(\Gamma(G))$.
Then $\lambda(G)^{\pi}$ and $\rho(G)^{\pi}$
are commuting regular subgroups of $\Gamma(G)$,
and thus
$\{\lambda(G)^{\pi},\rho(G)^{\pi}\}
= \{ \lambda(G), \rho(G)\} $.
Since $\lambda(G)$ and $\rho(G)$ are conjugate in
$\Gamma(G)$,
we may assume that $\lambda(G)^{\pi}= \lambda(G)$.
Thus $\pi \lambda_g \pi^{-1} = \lambda_{\alpha g}$
for some bijection $\alpha\colon G\to G$.
Clearly, $\alpha$ is a group automorphism.
As $\lambda(G)$ acts transitively on $G$, we may assume
$\pi(1) = 1$.
But then
$\pi(g) = \pi\lambda_g \pi^{-1}(1)
= \lambda_{\alpha g}(1)
= \alpha(g)$,
so $\pi\in \Aut G$.
\end{proof}
The conclusion of this corollary is also true for some other
groups (for example, $G=S_3$),
but not for all groups (for example, $G= S_3 \times S_3$).
\section{The combinatorial symmetry group of the Birkhoff polytope}
Let $D\colon G \to \GL(d,\reals)$ be a faithful representation
and let $P(D) = \conv\{ D(g) \mid g\in G \}$
be the corresponding representation polytope.
Then the vertices of $P(D)$ correspond to the elements of $G$.
We may thus view the affine and combinatorial symmetries
as permutations of $G$ itself.
\begin{lemma}\label{l:reppoltrivsyms}
Let
$D\colon G\to \GL(d,\reals)$
be a faithful representation
and $P(D)$ the representation polytope.
Then the affine symmetry group $\AGL(P(D))$
as permutation group on $G$ contains
$\Gamma(G)$ as defined in the last section.
\end{lemma}
\begin{proof}
The left multiplications $\lambda_g$ are realized
by left multiplication with
$D(g)$, and the right multiplications $\rho_g$
by right multiplication with $D(g)^{-1}$.
If $D$ is an orthogonal representation, then the
permutation $g\mapsto g^{-1}$ is realized by transposing
matrices, sending $D(g) $ to $D(g)^t = D(g^{-1})$.
The general case (which we will not need)
can be reduced to the orthogonal
case~\cite[Prop.~6.4]{FrieseLadisch16}.
\end{proof}
Now let $P\colon G= S_n \to \GL(n,\reals)$ be the
standard permutation representation of
the symmetric group~$S_n$, and let
\[ B_n := \conv\{ P(\sigma) \mid \sigma\in S_n\}
\]
be the Birkhoff polytope.
Theorem~\ref{main:birkhoff_symgrp} claims that
$\Gamma(S_n)$ is the combinatorial symmetry group of
$B_n$.
(The second claim of Theorem~\ref{main:birkhoff_symgrp} is that
these symmetries come from isometries of the matrix space.
This is then clear, since
the symmetries in $\Gamma(S_n)$ even act by permuting coordinates of
the matrices.)
\begin{proof}[Proof of Theorem~\ref{main:birkhoff_symgrp}]
Recall that the Birkhoff polytope consists of the doubly
stochastic matrices~\cite[Corollary~1.4.14]{LovaszPlummer86}.
In particular, for each index pair $(i,j)$,
the equality
$a_{ij}=0$ describes a facet of the Birkhoff polytope.
Thus its facets, as subsets of $S_n$, are given by
the $n^2$ subsets
\[ F_{ij} = \{\pi\in S_n \mid \pi(i)\neq j \},
\quad \text{$i$, $j=1$, $\dotsc $, $n$}.
\]
It will be more convenient to work with the complements
\[ A_{ij}= S_n \setminus F_{ij}
= \{ \pi \in S_n \mid \pi(i)=j \}
\]
of the facets.
For $\sigma$, $\tau\in S_n$,
we have
$\sigma A_{ij} \tau^{-1} = A_{\tau i, \sigma j} $.
We also have
$ A_{ij}^{-1} := \{ \pi^{-1}
\mid \pi \in A_{ij}
\}
= A_{ji}$.
Moreover, for $i$, $j$, $k$ and $l$ in $\{1,\dotsc,n\}$
we have
\[ \card{A_{ij}\cap A_{kl}}
=
\begin{cases}
(n-1)!, & \text{if } i=k, j=l, \\
0 & \text{if } i=k, j\neq l,\\
0 & \text{if } i\neq k, j=l, \\
(n-2)! \quad & \text{otherwise}.
\end{cases}
\]
Any combinatorial symmetry $\alpha$ permutes the facets and thus
the sets $A_{ij}$, and preserves cardinalities of their
intersections.
Let $\alpha\colon S_n \to S_n$ be an arbitrary
combinatorial symmetry of the Birkhoff polytope.
We have to show that $\alpha\in \Gamma(S_n)$,
the group containing the maps
$\pi \mapsto \sigma \pi^{\pm 1} \tau^{-1}$.
After replacing $\alpha$ by $\gamma \circ \alpha$
for some $\gamma\in \Gamma(S_n)$ of the form
$\gamma(\pi) = \sigma \pi \tau^{-1}$,
we may assume that $\alpha(A_{11})= A_{11}$.
Then $\card{\alpha(A_{12})\cap A_{11}} = \card{A_{12}\cap A_{11}}=0$,
and thus either $\alpha(A_{12})= A_{1j}$ for some $j\neq 1$
or $\alpha(A_{12})=A_{j1}$ for some $j\neq 1$.
If the latter is the case, we compose $\alpha$
with the map $\pi\mapsto \pi^{-1}$,
so we may assume that $\alpha(A_{12})=A_{1j}$.
Multiplying $A_{1j}$ from the left with the transposition
$(2,j)$ yields the set $A_{12}$,
and so we can assume that $\alpha(A_{12})= A_{12}$.
Now for $j\geq 3$, the set $\alpha(A_{1j})$ has empty intersection
with $A_{11}$ and $A_{12}$ and thus
$\alpha(A_{1j}) \in \{ A_{1k}\mid k\geq 3\}$.
Thus $\alpha$ induces a permutation
$\sigma$ of $\{3,\dotsc, n\}$ defined by
$\alpha(A_{1j})= A_{1,\sigma j}$.
Thus $\sigma^{-1} \alpha(A_{1j})= A_{1j}$,
and we may assume that $\alpha(A_{1j})=A_{1j}$
for all $j$.
Similarly, we can assume that
$\alpha(A_{j1})= A_{j1}$ for all $j$.
Thus, after composing $\alpha$ with suitable elements
from $\Gamma(S_n)$,
we may assume that $\alpha$ leaves each of the sets
$A_{1j}$ and $A_{j1}$ invariant.
For $k\geq 2$, $l\geq 2$ we have that
$A_{kl}$ is the unique set $S$ among the sets
$A_{ij}$ (with $i\geq 2$, $j\geq 2$)
such that $S\cap A_{k1}=\emptyset = S\cap A_{1l}$.
It follows that
$\alpha(A_{kl})=A_{kl}$ for all $k$, $l$.
Thus $\alpha$ is the identity.
It follows that the original $\alpha$ was already in
$\Gamma(S_n)$.
\end{proof}
\section{Characterization of the Birkhoff polytope}
In this section, we prove Theorem~\ref{main:birkhoff_unique}.
We first show the following weaker result.
\begin{lemma}\label{l:snbirk_unique}
Let $D\colon S_n \to \GL(d,\reals)$ be a representation
such that the representation polytope~$P(D)$ is combinatorially
equivalent to the Birkhoff polytope.
Then $D$ is effectively equivalent to
the standard permutation representation $P$ of $S_n$.
\end{lemma}
\begin{proof}
We have to show that $D$ has the same nontrivial constituents
as $P$, up to automorphisms of $S_n$.
Since we can replace $D$ by a stably equivalent representation,
we may (and do) assume that
the trivial character is not a constituent of the character of $D$.
A combinatorial isomorphism from the Birkhoff polytope~$B_n$
onto $P(D)$ sends a vertex $P(g)$ of $B_n$ (where $g\in S_n$)
to a vertex $D(\alpha(g))$ of $P(D)$,
where $\alpha\colon S_n \to S_n$ is a permutation of $S_n$.
Then the map sending
$\gamma\in \Sym{S_n}$ to
$\alpha \circ \gamma\circ \alpha^{-1}$
is an isomorphism from the combinatorial symmetry group of
$B_n$ onto the combinatorial symmetry group of $P(D)$.
The combinatorial symmetry group of the Birkhoff
polytope is $\Gamma(S_n)$,
and the combinatorial symmetry group of $P(D)$ contains
$\Gamma(S_n)$ (in its natural action on $P(D)$),
by Lemma~\ref{l:reppoltrivsyms}.
Therefore, the combinatorial symmetry group of $P(D)$
is just $\Gamma(S_n)$.
It follows that $\alpha \in \Norml_{\Sym{S_n}}(\Gamma(S_n))$.
By Lemma~\ref{l:sn_cent_est}, Corollary~\ref{c:normlgamma}
applies to $S_n$ and thus
$\alpha\in (\Aut S_n)\Gamma(S_n)$.
After multiplying $\alpha$ with an element of
$\Gamma(S_n)$, we may thus assume
$\alpha \in \Aut S_n$.
Since then $D$ and $D\circ\alpha$ are effectively equivalent,
we may assume that $\alpha = \Id_{S_n}$.
This means that the combinatorial isomorphism from $B_n$ onto $P(D)$
simply sends the vertex $P(g)$ to $D(g)$, for any $g\in S_n$.
In particular, a subset of $S_n$ corresponds to a face(t)
of $B_n$ (under $P$)
if and only if it corresponds to a face(t)
of the representation polytope $P(D)$ (under $D$).
Let $H \leq S_{n}$ be the stabilizer of a point,
say $n$. (So $H\iso S_{n-1}$.)
By the description of the facets of $B_n$, we know that
$S_n \setminus H = \{g \in S_n\mid g(n)\neq n\}$
corresponds to a facet of $B_n$.
Thus $D(S_n\setminus H)$ is a facet of $P(D)$.
Let $\phi$ be the character of $D$.
The character of the standard permutation representation~$P$
has the form $(1_H)^{S_n} = 1_{S_n} + \chi$,
where $\chi$ is an irreducible character of $S_n$.
We are going to show that $\chi$ is the only
nontrivial irreducible constituent of~$\phi$.
As we remarked in the first paragraph of the proof,
we can assume that $\phi$
does not contain the trivial character.
The matrix $\sum_{g\in S_n} D(g)$ is fixed under
multiplication with elements from $D(S_n)$,
and since the trivial representation is not a constituent of~$D$,
we have $\sum_{g\in S_n} D(g) = 0$.
Geometrically, this means that
the origin is the barycenter
of the representation polytope~$P(D)$.
As $D(S_n\setminus H)$ is a facet of $P(D)$,
we must have
\[ \sum_{g\in S_n \setminus H} D(g) \neq 0
,\quad \text{and} \quad
\sum_{g\in H} D(h) \neq 0.
\]
It follows that the restricted character
$\phi_H$ contains the trivial character $1_H$
as a constituent.
Using Frobenius reciprocity and the fact that
$(1_H)^{S_n} = 1_{S_n} + \chi$, we get
\[ 0 \neq [\phi_H, 1_H ] = [\phi, (1_H)^{S_n}]
= [\phi,1_{S_n}] + [\phi,\chi] = [\phi,\chi].
\]
Thus $\chi$ is a constituent of $\phi$.
Since dimension is a combinatorial invariant, we must have
$\dim P(D) = \dim B_n = \chi(1)^2 $.
On the other hand, we have
$\dim P(D) = \sum_{\psi} \psi(1)^2$,
where the sum runs over the nontrivial
irreducible constituents $\psi$ of $\phi$,
not counting multiplicities~\cite[Theorem~3.2]{guralnickperkinson06}.
It follows that $\chi$ is the only irreducible constituent of $\phi$,
and thus $D$ and $P$ are stably equivalent.
\end{proof}
\begin{remark}
In the preceding proof,
we reduced to the case that the combinatorial isomorphism
sends $P(g)$ to $D(g)$ (for any $g\in S_n$).
If we could show that then $P(g)\mapsto D(g)$
can be extended to an affine isomorphism,
Lemma~\ref{l:snbirk_unique} would follow
from a characterization of effective equivalence
by Baumeister and
Grüninger~\cite[Corollary~4.5]{BaumeisterGrueninger15}.
But we do not know how to do this, or whether this is even true
more generally
(for combinatorial isomorphisms of this form between
representation polytopes of arbitrary groups).
\end{remark}
Finally, we prove our main result:
\begin{proof}[Proof of Theorem~\ref{main:birkhoff_unique}]
Identify the vertices of $P(D)$ and $B_n$
with $G$ and $S_n$, respectively.
Let
$\gamma\colon G\to S_n$ be a combinatorial isomorphism.
Then $\gamma$ induces an isomorphism $\kappa_{\gamma}$
from the combinatorial symmetry group
$A$ of $P(D)$ onto the combinatorial symmetry group
$S_n\wr C_2$ of $B_n$ sending
$\alpha\in A$ to
$\kappa_{\gamma}(\alpha):=\gamma \circ \alpha \circ \gamma^{-1}$.
Obviously,
we have $\gamma(\alpha g) = \kappa_{\gamma}(\alpha)(\gamma g)$.
Thus the pair
$(\kappa_{\gamma}, \gamma)$ is an isomorphism
from the $A$-set $G$ onto the
$(S_n\wr C_2)$-set $S_n$.
In particular, $\kappa_{\gamma}$ sends subgroups
of $A$ which act regularly on $G$, onto subgroups
of $S_n \wr C_2$ which act regularly on $S_n$.
The left and right multiplications with elements of $G$
induce regular subgroups of $A$.
These are sent to regular subgroups
$L$ and $R$ (say) of $S_n \wr C_2$.
Since left and right multiplications centralize each other,
the subgroups $L$ and $R$ centralize each other.
If $n\geq 4$, then Lemma~\ref{l:snwrc2_reg} yields
that $L= S_n \times 1$ or $L=1\times S_n$.
Since $L\iso G$, we have that $G\iso S_n$.
In view of Lemma~\ref{l:snbirk_unique},
this finishes the proof in case $n\geq 4$.
In the case $n=3$, however, there is one additional
possibility (up to conjugacy in $S_3 \wr C_2$),
namely that
$L= R = C_2 \times C_3\iso C_6$.
And indeed, the action of
$C_2\times C_3$ on $\mat_3(\reals)$ yields the
Birkhoff polytope~$B_3$ as orbit polytope of $C_6$,
and this orbit polytope is affinely equivalent
to the representation polytope $P(D)$,
where $D\colon C_6 \to \GL(4,\reals)$
sends a generator of $C_6$ to
\[ \begin{pmatrix*}[r]
0 & 1 & & \\
-1 & -1 & & \\
& & 0 & -1 \\
& & 1 & 1
\end{pmatrix*}.
\]
\end{proof}
%\section*{Acknowledgments}
\bibliographystyle{mersenne-plain}
\bibliography{ALCO_52_Ladisch}
\end{document}