\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}