# Random quantum graphs

Alexandru Chirvasitu and Mateusz Wasilewski

###### Abstract

We prove a number of results to the effect that generic quantum graphs
(defined via operator systems as in the work of Duan-Severini-Winter / Weaver)
have few symmetries: for a Zariski-dense open set of tuples
$(X_{1},\cdots,X_{d})$ of traceless self-adjoint operators in the $n\times n$
matrix algebra the corresponding operator system has trivial automorphism
group, in the largest possible range for the parameters: $2\leq d\leq
n^{2}-3$. Moreover, the automorphism group is generically abelian in the
larger parameter range $1\leq d\leq n^{2}-2$. This then implies that for those
respective parameters the corresponding random-quantum-graph model built on
the GUE ensembles of $X_{i}$’s (mimicking the Erdős-Rényi $G(n,p)$ model) has
trivial/abelian automorphism group almost surely.

Key words: random matrix; random graph; quantum graph; operator system;
quantum relation

MSC 2020: 60B20; 05C80; 20G20; 20B25; 22E45; 15A30

## Introduction

The theory of quantum graphs can be traced back to the work of Duan, Severini
and Winter ([DSW13]) and Weaver ([Wea12]). In the former the authors define a
quantum confusability graph associated to a quantum channel, much like a
confusability graph arises from a classical channel. In the latter the author
develops the theory of quantum relations, inspired by his previous work with
Kuperberg ([KW12]) on quantum metric spaces. In both cases quantum graphs turn
out to be encoded by operator systems.

The work of Weaver provides a unified framework for classical and quantum
relations. In particular, one can identify classical graphs with operator
systems of a specific kind. As proved in [OP15, Theorem 3.3], these operator
systems are actually complete invariants of the graphs; two graphs are
isomorphic if and only if the associated operator systems are unitally
completely order isomorphic. This allowed the authors to associate new –
_quantum_ – invariants to classical graphs.

Another approach to quantum graphs was developed in [MRV18]. The authors,
inspired by previous work on quantum isomorphisms of graphs [LMR20], developed
a categorical framework for quantum functions. What turned out from their
investigations is that most of the information about the quantum isomorphisms
can be recovered from appropriate categories, apart from commutativity of the
algebra of functions on the vertices. This led them to include quantum graphs
into their considerations, which they define to be finite dimensional
$C^{\ast}$-algebras equipped with a noncommutative analogue of an adjacency
matrix. A priori there is no reason for this notion of a quantum graph to be
the same as the one mentioned above, but both approaches turn out to be
essentially equivalent (cf. § 1.2).

In this article we start studying random quantum graphs; random classical
graphs have a long history (see [ER59]). One of the first considered issues
was, whether a typical graph admits non-trivial symmetries. Symmetric objects
are expected to be special and it was confirmed in [ER63] that, as the size of
the graph increases, the proportion of graphs admitting a non-trivial
automorphism tends to $0$. We will address two different quantum versions of
this problem.

The first one has to do with _quantum_ automorphisms of graphs. In [LMR20] the
authors discovered an intriguing connection between certain non-local games,
originating in quantum information theory, and the quantum automorphism groups
of graphs introduced by Banica in [Ban05] (see also [Bic03]). In Section 2 we
improve upon known results about quantum automorphism groups of random graphs,
in particular we treat the case of the Erdős-Rényi $G(n,p)$ model.

######  Theorem A (Theorem 2.4).

Fix $p\in(0,1)$. Then the quantum automorphism group of a random graph in the
$G(n,p)$ model is trivial with overwhelming probability.

What is more, we treat the case of random regular graphs (Theorem 2.5) and use
it to produce large families of isospectral graphs that are not quantum
isomorphic (Proposition 2.7).

In Section 3 we start exploring a different quantum variant, namely
automorphism groups of random quantum graphs. The easiest way to provide a
random model for a quantum graph is to view it as an operator subsystem
$V\subset M_{n}$ of a matrix algebra – then $V$ of a fixed dimension can be
chosen according to the Haar measure on the Grassmannian. In this way we
arrive at the $QG(n,d)$ model. The automorphism group of $V\subset M_{n}$
consists of those automorphisms of $M_{n}$ that preserve $V$. Our first result
is that the automorphism group is typically abelian, unless $d=0$ or
$d=n^{2}-1$, which correspond to the operator systems $\mathbb{C}\mathds{1}$
and $M_{n}$, respectively.

######  Theorem B (Corollary 3.17).

Let $n\in{\mathbb{N}}$ and $1\leqslant d\leqslant n^{2}-2$. Then the
automorphism group of a quantum graph in the $QG(n,d)$ model is almost surely
abelian.

Note that we cannot hope for a better result in this regime, because for $d=1$
the random operator system we get is spanned by the identity and one self-
adjoint operator, so it would generate an abelian subalgebra, which clearly
has a non-trivial automorphism group, for example all the unitaries lying in
the algebra itself. It turns out, however, that if we exclude this case (and
the corresponding case $d=n^{2}-2$ on the other edge) then we do get trivial
automorphism groups almost surely.

######  Theorem C (Theorem 3.16).

Let $n\geqslant 3$ and $2\leqslant d\leqslant n^{2}-3$. Then the automorphism
group of a quantum graph in the $QG(n,d)$ model is almost surely trivial.

In graph theory there are two main models of random graphs: $G(n,M)$ and
$G(n,p)$. Our $QG(n,d)$ is an analogue of $G(n,M)$ and we can also consider
the counterpart of $G(n,p)$ denoted by $QG(n,p)$. However, we cannot define
this model as is done classically, because quantum graphs notoriously lack an
analogue of vertices. But we can easily derive the $QG(n,p)$ as a weighted sum
of $QG(n,d)$ models and an elementary computation yields the following
corollary.

######  Corollary D (Proposition 1.18).

If $p(n)\in(0,1)$ satisfies $\lim_{n\to\infty}n^{2}p(n)=\infty$ and
$\lim_{n\to\infty}(1-p(n))n^{2}=\infty$ then as $n$ goes to infinity the
automorphism group of a quantum graph in the $G(n,p(n))$ model is trivial
asymptotically almost surely.

There is another corollary that we would like to mention here. We view quantum
graphs as operator subsystems $V\subset M_{n}$ of matrix algebras and the
matrix algebra itself is part of the structure, being a quantum counterpart of
the coordinate algebra of the vertex set. But operator systems are interesting
in their own right and it is important to see what kind of information about
them we can recover. It turns out that in a suitable regime one can obtain
$M_{n}$ from an operator system $V$ chosen according to $QG(n,d)$ as its
$C^{\ast}$-envelope, thus we can conclude that these operator systems do not
have nontrivial automorphisms.

######  Corollary E (Proposition 1.16).

Let $n\geqslant 3$ and $2\leqslant d\leqslant n^{2}-3$. For almost every
operator system $V$ in the $QG(n,d)$ model the only unital complete order
self-isomorphism of $V$ is the identity.

### Acknowledgements

We thank Mike Brannan for numerous conversations on the topics covered here.

AC is grateful for funding through NSF grant DMS-2001128.

MW was supported by the Research Foundation – Flanders (FWO) through a
Postdoctoral Fellowship and by long term structural funding - Methusalem grant
of the Flemish Government.

##  1 Preliminaries

###  1.1 Random structures

As is customary in the literature, for $p\in[0,1]$ and a positive integer $n$
we denote by $G(n,p)$ the simple random graph built on the Erdös-Rényi model
with probability $p$: $n$ vertices and each of the possible $n\choose{2}$
edges has probability $p$ of being present, independently of each other.

On the other hand, given positive integers $r<n$, we write $G(n,r)$ for the
random $r$-regular graph: an $r$-regular graph on vertex set
$[n]=\\{1,\cdots,n\\}$ with all such graphs being assigned equal probability
(as in [Bol82], for instance).

We use the following terminology, following, e.g. [TV11, Definition 3].

######  Definition 1.1.

We say that an $n$-dependent event $E$ holds with overwhelming probability (or
overwhelmingly) if $P(E)=1-O(n^{-c})$ for every positive constant $c$ (where
the scaling factor implicit in the $O$ notation is $c$-dependent).
$\blacklozenge$

###  1.2 Quantum graphs - the quantum adjacency matrix and the quantum
relations perspective.

The aim of this section is to roughly outline how quantum graphs can be seen
in two distinct but ultimately equivalent lights. The following results can
essentially be deduced from Section 7 of [MRV18].

######  Definition 1.2.

Let $H$ be a finite dimensional Hilbert space and $M\subseteq B(H)$ be a
finite dimensional C∗-algebra. A quantum relation on $M$ is an
$M^{\prime}-M^{\prime}$-bimodule $V\subseteq B(H)$. I.e., a linear subspace
$V$ such that $M^{\prime}VM^{\prime}\subseteq V$. We call such a quantum
relation $V$ on $M$ symmetric if $V$ is self-adjoint: $V=V^{*}$, and reflexive
if $M^{\prime}\subset V$. $\blacklozenge$

In particular, a reflexive and symmetric quantum relation over any $M$ is an
operator system in $B(H)$, and every operator system is a reflexive, symmetric
quantum relation on $B(H)$. The classical motivation for this terminology
comes from the following fact:

######  Proposition 1.3 (Weaver).

Let $X$ be a finite set. There is a bijective correspondence between
(reflexive, symmetric) relations $R\subseteq X\times X$ and quantum relations
on $\ell^{\infty}(X)\subseteq B(\ell^{2}(X))$. The bijection is given by

$R\mapsto V_{R}=\text{span}\\{e_{ij}:(i,j)\in R\\}\qquad V\mapsto
R_{V}=\\{(i,j)\in X\times X:\exists T\in V\text{ s.t. }T_{ij}\neq 0\\}.$

Since any graph structure on a vertex set $X$ just corresponds to a reflexive
symmetric relation $R\subseteq X^{2}$ ($R$ is the set of edges), we have
Weaver’s notion of a quantum graph, which generalizes the matrix quantum
graphs coming from Duan-Severini-Winter.

In the classical setting we have therefore three ways to view a graph: an
adjacency matrix, a relation on the set of vertices and an operator system of
a special kind. We would like to explain how a similar correspondence works
for quantum graphs, where we replace the algebra of functions on the vertex
set by a matrix algebra. To make the approach cleaner, we will first discuss
the case of general quantum relations and then we will discuss what the
symmetry and reflexivity mean in all three pictures.

In order to work with adjacency matrices in the sense of [MRV18], we have to
pick a specific functional on the matrix algebra, and the choice of
normalization is not consistent in the literature. We will be working with the
pair $(M_{n},\tau)$, where $\tau(x):=n\operatorname{Tr}(x)$ so that
$\tau(\mathds{1})=n^{2}=\dim M_{n}$.

######  Lemma 1.4.

Let $m:M_{n}\otimes M_{n}\to M_{n}$ be the multiplication map. Let
$m^{\ast}:M_{n}\to M_{n}\otimes M_{n}$ be the adjoint with respect to the
inner product induced by $\tau$. Then
$m^{\ast}(e_{ij})=\frac{1}{n}\sum_{k}e_{ik}\otimes e_{kj}$. It follows that
$mm^{\ast}=Id$.

######  Proof.

Direct verification. $\blacksquare$

We will first handle the correspondence between subspaces of $M_{n}$ (quantum
relations in the sense of Weaver) and projections in $M_{n}\otimes
M_{n}^{op}$.

######  Proposition 1.5 (Weaver).

There is a bijective correspondence between the set of subspaces of $M_{n}$
and projections in $M_{n}\otimes M_{n}^{op}$.

######  Proof.

Recall that $M_{n}\otimes M_{n}^{op}$ acts on $M_{n}$ by left-right
multiplication. Denote the action map $M_{n}\otimes M_{n}^{op}\to B(M_{n})$ by
$\Phi$; it is actually a linear isomorphism, as verified by a simple dimension
count. Let $V\subset M_{n}$ be a subspace. Define the corresponding left ideal
$I_{V}\subset M_{n}\otimes M_{n}^{op}$ via $I_{V}:=\\{x\in M_{n}\otimes
M_{n}^{op}:\Phi(x)_{|V}=0\\}$. It is a well-known fact that left ideals in
finite dimensional $C^{\ast}$-algebras are principal and represented by a
unique projection $\widetilde{p_{V}}$. The projection
$p_{V}:=Id-\widetilde{p_{V}}$ will be the one we are interested in. So far we
have established a map $V\mapsto p_{V}$, which is actually order preserving.
It is not difficult to check that $\Phi(p_{V})$ is the orthogonal projection
from $M_{n}$ onto $V$ (with respect to the trace), so the correspondence
between $V$ and $p_{V}$ is bijective. $\blacksquare$

We will now go from the projection $p\in M_{n}\to M_{n}^{op}$ to the
corresponding adjacency matrix.

######  Lemma 1.6.

There is a bijective correspondence between elements $X\in M_{n}\otimes
M_{n}^{op}$ and linear maps $T\in B(M_{n})$ given by
$T_{X}(x):=(Id\otimes\tau)(X(1\otimes x))$ and $X_{T}:=(A\otimes
Id)m^{\ast}(\mathds{1})$.

######  Proof.

Let us begin by noting that $X_{T}$ is essentially the Choi matrix of the map
$T$: we have

$X_{T}=\frac{1}{n}\sum_{i,j=1}^{n}A(e_{ij})\otimes e_{ji}.$

On the other hand, any $X\in M_{n}\otimes M_{n}^{op}$ can uniquely represented
as $X=\frac{1}{n}\sum_{i,j}^{n}T_{ij}\otimes e_{ji}$. By a simple computation
we get

$T_{X}(x)=\sum_{i,j=1}^{n}T_{ij}\operatorname{Tr}(xe_{ji})=\sum_{i,j=1}^{n}x_{ij}T_{ij}.$

It follows that $T_{ij}=T_{X}(e_{ij})$, so we indeed have a bijective
correspondence. $\blacksquare$

We will now describe a class of linear maps on $M_{n}$ for which the
corresponding Choi matrix is a projection.

######  Proposition 1.7.

The element $P\in M_{n}\otimes M_{n}^{op}$ is a projection if and only if the
corresponding linear map $A:=T_{P}\in B(M_{n})$ satisfies $m(A\otimes
A)m^{\ast}=A$ and is completely positive.

######  Proof.

Recall that $P$ is of the form $P=\frac{1}{n}\sum_{i,j=1}^{n}A(e_{ij})\otimes
e_{ji}$. It is a projection if and only if it is idempotent and a positive
operator. Choi’s theorem says that it is positive iff the corresponding linear
map $A$ is completely positive. It is idempotent if it is equal to (recall
that we multiply in $M_{n}\otimes M_{n}^{op})$:

$\frac{1}{n^{2}}\sum_{i,j,k,l=1}^{n}A(e_{ij})A(e_{kl})\otimes e_{lk}e_{ji}.$

It follows that $j=k$ and we are left with

$\frac{1}{n^{2}}\sum_{i,l=1}^{n}\left(\sum_{j=1}^{n}A(e_{ij})A(e_{jl})\right)\otimes
e_{li}.$

It follows that $\frac{1}{n}\sum_{j=1}^{n}A(e_{ij})A(e_{jl})=A(e_{il})$, which
means exactly that $m(A\otimes A)m^{\ast}=A$, when applied to $e_{il}$, so we
are done. $\blacksquare$

######  Definition 1.8.

We call a completely positive map $A:M_{n}\to M_{n}$ a quantum adjacency
matrix if it satisfies

$m(A\otimes A)m^{\ast}=A.$

$\blacklozenge$

####  1.2.1 Symmetry and reflexivity in different guises

In Weaver’s terminology, a quantum graph is a symmetric and reflexive quantum
relation: for an operator space $V\in M_{n}$ these conditions mean that
$V=V^{\ast}$ and $Id\in V$, respectively. Thus a quantum graph is exactly an
operator subsystem of $M_{n}$. We would like to check now what do these
conditions mean in terms of the associated projection and the quantum
adjacency matrix.

######  Proposition 1.9.

Let $V\subset M_{n}$ and let $P_{V}\in M_{n}\otimes M_{n}^{op}$ be the
corresponding projection. The $V=V^{\ast}$ if and only if
$P_{V}=\sigma(P_{V})$, where $\sigma$ is an automorphism of $M_{n}\otimes
M_{n}^{op}$ that flips the two tensor factors. The condition $\mathds{1}\in V$
corresponds to $m(P_{V})=\mathds{1}$, where we abuse the notation slightly and
view the multiplication map as acting from $M_{n}\otimes M_{n}^{op}$ to
$M_{n}$.

######  Proof.

Recall that $\Phi(P_{V}):M_{n}\to M_{n}$ is the orthogonal projection onto
$V$. Therefore $\mathds{1}\in V$ iff $\Phi(P_{V})(\mathds{1})=\mathds{1}$,
which can be translated into $m(P_{V})=\mathds{1}$. If $P$ is the orthogonal
projection onto $V$, then the orthogonal projection onto $V^{\ast}$ is given
by $\widetilde{P}(x):=(Px^{\ast})^{\ast}$. If $P_{V}=\sum_{i}X_{i}\otimes
Y_{i}$, so $\Phi(P_{V})(x)=\sum_{i}X_{i}xY_{i}$. It follows that the
orthogonal projection onto $V^{\ast}$ is equal to
$\sum_{i}Y_{i}^{\ast}xX_{i}^{\ast}$. Recall that $P_{V}=\sum_{i}X_{i}\otimes
Y_{i}=\sum_{i}X_{i}^{\ast}\otimes Y_{i}^{\ast}$ is self-adjoint, so the
projection onto $V^{\ast}$ corresponds to $\sigma(P_{V})$, i.e. $V=V^{\ast}$
iff $P_{V}=\sigma(P_{V})$. $\blacksquare$

We will now check what the symmetry and reflexivity conditions mean in terms
of the quantum adjacency matrix.

######  Proposition 1.10.

Let $V\subset M_{n}$. We have $V=V^{\ast}$ if and only if the quantum
adjacency matrix $A:M_{n}\to M_{n}$ is self-adjoint. The condition $Id\in V$
is equivalent to the equality $m(A\otimes Id)m^{\ast}(\mathds{1})=\mathds{1}$.

######  Proof.

Let $P_{V}$ be the projection corresponding to $V$. Suppose that $V=V^{\ast}$
and $P_{V}=\sum_{i}P_{i}\otimes Q_{i}=\sum_{i}Q_{i}\otimes P_{i}$. The
adjacency matrix is equal to
$Ax=\sum_{i}P_{i}\tau(Q_{i}x)=\sum_{i}Q_{i}\tau(P_{i}x)$. If we compute

$\tau(Axy)=\sum_{i}\tau(P_{i}y)\tau(Q_{i}x)=\sum_{i}\tau(Q_{i}y)\tau(P_{i}x),$

we quickly see that $V=V^{\ast}$ is equivalent to $\tau((Ax)y)=\tau(xAy)$,
which combined with positivity of $A$ shows that it is self-adjoint.

Consider now the condition $\mathds{1}\in V$. Recall that
$P_{V}=\frac{1}{n}\sum_{i,j=1}^{n}A(e_{ij})\otimes e_{ji}$, so
$m(P_{V})=\mathds{1}$ means that

$\frac{1}{n}\sum_{i,j}A(e_{ij})e_{ji}=\mathds{1}.$

The left-hand side is equal to $m(A\otimes Id)m^{\ast}(\mathds{1})$.
$\blacksquare$

###  1.3 Correspondence between quantum relations and quantum adjacency
matrices made concrete

It will be useful to have a number of different perspectives on quantum
graphs. For example, it is very difficult to come up with a good random model
of a quantum adjacency matrix, but it is very simple, when we look at the
corresponding subspace of a matrix algebra. In order to benefit from the
situation, we need a more concrete way of translating from one approach to the
other. This is the aim of this subsection.

######  Proposition 1.11.

Let $V\subset M_{n}$ be a $d$-dimensional subspace with an orthonormal basis
(with respect to the usual trace) $(A_{i})_{i\in[d]}$. Then the orthogonal
projection $P_{V}\in M_{n}\otimes M_{n}^{op}$ is equal to
$\sum_{i,k,l}A_{i}e_{kl}\otimes A_{i}^{\ast}e_{lk}$. The quantum adjacency
matrix is given by $Ax=n\sum_{i=1}^{d}A_{i}xA_{i}^{\ast}$.

######  Proof.

The orthogonal projection onto $V$ is given by
$Px=\sum_{i=1}^{d}A_{i}\operatorname{Tr}(xA_{i}^{\ast})$. Note that
$\operatorname{Tr}y\mathds{1}=\sum_{k,l}e_{kl}ye_{lk}$, so

$Px=\sum_{i,k,l}A_{i}e_{kl}xA_{i}^{\ast}e_{lk}.$

It follows that for $X:=\sum_{i,k,l}A_{i}e_{kl}\otimes A_{i}^{\ast}e_{lk}$,
$\Phi(X)=P$, so $X=P_{V}$. If we have our projection, we can easily compute
the adjacency matrix

$Ax=\sum_{i,k,l}A_{i}e_{kl}\tau(xA_{i}^{\ast}e_{lk})=n\sum_{i,k,l}A_{i}e_{kl}(xA_{i}^{\ast})_{kl}.$

Note that $A_{i}e_{kl}=\sum_{r}(A_{i})_{rk}e_{rl}$, so we obtain

$Ax=n\sum_{i,k,l,r}(A_{i})_{rk}(xA_{i}^{\ast})_{kl}e_{rl}.$

After summing over $k$ we finally get

$Ax=n\sum_{i}A_{i}xA_{i}^{\ast}.$

$\blacksquare$

####  1.3.1 Automorphisms of quantum graphs

We will now see how to define automorphisms of quantum graphs in all three
pictures described above.

######  Definition 1.12.

Let $V\subset M_{n}$ be a quantum relation. An automorphism of $V$ is a
$\ast$-automorphism $\Phi:M_{n}\to M_{n}$ such that $\Phi(V)=V$. Since any
$\ast$-automorphism of $M_{n}$ is given by a conjugation by a unitary, we will
usually identify automorphisms of quantum relations with unitaries $U\in
M_{n}$ such that $UVU^{\ast}=V$. $\blacklozenge$

######  Proposition 1.13.

Let $V\subset M_{n}$ be a quantum relation. Let $P=\sum_{i}P_{i}\otimes
Q_{i}\in M_{n}\otimes M_{n}^{\operatorname{op}}$ be the corresponding
orthogonal projection and let $A:M_{n}\to M_{n}$ be the adjacency matrix. Then
a unitary $U\in M_{n}$ is an automorphism of $V$ iff
$P=\sum_{i}UP_{i}U^{\ast}\otimes UQ_{i}U^{\ast}$ iff
$U^{\ast}A(x)U=A(U^{\ast}xU)$. In particular, any unitary $U$ that gives an
automorphism commutes with the degree matrix $D:=A\mathds{1}$.

######  Proof.

Let $P_{V}:M_{n}\to M_{n}$ be the orthogonal projection onto $V$, represented
by $P\in M_{n}\otimes M_{n}^{\operatorname{op}}$. The orthogonal projection
onto $UVU^{\ast}$ is given by $P_{UVU^{\ast}}x=UP_{V}(U^{\ast}xU)U^{\ast}$. It
readily follows that if $P=\sum_{i}P_{i}\otimes Q_{i}$ then
$P_{U}=\sum_{i}UP_{i}U^{\ast}\otimes UQ_{i}U^{\ast}$.

Consider now the quantum adjacency matrix (see the proof of Proposition 1.10)
$Ax:=\sum_{i}P_{i}\tau(Q_{i}x)$. The quantum adjacency matrix corresponding to
$P_{U}$ is given by

$A_{U}x:=\sum_{i}UP_{i}U^{\ast}\tau(xUQ_{i}U^{\ast})=\sum_{i}UP_{i}U^{\ast}\tau(U^{\ast}xUQ_{i}).$

The two are equal if and only if $A(U^{\ast}xU)=U^{\ast}A(x)U$. If we apply
this equality to $x=\mathds{1}$ then we get
$A\mathds{1}=U^{\ast}A\mathds{1}U$, that is $UD=DU$. $\blacksquare$

A tensor-category-theoretic interpretation of Proposition 1.13 would run as
follows: the compact group $U_{n}$ acts on $M_{n}$ by conjugation, and
consider the subgroup $G\leq U_{n}$ leaving $V$ invariant. The dual of $M_{n}$
as a $U_{n}$-representation is isomorphic to the complex conjugate space
$\overline{M_{n}}\cong M_{n}$, via the trace pairing:

$M_{n}\otimes M_{n}\ni A\otimes B\mapsto\mathrm{Tr}(A^{*}B).$

Under $G$ the dual $\overline{V}\subset\overline{M_{n}}$ is also conjugation-
invariant, and upon identifying

$V\otimes\overline{V}\cong\mathrm{End}(V)$

the identity $\operatorname{id}\in\mathrm{End}(V)$, corresponding to

$\sum_{i=1}^{e}S_{i}\otimes T_{i}\in V\otimes\overline{V}$ (1-1)

for trace-dual bases $\\{S_{i}\\}\subset V$ and
$\\{T_{i}\\}\subset\overline{V}$, must also be $G$-invariant. In short:
conjugation by $U\otimes U$, $U\in G$ fixes 1-1 for any

  * •

basis $\\{S_{i}\\}$ for $V$;

  * •

with dual basis $\\{T_{i}\\}$ with respect to the trace pairing.

Note furthermore that since $M_{n}\cong\overline{M_{n}}$ via the adjoint map
$A\mapsto A^{*}$ and $V$ is self-adjoint (being an operator system), we have
$\overline{V}=V$. Finally, the degree matrix is nothing but the image of 1-1
through the multiplication $M_{n}\otimes M_{n}\to M_{n}$, which itself is
$U_{n}$-equivariant.

###  1.4 Random models of quantum graphs

In this section we will describe the random models that we will be dealing
with. For classical graphs there are two main models of interest (both called
Erdős-Rényi models): $G(n,p)$, where $0<p<1$ and $G(n,M)$, where $0\leqslant
M\leqslant\binom{n}{2}$. In the first one two vertices are connected by an
edge with probability $p$, independently over all pairs of vertices, and
$G(n,M)$ is a uniform distribution over all graphs with exactly $M$ edges. In
the $G(n,p)$ the probability that the graph has exactly $M$ edges is given by
the binomial distribution

$\binom{\binom{n}{2}}{M}p^{M}(1-p)^{\binom{n}{2}-M}$

and all graphs with $M$ edges have exactly the same probability. It follows
that the $G(n,p)$ can be recovered as a weighted sum of the $G(n,M)$ models
and this is the approach that we will take, since there is no reasonable
notion of a vertex of a quantum graph, so it does not seem feasible to define
the $G(n,p)$ model directly.

Traditionally random graphs are undirected and we will follow this tradition.
Moreover we will consider reflexive, undirected graphs, i.e. we will be
dealing with operator subsystems of the matrix algebra $M_{n}$. The dimension
of such a subsystem can be interpreted as the average degree of our quantum
graph; indeed, by Proposition 1.11 the normalized trace of the degree matrix
$D=A\mathds{1}$ is equal to $d$, the dimension of our operator system.
Actually, since we are dealing with reflexive graphs, it is more reasonable to
call the number $d-1$ the average degree.

In order to find a good random model of operator subsystems of a given
dimension $d+1$, we can notice that that its sufficient to take a random
$d$-dimensional subspace of Hermitian matrices and add identity to it. Among
the most famous models of self-adjoint matrices is the GUE, which we will
employ.

######  Definition 1.14.

Fix $n\in{\mathbb{N}}$ and $0\leqslant d\leqslant n^{2}-1$. We define the
model $QG(n,d)$ to be a random operator system
$V_{d}:=\operatorname{span}(\mathds{1},X_{1},\dots,X_{d}\\}$, where
$X_{1},\dots,X_{d}$ are independent GUE matrices. Actually, we will take
$X_{i}$ to be the traceless GUE matrix, i.e. the centered version of GUE which
is constructed from the usual GUE by subtracting an appropriate multiple of
the identity. $\blacklozenge$

######  Remark 1.15.

In the specified range of $d$ the GUE matrices $X_{1},\dots,X_{d}$ are almost
surely linearly independent, so their span is a $d$-dimensional subspace of
the space $M_{n,H}^{0}$ of traceless Hermitian matrices, which has dimension
$n^{2}-1$. We have therefore a map from a full measure subset of
$\left(M_{n,H}^{0}\right)^{d}$ to the Grassmannian
$\operatorname{Gr}(d,n^{2}-1)$, which maps the tuple $(X_{1},\dots,X_{d})$ to
its span. We can consider the probability measure on the Grassmannian by
pushing forward via this map. As the density of GUE is proportional to
$\exp(-\operatorname{Tr}X^{2})$, it is invariant under all maps on
$M_{n,H}^{0}$ orthogonal with respect to the Hilbert-Schmidt product, hence so
is its pushforward. It follows that the measure on the Grassmannian is
invariant under $O(n^{2}-1)$, i.e. it has to be the unique Haar measure. This
is the right analogue of a uniform distribution appearing in the classical
$G(n,M)$ model. $\blacklozenge$

It is not difficult now to check that E is a consequence of C. Before doing
that, recall that Hamana introduced in [Ham79] the $C^{\ast}$-envelope of an
operator system $S$, which is the unique $C^{\ast}$-algebra $C^{\ast}(S)$
containing $S$ completely order isomorphically, such that whenever $S$ is
embedded completely order isomorphically inside a $C^{\ast}$-algebra $B$ then
the identity on $S$ extends to a quotient from the $C^{\ast}$-algebra
generated by $S$ inside of $B$ onto $C^{\ast}(S)$.

######  Proposition 1.16.

Fix $n\geqslant 3$ and $2\leqslant d\leqslant n^{2}-3$. If the automorphism
group of the random quantum graph $QG(n,d)$ is almost surely trivial, then the
automorphism group of the underlying operator system is almost surely trivial.

######  Proof.

Since $d\geqslant 2$, the $C^{\ast}$-algebra generated by $V_{d}$ is almost
surely equal to $M_{n}$, as two independent GUE matrices almost surely
generate the full matrix algebra. Since the algebra $M_{n}$ is simple, it
follows that the $C^{\ast}$-envelope of $V_{d}$ is equal to $M_{n}$. It
follows that any complete order automorphism of $V_{d}$ gives rise to an
automorphism of $M_{n}$, which is exactly an automorphism of $V_{d}$ viewed as
a quantum graph. It follows that the automorphism of $V_{d}$ had to be the
identity. $\blacksquare$

It is time to introduce the analogue of the $G(n,p)$ model for quantum graphs.

######  Definition 1.17.

Fix $n\in{\mathbb{N}}$ and $0<p<1$. We define the random model $QG(n,p)$ in
the following way: we first choose a random $0\leqslant d\leqslant n^{2}-1$
according to the binomial distribution $B(n^{2}-1,p)$ and the choose a random
operator subsystem of $M_{n}$ according to the model $QG(n,d)$.
$\blacklozenge$

Here we can already show that D follows easily from C.

######  Proposition 1.18.

If for any $d$ between $2$ and $n^{2}-3$ the automorphism group of a quantum
graph in the $QG(n,d)$ model is almost surely trivial then the automorphism
group of a quantum graph in the $QG(n,p(n))$ model is asymptotically almost
surely trivial as soon as $\lim_{n\to\infty}n^{2}p(n)=\infty$ and
$\lim_{n\to\infty}n^{2}(1-p(n))=\infty$. If $p(n)$ satisfies
$\lim_{n\to\infty}n^{2-\varepsilon}p(n)=\infty$ and
$\lim_{n\to\infty}n^{2-\varepsilon}(1-p(n))=\infty$ for some $\varepsilon>0$
then it holds with overwhelming probability.

######  Proof.

For $d$ between $2$ and $n^{2}-3$ the automorphism group is almost surely
trivial, it can be nontrivial if $d$ happens to be equal to $0$, $1$,
$n^{2}-2$, or $n^{2}-1$. In the model $QG(n,p)$ number $d$ is chosen according
to the binomial distribution $N(n^{2}-1,p)$, so the probability that it is
equal to one of those four numbers is equal to
$P_{n}:=(1-p)^{n^{2}-1}+(n^{2}-1)p(1-p)^{n^{2}-2}+(n^{2}-1)p^{n^{2}-2}(1-p)+p^{n^{2}-1}$.
Let us look at the first term $(1-p)^{n^{2}-1}$. It can be rewritten as
$\left((1-p)^{\frac{1}{p}}\right)^{(n^{2}-1)p}$. By the inequality
$1-x\leqslant e^{-x}$, we have that $(1-p)^{p}\leqslant e^{-1}$, so this whole
expression is bounded above by $\exp(-(n^{2}-1)p))$. If $p\cdot n^{2}$
converges to infinity, then this expression converges to $0$. If we denote
$q_{n}:=(n^{2}-1)p(n)$, then the second term in in $P_{n}$ can be bounded
above by $q_{n}e^{-q_{n}}$, so it also converges to $0$. The last two terms
can be handled in the same way provided that we have
$\lim_{n\to\infty}(1-p(n))n^{2}=\infty$.

If the slightly stronger assumptions
$\lim_{n\to\infty}n^{2-\varepsilon}p(n)=\infty$ and
$\lim_{n\to\infty}n^{2-\varepsilon}(1-p(n))=\infty$ hold, then one can take
advantage of the exponential decay to show that the automorphism group is
trivial with overwhelming probability. $\blacksquare$

##  2 Small quantum automorphism groups

The present section is devoted to results to the effect that various
structures (graphs, quantum sets) have small quantum automorphism groups
“generically”.

###  2.1 Enhanced quantum sets

######  Definition 2.1.

A finite measured quantum set is a pair $X=({\mathcal{O}}(X),\psi_{X})$
consisting of a finite-dimensional $C^{*}$-algebra ${\mathcal{O}}(X)$ and a
state $\psi_{X}$ on it. The size or cardinality $|X|$ of $X$ is
$\dim{\mathcal{O}}(X)$.

We often abbreviate the term to ‘quantum set’ and write $L^{2}(X)$ for the
Hilbert space structure induced on ${\mathcal{O}}(X)$ by the state.

An enhanced quantum set is a finite measured quantum set $X$ equipped with a
self-adjoint operator $A_{X}$ on $L^{2}(X)$. An enhanced quantum set is demi-
classical if the underlying algebra ${\mathcal{O}}(X)$ is commutative.

Unless specified otherwise states $\psi_{X}$ as above are assumed faithful.
$\blacklozenge$

We give sufficient conditions that will ensure the quantum automorphism group
of a demi-classical enhanced quantum set is trivial. This requires some
preparation.

######  Definition 2.2.

Let $(e_{i})_{i=1}^{n}$ be a basis of a finite-dimensional vector space $V$.
Two vectors in $V$ overlap with respect to $(e_{i})$ (or simply overlap when
the basis is understood) if their expansions contain non-zero coefficients
with respect to at least one $e_{i}$.

An operator $A\in\mathrm{End}(V)$ is thick (with respect to $(e_{i})$) if all
of its eigenvectors mutually overlap. $\blacklozenge$

In the context of a demi-classical enhanced quantum set the basis will always
be the standard one, consisting of minimal projections of ${\mathcal{O}}(X)$,
and we will be typically interested in the thickness of the adjacency matrix
$A_{X}$.

######  Proposition 2.3.

Let $X=({\mathcal{O}}(X),\psi_{X},A_{X})$ be a demi-classical enhanced quantum
set whose adjacency matrix $A_{X}$ has simple spectrum and is thick. Then, the
quantum automorphism group $G_{X}$ isomorphic to $({\mathbb{Z}}/2)^{n}$ for
some $n$.

######  Proof.

It is enough to argue that the $G_{X}$ is classical, for then the fact that it
is a $2$-group follows:

Suppose we know that $G_{X}$ is classical. Then every $T\in G_{X}$ operates as
a permutation on the classical set $X$ and scales each eigenvector $v$ of
$A_{X}$ (because the spectrum is simple): $Tv=\lambda v$ for some
$\lambda\in\mathbb{C}$. Since $T$ permutes the components of $v$ the scalar
$\lambda$ must be a root of unity, and the fact that $v$ is a real vector
implies that $\lambda=\pm 1$.

It thus remains to argue that under the hypotheses $G_{X}$ is indeed
classical. To see this, note first that the coaction preserves the one-
dimensional eigenspaces of $A_{X}$ and hence every eigenvector $v$ gives rise
to a grouplike element $g_{v}$ via

$v\mapsto v\otimes g_{v}.$ (2-1)

It follows that ${\mathcal{O}}(G_{X})$ is the group algebra of a finite group
$\Gamma$ generated by the $g_{v}$ (as $v$ ranges over an eigenbasis for
$A_{X}$) so it will be enough to show that every two $g_{v}$ commute (for then
$\Gamma$ is abelian and $G_{X}=\widehat{\Gamma}$ will be its Pontryagin dual).

The coaction 2-1 is nothing but a $\Gamma$-graded algebra structure on
${\mathcal{O}}(X)$. This grading assigns degree $g_{v}$ to each $v$ and, being
compatible with the algebra structure, assigns degree $g_{v}g_{w}$ to $vw=wv$.
The thickness hypothesis shows that $vw\neq 0$ and hence
$g_{v}g_{w}=g_{w}g_{v}$. This finishes the proof. $\blacksquare$

###  2.2 Plain graphs

Here we give an alternative proof of [LMR20, Theorem 3.14], stating that as
the size $n$ goes to infinity, the probability that the random graph
$G\left(n,\frac{1}{2}\right)$ has trivial quantum automorphism group goes to
$1$. We also generalize that result slightly in that the random graphs being
considered are $G(n,p)$ rather than $G\left(n,\frac{1}{2}\right)$.

######  Theorem 2.4.

Let $p\in(0,1)$. As $n\to\infty$ the probability that the random graph
$G(n,p)$ has trivial quantum automorphism group approaches $1$.

######  Proof.

We know from [TV17, Theorem 1.3] or [OVW16, Theorem 1.4] that overwhelmingly
(see Definition 1.1), the adjacency matrix $A=A_{X}$ of a random graph has
simple spectrum. Furthermore, the second part of [OVW16, Theorem 1.4] also
shows that overwhelmingly, no $A$-eigenvectors have any vanishing coordinates.

This latter condition (all-non-zero coordinates) is stronger than thickness in
the sense of Definition 2.2, and hence we conclude from Proposition 2.3 that
with overwhelming probability for $X=G(n,p)$, the quantum automorphism group
$G_{X}$ is of the form $({\mathbb{Z}}/2)^{d}$ and in particular classical.

We can now finish using the well known fact that fact almost all random graphs
$G(n,p)$ have trivial classical automorphism group (e.g. [ER63, Theorem 2] for
the case $p=\frac{1}{2}$ and [KSV02, Theorem 3.1] in general). $\blacksquare$

###  2.3 Regular and isospectral graphs

The generic rigidity result in Theorem 2.4 also applies to random regular
graphs $G(n,r)$.

######  Theorem 2.5.

Fix a positive integer $r\geq 3$. As $n\to\infty$ the probability that the
random graph $G(n,r)$ has trivial quantum automorphism group approaches $1$.

######  Proof.

Let $x$ be a vertex of a finite graph. Following [Bol82] we denote by
$d_{i}(x)$ the number of vertices at distance $i$ from $x$. According to
[Bol82, Theorem 6] the probability that the vertices of a random regular graph
have distinct sequences

$d_{1}(x),\ d_{2}(x),\ \cdots$

approaches $1$. Since two vertices $x,y$ in the same orbit of a quantum action
on the graph will have

$d_{i}(x)=d_{i}(y),\ \forall i\geq 1,$

the conclusion follows. $\blacksquare$

Theorem 2.5 will allow us to extend [BCE+20, Example 4.18], obtaining an
abundance of pairs of non-quantum-isomorphic, isospectral graphs with trivial
quantum automorphism groups. The construction mimics that in loc. cit., based
around the procedure outlined in [GM82] for producing isospectral graphs.
Recall [GM82, Theorem 2.2]:

######  Theorem 2.6.

Let $\Gamma$ be a regular graph with $2m$ vertices and partition its vertex
set as $V^{\prime}\sqcup V^{\prime\prime}$ with

$|V^{\prime}|=|V^{\prime\prime}|=m.$

The two graphs $\Gamma^{\prime}$, $\Gamma^{\prime\prime}$ obtained by adding a
vertex and connecting it to $V^{\prime}$ (respectively $V^{\prime\prime}$) are
isospectral.

The following result proves the existence of the announced examples.

######  Proposition 2.7.

Fix a positive integer $r\geq 3$ and consider a random regular graph
$\Gamma=G(2m,r)$ as $m\to\infty$, with $\Gamma^{\prime}$ and
$\Gamma^{\prime\prime}$ as in Theorem 2.6.

  1. (a)

As $m\to\infty$ the probability that $\Gamma^{\prime}$ and
$\Gamma^{\prime\prime}$ have trivial quantum automorphism groups approaches
$1$.

  2. (b)

The same holds for the probability that $\Gamma^{\prime}$ and
$\Gamma^{\prime\prime}$ are not quantum isomorphic.

######  Proof.

We focus on a, as the proof of b is parallel.

For $m>r$ $\Gamma^{\prime}$ has a single vertex of degree $>r$. Since vertices
in the same orbit of a quantum action on a graph have equal degrees, any such
action on $\Gamma^{\prime}$ will preserve both the extra vertex and the
subgraph $\Gamma\subset\Gamma^{\prime}$. But by Theorem 2.5 the probability
that the latter action on $\Gamma$ is trivial approaches $1$ as $m\to\infty$,
hence the conclusion. $\blacksquare$

##  3 Generic small automorphism groups

In this section we study automorphism groups of quantum graphs.

###  3.1 Conjugation actions on tuples

We need a number of remarks on the conjugation action by $GL_{n}$, $U_{n}$
and/or their projective versions $PSL_{n}$, $PSU_{n}$, etc. on spaces spanned
by tuples of matrices. The results have an algebraic-geometric flavor,
revolving around the geometric invariant theory of reductive-group actions; we
collect those results in the present subsection for future reuse. We assume
some familiarity with linear algebraic groups as covered in a number of good
sources: [Hum75, Bor91], etc.

First, we fix some conventions.

######  Convention 3.1.

Throughout,

${\mathcal{X}}:=\\{X_{i},\ 1\leq i\leq d\\}$ (3-1)

denotes a $d$-tuple of $n\times n$ matrices, with $d$ and $n$ fixed ahead of
time and understood from context; we occasionally vary the base symbol ‘$X$’
as in ${\mathcal{Y}}$ denoting a tuple of $Y_{i}$, etc. We say that
${\mathcal{X}}$ is self-adjoint if $X_{i}$ are, i.e. $X_{i}^{*}=X_{i}$.

With that in place,

$\langle X_{i}\rangle:=\mathrm{span}\\{X_{i},\ 1\leq i\leq d\\}$ (3-2)

will be the span of the matrices.

The tuple 3-1 is

  * •

linearly independent, or

  * •

self-adjoint, or

  * •

traceless

if all the $X_{i}$ are.

For linearly independent ${\mathcal{X}}$ we write

$\Lambda{\mathcal{X}}:=X_{1}\wedge\cdots\wedge X_{d}\in\Lambda^{d}M_{n}$

for the corresponding element of the exterior power of the space of matrices.
The span $\langle{\mathcal{X}}\rangle$ can then be identified with an element
of the Grassmannian $\mathrm{Gr}(d,M_{n})$ of $d$-dimensional subspaces of
$M_{n}$, and that element is identified with the line
${\mathbb{C}}\Lambda{\mathcal{X}}\in{\mathbb{P}}(\Lambda^{d}M_{n})$ (regarded
as an element of the projective space of $\Lambda^{d}M_{n}$) upon embedding

$\mathrm{Gr}(d,M_{n})\subset{\mathbb{P}}(\Lambda^{d}M_{n})$

via the Plücker embedding [Har92, Example 6.6]. $\blacklozenge$

The subsequent discussion will hinge crucially on the following observation.

######  Lemma 3.2.

Let ${\mathcal{X}}$ be a linearly independent self-adjoint tuple 3-1. Then,
the orbit of $\Lambda{\mathcal{X}}\in\Lambda^{d}M_{n}$ under the conjugation
action by $G:=PSL_{n}$ is Zariski-closed.

######  Proof.

The complex algebraic variety $G$ has a real structure [Bor91, AG §11] whose
underlying real points make up precisely the maximal compact subgroup
$G_{{\mathbb{R}}}:=PSU_{n}$ of $G$. Note moreover that conjugation by unitary
operators preserves the real vector space

$M_{n,{\mathbb{R}}}:=\\{\text{self-adjoint matrices}\\}$

which in turn is a real structure for $M_{n}$ in the sense that

$M_{n}\cong M_{n,{\mathbb{R}}}\otimes_{{\mathbb{R}}}{\mathbb{C}}.$

It follows that $\Lambda^{d}M_{n}$ is a representation of $G$ defined over
${\mathbb{R}}$. Since the orbit of $\Lambda{\mathcal{X}}$ is closed (in the
standard topology) under the compact group $G_{{\mathbb{R}}}$, the conclusion
follows from [Bir71, Corollary 5.3]. $\blacksquare$

In particular, we also have

######  Corollary 3.3.

Let ${\mathcal{X}}$ be a linearly independent self-adjoint tuple 3-1. Then,
the stabilizer group $G_{\Lambda{\mathcal{X}}}$ of
$\Lambda{\mathcal{X}}\in\Lambda^{d}M_{n}$ under the conjugation action by
$G:=PSL_{n}$ is reductive.

######  Proof.

Indeed, by [Lun73, §2, Proposition] (attributed there to Matsushima [Mat60])
this is a consequence of the closure of the orbit

$G(\Lambda{\mathcal{X}})\subset\Lambda^{d}M_{n},$

which in turn is asserted by Lemma 3.2. $\blacksquare$

######  Theorem 3.4.

Let ${\mathcal{X}}$ be a linearly independent self-adjoint tuple 3-1 and set
$G:=PSL_{n}$ and $K:=PSU_{n}$. Then:

  1. (a)

For $\Lambda{\mathcal{Y}}\in\Lambda^{d}M_{n}$ in a Zariski-open neighborhood
of $\Lambda{\mathcal{X}}$ the isotropy group $G_{\Lambda{\mathcal{Y}}}$ is
conjugate to a subgroup of $G_{\Lambda{\mathcal{X}}}$.

  2. (b)

The same goes for the isotropy groups $K_{\bullet}$ with
$\bullet\in\\{\Lambda{\mathcal{Y}},\Lambda{\mathcal{X}}\\}$ and self-adjoint
${\mathcal{Y}}$.

  3. (c)

Finally, the analogous result holds for the isotropy groups $K_{\bullet}$,
$\bullet\in\\{\langle{\mathcal{Y}}\rangle,\langle{\mathcal{X}}\rangle\\}$ and
self-adjoint ${\mathcal{Y}}$ again, this time the action being that of $K$ on
the Grassmannian $\mathrm{Gr}(d,M_{n})$.

######  Proof.

We prove the three claims separately.

a: As observed in [Ric72, Remark (b) following Proposition 3.3], this follows
from

  * •

the Zariski-closure of the orbit $G(\Lambda{\mathcal{X}})$ (provided by Lemma
3.2) and

  * •

Luna’s étale slice theorem [Lun73, §III.1].

b: For self-adjoint ${\mathcal{Y}}$ the isotropy group
$G_{\Lambda{\mathcal{Y}}}$ is invariant under the complex-conjugate-linear
involution $\Theta:x\mapsto(x^{*})^{-1}$ and

$K_{\bullet}=\\{g\in G_{\bullet}\ |\ \Theta(x)=x\\}.$ (3-3)

This then implies

$G_{\Lambda{\mathcal{Y}}}\subseteq G_{\Lambda{\mathcal{X}}}\Rightarrow
K_{\Lambda{\mathcal{Y}}}\subseteq K_{\Lambda{\mathcal{X}}}.$ (3-4)

Now note furthermore that the inner product

$\langle A,B\rangle:=\mathrm{tr}(A^{*}B),\ A,B\in M_{n}$

induces one on $\Lambda^{d}M_{n}$ making the latter into a Hilbert space in
such a manner that the conjugation action by $G$ respects the $*$-structures:
if we denote that representation by $\rho:G\to GL(\Lambda^{d}M_{n})$ then

$\rho(X^{*})=\rho(X)^{*}\in GL(\Lambda^{d}M_{n}).$

Coupled with 3-3 this means that once we identify $G_{\bullet}$ with a
subgroup of $GL(\Lambda^{d}M_{n})$, $K_{\bullet}$ is its intersection with the
unitary group of $U(\Lambda^{d}M_{n})$. $G_{\bullet}$ thus has a polar
decomposition with respect to $K_{\bullet}$ respectively (e.g. [Ber, the
result labeled ‘Mostow’s Theorem’, p.7]) and the latter are maximal compact
subgroups of the (reductive, by Corollary 3.3) groups $G_{\bullet}$. It
follows that

$K_{\Lambda{\mathcal{Y}}}\subseteq K_{\Lambda{\mathcal{X}}}\Rightarrow
G_{\Lambda{\mathcal{Y}}}\subseteq G_{\Lambda{\mathcal{X}}}.$

by taking Zariski closures, supplementing 3-3 and finishing the proof of b.

c: Preserving the span $\langle{\mathcal{Y}}\rangle\in\mathrm{Gr}(r,M_{n})$
means preserving the line through $\Lambda{\mathcal{Y}}\in\Lambda^{d}M_{n}$.
The group $K$ acts by unitary transformations on the real Hilbert space

$\Lambda^{d}_{{\mathbb{R}}}M_{n,{\mathbb{R}}}\subset\Lambda^{d}M_{n}\cong\Lambda^{d}_{{\mathbb{R}}}M_{n,{\mathbb{R}}}\otimes_{{\mathbb{R}}}{\mathbb{C}},$

where $M_{n,{\mathbb{R}}}$ denotes self-adjoint matrices, as in the proof of
Lemma 3.2, and ‘$\Lambda^{d}_{{\mathbb{R}}}$’ denotes exterior powers of real
vector spaces over ${\mathbb{R}}$. It follows that under the $K$-action
preserving the line means acting on it as $\pm 1$. But then, for elements of
$K$, fixing $\langle{\mathcal{Y}}\rangle$ is equivalent to fixing

$\Lambda{\mathcal{Y}}\otimes\Lambda{\mathcal{Y}}\in(\Lambda^{d}M_{n})^{\otimes
2}.$

The same argument used in the proof of b now applies with
$\Lambda{\mathcal{X}}^{\otimes 2}$ and $(\Lambda^{d}M_{n})^{\otimes 2}$ in
place of $\Lambda{\mathcal{X}}$ and $\Lambda^{d}M_{n}$ respectively (and
similarly for ${\mathcal{Y}}$). $\blacksquare$

Note also the following consequence regarding principal orbits for the actions
of $PSL_{n}$ and $PSU_{n}$ on the self-adjoint Grassmannians. Recall (e.g.
[Ric72, Introduction] or [Aud91, discussion following Proposition I.2.5]) that
a principal orbit for an action is an orbit $Gx$ with the property that the
isotropy groups $G_{y}$ are conjugate to $G_{x}$ throughout a dense open set
$U$ of points $y$.

In the present context we are interested in having $U$ dense open in the
Zariski (rather than usual) topology, hence the phrase Zariski-principal in
the following statement.

######  Corollary 3.5.

The actions of

  * •

$G:=PSL_{n}$ on linearly-independent, self-adjoint $\Lambda{\mathcal{X}}$;

  * •

$K:=PSU_{n}$ on linearly-independent, self-adjoint $\Lambda{\mathcal{X}}$;

  * •

$K$ on spans $\langle{\mathcal{X}}\rangle$ for linearly-independent, self-
adjoint ${\mathcal{X}}$

all have Zariski-principal orbits for arbitrary $d$ and $n$.

######  Proof.

This is immediate from Theorem 3.4: in each case pick a Zariski-open non-empty
(and hence dense, by the irreducibility of the varieties involved) set where
the isotropy group has minimal dimension and the smallest number of components
in the usual topology. $\blacksquare$

######  Remark 3.6.

Actions of compact Lie groups on connected manifolds always have principal
orbits in the usual topology ( as proved for instance in [Aud91, Proposition
I.2.5] and noted in [Ric72, Introduction]); in Corollary 3.5, however, we are
interested in the Zariski topology instead. $\blacklozenge$

In light of Corollary 3.5 the following piece of notation and terminology
makes sense.

######  Notation 3.7.

For positive integers $d$ and $n$ we write
$\textsc{gen}K_{\Lambda{\mathcal{X}}}(d,n)$ of
$\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(d,n)$ for the isotropy group in
$K:=PSU_{n}$ of a generic $\Lambda{\mathcal{X}}$ or, respectively,
$\langle{\mathcal{X}}\rangle$ for self-adjoint, traceless, linearly-
independent $d$-tuples ${\mathcal{X}}\subset M_{n}$.

This is not quite a subgroup of $K$ but rather a conjugacy class therein; we
abuse notation slightly by speaking of $\textsc{gen}K_{\cdots}$ as groups. We
also suppress $d$ and/or $n$ from the notation when convenient, as in
$\textsc{gen}K$ or $\textsc{gen}K(d)$. $\blacklozenge$

In the following statement a group-theoretic property ${\mathcal{P}}$ (e.g.
being finite, trivial, abelian, metabelian, solvable, nilpotent, etc. etc.) is

  * •

hereditary if property ${\mathcal{P}}$ for a group $\Gamma$ entails the
property for all subgroups of $\Gamma$;

  * •

algebraic if property ${\mathcal{P}}$ for a subgroup of a linear algebraic
group entails it for its Zariski closure.

######  Corollary 3.8.

Let $G:=PSL_{n}$ and $K:=PSU_{n}$ be as in Theorem 3.4 and ${\mathcal{P}}$ a
hereditary group-theoretic property for subgroups of a complex linear
algebraic group.

  1. (1)

If the isotropy group $K_{\Lambda{\mathcal{X}}}$ has property ${\mathcal{P}}$
for at least one linearly independent self-adjoint 3-1 then this is the case
for a Zariski-open dense set of tuples ${\mathcal{X}}$.

  2. (2)

The analogous statement holds for isotropy groups
$K_{\langle{\mathcal{X}}\rangle}$ of spans.

  3. (3)

If furthermore ${\mathcal{P}}$ is algebraic then under the hypothesis of 1 its
conclusion holds for algebraic isotropy groups $G_{\Lambda{\mathcal{X}}}$.

######  Proof.

1 and 2 follow immediately from parts b and c of Theorem 3.4, noting that all
varieties involved are irreducible and hence Zariski-density follows from
openness and non-emptiness. As for 3, it follows from the remark made in the
course of the proof of Theorem 3.4 that $K_{\Lambda{\mathcal{X}}}\subset
G_{\Lambda{\mathcal{X}}}$ is maximal compact (and hence Zariski-dense, since
$G_{\Lambda{\mathcal{X}}}$ is reductive by Corollary 3.3). $\blacksquare$

###  3.2 Small isotropy groups

We will be interested in proving results to the effect that the isotropy
unitary group $PSU_{n,\langle{\mathcal{X}}\rangle}$ is small, generically in
the self-adjoint tuple ${\mathcal{X}}$. A number of other simplifying
assumptions will frequently be in place:

  * •

since $1\in M_{n}$ is of course fixed under conjugation, we may as well focus
on traceless ${\mathcal{X}}$ (see Convention 3.1);

  * •

since $d$-tuples of traceless $n\times n$ matrices generically have maximal
dimension

$\min(d,n^{2}-1),$

we assume $d\leq n^{2}-1$ and focus on linearly independent tuples.

  * •

A single self-adjoint matrix will of course have a positive-dimensional
commutant in $M_{n}$, so for $PSU_{n,\langle{\mathcal{X}}\rangle}$ to ever be
trivial we need $2\leq d\leq n^{2}-1$. Additionally, Lemma 3.9 below also
requires $(n^{2}-1)-d\geq 2$ in order to have trivial isotropy groups. In
short, we need

$2\leq d\leq n^{2}-3,$

so we focus on $n\geq 3$ to ensure this range is non-empty.

######  Lemma 3.9.

If ${\mathcal{X}}$ is a linearly independent, self-adjoint traceless $d$-tuple
then

$PSU_{n,\langle{\mathcal{X}}\rangle}=PSU_{n,\langle{\mathcal{X}}\rangle^{\perp}},$

where ‘$\perp$’ indicates the orthogonal complement with respect to the trace
inner product

$\braket{A}{B}=\mathrm{tr}(A^{*}B).$

######  Proof.

This is immediate: the conjugation action by $U_{n}$ is unitary with respect
to the trace inner product in the statement. $\blacksquare$

We note a number of inductive results.

######  Proposition 3.10.

For $n\geq 3$, $2\leq d\leq n^{2}-3$, if
$\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(d,n)$ is trivial then so is the
conjugacy class $\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(d^{\prime},n+1)$
for $2\leq d^{\prime}\leq n^{2}-2$.

The same holds for abelian $\textsc{gen}K$ or for the requirement that it have
order $\leq 2$.

######  Proof.

We focus on the first statement, the second one being entirely analogous.
Consider two cases:

($2\leq d\leq n^{2}-3$) Consider a generic self-adjoint linearly-independent
$d$-tuple $(X_{i})_{i=1}^{d}$ of $(n+1)\times(n+1)$ matrices all of whose non-
zero entries are concentrated in the upper left-hand $n\times n$ corner. The
non-unital subalgebra of $M_{n+1}$ it generates is the upper-left-hand corner
$M_{n}\subset M_{n+1}$, so any unitary $U$ that preserves the span
$\langle{\mathcal{X}}\rangle$ under conjugation will also preserve that matrix
algebra. But then it follows that $U$

  * •

decomposes as a block-diagonal matrix with blocks of size $n$ and $1$,

  * •

and hence its upper left-hand $n\times n$ block acts by conjugation on
$M_{n}\subset M_{n+1}$ preserving $\langle{\mathcal{X}}\rangle$ therein.

The hypothesis and the genericity of ${\mathcal{X}}$ imply that the upper
left-hand $n\times n$ block of $U$ is scalar. This is true of every $U$
projecting to $K_{\langle{\mathcal{X}}\rangle}$, and hence
$K_{\langle{\mathcal{X}}\rangle}$ acts trivially on
$\langle{\mathcal{X}}\rangle$ (i.e. fixes every vector, not just the span).

By continuity the same holds of all tuples sufficiently close to
${\mathcal{X}}$, and hence generically. But for generic ${\mathcal{X}}\subset
M_{n+1}$ the algebra it generates is all of $M_{n+1}$, meaning that
$K_{\langle{\mathcal{X}}\rangle}$ must indeed be trivial.

As for the remaining case:

($d=n^{2}-2$) Simply repeat the argument above appending one additional
diagonal matrix to the tuple, with non-zero $(n+1)\times(n+1)$ entry.
$\blacksquare$

Also note the following variant.

######  Lemma 3.11.

Suppose that for some $n\geq 3$ and $1\leq d$ there is a self-adjoint
$d$-tuple ${\mathcal{Y}}$ of $(n-1)\times(n-1)$ matrices with zero diagonal
such that no non-scalar diagonal unitary preserves their span. Then,
$\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(d+1,n)$ is trivial.

######  Proof.

As in the proof of Proposition 3.10, regard the matrices in ${\mathcal{Y}}$ as
elements of $M_{n}$ via the upper-left-corner embedding $M_{n-1}\subset
M_{n}$. Then, expand ${\mathcal{Y}}$ to
${\mathcal{X}}:={\mathcal{Y}}\cup\\{X\\}$ by adding a generic diagonal self-
adjoint traceless operator $X\in M_{n}$.

The algebra generated by ${\mathcal{X}}$ will be
$M_{n-1}\times{\mathbb{C}}\subset M_{n}$, so the unitary group
$G=K_{\langle{\mathcal{X}}\rangle}$ preserving $\langle{\mathcal{X}}\rangle$
embeds in $U_{n-1}\times{\mathbb{S}}^{1}\subset U_{n}$ and hence leaves
invariant the decomposition
${\mathbb{C}}^{n}\cong{\mathbb{C}}^{n-1}\oplus{\mathbb{C}}$ obtained by
separating the last coordinate. $G$ thus acts on the span
${\mathcal{X}}^{\prime}\subset M_{n-1}$ of the top left $(n-1)\times(n-1)$
blocks of the matrices in ${\mathcal{X}}$.

The trivial-diagonal assumption ensures that the upper left block $X^{\prime}$
of $X$ is the unique operator in $\langle{\mathcal{X}}^{\prime}\rangle$

  * •

in its conjugacy class, and

  * •

having trace $\mathrm{tr}~{}X^{\prime}$,

since any such operator is of the form $X^{\prime}+A$ for off-diagonal $A$ and
hence being conjugate to $X^{\prime}$ entails $A=0$ by a Hilbert-Schmidt-norm
comparison.

It follows that $G$ fixes $X^{\prime}$ and hence consists of diagonal
operators. But then the additional assumption on ${\mathcal{Y}}$ shows that
$G$ is a scalar on ${\mathbb{C}}^{n-1}$. All in all, this means that $G$ acts
trivially on ${\mathcal{X}}$; we can now conclude as in the proof of
Proposition 3.10. $\blacksquare$

We will use Lemma 3.11 in conjunction with the following simple observation.

######  Lemma 3.12.

Let $p\geq 2$ be a positive integer. A generic $m$-dimensional real subspace
$W\leq{\mathbb{C}}^{p}$ with $1\leq m\leq 2p-1$ is not invariant under any
non-trivial diagonal unitary $\pm 1\neq U\in U_{p}$.

######  Proof.

Denote by $e_{i}$, $1\leq i\leq p$ the standard basis of ${\mathbb{C}}^{p}$
and identify

$V_{i}:={\mathbb{C}}e_{i}\cong{\mathbb{R}}^{2}$

(and thus ${\mathbb{C}}^{p}\cong{\mathbb{R}}^{2p}$). For each $1\leq i\leq p$
we can find $m$-dimensional subspaces of ${\mathbb{R}}^{2p}$ that intersect
$V_{i}$ along a line. Such spaces cannot be invariant under diagonal unitaries
whose $i^{th}$ eigenvalue is $\neq\pm 1$. This non-invariance is generic for
each $i$, and hence generic $W$ will not be invariant under any diagonal non-
involutive unitaries.

This leaves the diagonal involutions to deal with, i.e. the diagonal unitaries
with eigenvalues $\pm 1$. If such a unitary $U$ is non-scalar then it splits
${\mathbb{R}}^{2p}$ into a direct sum of non-zero $\pm 1$ eigenspaces $V_{+}$
and $V_{-}$, and $W$ is $U$-invariant if and only if

$W=(W\cap V_{+})\oplus(W\cap V_{-}).$

That this is generically not the case can be verified by a simple dimension
count: there are only finitely many choices for $V_{\pm}$ (aligned with the
fixed coordinate system we are considering), and one can check that for each
specific choice of non-zero $V_{\pm}$ and each choice of

$\dim W\cap V_{+},\quad\dim W\cap V_{-}$

(of which there are finitely many) the dimension of

$(\text{variety of possible }W\cap V_{+})\times(\text{variety of possible
}W\cap V_{-})$

is smaller than that of the real Grassmannian $Gr(m,2p)$ parametrizing our
$W$. $\blacksquare$

The same type of dimension-counting argument used in the proof of Lemma 3.12
also proves the following variant, of use below.

######  Lemma 3.13.

The conclusion of Lemma 3.12 holds for real planes $W\leq{\mathbb{C}}^{p}$,
$\dim_{{\mathbb{R}}}W=2$ and unitaries $U$ ranging over the semidirect product
$D_{p}\rtimes S_{p}$ of diagonal matrices by permutation matrices.

######  Proof.

Lemma 3.12 shows that a unitary $U\in D_{p}\rtimes S_{p}$ leaving a generic
$W$ invariant must have finite order, bounded by $2p!$: indeed, if $U=DP$ is a
decomposition as a product of a diagonal and a permutation matrix, then
$U^{t}=\pm 1$ if $t$ is the least common multiple of the cycle lengths of $P$.
Furthermore, by Lemma 3.12 again, it is enough to consider factorizations
$U=DP$ for non-trivial $P$ (otherwise we are back in the diagonal case).

Decomposing $U$ as a product $DP$ for diagonal $D$ and a permutation matrix
$P$ we will, for the sake of simplicity, assume $P$is a single cycle of order
$p\geq 2$ (in general it will decompose as a product of disjoint cycles, but
this will suffice to illustrate the dimension count).

We have $U^{p}=\pm 1$ (as noted above), so the $p$ eigenvalues of $D$ provide
$p-1$ (real, as opposed to complex) degrees of freedom (because their product
is $\pm 1$). ${\mathbb{C}}^{p}\cong{\mathbb{R}}^{2p}$ decomposes as a direct
sum of $p$ 2-dimensional $U$-eigenspaces, and for $W$ invariance under $U$
means:

  * •

coinciding with one of these eigenspaces, which makes for a 0-dimensional
variety of such $W$ for each choice of $D$-eigenvalues, or

  * •

decomposing as the direct sum of two lines, on in each of two distinct
$U$-eigenspaces; this makes for a 2-dimensional variety, since each line is
selected from a 2-plane and hence ranges over a real projective line.

All in all, counting the $p-1$ degrees of freedom in selecting the eigenvalues
of $D$, the two cases give spaces of dimension $p-1$ and $p+1$ respectively.
In summary, the $W$ invariant under some $U=DP$ range over a
$(p+1)$-dimensional space. On the other hand the Grassmannian parametrizing
the planes $W\leq{\mathbb{R}}^{2p}$ has dimension $2(2p-2)>p+1$ (since $p\geq
2$), finishing the proof. $\blacksquare$

######  Corollary 3.14.

For $3\leq n$ and $2\leq d\leq(n-1)(n-2)$ the group
$\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(d,n)$ is trivial.

######  Proof.

This follows from Lemma 3.11 (with $d$ in place of that result’s $d+1$),
noting that by Lemma 3.12 applied to

$\displaystyle{\mathbb{C}}^{p}$ $\displaystyle\cong\text{strictly upper-
triangular $(n-1)\times(n-1)$ matrices}$ $\displaystyle\cong\text{off-diagonal
self-adjoint $(n-1)\times(n-1)$ matrices}$

we can find

$1\leq d-1\leq 2p-1=(n-1)(n-2)-1$

self-adjoint off-diagonal $(n-1)\times(n-1)$ whose span is not preserved by
non-scalar unitaries. By Lemma 3.11, this gives us the desired range $2\leq
d\leq(n-1)(n-2)$. $\blacksquare$

######  Convention 3.15.

Throughout the discussion below, we will abuse language slightly by referring
to elements of $K_{\langle{\mathcal{X}}\rangle}$ as matrices (rather than
matrices modulo scalars). $\blacklozenge$

######  Theorem 3.16.

For $3\leq n$ and $2\leq d\leq n^{2}-3$ the group
$\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(d,n)$ is trivial.

######  Proof.

We treat the case $n\geq 5$ here, delegating the small cases $n=3,4$ to
Proposition 3.18. The argument is by induction on $n\geq 5$, via Proposition
3.10.

In the base case $n=5$ Corollary 3.14 takes care of the range $2\leq
d\leq(n-1)(n-2)=12$. Since this is precisely half of the range
$2..(n^{2}-1=24)$, we conclude by Lemma 3.9, which allows us to bootstrap the
left-hand half.

As for the induction step of passing to $n+1$ from lower values, we obtain

  * •

the range $2..n^{2}-2$ from Proposition 3.10;

  * •

the range $2..2n+1$ by applying Corollary 3.14 to $n+1$ (in place of $n$) and
noting that

$n(n-1)=((n+1)-1)((n+1)-2)$

dominates our desired upper bound $2n+1$ because $n\geq 5$ (in fact $n\geq 4$
would suffice here);

  * •

and hence the range

$n^{2}-1\quad..\quad(n+1)^{2}-3\quad=\quad((n+1)^{2}-1)-(2n+1)\quad..\quad((n+1)^{2}-1)-2$

by reflection, via Lemma 3.9.

This finishes the proof. $\blacksquare$

######  Corollary 3.17.

For $3\leq n$ and $1\leq d\leq n^{2}-2$ the group
$\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(d,n)$ is abelian.

######  Proof.

The case $2\leq d\leq n^{2}-3$ is covered by Theorem 3.16, whereas a single
traceless matrix $X$ will have simple spectrum and be inequivalent to $-X$,
ensuring that the subgroup of $U_{n}$ preserving the span ${\mathbb{R}}X$ is
diagonal in a basis diagonalizing $X$. $\blacksquare$

######  Proposition 3.18.

The conclusion of Theorem 3.16 holds for $n=3,4$.

######  Proof.

Given the symmetry $d\leftrightarrow n^{2}-1-d$ provided by Lemma 3.9,
Corollary 3.14 covers everything except for the cases

$(n,d)=(3,3),\ (3,4)\text{ and }(4,7),$

which we treat here.

$(n,d)=(3,3):$ In general, for any $n\geq 3$, we can resolve the $d=n$ case by
selecting a tuple ${\mathcal{X}}$ consisting of $n-1$ linearly independent
diagonal matrices $X_{1}$ up to $X_{n-1}$ together with an $n^{th}$ matrix
$X_{n}$ that

  * •

commutes with no non-scalar diagonal operators, ensuring that every $U\in
K_{\langle{\mathcal{X}}\rangle}$ preserves the diagonal algebra and hence
belongs to the semidirect product $D_{n}\rtimes S_{n}$ of the diagonal
unitaries and the permutation matrices;

  * •

is not unitarily equivalent to $-X_{n}$, so that a unitary that preserves the
span ${\mathbb{R}}X_{n}$ must commute with $X_{n}$;

  * •

is generic enough to ensure that no non-scalar unitary commutes with it, as in
the proof of Corollary 3.14 (via Lemma 3.12);

  * •

has above-diagonal entries of distinct moduli, ensuring that no $DP\in
D_{n}\rtimes S_{n}$ for a non-trivial permutation $P$ commutes with it.

Such a tuple ${\mathcal{X}}$ would then have trivial
$K_{\langle{\mathcal{X}}\rangle}\subset PSU_{n}$.

$(n,d)=(3,4)$ or $(4,7):$ We treat the cases in parallel to an extent. In both
cases, we first consider tuples ${\mathcal{X}}$ constructed as follows:

  * •

$n-1$ traceless diagonal operators $X_{i}$, $1\leq i\leq n-1$ spanning
(together with $1$) the diagonal algebra $D_{n}$;

  * •

a linearly independent, self-adjoint traceless tuple $\mathcal{ND}$ of $2n-4$
operators $X_{i}$, $n\leq i\leq d$, all of whose non-zero entries are non-
diagonal and on the last row/column.

If $\mathcal{ND}$ is chosen generically so as to ensure the span
$\langle\mathcal{ND}\rangle$ contains no matrices with precisely one non-zero
entry on the last column, the only elements in the span
$\langle{\mathcal{X}}\rangle$ whose squares belong to $\langle
1,{\mathcal{X}}\rangle$ are diagonal. This intrinsic characterization of
$D_{n}\subset\langle{\mathcal{X}}\rangle$ implies that
$K_{\langle{\mathcal{X}}\rangle}$ preserves it, and hence once more

$K_{\langle{\mathcal{X}}\rangle}\subseteq DU_{n}\rtimes S_{n}.$

On the other hand $K_{\langle{\mathcal{X}}\rangle}$ also preserves the
orthogonal complement $\langle\mathcal{ND}\rangle$ of $D_{n}$ in $\langle
1,{\mathcal{X}}\rangle$, so in fact it must be contained in the semidirect
product $DU_{n}\rtimes S_{n-1}$, where the latter is the group of $n\times n$
permutation matrices permuting only the first $n-1$ coordinates.

Next, note that the real subspace $W$ of ${\mathbb{C}}^{n-1}$ spanned by the
last columns of the matrices in $\mathcal{ND}$ (where the last columns are
regarded as having $n-1$ entries upon dropping their last zero entry) has real
dimension $2n-4$. This means that by Lemma 3.13, generically, that span is not
preserved by any operator in $DU_{n-1}\rtimes S_{n-1}$ save for $-I_{n-1}$:
for $n=3$ we can apply Lemma 3.13 directly, whereas for $n=4$ we can apply it
to the 2-dimensional orthogonal complement of the 4-dimensional $W$. This in
turn means that the only unitary operators in $DU_{n}\rtimes S_{n-1}$ that
preserve $\langle\mathcal{ND}\rangle$ are those of the form

$\mathrm{diag}(\lambda,\cdots,\lambda,\pm\lambda),\quad\lambda\in{\mathbb{S}}^{1}.$

In short, $K_{\langle{\mathcal{X}}\rangle}$ must be contained in this latter
diagonal group.

Now select new tuples repeating the construction virtually verbatim, the only
difference being that the $2n-4$ matrices (for $n=3,4$) in $\mathcal{ND}$ now
have non-zero entries only immediately above/below the main diagonal (i.e.
entries $(i,i\pm 1)$ for $1\leq i\leq n-1$).

Essentially the same argument this time around shows that
$K_{\langle{\mathcal{X}}\rangle}$ will be contained in $D_{n}\rtimes S_{n}$
and act as $-1$ on the off-diagonal matrices $\mathcal{ND}$, But this means
that (unless scalar) it consists of diagonal unitary matrices of the form

$(\lambda,-\lambda\cdots,-\lambda,\lambda)$ (3-5)

(alternating signs).

This already settles the case $n=4$: if
$\textsc{gen}K_{\langle{\mathcal{X}}\rangle}(7,4)$ were non-trivial then Proof
and 3-5, which are obtainable by limiting the generic behavior, would mean
that generically the non-trivial element of $K_{\langle{\mathcal{X}}\rangle}$
has (up to scaling) both a 1 and a 2-dimensional $(-1)$-eigenspace: a
contradiction.

As for the remaining case $(n,d)=(3,4)$, we can take for ${\mathcal{X}}$ a
tuple consisting of one diagonal matrix $X_{1}$ together with 5 generically-
chosen matrices as in previous $\mathcal{ND}$. $\langle{\mathcal{X}}\rangle$
thus consists of matrices of the form

$\begin{pmatrix}x&0&a\\\ 0&y&b\\\ \overline{a}&\overline{b}&z\end{pmatrix}$

with $x$, $y$ and $z$ unique up to simultaneous scaling and $(a,b)$ ranging
over a 3-dimensional real subspace of ${\mathbb{C}}^{2}$. If, say, $x$ and $y$
have equal signs and $(x,y,z)$ is otherwise generic, such a matrix will be
invertible as soon as it has non-zero diagonal. This means that once more
$K:=K_{\langle{\mathcal{X}}\rangle}$ preserves the span ${\mathbb{R}}X_{1}$ of
the diagonal matrix $X_{1}=\mathrm{diag}(x,y,z)$ and hence also
$\langle\mathcal{ND}\rangle$. The genericity of $X_{1}$ further ensures that
$K$ consists of diagonal matrices.

But according to the discussion above, if the generic $K$ is non-trivial then
it consists (modulo scalars) of involutive matrices with 1-dimensional
$(-1)$-eigenspace (cf. Proof), acting on $\langle{\mathcal{X}}\rangle$ with
2-dimensional $\pm 1$-eigenspaces. It remains to observe that in the present
setup no diagonal unitary with 1-dimensional $(-1)$-eigenspace can act with a
2-dimensional $(-1)$-eigenspace on the 3-dimensional real span consisting of

$\begin{pmatrix}0&0&a\\\ 0&0&b\\\ \overline{a}&\overline{b}&0\end{pmatrix}$

with $(a,b)$ as above. This contradicts the non-triviality of the generic $K$,
finishing the proof. $\blacksquare$

###  3.3 The degree matrix

In this subsection we take another route to the main results. We will employ
properties of the degree matrix of a quantum graph. Theorem 3.21 is the same
as Corollary 3.17 and Theorem 3.22 is a weaker version of Theorem 3.16. Even
though we do not fully recover our results, in this approach we obtain
somewhat explicit examples of tuples with trivial automorphism groups, where
we only use a little randomness to obtain diagonal matrices with certain
properties.

######  Proposition 3.19.

Let $V=\operatorname{span}(\mathds{1},X_{1},\dots,X_{d})\subset M_{n}$ be an
operator system generated by $d$ traceless self-adjoint matrices $X_{1},\dots
X_{d}$. Let $A:M_{n}\to M_{n}$ be the corresponding quantum adjacency matrix,
given by Proposition 1.11. If the degree matrix $D:=A\mathds{1}$ has simple
spectrum then the automorphism group of $V$ is abelian. Moreover, the
complement of the set of tuples $(X_{1},\dots,X_{d})$ such that $D$ has simple
spectrum is a closed subvariety, so if there exists such a $d$-tuple, almost
surely all $d$-tuples have this property.

######  Proof.

If $U$ is a unitary in $M_{n}$ such that $UVU^{\ast}=V$, then
$UA(U^{\ast}xU)U^{\ast}=A(x)$, hence $U(A\mathds{1})U^{\ast}=A(\mathds{1})$.
So, as before, if $D=A\mathds{1}$ has simple spectrum then the set of such
unitaries is commutative.

By Proposition 1.11 we have $D=n\sum_{i}A_{i}^{2}$, if $(A_{i})$ is an
orthonormal basis of $V$ consisting of Hermitian matrices. Such a basis can be
obtained from the tuple $(X_{1},\dots,X_{d})$ via the Gram-Schmidt procedure,
i.e. using only algebraic operations. Since having simple spectrum can also be
described as vanishing of a certain polynomial, the set of “bad” tuples is
algebraic, so it has measure zero as soon as it is proper. $\blacksquare$

We will be working with with operator systems for which the degree matrix $D$
is diagonal. We need the following lemma to show that one can construct
operator systems with diagonal degree matrices that have no repeated
eigenvalues.

######  Lemma 3.20.

Let $1\leqslant d\leqslant n-2$. Let $\Lambda=(\lambda_{1},\dots,\lambda_{n})$
be an arbitrary diagonal matrix. Then there exists a $d$-tuple of traceless
diagonal matrices $(X_{1},\dots,X_{d})$ such that $D+\Lambda$ has no repeated
eigenvalues.

######  Proof.

Let $U\in O(n)$ be a Haar orthogonal matrix. Then for each $j$ we can consider
the diagonal matrix $u_{j}:=\sum_{k}u_{jk}e_{k}$, where $e_{k}$ is a shorthand
for $e_{kk}$. For different $j$’s these matrices are mutually orthogonal. Let
$(\tilde{u}_{j})_{j\in[n]}$ be the centered version of $(u_{j})_{j\in[n]}$,
i.e. we subtract from each $u_{j}$ a suitable multiple of the identity to make
it traceless and then apply the Gram-Schmidt procedure to obtain an
orthonormal set. Then
$V:=\operatorname{span}(\mathds{1},\tilde{u}_{1},\dots,\tilde{u}_{d})$ is an
operator system whose degree matrix is equal to
$D=\mathds{1}+n\sum_{j=1}^{d}\widetilde{u}_{j}^{2}$. For convenience, we will
work with the matrix $\widetilde{D}:=\sum_{j=1}^{d}\widetilde{u}_{j}^{2}$.

We want to show that there exists a choice of $U$ such that
$\widetilde{D}+\Lambda$ has no repeated eigenvalues, i.e. all its entries are
distinct. In fact it holds almost surely. In order to prove that, we have to
show for a given pair of diagonal entries that they are different almost
surely; it will follow that almost surely all entries are different.

Let us do it for entries $1$ and $2$. Clearly equality of these two entries is
an algebraic equation in the entries of $U$, so it will hold on measure zero
set as soon as we can exhibit a single example. We will start with the
following vectors $u_{1}=c_{1}e_{1}-c_{2}e_{d+1}-c_{3}e_{d+2}$,
$\widetilde{u}_{k}=e_{k}-\frac{1}{n}\sum_{l=1}^{n}e_{l}$ for
$k\in\\{2,\dots,d\\}$. All the $\widetilde{u}_{k}$’s for $k\geqslant 2$ are
orthogonal to $u_{1}$, so the same will be true for $(u_{k})_{k=2}^{d}$ – the
orthonormal family obtained from $(\widetilde{u}_{k})_{k=2}^{d}$ via the Gram-
Schmidy procedure. We need the coefficients of $u_{1}$ to satisfy
$c_{1}=c_{2}+c_{3}$ and $c_{1}^{2}+c_{2}^{2}+c_{3}^{2}=1$. Note that the
contribution to the entries of $\widetilde{D}+\Lambda$ coming from the vectors
$(u_{k})_{k=2}^{d}$ is independent of our choice for $u_{1}$, so we can
include it in the matrix $\Lambda$, by forming a new matrix
$\widetilde{\Lambda}$. With this choice the first entry of
$\widetilde{D}+\widetilde{\Lambda}$ is equal to
$c_{1}^{2}+\widetilde{\lambda}_{1}$ and the second one is equal to
$\widetilde{\lambda}_{2}$. We can easily choose an appropriate $c_{1}$ so that
the two are not equal. The lemma follows. $\blacksquare$

######  Theorem 3.21.

Fix $n$ and $d\in\\{1,\dots,n^{2}-2\\}$. For almost every $d$-tuple
$(X_{1},\dots,X_{d})$ of traceless self-adjoint matrices the automorphism
group of the quantum graph
$V:=\operatorname{span}\\{\mathds{1},X_{1},\dots,X_{d}\\}$ is abelian.

Before proving this theorem, we need to introduce a certain orthonormal family
of Hermitian matrices in $M_{n}$ that will allow us to build operator systems
with diagonal degree matrices. For any pair $i\neq j$ of numbers in
$\\{1,\dots,n\\}$ we define

$f_{ij}:=\left\\{\begin{array}[]{cl}\frac{1}{\sqrt{2}}(e_{ij}+e_{ji})&\text{if
}i<j\\\ \frac{i}{\sqrt{2}}(e_{ij}-e_{ji})&\text{if }i>j\end{array}\right.$

Note that the family $\mathcal{F}:=(f_{ij})$ is orthonormal and
$f_{ij}^{2}=\frac{1}{2}(e_{ii}+e_{jj})$ is diagonal.

######  Proof (of Theorem 3.21).

By previous discussion, for any $d\in\\{1,\dots,n^{2}-2\\}$ we just need to
provide a single tuple such that the degree matrix has no repeated
eigenvalues.

If $d\leqslant n-2$ then we can use the Lemma 3.20 with $\Lambda=0$. If
$d>n-2$. Then we take a subset of the family $\mathcal{F}$ of cardinality
$d-n+2$, which is always possible, because $\mathcal{F}$ has $n^{2}-n$
elements. We get a corresponding degree matrix $D_{1}$, which is diagonal. By
Lemma 3.20 we can choose an $n-2$-tuple of traceless diagonal matrices with
the corresponding diagonal degree matrix $D_{2}$ such that $D_{1}+D_{2}$ has
no repeated eigenvalues. But $D:=D_{1}+D_{2}$ is exactly the degree matrix of
the combined operator system, which has therefore a degree matrix with simple
spectrum. This ends the proof of the theorem. $\blacksquare$

######  Theorem 3.22.

Let $n\geqslant 6$ and $4\leq d\leq n^{2}-5$. We can construct a $d$-tuple
$(X_{1},\dots,X_{d})$ of traceless Hermitian matrices, such that the degree
matrix is diagonal and has simple spectrum and the automorphism group of the
corresponding quantum graph is trivial.

######  Proof.

We will first show that there exists an appropriate family of Hermitian
matrices with zero diagonals and with a diagonal degree matrix such that there
is no nontrivial diagonal matrix that preserves the span upon conjugation.
Then we will invoke the Lemma 3.20 to upgrade our degree matrix to a one with
simple spectrum, which will show that diagonal matrices were the only possible
candidates for automorphisms.

Assume first that $n\geqslant 7$. Define
$X_{1}:=\sum_{i=1}^{\left[(n-1)/2\right]}f_{2i,2i+1}$ and
$X_{2}:=\sum_{i=1}^{\left[n/2\right]}f_{2i-1,2i}$. As $X_{1}$ and $X_{2}$ are
orthogonal and $X_{1}^{2}$ and $X_{2}^{2}$ are diagonal, the corresponding
degree matrix is diagonal. Let $U:=(u_{1},\dots,u_{n})$ be a diagonal unitary
matrix. Since the automorphism group is really the quotient of the subgroup of
unitaries by the center, i.e. the scalar matrices, we may assume that
$u_{1}=1$. Recall that if $X=(x_{ij})$ is a matrix then $UXU^{\ast}$ has
entries $(u_{i}u_{j}^{-1}x_{ij})$. We can now check when the
$\operatorname{span}(X_{1},X_{2})$ is preserved upon conjugation by $U$. One
condition is that the entries $(i,i+1)$ and $(i+1,i)$ are equal which gives
$u_{i}u_{i+1}^{-1}=u_{i+1}u_{i}^{-1}$, i.e. $u_{i}^{2}=u_{i+1}^{2}$, i.e. the
squares of entries are constant. As $u_{1}=1$, we conclude that $u_{i}=\pm 1$,
so we will from now on write $u_{i}u_{i+1}$ instead of $u_{i}u_{i+1}^{-1}$.
From the form of $X_{1}$ and $X_{2}$ we get that
$u_{i}u_{i+1}=u_{i+2}u_{i+3}$. In particular, only $u_{2}$ and $u_{3}$ are
free variables, because, for example, $u_{4}=u_{2}u_{3}$, since
$u_{1}u_{2}=u_{3}u_{4}$. From the equality $u_{2}u_{3}=u_{4}u_{5}$ it follows
that $u_{5}=1$. From $u_{3}u_{4}=u_{5}u_{6}$, we get $u_{6}=u_{3}u_{4}=u_{2}$.
Moreover, from $u_{2}u_{3}=u_{4}u_{5}=u_{6}u_{7}$ we get that $u_{7}=u_{3}$.
We need to add another matrix to conclude that $u_{2}=u_{3}=1$, which would
prove that $U=\mathds{1}$.

Our choice will be $Y=f_{14}+f_{25}+f_{37}$. We get
$u_{1}u_{4}=u_{2}u_{5}=u_{3}u_{7}$. As $u_{1}=u_{5}=1$, we obtain
$u_{2}=u_{4}$, so $u_{3}=1$, since $u_{2}u_{3}=u_{4}$. On the other hand,
$u_{3}u_{7}=1$, so $u_{4}=u_{2}=1$ and we conclude that all $u_{i}$’s are
equal to one. So as soon as we have the span of $(X_{1},X_{2},Y)$ and nothing
else happens at the entries used by these matrices we will not have nontrivial
diagonal matrices preserving the subspaces upon conjugation. These matrices
have in total $2n+4$ non-zero entries. We do not want to touch the diagonal,
so we have $n^{2}-3n-4$ entries left, where we can insert other members of the
family $\mathcal{F}=(f_{ij})$; whichever we choose, the resulting degree
matrix will be diagonal. After having made this choice, we can invoke the
Lemma 3.20 to choose between $1$ and $n-2$ diagonal matrices that force the
degree matrix of the whole quantum graph to have a simple spectrum.

We have to use at least $4$ matrices in this approach: $X_{1}$, $X_{2}$, $Y$,
and one diagonal, which gives the lower bound $d\geqslant 4$. To get to
$n^{2}-5$, note that it is sufficient to go up to $\frac{n^{2}-1}{2}$, by
using Lemma 3.9. The only thing to note is that is that the degree matrix of
the orthogonal complement will also be diagonal. This follows from the fact
that the degree matrix of the sum of the two will be the sum of the degree
matrices, and this sum is equal to the whole space of traceless matrices,
whose degree matrix is a multiple of identity. Now note that in our
construction we left $n^{2}-3n-4$ unused entries and we can add to it our $3$
matrices $X_{1}$, $X_{2}$, and $Y$, and up to $n-2$ diagonal matrices, so we
we can have a $d$-tuple with $d=n^{2}-2n-3$. This is larger than
$\frac{n^{2}-1}{2}$ already for $n\geqslant 3$.

To deal with the case $n=6$, we use slightly different matrices $X_{1}$,
$X_{2}$, and $Y$. Namely, we take $X_{1}:=f_{12}+f_{34}+f_{56}$,
$X_{2}:=f_{23}+f_{45}+f_{16}$, and $Y:=f_{15}+f_{36}$. By examining $X_{1}$
and $X_{2}$ we get the equalities $u_{1}u_{2}=u_{3}u_{4}=u_{5}u_{6}$ and
$u_{2}u_{3}=u_{4}u_{5}=u_{1}u_{6}$. Remembering that $u_{1}=1$, we get
$u_{3}=u_{5}=1$ and $u_{2}=u_{4}=u_{6}$. If we include $Y$, we get the
additional condition $u_{1}u_{5}=u_{3}u_{6}$, so $u_{6}=1$. In case there are
$16$ unused entries, so we can construct a $d$-tuple with $d=23$, which is
larger than $\frac{35}{2}$. $\blacksquare$

## References

  * [Aud91] Michèle Audin.  The topology of torus actions on symplectic manifolds, volume 93 of Progress in Mathematics.  Birkhäuser Verlag, Basel, 1991.  Translated from the French by the author.
  * [Ban05] Teodor Banica.  Quantum automorphism groups of homogeneous graphs.  J. Funct. Anal., 224(2):243–280, 2005.
  * [BCE+20] Michael Brannan, Alexandru Chirvasitu, Kari Eifler, Samuel Harris, Vern Paulsen, Xiaoyu Su, and Mateusz Wasilewski.  Bigalois extensions and the graph isomorphism game.  Comm. Math. Phys., 375(3):1777–1809, 2020.
  * [Ber] Maxime Bergeron.  Complex reductive algebraic groups.  http://www.math.uchicago.edu/~mbergeron/ComplexReductive.pdf.
  * [Bic03] Julien Bichon.  Quantum automorphism groups of finite graphs.  Proc. Amer. Math. Soc., 131(3):665–673, 2003.
  * [Bir71] David Birkes.  Orbits of linear algebraic groups.  Ann. of Math. (2), 93:459–475, 1971.
  * [Bol82] Béla Bollobás.  Distinguishing vertices of random graphs.  In Graph theory (Cambridge, 1981), volume 62 of North-Holland Math. Stud., pages 33–49. North-Holland, Amsterdam-New York, 1982\.
  * [Bor91] Armand Borel.  Linear algebraic groups, volume 126 of Graduate Texts in Mathematics.  Springer-Verlag, New York, second edition, 1991.
  * [DSW13] Runyao Duan, Simone Severini, and Andreas Winter.  Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number.  IEEE Trans. Inform. Theory, 59(2):1164–1174, 2013.
  * [ER59] P. Erdős and A. Rényi.  On random graphs. I.  Publ. Math. Debrecen, 6:290–297, 1959.
  * [ER63] P. Erdős and A. Rényi.  Asymmetric graphs.  Acta Math. Acad. Sci. Hungar, 14:295–315, 1963.
  * [GM82] C. D. Godsil and B. D. McKay.  Constructing cospectral graphs.  Aequationes Math., 25(2-3):257–268, 1982.
  * [Ham79] Masamichi Hamana.  Injective envelopes of operator systems.  Publ. Res. Inst. Math. Sci., 15(3):773–785, 1979.
  * [Har92] Joe Harris.  Algebraic geometry, volume 133 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1992.  A first course.
  * [Hum75] James E. Humphreys.  Linear algebraic groups.  Springer-Verlag, New York-Heidelberg, 1975.  Graduate Texts in Mathematics, No. 21.
  * [KSV02] Jeong Han Kim, Benny Sudakov, and Van H. Vu.  On the asymmetry of random regular graphs and random graphs.  Random Structures Algorithms, 21(3-4):216–224, 2002.  Random structures and algorithms (Poznan, 2001).
  * [KW12] Greg Kuperberg and Nik Weaver.  A von Neumann algebra approach to quantum metrics.  Mem. Amer. Math. Soc., 215(1010):v, 1–80, 2012.
  * [LMR20] Martino Lupini, Laura Mančinska, and David E. Roberson.  Nonlocal games and quantum permutation groups.  J. Funct. Anal., 279(5):108592, 44, 2020.
  * [Lun73] Domingo Luna.  Slices étales.  In Sur les groupes algébriques, pages 81–105. Bull. Soc. Math. France, Paris, Mémoire 33. 1973.
  * [Mat60] Yozô Matsushima.  Espaces homogènes de Stein des groupes de Lie complexes.  Nagoya Math. J., 16:205–218, 1960.
  * [MRV18] Benjamin Musto, David Reutter, and Dominic Verdon.  A compositional approach to quantum functions.  J. Math. Phys., 59(8):081706, 42, 2018.
  * [OP15] Carlos M. Ortiz and Vern I. Paulsen.  Lovász theta type norms and operator systems.  Linear Algebra Appl., 477:128–147, 2015.
  * [OVW16] Sean O’Rourke, Van Vu, and Ke Wang.  Eigenvectors of random matrices: a survey.  J. Combin. Theory Ser. A, 144:361–442, 2016.
  * [Ric72] R. W. Richardson, Jr.  Principal orbit types for algebraic transformation spaces in characteristic zero.  Invent. Math., 16:6–14, 1972.
  * [TV11] Terence Tao and Van Vu.  Random matrices: universality of local eigenvalue statistics.  Acta Math., 206(1):127–204, 2011.
  * [TV17] Terence Tao and Van Vu.  Random matrices have simple spectrum.  Combinatorica, 37(3):539–553, 2017.
  * [Wea12] Nik Weaver.  Quantum relations.  Mem. Amer. Math. Soc., 215(1010):v–vi, 81–140, 2012.

Department of Mathematics, University at Buffalo, Buffalo, NY 14260-2900, USA

E-mail address<EMAIL_ADDRESS>
Department of Mathematics - Section of Analysis, KU Leuven, Leuven, Belgium

E-mail address<EMAIL_ADDRESS>