How Jellyfish Characterise Alternating Group Equivariant Neural Networks

Edward Pearce–Crumpimperial

imperialDepartment of Computing, Imperial College London, United Kingdom

Edward<EMAIL_ADDRESS>
Machine Learning, ICML

We provide a full characterisation of all of the possible alternating group ($A_n$) equivariant neural networks
whose layers are some tensor power of $\mathbb{R}^{n}$.
In particular,
we find a basis of matrices for the learnable, linear, $A_n$–equivariant layer functions between such tensor power spaces
in the standard basis of $\mathbb{R}^{n}$.

We also describe how our approach generalises to the construction of neural networks that are equivariant to local symmetries.

§ INTRODUCTION

There has been a growing research effort in deep learning to develop

neural network architectures that can be used to learn efficiently from data that possesses an underlying symmetry.
These architectures guarantee that the functions that are learned are subject to a geometric property,
known as equivariance,
that is connected with the symmetry group.
Group equivariant neural networks are important due to the additional advantages that they offer over traditional multilayer perceptron models.
For example, they commonly display high levels of parameter sharing within each layer, resulting in significantly fewer parameters overall.
This often leads to models that show improved prediction performance on new data.

Creating neural network architectures that can be used to learn efficiently from data that has an underlying symmetry

has become an active area of research in deep learning.
All of these architectures

that the functions that can be learned have
a fundamental geometric property in relation to the symmetry group that is involved: namely, equivariance.
The importance of group equivariant neural networks is in part owing to the additional benefits that they offer over their standard multilayer perceptron counterparts.

Typically, they exhibit high levels of parameter sharing within each layer, resulting in far fewer parameters overall.
This often leads to models that have better predictive performance on unseen data.

The symmetry group that has received the most attention,
in terms of it

being explicitly incorporated into

neural network architectures,
is the group of all permutations on some fixed number of objects, called the symmetric group.

Creating neural networks that are equivariant to permutations is highly desirable as many data structures, such as sets and graphs, exhibit natural permutation symmetry.

It is easily understood that the labelling of the elements of a set or the vertices of a graph is arbitrary;
hence, it is crucial to ensure that the functions that are learned from such data

do not depend on how the data is labelled.

In this paper,
we look instead at how to construct neural networks that are equivariant to the alternating group.
The alternating group is an index two subgroup of the symmetric group consisting solely

of all
of the
even permutations.

Alternating group symmetry has proven to be particularly useful when learning from spherical image data that has been discretely represented on an icosahedron
[Zhang et al., 2019];
in constructing convolutional neural networks on an icosahedron
[Cohen et al., 2019];
and in estimating polynomials that are invariant to the action of the alternating group
[Kicki et al., 2020].

we give a full characterisation of all of the possible alternating group equivariant neural networks whose layers are some tensor power of $\mathbb{R}^{n}$ by finding a basis of matrices for the learnable, linear, alternating group equivariant layer functions between such tensor power spaces in the standard basis of $\mathbb{R}^{n}$.

Our approach is similar the one presented in the papers written by
Pearce–Crump pearcecrump, pearcecrumpB.
They used different sets of set partition diagrams to characterise
all of the learnable, linear, group equivariant layer functions
between tensor power spaces in the standard basis of $\mathbb{R}^{n}$
for the following groups:
the symmetric group $S_n$; the orthogonal group $O(n)$; the symplectic group $Sp(n)$; and the special orthogonal group $SO(n)$.
We will show that in the case of the alternating group $A_n$,

the layer functions can also be characterised by

sets of set partition diagrams.

To do this, we use a concept that was first introduced by Comes comes, namely, so-called jellyfish.
In their paper, they largely determined the theory of alternating group equivariance; however, they relied heavily on the language of category theory in their exposition.
We simplify their approach, and provide proofs that are more accessible

the machine learning community.

The main contributions of this paper, which appear in Section <ref> onwards, are as follows:

* We are the first to show how the combinatorics underlying set partition diagrams, together with some jellyfish, serves as the theoretical foundation for constructing neural networks that are equivariant to the alternating group when the layers are some tensor power of $\mathbb{R}^{n}$.

In particular, we find a basis for the learnable, linear, $A_n$–equivariant layer functions between such tensor power spaces in the standard basis of $\mathbb{R}^{n}$.

* We extend our approach to show how to construct neural networks that are equivariant to local symmetries.

Order of work:
1. recall the $S_n$ orbits and how they link to partition diagrams with up to $n$ blocks.
Recall the flattening procedure too ...
2. describe how to get the $A_n$ orbits + dimension formulae.
3. describe how to adapt the appropriate diagrams to "identify" the $A_n$ orbits for $n-1$ and $n$ block partition diagrams.
(suggest that this gives you a Schur–Weyl duality between jellyfish partition algebra and ??)
4. Add in proofs for these things.
5. Add in for features, biases (use my nice short explanation from IJCAI submission for Brauer paper)
6. Generalise to local symmetries (again, use my nice short explanation for Brauer paper)
7. Short section doing a summary of partitions, brauer, and jellyfish in terms of category theory (and string diagrams) and how you get group equivariant neural networks this way ... suggesting a new line of approach (adding appropriate references)!
8. Examples?

§ PRELIMINARIES

We choose our field of scalars to be $\mathbb{R}$ throughout.
Tensor products are also taken over $\mathbb{R}$, unless otherwise stated.
Also, we let $[n]$ represent the set $\{1, \dots, n\}$.

Recall that a representation of a group $G$ is a choice of vector space $V$ over $\mathbb{R}$ and a group homomorphism

\begin{equation} \label{grouprephom}
\rho : G \rightarrow GL(V)
\end{equation}

We choose to focus on finite-dimensional vector spaces $V$
that are some tensor power of $\mathbb{R}^{n}$
in this paper.

We often abuse our terminology by calling $V$ a representation of $G$, even though the representation is technically the homomorphism $\rho$.
When the homomorphism $\rho$ needs to be emphasised alongside its vector space $V$, we will use the notation $(V, \rho)$.

§ $(\MATHBB{R}^{N})^{\OTIMES K}$, A REPRESENTATION OF BOTH $S_N$ AND $A_N$

Recall that $S_n$ is the group of all permutations on $[n]$, and that $A_n$ is the subgroup of $S_n$ consisting of all permutations on $[n]$ whose image under the function

\begin{equation}
\sgn : S_n \rightarrow \{\pm 1\}
\end{equation}

is $+1$, where $\sgn$ is defined, for all $\sigma \in S_n$, as

\begin{equation}
\sgn(\sigma)
\coloneqq
\begin{cases}
+1 & \text{if $\sigma$ is an even permutation in $S_n$} \\
-1 & \text{if $\sigma$ is an odd permutation in $S_n$} \\
\end{cases}
\end{equation}

We have that $\mathbb{R}^{n}$ is a representation of $S_n$ via its (left) action on the basis $\{e_a \mid a \in [n]\}$ which is extended linearly,
where, specifically, the action is given by

\begin{equation}
\sigma \cdot e_a = e_{\sigma(a)} \text{ for all } \sigma \in S_n \text{ and } a \in [n]
\end{equation}

Restricting this action to $A_n$ and extending linearly shows that $\mathbb{R}^{n}$ is also a representation of $A_n$.

We also have that any $k$-tensor power of $\mathbb{R}^{n}$, $(\mathbb{R}^{n})^{\otimes k}$, for any $k \in \mathbb{Z}_{\geq 0}$, is a representation of $S_n$,
since the elements

\begin{equation} \label{tensorelementfirst}
e_I \coloneqq e_{i_1} \otimes e_{i_2} \otimes \dots \otimes e_{i_k}
\end{equation}

for all $I \coloneqq (i_1, i_2, \dots, i_k) \in [n]^k$ form a basis of
$(\mathbb{R}^{n})^{\otimes k}$,
and the action of $S_n$ that maps a basis element of
$(\mathbb{R}^{n})^{\otimes k}$
of the form (<ref>) to

\begin{equation}
e_{\sigma(I)} \coloneqq e_{\sigma(i_1)} \otimes e_{\sigma(i_2)} \otimes \dots \otimes e_{\sigma(i_k)}
\end{equation}

can be extended linearly.
Again, restricting this action to $A_n$ and extending linearly shows that
$(\mathbb{R}^{n})^{\otimes k}$
is also a representation of $A_n$.

We denote the representation of $S_n$ by $\rho_{k}$.
We will use the same notation for the restriction of this representation to $A_n$, with the context making clear that it is the restriction of the $S_n$ representation.

For more on the representation theory of the symmetric and alternating groups, see [Sagan, 2000] and [Ceccherini-Silberstein et al., 2010].

§ GROUP EQUIVARIANT NEURAL NETWORKS

Group equivariant neural networks are constructed by alternately composing linear and non-linear $G$-equivariant maps between representations of a group $G$.

The following is based on the material presented in [Lim & Nelson, 2022].

We first define $G$-equivariance:

Suppose that $(V, \rho_{V})$ and $(W, \rho_{W})$
are two representations of a group $G$.

A map $\phi : V \rightarrow W$ is said to be $G$-equivariant if,
for all $g \in G$ and $v \in V$,

\begin{equation} \label{Gequivmapdefn}
\phi(\rho_{V}(g)[v]) = \rho_{W}(g)[\phi(v)]
%\text{ for all } g \in G \text{ and } v \in V.
\end{equation}

The set of all linear $G$-equivariant maps between $V$ and $W$ is denoted by $\Hom_{G}(V,W)$.
When $V = W$, we write this set as $\End_{G}(V)$.
It can be shown that $\Hom_{G}(V,W)$ is a vector space over $\mathbb{R}$, and that $\End_{G}(V)$ is an algebra over $\mathbb{R}$.
See [Segal, 2014] for more details.

A special case of $G$-equivariance is $G$-invariance:

The map $\phi$ given in Definition <ref> is said to be $G$-invariant if $\rho_{W}$ is defined to be the $1$-dimensional trivial representation of $G$.
As a result, $W = \mathbb{R}$.

We can now define the type of neural network that is the focus of this paper:

An $L$-layer $G$-equivariant neural network $f_{\mathit{NN}}$ is a composition of layer functions

\begin{equation}
f_{\mathit{NN}} \coloneqq f_L \circ \ldots \circ f_{l} \circ \ldots \circ f_1
\end{equation}

such that the $l^{\text{th}}$ layer function is a map of representations of $G$

\begin{equation}
f_l: (V_{l-1}, \rho_{l-1}) \rightarrow (V_l, \rho_l)
\end{equation}

that is itself a composition

\begin{equation} \label{Glayerfidefn}
f_l \coloneqq \sigma_l \circ \phi_l
\end{equation}

of a learnable, linear, $G$-equivariant function

\begin{equation} \label{Glayerlinear}
\phi_l : (V_{l-1}, \rho_{l-1}) \rightarrow (V_l, \rho_l)
\end{equation}

together with
a fixed, non-linear activation function

\begin{equation}
\sigma_l: (V_l, \rho_l) \rightarrow (V_l, \rho_l)
\end{equation}

such that

* $\sigma_l$ is a $G$-equivariant map, as in (<ref>), and

* $\sigma_l$ acts pointwise (after a basis has been chosen for each copy of $V_l$ in $\sigma_l$.)

We focus on the learnable, linear, $G$-equivariant functions in this paper, since the non-linear functions are fixed.
Note that, after picking a basis for each layer space in the set $\{V_l\}$,
the number of parameters
that appear
in a matrix representation of a learnable, linear, $G$-equivariant function of the form (<ref>), that is, in a weight matrix for the $l^{\text{th}}$ layer function,
is equal to the number of matrices that appear in a basis for
given a basis of
the weight matrix itself is a weighted linear combination of these basis matrices, where each coefficient in the linear combination is a parameter to be learned.

The entire neural network $f_{\mathit{NN}}$ is itself a $G$-equivariant function because
it can be shown that
the composition of any number of $G$-equivariant functions is itself $G$-equivariant.

One way of making
a neural network of the form given in Definition <ref>
is by choosing the representation in the final layer
to be the $1$-dimensional trivial representation of $G$.

§ SYMMETRIC GROUP

In this section, we recall the technique
of using set partitions
to find a basis of

$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
in the standard basis of $\mathbb{R}^{n}$
since it will feature heavily in what follows for the alternating group.
For more details, see [Maron et al., 2019], [Ravanbakhsh, 2020], and
[Pearce-Crump, 2022].

§.§ Set Partitions

For $l, k \in \mathbb{Z}_{\geq 0}$, consider the set $[l+k]$ having $l+k$ elements.
We can create a set partition of $[l+k]$ by partitioning it into a number of subsets.
We call the subsets of a set partition blocks.
Define $\Pi_{l+k}$ to be the set of all set partitions of $[l+k]$.
Let $\Pi_{l+k, n}$ be the subset of $\Pi_{l+k}$ consisting of all set partitions of $[l+k]$ having at most $n$ blocks.

As the number of set partitions in $\Pi_{l+k}$ having exactly $t$ blocks is the Stirling number
\begin{Bsmallmatrix}
\end{Bsmallmatrix}
of the second kind, we see that the number of elements in $\Pi_{l+k}$ is equal to $\Bell(l+k)$, the $(l+k)^{\text{th}}$ Bell number, and that the number of elements in $\Pi_{l+k,n}$ is therefore equal to

\begin{equation}
\sum_{t=1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
\coloneqq \Bell(l+k,n)
\end{equation}

the $n$-restricted $(l+k)^{\text{th}}$ Bell number.

For each set partition $\pi$ in $\Pi_{l+k}$, we can define a diagram $d_{\pi}$
that has two rows of vertices and edges between vertices such that there are

* $l$ vertices on the top row, labelled by $1, \dots, l$

* $k$ vertices on the bottom row, labelled by $l+1, \dots, l+k$, and

* the edges between the vertices are such that the connected components of $d_\pi$ correspond to the blocks of $\pi$.

In particular, $d_{\pi}$ represents the equivalence class of all diagrams with connected components equal to the blocks of $\pi$.

A diagram $d_{\pi}$ corresponding to the set partition $\pi$ given in (<ref>) with $l=3$ and $k=5$.

For example, if $l = 3$ and $k = 5$, a diagram
corresponding to the set partition

\begin{equation} \label{examplesetpart}
\pi \coloneqq \{1, 5 \mid 2, 4 \mid 3, 6, 8 \mid 7 \}
\end{equation}

in $\Pi_{8}$ consisting of $4$ blocks is given in Figure <ref>.

We can define another diagram related to each set partition
diagram $d_\pi$:

it is the flattened version of $d_\pi$, where we pull the top row of $l$ vertices down and to the left of the bottom row of $k$ vertices, maintaining the order of the labels.

For example, the flattened diagram
corresponding to the set partition diagram shown in Figure <ref> is

given in Figure <ref>.

The flattened diagram corresponding to
the set partition diagram shown in Figure <ref>.

A Basis of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$

We begin by noting that
$\Hom((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
has a standard basis of matrix units

\begin{equation}
\{E_{I,J}\}_{I \in [n]^l, J \in [n]^k}
\end{equation}

where $E_{I,J}$ has a $1$ in the $(I,J)$ position and is $0$ elsewhere.

expressing $f \in
\Hom((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
in this basis as

\begin{equation}
f = \sum_{I \in [n]^l}\sum_{J \in [n]^k} f_{I,J}E_{I,J}
\end{equation}

it can be shown that
$f \in \Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$ if and only if

\begin{equation} \label{centeq1}
f_{\sigma(I),\sigma(J)} = f_{I,J}
\end{equation}

for all $\sigma \in S_n$ and $I \in [n]^{l}, J \in [n]^{k}$.

Concatenating each $I \in [n]^l, J \in [n]^{k}$ into a single element $(I, J) \in [n]^{l+k}$,
we see from (<ref>) that the basis elements of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
are in bijective correspondence with the orbits coming from the action of $S_n$ on $[n]^{l+k}$, where $\sigma \in S_n$ acts on the pair $(I,J)$ by

\begin{equation} \label{sigmapairaction}
\sigma(I,J) \coloneqq (\sigma(I),\sigma(J))
\end{equation}

As $S_n$ acts on $[n]$ transitively, it acts on $[n]^{l+k}$ transitively, meaning that the orbits under this action actually partition the set $[n]^{l+k}$ into equivalence classes.

Furthermore, we can define a bijection between the orbits
coming from the action of $S_n$ on $[n]^{l+k}$
and the set partitions $\pi$ in $\Pi_{l+k}$ having at most $n$ blocks.
Indeed, if $(I,J)$ is a class representative of an orbit, then,

replacing momentarily the elements of $J$ by $i_{l+m} \coloneqq j_m$ for all $m \in [k]$,
so that

\begin{align} \label{pairedblocks}
& = (i_1, i_2, \dots, i_l, j_1, j_2, \dots, j_k) \nonumber \\
& = (i_1, i_2, \dots, i_l, i_{l+1}, i_{l+2}, \dots i_{l+k})
\end{align}

we define the bijection by

\begin{equation} \label{blockbij}
i_x = i_y \iff x, y \text{ are in the same block of } \pi
\end{equation}

for all $x$, $y \in [l+k]$.

The bijection (<ref>) is independent of the choice of class representative since

\begin{equation}
i_x = i_y \iff \sigma(i_x) = \sigma(i_y) \text{ for all } \sigma \in S_n
\end{equation}

Notice that the LHS of (<ref>) is checking for an equality on the elements of $[n]$, whereas the RHS is separating the elements of $[l+k]$ into blocks; hence $\pi$ must have at most $n$ blocks.

As a result, we have shown the following.

The basis elements of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$,
in the standard basis of $\mathbb{R}^{n}$,
correspond bijectively with all set partitions $\pi$ in $\Pi_{l+k}$ having at most $n$ blocks,
which correspond bijectively with the orbits coming from the action of $S_n$ on $[n]^{l+k}$.

We can obtain the basis elements themselves, as follows:

Taking a set partition $\pi$ in $\Pi_{l+k,n}$,
and denoting the number of blocks in $\pi$ by $t$, we obtain a labelling of the blocks by letting $B_1$ be the block that contains the number $1 \in [l+k]$, and iteratively letting $B_j$, for $1 < j \leq t$, be the block that contains the smallest number in $[l+k]$ that is not in $B_1 \cup B_2 \cup \dots \cup B_{j-1}$.

Using this labelling of the blocks, we can create an element of $[n]^{l+k}$ by letting the $i^{\text{th}}$ position, $i \in [l+k]$, be the label of the block containing the number $i$.
This is called the block labelling of $\pi$.
Denote it by the pair $(I_{\pi},J_{\pi})$, where clearly $I_{\pi} \in [n]^l$ and $J_{\pi} \in [n]^{k}$.

In doing so, we have created a representative of the orbit for the $S_n$ action on $[n]^{l+k}$ corresponding to the set partition $\pi \in \Pi_{l+k,n}$
under the bijection given in (<ref>).
Denote this orbit by $O_{S_n}((I_{\pi},J_{\pi}))$.

We form a basis element of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$,
denoted by $X_{\pi}$,
by adding together all matrix units

whose indexing pair $(I,J)$ appears
in the orbit $O_{S_n}((I_{\pi},J_{\pi}))$; that is,

\begin{equation} \label{equivbasiselement}
%\sum_{(P,Q) \in O((I,L)_{\pi})} E_{P,Q}
X_\pi \coloneqq \sum_{(I,J) \in O_{S_n}((I_{\pi},J_{\pi}))} E_{I,J}
\end{equation}

We see that $X_\pi$ is a basis element of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
by (<ref>).

Doing this for each set partition $\pi$ in $\Pi_{l+k,n}$, or, equivalently, for all of the orbits coming from the action of $S_n$ on $[n]^{l+k}$, gives:

For $l, k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
we have that

\begin{equation}
\{X_\pi \mid \pi \in \Pi_{l+k,n}\}
\end{equation}

is a basis of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$,
and so

\begin{align}
\dim
\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})
& =
%\sum_{t = 1}^{n}
%\nonumber \\
%& =
\Bell(l+k, n)
\end{align}

§ ALTERNATING GROUP

In exactly the same way as for the symmetric group, we can show that the basis elements of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
are in bijective correspondence with the orbits coming from the action of $A_n$ on $[n]^{l+k}$.

However, the major difference
between the symmetric group and the alternating group
is that the $A_n$ orbits on $[n]^{l+k}$, and consequently the basis elements of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$,
are not necessarily in bijective correspondence with the set partitions of $[l+k]$ having at most $n$ blocks.
This is because some of the $S_n$ orbits on $[n]^{l+k}$ become the disjoint union of more than one $A_n$ orbit on $[n]^{l+k}$.
We say that an $S_n$ orbit on $[n]^{l+k}$ splits if it is the disjoint union of more than one $A_n$ orbit on $[n]^{l+k}$.
Our first task is to identify which $S_n$ orbits on $[n]^{l+k}$ split and which do not.

Let $\pi$ be a set partition in $\Pi_{l+k, n}$ having some $t$ blocks.
Its corresponding $S_n$ orbit on $[n]^{l+k}$ is $O_{S_n}((I_\pi, J_\pi))$.

Choose some arbitrary element $(I_\alpha, J_\alpha) \in O_{S_n}((I_\pi, J_\pi))$, and consider its $A_n$ orbit on $[n]^{l+k}$.
We shall denote it by $O_{A_n}((I_\alpha, J_\alpha))$.
Clearly, $O_{A_n}((I_\alpha, J_\alpha)) \subseteq O_{S_n}((I_\pi, J_\pi))$, since $A_n$ is a subgroup of $S_n$.

Denote the stabilizer of $(I_\pi, J_\pi)$ under the action of $S_n$ by $\Stab_{S_n}((I_\pi, J_\pi))$, and the stabilizer of $(I_\alpha, J_\alpha)$ under the action of $A_n$ by $\Stab_{A_n}((I_\alpha, J_\alpha))$.

Then, by the Orbit–Stabilizer Theorem, we have that

\begin{equation} \label{orbstabSn}
\left|O_{S_n}((I_\pi, J_\pi))\right|
\frac{|S_n|}{|\Stab_{S_n}((I_\pi, J_\pi))|}
\frac{n!}{(n-t)!}
\end{equation}

as $\Stab_{S_n}((I_\pi, J_\pi)) \cong S_{n-t}$,

\begin{align}
\left|O_{A_n}((I_\alpha, J_\alpha))\right|
& =
\frac{|A_n|}{|\Stab_{A_n}((I_\alpha, J_\alpha))|} \nonumber \\
& =
\frac{n!}{2|\Stab_{A_n}((I_\alpha, J_\alpha))|} \label{orbstabAn}
\end{align}

Since each $S_n$ orbit will either be an $A_n$ orbit or a disjoint union of $A_n$ orbits,

by studying $\Stab_{A_n}((I_\alpha, J_\alpha))$, we shall see under what conditions the $S_n$ orbits split.
Indeed, these conditions are given in the following theorem:

Let $\pi$ be a set partition in $\Pi_{l+k,n}$ having some $t$ blocks, and consider its corresponding $S_n$ orbit on $[n]^{l+k}$,
$O_{S_n}((I_\pi, J_\pi))$.

If $t \leq n-2$, then $O_{S_n}((I_\pi, J_\pi))$ does not split.

If $t = n-1$ or $n$, then $O_{S_n}((I_\pi, J_\pi))$ splits into a disjoint union of exactly two $A_n$ orbits.

Consider the case where $\pi$ has $t = n$ blocks.
Choose some arbitrary element $(I_\alpha, J_\alpha) \in O_{S_n}((I_\pi, J_\pi))$, and

$\Stab_{A_n}((I_\alpha, J_\alpha))$,
the stabilizer of $(I_\alpha, J_\alpha)$ under the action of $A_n$.
Since all of the elements in $[n]$ appear in the tuple $(I_\alpha, J_\alpha)$,
the only element of $A_n$ that fixes the entries of $(I_\alpha, J_\alpha)$
is the identity element; that is, $\Stab_{A_n}((I_\alpha, J_\alpha)) = \{e_{A_n}\}$.

Hence, by the Orbit–Stabilizer Theorem,

we have that
$\left|O_{A_n}((I_\alpha, J_\alpha))\right| = \frac{n!}{2}$.
$\left|O_{S_n}((I_\pi, J_\pi))\right| = n!$ in this case,

and because
$(I_\alpha, J_\alpha)$ was an arbitary element of $O_{S_n}((I_\pi, J_\pi))$,
we see that,
by another application of the Orbit–Stabilizer Theorem,
$O_{S_n}((I_\pi, J_\pi))$ splits into a disjoint union of two $A_n$ orbits.

Similarly, for the case where $\pi$ has $t = n-1$ blocks, we see that
$\Stab_{A_n}((I_\alpha, J_\alpha)) = \{e_{A_n}\}$,
and so, by the same argument,

$O_{S_n}((I_\pi, J_\pi))$ splits into a disjoint union of two $A_n$ orbits.

Finally, for $t \leq n-2$, we have that $\Stab_{A_n}((I_\alpha, J_\alpha)) \cong A_{n-t}$, and so, by the Orbit–Stabilizer Theorem,

we see that
$\left|O_{A_n}((I_\alpha, J_\alpha))\right| =
\left|O_{S_n}((I_\pi, J_\pi))\right|$.
Consequently, the $S_n$ orbit $O_{S_n}((I_\pi, J_\pi))$ does not split.

The case for $t \leq n - 2$ in Theorem <ref> was proven independently in [Maron et al., 2019].

As a result, we immediately obtain the following two theorems:

Let $k, l \in \mathbb{Z}_{\geq 0}$ and $n \in \mathbb{Z}_{\geq 1}$.

If $\pi$ is a set partition in $\Pi_{l+k,n}$ having $n-2$ blocks or fewer, then $\pi$ corresponds bijectively to a basis element of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$,

Otherwise, $\pi$ corresponds to two basis elements of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$.

For $k, l \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
the dimension of
\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})
is equal to

\begin{equation}
\sum_{t=1}^{n-2}
\begin{Bmatrix}
\end{Bmatrix}
\begin{Bmatrix}
\end{Bmatrix}
\begin{Bmatrix}
\end{Bmatrix}
\end{equation}

In other words, Theorem <ref> tells us that finding a basis of
\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})
in the standard basis of $\mathbb{R}^{n}$ is very similar to finding a basis of
\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})
in the standard basis of $\mathbb{R}^{n}$, since finding the basis amounts once again to considering all of the set partitions of $[l+k]$ having at most $n$ blocks.

Indeed, if a set partition $\pi$ in $\Pi_{l+k,n}$ has at most $n-2$ blocks, then we see that $X_\pi$ given in (<ref>) is a basis element of
\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})
since, in this case, $O_{S_n}((I_\pi, J_\pi)) = O_{A_n}((I_\pi, J_\pi))$,

by Theorem <ref>.

The question remains as to how to take a set partition $\pi$ in $\Pi_{l+k,n}$ having either $n-1$ or $n$ blocks and use it to obtain the two basis elements of
\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})
that it corresponds to.
Said differently, we

would like to
take such a set partition $\pi$ and identify the two $A_n$ orbits that its
$S_n$ orbit on $[n]^{l+k}$,
$O_{S_n}((I_\pi, J_\pi))$, splits into.

§.§ Enter: the Jellyfish

Comes comes originally came up with the idea of using jellyfish to identify the two $A_n$ orbits; here, however, our choice of exposition is rather different and our proofs are simpler than those given in their paper.

We begin by defining the following map.

For $n \in \mathbb{Z}_{\geq 1}$,
we define the determinant map

\begin{equation} \label{detmap}
\det : (\mathbb{R}^{n})^{\otimes n} \rightarrow \mathbb{R}
\end{equation}

on the standard basis of $(\mathbb{R}^{n})^{\otimes n}$ by

\begin{equation} \label{detmapdefn}
e_{I} = e_{i_1} \otimes \dots \otimes e_{i_n}
\mapsto
\begin{vmatrix}
e_{i_1} & \dots & e_{i_n}
\end{vmatrix}
\end{equation}

and extend linearly,
where the RHS of (<ref>) is the determinant of an $n \times n$ matrix.

The determinant map is an element of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes n}, (\mathbb{R}^{n})^{\otimes 0})$,
but it is not an element of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes n}, (\mathbb{R}^{n})^{\otimes 0})$.

It is clear that the determinant map is a linear map.

Then, for any $\sigma \in S_n$, we have that

\begin{equation} \label{detSnequiv}
\det(\rho_n(\sigma)[e_{I}])
(-1)^{\sgn(\sigma)} \det(e_{I})
\end{equation}

since a transposition in $S_n$ corresponds to swapping two columns of the $n \times n$ matrix.

As $\sgn(\sigma) = 1$ for all $\sigma \in A_n$,
(<ref>) shows that
$\det$ is an element of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes n}, (\mathbb{R}^{n})^{\otimes 0})$.
It is enough to see that for any odd permutation in $S_n$, (<ref>) implies that
$\det$ is not an element of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes n}, (\mathbb{R}^{n})^{\otimes 0})$.

For each $n \in \mathbb{Z}_{\geq 1}$,
we represent the determinant map by a diagram that has a single row of $n$ vertices, each of which is attached to a blue head.
We will call this diagram a jellyfish, for obvious reasons.

For example, if $n = 3$, the jellyfish has the form

It is important to highlight that the determinant map (<ref>) is different from the determinant operator on an $n \times n$ matrix.
In particular, the determinant map is a linear map on
$(\mathbb{R}^{n})^{\otimes n}$
whereas the determinant operator on $n \times n$ matrices is not linear.

We introduce the following useful lemma.

The determinant map applied to a standard basis vector of
$(\mathbb{R}^{n})^{\otimes n}$
gives either $-1, 0$ or $+1$.

$e_{I} = e_{i_1} \otimes \dots \otimes e_{i_n}$
be a standard basis vector of
$(\mathbb{R}^{n})^{\otimes n}$.

If $i_x = i_y$ for some $1 \leq x \neq y \leq n$, then $\det(e_I) = 0$ since two columns in the $n \times n$ matrix will be the same.
Otherwise, $\{i_1, \dots, i_n\}$ is some permutation of $[n]$.
$e_{[n]} \coloneqq e_{1} \otimes \dots \otimes e_{n}$, we know that
$\det(e_{[n]}) = +1$.
Since, in this case, $e_{I} = \rho_n(\sigma)e_{[n]}$ for some $\sigma \in S_n$,
we can use (<ref>) to calculate
$\det(e_{I})$, giving a result of $\pm 1$.

We can view
Lemma <ref> in another way; namely, that the determinant map

splits basis vectors of
$(\mathbb{R}^{n})^{\otimes n}$
into disjoint classes.
Let us call these classes $-1, 0$ and $+1$.

Consequently, Remark <ref>
suggests that the determinant map is a possible candidate function
for identifying the $A_n$ orbits that the $S_n$ orbit
$O_{S_n}((I_\pi, J_\pi))$ splits into, where

$\pi$ is a set partition in $\Pi_{l+k,n}$ having either $n-1$ or $n$ blocks.

However, since the determinant map is a map
$(\mathbb{R}^{n})^{\otimes n} \rightarrow \mathbb{R}$,

and the elements of $O_{S_n}((I_\pi, J_\pi))$ are elements of $[n]^{l+k}$,
to use the determinant map to try to identify the $A_n$ orbits in $O_{S_n}((I_\pi, J_\pi))$,

it would be useful to create a map
$g_\pi : (\mathbb{R}^{n})^{\otimes l+k} \rightarrow (\mathbb{R}^{n})^{\otimes n}$
that corresponds bijectively with the set partition $\pi$,

since such a map would project standard basis elements of $(\mathbb{R}^{n})^{\otimes l+k}$ onto, at the very least, a linear combination of basis elements of $(\mathbb{R}^{n})^{\otimes n}$.
We could then use the splitting property of the determinant map on such linear combinations to try to split the elements of $O_{S_n}((I_\pi, J_\pi))$ into different classes.
However, in order to use the three classes given in Remark <ref>, we cannot choose any map $(\mathbb{R}^{n})^{\otimes l+k} \rightarrow (\mathbb{R}^{n})^{\otimes n}$.
We will see that with a clever choice of $g_\pi$, the determinant map then splits the elements of $O_{S_n}((I_\pi, J_\pi))$ into the $\pm 1$ classes and sends all other elements of $[n]^{l+k}$ to the $0$ class.

We create $g_\pi$ as follows.
Flatten the diagram $d_{\pi}$ that corresponds to $\pi$.
Add a new top row of $n$ vertices above the row of $l+k$ vertices.
From the bottom row, take the lowest numbered vertex in block $i$ of $\pi$, $1 \leq i \leq t$, where $t = n - 1$ or $n$, and connect that vertex to vertex $i$ in the top row.
Call this new diagram $b_\pi$.

We claim the following:

The diagram $b_\pi$ corresponds bijectively with a basis element of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes l+k}, (\mathbb{R}^{n})^{\otimes n})$.
Consequently, we define $g_\pi$ to be this basis element.

It is clear that the diagram $b_\pi$ corresponds to a set partition of $[n+l+k]$ having exactly $n$ blocks.
Hence this set partition is an element of $\Pi_{n+l+k,n}$.
Since each set partition in $\Pi_{n+l+k,n}$ corresponds bijectively with a basis element of
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes l+k}, (\mathbb{R}^{n})^{\otimes n})$,
by Theorem <ref>, we obtain the result.

The following result is immediate from the construction of the diagram $b_\pi$.

In the standard basis of matrix units of
$\Hom((\mathbb{R}^{n})^{\otimes l+k}, (\mathbb{R}^{n})^{\otimes n})$,
$g_\pi$ is given by

\begin{equation} \label{gpiform}
g_\pi \coloneqq
\sum_{(K,I,J) \in O_{S_n}((K_{\pi},I_{\pi},J_{\pi}))} E_{K,(I,J)}
\end{equation}

\begin{equation}
K_{\pi} \coloneqq (1, 2, \dots, n)
\end{equation}

and $O_{S_n}((K_{\pi},I_{\pi},J_{\pi}))$ is defined to be

\begin{equation} \label{OKpiIpiJpi}
\left\{ (K,I,J) \; \middle\vert
\begin{array}{l}
(I,J) \in O_{S_n}((I_{\pi},J_{\pi})) \\
\text{and if } (I,J) = \sigma(I_{\pi},J_{\pi}), \\
\text{then } K \coloneqq \sigma(K_{\pi})
\end{array}
\right\}
\end{equation}

In order to see that $g_\pi$ has the properties that we need, we first define the following map.

Let $\pi$ be a set partition in $\Pi_{l+k,n}$ having either $n-1$ or $n$ blocks.
Then we define $f_\pi \coloneqq \det \circ \, g_\pi : (\mathbb{R}^{n})^{\otimes l+k} \rightarrow \mathbb{R}$.
Clearly, $f_\pi$ corresponds bijectively with the set partition $\pi$.

We can associate to $f_\pi$ a diagram that is built from the composition of $b_\pi$ (which corresponds to the map $g_\pi$) and a jellyfish (which corresponds to the determinant map).

For example, the diagram that is associated to $f_\pi$ for the set partition $\pi$ whose diagram $d_\pi$ is given in Figure <ref>,
where we choose $l=3$, $k=5$ and $n=5$, is

The map $f_\pi$ is an element of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes l+k}, (\mathbb{R}^{n})^{\otimes 0})$.

Let $e_{(I,J)}$ be any standard basis vector in $(\mathbb{R}^{n})^{\otimes l+k}$, where $I \in [n]^l$ and $J \in [n]^k$.

Then, for all $\sigma \in A_n$, we have that

\begin{align}
& =
\det \circ \, g_\pi
(\rho_{l+k}(\sigma)[e_{(I,J)}]) \\
& =
\det(\rho_n(\sigma)[g_\pi(e_{(I,J)})]) \label{gpiequiv} \\
& =
\det(g_\pi(e_{(I,J)})) \label{gpidet} \\
& =
\end{align}

where, in (<ref>), we have used Proposition <ref>
and in (<ref>), we have used (<ref>).

We come to the crucial result for our purposes.

Let $e_{(I,J)}$ be any standard basis vector in $(\mathbb{R}^{n})^{\otimes l+k}$, where $I \in [n]^l, J \in [n]^k$.

\begin{equation}
f_\pi : e_{(I,J)} \rightarrow
\begin{cases}
\pm 1 & \text{if $(I,J) \in O_{S_n}((I_\pi, J_\pi))$} \\
0     & \text{otherwise}
\end{cases}
\end{equation}

For any standard basis vector $e_{(I,J)}$ in
$(\mathbb{R}^{n})^{\otimes l+k}$,
we have, on a matrix unit of
$\Hom((\mathbb{R}^{n})^{\otimes l+k}, (\mathbb{R}^{n})^{\otimes n})$, that

\begin{equation} \label{matrixunitmult}
E_{K, (L,M)}e_{(I,J)}
\delta_{((L,M),(I,J))}e_{K}
\end{equation}

where $e_{K}$ is a standard basis vector in
$(\mathbb{R}^{n})^{\otimes n}$.

Hence, by (<ref>), we see that,
for the otherwise case,

$g_\pi(e_{(I,J)}) = 0$, and so
$f_\pi(e_{(I,J)}) = 0$.

If $(I,J) \in O_{S_n}((I_\pi, J_\pi))$, then we have that
$(I,J) = \sigma(I_{\pi},J_{\pi})$ for some $\sigma \in S_n$.

Hence, by (<ref>), (<ref>) and
the definition of
given in (<ref>),
we see that
$g_\pi(e_{(I,J)}) = e_{K}$,
$K = \sigma(K_{\pi})$.

Since $K$ is a permutation of $[n]$, we can apply Lemma <ref>
to get that
$f_\pi(e_{(I,J)}) = \det(e_{K}) = \pm 1$.

Let $\pi$ be the set partition in $\Pi_{l+k,n}$ given in the statement of the theorem.
By the transitivity of the action of $S_n$ on $[n]^{l+k}$,
we know that every pair $(I,J) \in [n]^{l+k}$ belongs to exactly one $S_n$ orbit
$O_{S_n}((I_\omega, J_\omega))$
corresponding to some set partition $\omega$ in $\Pi_{l+k,n}$.

We define a partial ordering on the set partitions in $\Pi_{l+k}$,
denoted by $\preceq$, which states that, for all $\pi_1$, $\pi_2 \in \Pi_{l+k}$,
$\pi_1 \preceq \pi_2$
if every block of $\pi_1$ is contained in a block of $\pi_2$.

We consider three cases:

If $\pi \not\preceq \omega$, then
$g_\pi(e_{(I,J)}) = 0$, and so
$f_\pi(e_{(I,J)}) = 0$.

If $\pi \prec \omega$ (strict), then
$g_\pi$ maps $e_{(I,J)}$
to a linear combination of standard basis vectors in
$(\mathbb{R}^{n})^{\otimes n}$
where each term in the sum, of the form
$e_{K} = e_{k_1} \otimes \dots \otimes e_{k_n}$,
has at least two indices $k_x, k_y$ equal, where $1 \leq x \neq y \leq n$.
This is because $\omega$, being coarser than $\pi$, has a block that is the union of at least two blocks in $\pi$, and so, by the construction of $g_\pi$, $g_\pi$ will map the indices in $(I,J)$ that correspond to those two blocks to the same index in $[n]$.
CHECK THE PRECISION OF THE EXPLANATION IN THIS
Hence, by the linearity of the determinant map, $f_\pi(e_{(I,J)}) = 0$.

If $\pi = \omega$, then
$g_\pi$ maps $e_{(I,J)}$
to a linear combination of standard basis vectors in
$(\mathbb{R}^{n})^{\otimes n}$,
where each term in the sum is of the form
$e_{K} = e_{k_1} \otimes \dots \otimes e_{k_n}$.
However, in this case, there will exactly one term in the sum
with $k_1, \dots, k_n$ pairwise distinct WHY IS THIS THE CASE?, and so, by Lemma (<ref>) and the linearity of the determinant map, we see that
$f_\pi(e_{(I,J)}) = \pm 1$.
CAN I DO THIS DIFFERENTLY, BY UNDERSTANDING THE FORM OF $g_\pi$ in terms of a sum of standard unit matrices
$O_{S_n}((I_\pi, J_\pi))$

Consequently, we can define the following two sets:

\begin{equation} \label{Opiplus}
\coloneqq
\{(I,J) \in O_{S_n}((I_\pi, J_\pi)) \mid f_\pi(e_{(I,J)}) = +1\}
\end{equation}

\begin{equation} \label{Opiminus}
\coloneqq
\{(I,J) \in O_{S_n}((I_\pi, J_\pi)) \mid f_\pi(e_{(I,J)}) = -1\}
\end{equation}

We claim the following result.

$O_\pi^{+}$ and $O_\pi^{-}$ are the two $A_n$ orbits that $O_{S_n}((I_\pi, J_\pi))$ splits into.

It is enough to show that if $(I,J) \in O_\pi^{+}$, then $\sigma(I,J) \in O_\pi^{+}$ for all $\sigma \in A_n$, and
if $(I,J) \in O_\pi^{-}$, then $\sigma(I,J) \in O_\pi^{-}$ for all $\sigma \in A_n$,
where the action of $\sigma$ on the pair $(I,J)$ is given in (<ref>).
Indeed, by Proposition <ref>, we have that

\begin{equation}
\end{equation}

Applying Theorem <ref> gives the result.

$O_\pi^{+}$ as $O_{A_n}((I_\pi^{+}, J_\pi^{+}))$, and
$O_\pi^{-}$ as $O_{A_n}((I_\pi^{-}, J_\pi^{-}))$, we obtain the two basis elements of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k},(\mathbb{R}^{n})^{\otimes l})$
from the one set partition $\pi \in \Pi_{l+k,n}$ that has either $n-1$ or $n$ blocks,

\begin{equation} \label{Xpiplus}
X_\pi^{+} \coloneqq \sum_{(I,J) \in O_{A_n}((I_\pi^{+}, J_\pi^{+}))} E_{I,J}
\end{equation}

\begin{equation} \label{Xpiminus}
X_\pi^{-} \coloneqq \sum_{(I,J) \in O_{A_n}((I_\pi^{-}, J_\pi^{-}))} E_{I,J}
\end{equation}

We summarise the above results into the following theorem.

For $l, k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
the union of the two sets

\begin{equation}
\{X_\pi \mid \pi \in \Pi_{l+k,n-2}\}
\end{equation}

\begin{equation}
\{X_\pi^{+}, X_\pi^{-} \mid \pi \in \Pi_{l+k,n}\setminus\Pi_{l+k,n-2}\}
\end{equation}

forms a basis of
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$.
Its dimension is given in Theorem <ref>.

In Algorithm <ref>,
we present some pseudocode
for how to explicitly construct the
weight matrix for an $A_n$-equivariant linear layer mapping
$(\mathbb{R}^{n})^{\otimes k} \rightarrow (\mathbb{R}^{n})^{\otimes l}$ in the standard basis of $\mathbb{R}^{n}$.
We assume that we have access to the following procedures:

* SymmGrpOrbit calculates the $S_n$ orbit for a set partition $\pi \in \Pi_{l+k,n}$.

* Flatten takes a set partition diagram with $l$ vertices in the top row and $k$ vertices in the bottom row, and returns its equivalent flattened set partition diagram having a single row of $l+k$ vertices, as per Section <ref>.

* NewTopRowConnect takes a flattened set partition diagram having either $n-1$ or $n$ blocks, inserts a new top row consisting of $n$ vertices, and connects the lowest numbered vertex in each block $i$ to vertex $i$ in the top row.

* AttachJellyfish takes a set partition diagram $b_\pi$ with $n$ vertices in the top row and $l+k$ vertices in the bottom row having either $n-1$ or $n$ blocks, attaches a jellyfish with $n$ legs to the top row, and returns the function $f_\pi$ that is associated with this new diagram.

We give an example that explicitly shows how to construct such a weight matrix in the Technical Appendix, in the case where $n=2$, $k=2$ and $l=1$.

We appreciate that there will be some technical challenges
when implementing Algorithm <ref> given the current state of computer hardware.
We discuss this in more detail in the Technical Appendix.

It is possible to extend our results by looking at linear layer functions that are equivariant to a direct product of alternating groups;
this is given in full in

the Technical Appendix.

How to Calculate the Weight Matrix for an $A_n$ Equivariant Linear Layer Mapping $(\mathbb{R}^{n})^{\otimes k} \rightarrow (\mathbb{R}^{n})^{\otimes l}$

Input: $n$, $k$, $l$
Output: Weight Matrix $M$

Initialize $M = 0$.
$\pi \in \Pi_{l+k,n-2}$

$O_{S_n}((I_\pi, J_\pi)) = $ SymmGrpOrbit$(\pi, n)$
$X_\pi = \sum_{(I,J) \in O_{S_n}((I_{\pi},J_{\pi}))} E_{I,J}$
$M = M + \lambda_\pi X_\pi$
$\pi \in \Pi_{l+k,n} \setminus \Pi_{l+k,n-2}$
$d_\pi = $ Flatten$(d_\pi)$
$b_\pi = $ NewTopRowConnect$(d_\pi, n)$
$f_\pi = $ AttachJellyfish$(b_\pi, n)$

$O_{S_n}((I_\pi, J_\pi)) = $ SymmGrpOrbit$(\pi, n)$
$(I,J) \in O_{S_n}((I_\pi, J_\pi))$
$f_\pi(e_{(I,J)}) = +1$
$O_{A_n}((I_\pi^{+}, J_\pi^{+})).$Append$((I,J))$
$O_{A_n}((I_\pi^{-}, J_\pi^{-})).$Append$((I,J))$
$X_\pi^{+} = \sum_{(I,J) \in O_{A_n}((I_\pi^{+}, J_\pi^{+}))} E_{I,J}$
$X_\pi^{-} = \sum_{(I,J) \in O_{A_n}((I_\pi^{-}, J_\pi^{-}))
} E_{I,J}$
$M = M + \lambda_\pi^{+} X_\pi^{+} + \lambda_\pi^{-} X_\pi^{-}$
Return: $M$

§ ADDING FEATURES AND BIASES

§.§ Features

We have assumed throughout that the feature dimension for all of the layers appearing in the neural network is one.
We can adapt all of the results that have been shown for the case where the feature dimension of the layers is greater than one.

Suppose that an $r$-order tensor has a feature space of dimension $d_r$.
We now wish to find a basis for

\begin{equation} \label{Homfeatures}
\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k} \otimes \mathbb{R}^{d_k}, (\mathbb{R}^{n})^{\otimes l} \otimes \mathbb{R}^{d_l})
\end{equation}

in the standard basis of $\mathbb{R}^{n}$.

Such a basis can be found by making the following substitutions,
where now $i \in [d_l]$ and $j \in [d_k]$:

* replace $E_{I,J}$ by $E_{I,i,J,j}$ in (<ref>), (<ref>), and (<ref>)

* relabel $X_\pi$ by $X_{\pi, i, j}$,
$X_\pi^{+}$ by $X_{\pi, i, j}^{+}$, and
$X_\pi^{-}$ by $X_{\pi, i, j}^{-}$.

Consequently, a basis for (<ref>) in the standard basis of $\mathbb{R}^{n}$ is given by the union of the two sets

\begin{equation}
\{X_{\pi, i, j} \mid \pi \in \Pi_{l+k,n-2}, i \in [d_l], j \in [d_k]\}
\end{equation}

\begin{equation}
\left\{X_{\pi, i, j}^{+}, X_{\pi, i, j}^{-} \;\middle\vert
\begin{array}{l}
\pi \in \Pi_{l+k,n}\setminus\Pi_{l+k,n-2}, \\
i \in [d_l], j \in [d_k]
\end{array}
\right\}
\end{equation}

§.§ Biases

Including bias terms in the layer functions of a $A_n$-equivariant neural network is harder, but it can be done.
For the learnable linear layers of the form
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$,
Pearce–Crump pearcecrump shows that the $A_n$-equivariance of the bias function,
$\beta : ((\mathbb{R}^{n})^{\otimes k}, \rho_k) \rightarrow
((\mathbb{R}^{n})^{\otimes l}, \rho_l)$,
needs to satisfy

\begin{equation} \label{Anbiasequiv}
c = \rho_l(g)c
\end{equation}

for all $g \in A_n$ and $c \in (\mathbb{R}^{n})^{\otimes l}$.

Since any $c \in (\mathbb{R}^{n})^{\otimes l}$
satisfying (<ref>) can be viewed as an element of
$\Hom_{A_n}(\mathbb{R}, (\mathbb{R}^{n})^{\otimes l})$,
to find the matrix form of $c$, all we need to do is to find a basis for
$\Hom_{A_n}(\mathbb{R}, (\mathbb{R}^{n})^{\otimes l})$.

But this is simply a matter of applying Theorem <ref>,
setting $k = 0$.

§ RELATED WORK

The theory for the alternating group has its roots in the theory for the symmetric group and its links to the partition algebra.
Jones Jones constructed a surjective algebra homomorphism between the partition algebra $P_k(n)$ and the centraliser algebra of the symmetric group, $\End_{S_n}((\mathbb{R}^{n})^{\otimes k})$.
Most notably, Benkart and Halverson went on to develop much of the theory for the duality between the symmetric group and the partition algebra in a number of important papers BHH, BenHal1, BenHal2.
Bloss bloss used the result of Jones Jones to study the centralizer algebra of the alternating group, $\End_{A_n}((\mathbb{R}^{n})^{\otimes k})$.
He showed that the partition algebra $P_k(n)$, which has a basis consisting of set partition diagrams having two rows of $k$ vertices, is isomorphic to the centralizer algebra when $n \geq 2k + 2$.
He also highlighted the difficulty of finding a diagrammatic approach for characterising $\End_{A_n}((\mathbb{R}^{n})^{\otimes k})$ in the remaining cases since he recognised that the $S_n$ orbits that correspond bijectively with the set partition diagrams split in these cases.
Comes comes solved this problem and extended it to all $\Hom$–spaces
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$, developing much of the theory in the process.
In particular, he came up with the idea of using the
determinant map to show how the $S_n$ orbits split, and introduced jellyfish to represent this map in its diagrammatic form.

Finding the form of neural networks that are equivariant to a particular group has become an important area of research.

Zaheer et al. deepsets introduced the first permutation equivariant neural network, called Deep Sets, for learning from sets in a permutation equivariant manner.
Maron et al. maron2018 were the first to study the problem of classifying all of the linear permutation equivariant and invariant neural network layers, with their motivation coming from learning relations between the nodes of graphs.
They characterised all of the learnable, linear, permutation equivariant layer functions in
$\Hom_{S_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
in the practical cases (specifically, when $n \geq k+l$).
They used some equalities involving Kronecker products to find a number of fixed point equations which they solved to find a basis, in tensor form, for the layer functions under consideration.

As discussed in the Introduction,
the approach taken in this paper to
characterise all of the learnable, linear, equivariant layer functions in
$\Hom_{A_n}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
is similar to the one seen in the papers written by
Pearce–Crump pearcecrump, pearcecrumpB.
They used various sets of set partition diagrams to characterise
all of the learnable, linear, equivariant layer functions in
$\Hom_{G}((\mathbb{R}^{n})^{\otimes k}, (\mathbb{R}^{n})^{\otimes l})$
when $G$ is any of the following groups:
the symmetric group $S_n$, the orthogonal group $O(n)$, the symplectic group $Sp(n)$, and the special orthogonal group $SO(n)$.

§ CONCLUSION

We are the first to show how the combinatorics underlying set partition diagrams, together with some jellyfish representing the determinant map, provides the theoretical background for constructing neural networks that are equivariant to the alternating group when the layers are some tensor power of $\mathbb{R}^{n}$.
We looked at the problem of calculating the form of the learnable, linear, $A_n$–equivariant layer functions between such tensor power spaces in the standard basis of $\mathbb{R}^{n}$.
We achieved this by finding a basis for the $\Hom$–spaces in which these layer functions live.
In particular, we showed how set partition diagrams correspond to a number of basis elements, and we used jellyfish to identify the individual basis elements when a set partition diagram corresponded to more than one basis element.
In doing so, we calculated the number of parameters that appear in these layer functions.
We also generalised our approach to show how to construct neural networks that are equivariant to local symmetries.

§ ACKNOWLEDGEMENTS

The author would like to thank his PhD supervisor Professor William J. Knottenbelt for being generous with his time throughout the author's period of research prior to the publication of this paper.

This work was funded by the Doctoral Scholarship for Applied Research which was awarded to the author under Imperial College London's Department of Computing Applied Research scheme.
This work will form part of the author's PhD thesis at Imperial College London.

[Barcelo & Ram, 1997]
Barcelo, H. and Ram, A.
Combinatorial Representation Theory, 1997.

[Benkart & Halverson, 2019]
Benkart, G. and Halverson, T.
Partition algebras $P_k(n)$ with $2k>n$ and the fundamental
theorems of invariant theory for the symmetric group $S_n$.
J. London Math. Soc, 990 (2):0 194–224,
URL <https://doi.org/10.1112/jlms.12175>.

[Benkart & Halverson, 2019]
Benkart, G. and Halverson, T.
Partition Algebras and the Invariant Theory of the Symmetric
In Barcelo, H., Karaali, G., and Orellana, R. (eds.), Recent
Trends in Algebraic Combinatorics, volume 16 of Association for Women
in Mathematics Series, pp.  1–41. Springer, 2019b.
URL <https://doi.org/10.1007/978-3-030-05141-9>.

[Benkart et al., 2017]
Benkart, G., Halverson, T., and Harman, N.
Dimensions of irreducible modules for partition algebras and tensor
power multiplicities for symmetric and alternating groups.
J. Algebraic Combin., 460 (1):0 77–108, 2017.
ISSN 0925-9899.
URL <https://doi.org/10.1007/s10801-017-0748-4>.

[Bloss, 2005]
Bloss, M.
The Partition Algebra as a Centralizer Algebra of the
Alternating Group.
Communications in Algebra, 33:0 2219–2229, 2005.
URL <https://doi.org/10.1081/AGB-200063579>.

[Brauer, 1937]
Brauer, R.
On Algebras Which Are Connected with the Semisimple
Continuous Groups.
Ann. Math., 38:0 857–872, 1937.
ISSN 0003486X.
URL <https://doi.org/10.2307/1968843>.

[Ceccherini-Silberstein et al., 2010]
Ceccherini-Silberstein, T., Scarabotti, F., and Tolli, F.
Representation Theory of the Symmetric Groups.
Cambridge University Press, 2010.

[Cohen & Welling, 2016]
Cohen, T. and Welling, M.
Group Equivariant Convolutional Networks.
In Balcan, M. F. and Weinberger, K. Q. (eds.), Proceedings of
The 33rd International Conference on Machine Learning, volume 48 of
Proceedings of Machine Learning Research, pp.  2990–2999, New York,
New York, USA, 20–22 Jun 2016. PMLR.
URL <https://proceedings.mlr.press/v48/cohenc16.html>.

[Cohen et al., 2019]
Cohen, T., Weiler, M., Kicanaoglu, B., and Welling, M.
Gauge Equivariant Convolutional Networks and the Icosahedral
In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of
the 36th International Conference on Machine Learning, volume 97 of
Proceedings of Machine Learning Research, pp.  1321–1330. PMLR,
09–15 Jun 2019.
URL <https://proceedings.mlr.press/v97/cohen19d.html>.

[Comes, 2020]
Comes, J.
Jellyfish Partition Categories.
Algebr Represent Theor, 23:0 327–347, 2020.
URL <https://doi.org/10.1007/s10468-018-09851-7>.

[Goodman & Wallach, 2009]
Goodman, R. and Wallach, N. R.
Symmetry, Representations and Invariants.
Springer, 2009.

[Halverson & Ram, 2005]
Halverson, T. and Ram, A.
Partition algebras.
European J. Combin., 260 (6):0 869–921, 2005.
ISSN 0195-6698.
URL <https://doi.org/10.1016/j.ejc.2004.06.005>.

[Halverson & Ram, 2022]
Halverson, T. and Ram, A.
Gems from the Work of Georgia Benkart.
Notices of the American Mathematical Society, 690
(3):0 375–384, March 2022.
URL <https://doi.org/10.1090/noti2447>.

[Jones, 1994]
Jones, V.
The Potts model and the symmetric group.
In Araki, H., Kawahigashi, Y., and Kosaki, H. (eds.),
Subfactors: Proceedings of the Taniguchi Symposium on Operator
Algebras (Kyuzeso, 1993), pp.  259–267. World Scientific, 1994.

[Kicki et al., 2020]
Kicki, P., Ozay, M., and Skrzypczynski, P.
A Computationally Efficient Neural Network Invariant to the
Action of Symmetry Subgroups, 2020.

[Kondor et al., 2018]
Kondor, R., Lin, Z., and Trivedi, S.
Clebsch–Gordan Nets: a Fully Fourier Space
Spherical Convolutional Neural Network.
In Bengio, S., Wallach, H., Larochelle, H., Grauman, K.,
Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural
Information Processing Systems, volume 31. Curran Associates, Inc., 2018.

[Lim & Nelson, 2022]
Lim, L.-H. and Nelson, B. J.
What is an equivariant neural network?, 2022.

[Maron et al., 2019]
Maron, H., Ben-Hamu, H., Shamir, N., and Lipman, Y.
Invariant and Equivariant Graph Networks.
In International Conference on Learning Representations,
URL <https://openreview.net/forum?id=Syx72jC9tm>.

[Maron et al., 2019]
Maron, H., Fetaya, E., Segol, N., and Lipman, Y.
On the Universality of Invariant Networks.
In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of
the 36th International Conference on Machine Learning, volume 97 of
Proceedings of Machine Learning Research, pp.  4363–4371. PMLR,
09–15 Jun 2019b.
URL <https://proceedings.mlr.press/v97/maron19a.html>.

[Maron et al., 2020]
Maron, H., Litany, O., Chechik, G., and Fetaya, E.
On Learning Sets of Symmetric Elements.
In III, H. D. and Singh, A. (eds.), Proceedings of the 37th
International Conference on Machine Learning, volume 119 of
Proceedings of Machine Learning Research, pp.  6734–6744. PMLR,
13–18 Jul 2020.
URL <https://proceedings.mlr.press/v119/maron20a.html>.

[Pearce-Crump, 2022]
Pearce-Crump, E.
Connecting Permutation Equivariant Neural Networks and
Partition Diagrams.
, 2022a.

[Pearce-Crump, 2022]
Pearce-Crump, E.
Brauer's Group Equivariant Neural Networks.
, 2022b.

[Ravanbakhsh, 2020]
Ravanbakhsh, S.
Universal Equivariant Multilayer Perceptrons.
In Proceedings of the 37th International Conference on Machine
Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of
Proceedings of Machine Learning Research, pp.  7996–8006. PMLR,
URL <http://proceedings.mlr.press/v119/ravanbakhsh20a.html>.

[Sagan, 2000]
Sagan, B. E.
The Symmetric Group: Representations, Combinatorial Algorithms,
and Symmetric Functions.
Springer, 2000.

[Segal, 2014]
Segal, E.
Group Representation Theory.
Course Notes for Imperial College London, 2014.

[Zaheer et al., 2017]
Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, B., Salakhutdinov, R. R., and
Smola, A. J.
Deep Sets.
In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R.,
Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural
Information Processing Systems, volume 30. Curran Associates, Inc., 2017.

[Zhang et al., 2019]
Zhang, C., Liwicki, S., Smith, W., and Cipolla, R.
Orientation-Aware Semantic Segmentation on Icosahedron
In 2019 IEEE/CVF International Conference on Computer Vision
(ICCV), pp.  3532–3540, Los Alamitos, CA, USA, nov 2019. IEEE Computer

§ THE WEIGHT MATRIX FOR $S_2$ AND $A_2$–EQUIVARIANT LINEAR LAYER FUNCTIONS FROM $(\MATHBB{R}^{2})^{\OTIMES 2}$ TO $\MATHBB{R}^{2}$

We first show how to find a basis of
$\Hom_{S_2}((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$,
where, in this case, $n=2$, $k=2$, and $l=1$.

To do this, we first need to find all set partitions in $\Pi_{1+2,2}$, that is, all set partitions $\pi$ of $3$ having at most $2$ blocks.
The first column of Figure <ref> shows these set partitions in their equivalent diagram form, $d_\pi$.
Each of these set partition diagrams corresponds to a basis element in
$\Hom_{S_2}((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$, by Theorem <ref>.

To obtain the basis elements themselves, we first recall that each set partition $\pi$ corresponds to an orbit
$O_{S_2}((I_\pi, J_\pi))$
coming from the action of $S_2$ on $[2]^{1+2}$.
A representative of each orbit, called the block labelling, is given in the third column of Figure <ref>,
and it is found by letting the $i^{\text{th}}$ position in $[1+2]$ be the label of the block in $\pi$ containing the number $i$, where the blocks of $\pi$ have themselves been labelled by letting
$B_1$ be the block that contains the number $1 \in [1+2]$, and, if $\pi$ has $2$ blocks, letting $B_2$ be the other block in $\pi$.

Finally, we form a basis element $X_\pi$
$\Hom_{S_2}((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$
by summing over all matrix units in
$\Hom((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$
that are indexed by the elements of
$O_{S_2}((I_\pi, J_\pi))$, as stated in (<ref>).
These basis elements are given in the fourth column of Figure <ref>.

colspec = X[c,h]X[c]X[c]X[c],
stretch = 0,
rowsep = 5pt,
hlines = 1pt,
vlines = 1pt,

Set Partition Diagram
Block Labelling
$(I_{\pi} \mid J_{\pi})$
Standard Basis Element

0.6orbit21sq1     $\{1, 2, 3\}$     $\{1 \mid 1, 1\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 1	& 0	& 0	& 0	\\
2		& 0	& 0	& 0	& 1
\end{bNiceArray}

0.6orbit21sq2	    $\{1, 2 \mid 3\}$ 	    $\{1 \mid 1, 2\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 1	& 0	& 0	\\
2		& 0	& 0	& 1	& 0
\end{bNiceArray}

0.6orbit21sq3	    $\{1, 3 \mid 2\}$ 	    $\{1 \mid 2, 1\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 1	& 0	\\
2		& 0	& 1	& 0	& 0
\end{bNiceArray}

0.6orbit21sq4	    $\{1 \mid 2, 3\}$ 	    $\{1 \mid 2, 2\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 0	& 1	\\
2		& 1	& 0	& 0	& 0
\end{bNiceArray}

We use Theorem <ref>
to obtain a basis of
$\Hom_{S_2}((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$
from all of the
set partitions in $\Pi_{1+2,2}$.

the weight matrix for an $S_2$–equivariant linear layer function from $(\mathbb{R}^{2})^{\otimes 2}$ to $\mathbb{R}^{2}$
is of the form

\begin{equation}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& \lambda_1	& \lambda_2	& \lambda_3	& \lambda_4	\\
2		& \lambda_4	& \lambda_3	& \lambda_2	& \lambda_1
\end{bNiceArray}
\end{equation}

for scalars $\lambda_1, \dots, \lambda_4 \in \mathbb{R}$.

Next, we show how to find a basis of
$\Hom_{A_2}((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$.
Again, we consider all set partitions in $\Pi_{1+2,2}$.

Since $n = 2$, the $S_2$ orbit corresponding to each set partition in $\Pi_{1+2,2}$

splits because each set partition has either $1$ or $2$ blocks.

We show in full how to find the two basis elements
$X_\pi^{+}$, $X_\pi^{-}$
$\Hom_{A_2}((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$
that corresponds to the first set partition diagram $d_\pi$ in Figure <ref>, where $\pi = \{1,2,3\}$, and state what they are for the other set partition diagrams in Figure <ref>.

First, we flatten the set partition diagram $d_\pi$.
Then we add a new top row consisting of $n=2$ vertices, and connect the lowest numbered vertex in each block $i$ of $\pi$ to vertex $i$ in the top row.
Hence, we obtain the diagram $b_\pi$, which is

\begin{equation}
\begin{aligned}
\scalebox{0.6}{\tikzfig{flatorbit21sq1}}
\end{aligned}
\end{equation}

Next, we attach a two-legged jellyfish to the top row of vertices,

\begin{equation}
\scalebox{0.6}{\tikzfig{jellyfishorbit21sq1}}
\end{equation}

This is the diagram that is associated with the function $f_\pi$ that is given in Proposition <ref>.

To obtain the two $A_2$ orbits

$O_{A_2}((I_\pi^+, J_\pi^+))$

$O_{A_2}((I_\pi^-, J_\pi^-))$
corresponding to $\pi$, we apply Theorem <ref>.

From Figure <ref>, we see that
$O_{S_2}((I_\pi, J_\pi)) = \{(1,1,1), (2,2,2)\}$,
and so, we have that

\begin{equation}
= \det \circ \, g_\pi(e_{(1,1,1)})
= \det(e_{(1,1)} + e_{(1,2)})
= +1
\end{equation}

\begin{equation}
= \det \circ \, g_\pi(e_{(2,2,2)})
= \det(e_{(2,1)} + e_{(2,2)})
= -1
\end{equation}

Hence, by
(<ref>) and
we have that

\begin{equation}
O_{A_2}((I_\pi^+, J_\pi^+))
= \{(1,1,1)\}
\end{equation}

\begin{equation}
O_{A_2}((I_\pi^-, J_\pi^-))
= \{(2,2,2)\}
\end{equation}

and so,
by (<ref>) and

\begin{equation}
= E_{(1 \mid 1,1)}
\end{equation}

\begin{equation}
= E_{(2 \mid 2,2)}
\end{equation}

Consequently, from the matrices given in Figure <ref>,

the weight matrix for an $A_2$–equivariant linear layer function from $(\mathbb{R}^{2})^{\otimes 2}$ to $\mathbb{R}^{2}$
is of the form

\begin{equation}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& \lambda_1	& \lambda_3	& \lambda_5	& \lambda_7	\\
2		& \lambda_8	& \lambda_6	& \lambda_4	& \lambda_2
\end{bNiceArray}
\end{equation}

for scalars $\lambda_1, \dots, \lambda_8 \in \mathbb{R}$.

colspec = X[c,h]X[c]X[c]X[c],
stretch = 0,
rowsep = 5pt,
hlines = 1pt,
vlines = 1pt,

Set Partition Diagram
$d_\pi$ 	    Partition
Standard Basis Element
Standard Basis Element

0.6orbit21sq1      $\{1, 2, 3\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 1	& 0	& 0	& 0	\\
2		& 0	& 0	& 0	& 0
\end{bNiceArray}

\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 0	& 0	\\
2		& 0	& 0	& 0	& 1
\end{bNiceArray}

0.6orbit21sq2	    $\{1, 2 \mid 3\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 1	& 0	& 0	\\
2		& 0	& 0	& 0	& 0
\end{bNiceArray}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 0	& 0	\\
2		& 0	& 0	& 1	& 0
\end{bNiceArray}

0.6orbit21sq3	    $\{1, 3 \mid 2\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 1	& 0	\\
2		& 0	& 0	& 0	& 0
\end{bNiceArray}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 0	& 0	\\
2		& 0	& 1	& 0	& 0
\end{bNiceArray}

0.6orbit21sq4	    $\{1 \mid 2, 3\}$
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 0	& 1	\\
2		& 0	& 0	& 0	& 0
\end{bNiceArray}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c} | *{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1		& 0	& 0	& 0	& 0	\\
2		& 1	& 0	& 0	& 0
\end{bNiceArray}

By considering which set partitions in $\Pi_{1+2,2}$ split, we obtain a basis of
$\Hom_{A_2}((\mathbb{R}^{2})^{\otimes 2}, \mathbb{R}^{2})$.

Note that if $n=3$, then we also need to consider the set partition diagram

\begin{equation}
\begin{aligned}
\scalebox{0.6}{\tikzfig{orbit21sq5}}
\end{aligned}
\end{equation}

corresponding to the set partition $\{1 \mid 2 \mid 3\}$, since this is a valid set partition in $\Pi_{1+2,3}$.
In this case,
only the set partition $\{1,2,3\}$ does not split.
Hence, while the dimension of
\Hom_{S_3}((\mathbb{R}^{3})^{\otimes 2}, \mathbb{R}^{3})
is $5$,
the dimension of
\Hom_{A_3}((\mathbb{R}^{3})^{\otimes 2}, \mathbb{R}^{3})
is $9$.

However, if $n \geq 4$, then none of the set partitions in $\Pi_{1+2,n}$
split, and so, in this case,

\begin{equation}
\Hom_{S_n}((\mathbb{R}^{n})^{\otimes 2}, \mathbb{R}^{n})
\Hom_{A_n}((\mathbb{R}^{n})^{\otimes 2}, \mathbb{R}^{n})
\end{equation}

Consequently, the basis $\{X_\pi\}$, of size $5$, is the same for each space.

§ LIMITATIONS AND FEASIBILITY

It is important to acknowledge that given the
current limitations of hardware, there will be some challenges when
implementing the neural networks that are discussed in this paper.
In particular, significant engineering efforts will be needed to achieve the required scale because storing high-order tensors in memory

is not a straightforward task.
This was demonstrated by Kondor et al. clebschgordan, who had to develop custom CUDA kernels in order to implement their tensor product based neural networks.
Nevertheless, we anticipate that with the increasing availability of computing power, higher-order group equivariant neural networks will become more prevalent in practical applications.
Notably, while the dimension of tensor power spaces increases exponentially with their order, the dimension of the space of equivariant maps between such tensor power spaces is often much smaller, and the corresponding matrices are typically sparse.
Therefore, while storing these matrices may present some technical difficulties, it should be feasible with the current computing power that is available.

§ EQUIVARIANCE TO LOCAL SYMMETRIES

We can extend our results to looking at linear layer functions that are equivariant to a direct product of alternating groups;
that is, we can construct neural networks that are equivariant to local symmetries.
The case for an external tensor product of order $1$ tensors can be found in [Maron et al., 2020]; below, we show the equivariance for any tensors of any order.

We wish to find a basis for

\begin{equation} \label{genericHomspace}
%\Hom_{A_{n_1} \times \dots \times A_{n_p}}(V, W)
\Hom_{A_{n_1} \times \dots \times A_{n_p}}(
(\mathbb{R}^{n_1})^{\otimes {k_1}} \boxtimes \dots \boxtimes (\mathbb{R}^{n_p})^{\otimes {k_p}},
(\mathbb{R}^{n_1})^{\otimes {l_1}} \boxtimes \dots \boxtimes (\mathbb{R}^{n_p})^{\otimes {l_p}})
\end{equation}

where $\boxtimes$ is the external tensor product.

The $\Hom$-space given in (<ref>) is isomorphic to

\begin{equation} \label{tensorgenericHomspace}
\bigotimes_{r=1}^{p} \Hom_{A_{n_r}}((\mathbb{R}^{n_r})^{\otimes k_r}, (\mathbb{R}^{n_r})^{\otimes l_r})
\end{equation}

As Theorem <ref> gives a basis for each individual $\Hom$–space in (<ref>), we can obtain a basis for the overall $\Hom$–space (<ref>) by forming all possible $p$–length Kronecker products of basis elements in the standard way for tensor product spaces.