Connecting Permutation Equivariant Neural Networks and Partition Diagrams

Edward Pearce–Crump<EMAIL_ADDRESS>
Department of Computing

Imperial College London

SW7 2BX, UK

My editor

We show how the Schur–Weyl duality that exists between the partition algebra and the symmetric group results in a stronger theoretical foundation for characterising
all of the possible permutation equivariant neural networks whose layers are some tensor power of the permutation representation $M_n$ of the symmetric group $S_n$.
In doing so, we unify two separate bodies of literature, and we correct some of the major results that are now widely quoted by the machine learning community.
In particular, we find a basis of matrices for the learnable, linear, permutation equivariant layer functions between such tensor power spaces in the standard basis of $M_n$ by using an elegant graphical representation of a basis of set partitions for the partition algebra and its related vector spaces.
Also, we show how we can calculate
the number of weights that must appear in these layer functions by looking at certain paths through the McKay quiver for $M_n$.
Finally, we describe how our approach generalises to the construction of neural networks that are equivariant to local symmetries.

permutation equivariant neural networks, symmetric group, combinatorial representation theory, schur–weyl duality, partitions

§ INTRODUCTION

Permutation equivariant neural networks were born out of the desire to be able to learn from data that has, at its core, permutation symmetry.
For example, sets and graphs are data structures that exhibit such symmetry.
Indeed, the labelling of the elements of a set or of the nodes of a graph is arbitrary; hence, any function that is learned from

data that has permutation symmetry

should not depend on how the data is labelled.

Despite there being a number of papers on this research topic, such as
[Zaheer et al., 2017],
[Hartford et al., 2018],
[Maron et al., 2019],
[Thiede et al., 2020],
[Finzi et al., 2021], and
[Pan and Kondor, 2022],
whose details we explore further in Section <ref>,

we believe that two major issues remain:

* Some of the early major results that are now widely quoted by the more recent papers in the field are missing key technical details whose exclusion significantly impacts the correct construction of these neural networks.

* The approaches that have been taken to prove the major results are all rather different, which suggests that there may be
one overarching set of reasons as to why all of these results are true.

In this paper, we suggest a new approach.
We show how the representation theory of the partition algebra, developed by pure mathematicians, can be used to construct permutation equivariant neural networks whose layers are some tensor power of the permutation representation $M_n$ of dimension $n$ of the symmetric group $S_n$.
These neural networks learn from data that exhibit relationships up to any order.
For example, the individual elements of a set exhibit first order relationships, whereas the nodes of a graph exhibit second order relationships.

In making the connection between the partition algebra and these permutation equivariant neural networks,
we create a strong theoretical foundation that we believe resolves the two major issues stated above.
In particular, we show how the
construction of these neural networks is
founded upon

a number of combinatorial objects, which overall makes for a rather satisfying theory.

The main contributions of this paper are as follows:

* We are the first to show how the combinatorics underlying the partition algebra and its related vector spaces,
adapted from the Schur–Weyl duality that exists between the partition algebra and the symmetric group,
provides the theoretical background for constructing permutation equivariant neural networks
when the layers are some tensor power of the permutation representation $M_n$ of the symmetric group $S_n$.

* In particular, we find a basis of matrices for the learnable, linear, permutation equivariant layer functions between such tensor power spaces in the standard basis of $M_n$ by using an elegant graphical representation of a basis of set partitions for the partition algebra and its related vector spaces.

* We derive a number of combinatorial constructions that can be used to calculate the number of weights that must appear in the learnable, linear layer functions of the permutation equivariant neural networks in question.
In particular, we show how the McKay quiver for the representation $M_n$ of the symmetric group $S_n$ combined with the fact that $S_n$ is in Schur–Weyl duality with a tensor power centraliser algebra, $\End_{S_n}(M_n^{\otimes k})$, enables us to calculate the number of weights.

* We generalise this diagrammatical approach to show how to construct neural networks that are equivariant to local symmetries.

* We suggest that Schur–Weyl duality is a powerful mathematical concept that could be used to characterise other group equivariant neural networks beyond those considered in this paper.

§ PRELIMINARIES

§.§ A Word on Notation

In the following, we denote the symmetric group of permutations of $n$ objects by $S_n$.

We choose our field of scalars to be $\mathbb{C}$ throughout, although the results generalise to any field $\mathbb{F}$ of characteristic zero, such as $\mathbb{R}$.
Tensor products are also taken over $\mathbb{C}$, unless otherwise stated.

In most cases, we let $[n]$ represent the set $\{1, \dots, n\}$, although at times
we use the same notation to refer to the $1$-dimensional trivial representation of $S_n$.
The context should make clear what is being referred to, although if there is any doubt, we use the word shape before $[n]$ to make clear that we are referring to the representation and not the set of $n$ elements.

§.§ Representations of the Symmetric Group and its Branching Rules

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

\begin{equation}
\rho : S_n \rightarrow GL(V)
\end{equation}

We choose to focus on finite-dimensional vector spaces $V$ in this paper.

We often abuse our terminology by calling $V$ a representation of $S_n$, 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)$.

We will also refer to such $V$ as $S_n$-modules, again abusing our notation slightly.
Technically, $V$ is a module over the group algebra $\mathbb{C}[S_n]$ and not the group.
However, because this is done elsewhere in the literature, we will do the same in this paper.
Ultimately, these are all interchangeable ways of referring to the same concept.

For more details on the basics of representation theory, see any of
[Goodman and Wallach, 2009],
[Ceccherini-Silberstein et al., 2010],
or [Segal, 2014].

It is well known that the representation theory of the symmetric group can be formulated using a combinatorial approach

that is intimately connected to the partitions of some non-negative integer $n$ and their associated Young frames.

A partition $\lambda$ of $n$, denoted by $\lambda \vdash n$, is defined to be a tuple $(\lambda_1, \lambda_2, \dots, \lambda_k)$
of non-negative integers
such that

* $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_k > 0$ and

* $\sum_{i = 1}^{k} \lambda_i = n$

We say that such a partition consists of $k$ parts, and we define its length to be $k$.
We denote the set of all partitions of $n$ by $\Lambda(S_n)$.

As a matter of convention, when a partition has parts whose values are the same, instead of writing the parts separately, we group them together using power notation.
For example, we express the partition $(5, 5, 5, 3, 3, 2, 1, 1, 1, 1) \vdash 27$ as $(5^3, 3^2, 2, 1^4) \vdash 27$.

To every partition $\lambda \vdash n$ we associate a Young frame of shape $\lambda$, that is, a diagram consisting of $k$ rows, where row $i$ consists of $\lambda_i$ boxes (by convention, the row number increases downwards).
We will denote a Young frame of shape $\lambda$ also by $\lambda$, with the context making clear what is being referred to. Figure <ref>a) shows the Young frame for the partition $(4, 2^2) \vdash 8$.

For each partition $\lambda \vdash n$ we can assign to its corresponding Young frame of shape $\lambda$ a set of coordinates, with the rows being numbered from top to bottom (with starting index $1$) and the columns from left to right (also with starting index $1$).
We say that the box at coordinates $(i, j)$ is removable if there is no box at the locations $(i + 1, j)$ and $(i, j+1)$.
We say that the box at coordinates $(i, j)$ is addable if, when $i = 1$, $j = \lambda_1 + 1$, else, when $i > 1$, $\lambda_i = j - 1 < \lambda_{i-1}$.
Figure <ref>b) shows the removable (X) and addable (*) boxes for the Young frame of shape $(4, 2^2) \vdash 8$.

a) The Young frame for the partition $(4, 2^2) \vdash 8$.
b) X denotes the removable boxes, whereas * denotes the addable boxes.

For each partition $\lambda \vdash n$, a Young tableau of shape $\lambda$ is a bijection between the set $\{1, 2, \ldots, n\}$ and the boxes of the Young frame of shape $\lambda$.
We represent such a bijection diagrammatically by filling in the boxes of the Young frame with the numbers $1, 2, \ldots, n$ such that each number appears in exactly one box.
Figure <ref>a) gives an example of a Young tableau for the partition $(4, 2^2) \vdash 8$.
A Young tableau of shape $\lambda$ is said to be standard if the numbers are increasing in each row (from left to right) and in each column (from top to bottom).
Figure <ref>b) gives an example of a standard Young tableau for the partition $(4, 2^2) \vdash 8$.
Note that the Young tableau given in Figure <ref>a) is not standard.

a) A Young tableau for the partition $(4, 2^2) \vdash 8$. It is not standard.
b) A standard Young tableau for the partition $(4, 2^2) \vdash 8$.

For each partition $\lambda \vdash n$, we can also construct equivalence classes of Young tableaux of shape $\lambda$ as follows.
Let $t_1$ and $t_2$ be Young tableaux of shape $\lambda$.
Then $t_1$ and $t_2$ are said to be row equivalent, written $t_1 \sim t_2$, if each row of the tableaux contains the same elements.
For example, the Young tableau given in Figure <ref>a) is row equivalent to the Young tableau given in Figure <ref>b).
It can be shown that $\sim$ is an equivalence relation, which leads to the following definition:
a Young tabloid $\{t\}$ of shape $\lambda$ is an equivalence class under $\sim$, that is:

\{t\} \coloneqq \{t_1 \mid t_1 \sim t\}

where the shape of $t$ is $\lambda$.
We represent a Young tabloid of shape $\lambda$ by taking the rows of a representative of the equivalence class (a Young tableau of shape $\lambda$) and drawing lines between the rows.
Figure <ref> gives an example of a Young tabloid for the partition $(3, 1) \vdash 4$, taking the standard Young tableau of the equivalence class as its representative.

A Young tabloid for the partition $(3, 1) \vdash 4$.

The combinatorial objects introduced above can be used to construct representations of $S_n$, as follows.

For each partition $\lambda \vdash n$, it can be shown that there is a representation of $S_n$ which has a basis that is the set of all Young tabloids of shape $\lambda$.
We denote this representation by $M^{\lambda}$, and it is called the permutation representation corresponding to $\lambda$.

$M^\lambda$ itself may or may not be irreducible, but it can be shown that, as part of its decomposition into irreducible representations of $S_n$, it has one copy of an irreducible representation which is denoted by $S_n^\lambda$.
$S_n^\lambda$ is called a Specht module, and it can be shown that the set

\{S_n^\lambda \mid \lambda \in \Lambda(S_n)\}

is a complete set of irreducible representations for $S_n$ (up to equivalence).
That is, the irreducible representations of $S_n$ (up to equivalence) are in bijective correspondence with the set of partitions of $n$.
Furthermore, it can be shown that each $S_n^\lambda$ has a basis which is in bijective correspondence with the set of all standard Young tableaux of shape $\lambda$, whose size, $f_n^{\lambda}$, is given by the hook-length formula

\begin{equation}
f_n^{\lambda} = \frac{n!}{\prod_{i, j \in \lambda} h_{i,j}}
\end{equation}

where $h_{i,j}$ is equal to the number of boxes to the right of $(i,j)$ in the same row, plus the number of boxes below $(i,j)$ in the same column, plus $1$.

It is also well known that there is a branching rule for irreducible representations of $S_n$.

It exists in two versions, depending on whether we are restricting or inducing representations of $S_n$.

The restriction version states that for any partition $\lambda \vdash n$, its accompanying irreducible representation of $S_n$, $S_n^\lambda$, can be expressed in the following form when restricted to be a representation of $S_{n-1}$:

\begin{equation} \label{youngrestriction}
\Res^{S_n}_{S_{n-1}}(S_n^\lambda)
%= \bigoplus_{\mu \vdash n-1: \mu \leftarrow \lambda} S_{n-1}^\mu
\cong \bigoplus_{\substack{\mu \vdash n-1 \\ \mu \leftarrow \lambda}} S_{n-1}^\mu
\end{equation}

where the direct sum is taken over all partitions $\mu \vdash n-1$ such that $\mu$ can be obtained by removing a box from the Young frame of $\lambda$ (which is denoted by $\mu \leftarrow \lambda$).

The induction version states that for any partition $\lambda \vdash n$, its accompanying irreducible representation of $S_n$, $S_n^\lambda$, can be expressed in the following form when induced to be a representation of $S_{n+1}$:

\begin{equation} \label{younginduction}
\Ind^{S_{n+1}}_{S_n}(S_n^\lambda)
%= \bigoplus_{\mu \vdash n+1: \lambda \leftarrow \mu} S_{n+1}^\mu
\cong \bigoplus_{\substack{\mu \vdash n+1 \\ \lambda \leftarrow \mu}} S_{n+1}^\mu
\end{equation}

where the direct sum is taken over all partitions $\mu \vdash n+1$ such that $\mu$ can be obtained by adding a box to the Young frame of $\lambda$ (which is denoted by $\lambda \leftarrow \mu$).
These versions are, in fact, equivalent under the Frobenius Reciprocity Theorem.

For more details on the representation theory of the symmetric group, see [Sagan, 2000] or [Vershik and Okounkov, 2005].

§.§ A Special Isomorphism between Two Representations of $S_n$.

We consider a special representation of the symmetric group throughout much of the rest of this paper.
It is $M^{[n-1,1]}$, the permutation representation of $S_n$ of dimension $n$.
Since it is so important in what follows, we give it some special notation:

\begin{equation}
M_n \coloneqq M^{[n-1,1]}
\end{equation}

Recall that $M_n$ has a basis consisting of all tabloids of shape $[n-1,1]$.
We identify this basis with the basis labelled by $\{v_a \mid a \in [n]\}$ under the isomorphism that maps the tabloid with the number $a$ in the second row to $v_a$.

$M_n$ is a representation of $S_n$ via its (left) action on the basis $\{v_a \mid a \in [n]\}$ which is extended linearly,
where, specifically, the action is given by

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

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

\begin{equation} \label{tensorelementfirst}
v_I \coloneqq v_{i_1} \otimes v_{i_2} \otimes \dots \otimes v_{i_k}
\end{equation}

for all $I \coloneqq (i_1, i_2, \dots, i_k) \in [n]^k$ form a basis of $M_n^{\otimes k}$,

and the action of $S_n$ that maps a basis element of $M_n^{\otimes k}$ of the form (<ref>) to

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

can be extended linearly.
We denote the representation itself by $\rho_{k}$.

However, we also see that $\mathbb{C}^n$ is isomorphic to $M_n$ as representations of $S_n$, where if $\{e_a \mid a \in [n]\}$ is the standard basis of $\mathbb{C}^n$, and the action of $S_n$ on this basis is defined by

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

and is extended linearly,
then the isomorphism of representations is given by $e_a \mapsto v_a$.

Hence, $(\mathbb{C}^{n})^{\otimes k}$ is isomorphic to $M_n^{\otimes k}$ as representations of $S_n$.
But since
(\mathbb{C}^{n})^{\otimes k}$
is isomorphic to
\mathbb{C}^{n^k}
we get that

\begin{equation} \label{cnkmnkiso}
\mathbb{C}^{n^k} \cong M_n^{\otimes k}
\end{equation}

as representations of $S_n$.

We have chosen to highlight the isomorphism between $\mathbb{C}^{n^k}$ and $M_n^{\otimes k}$ as representations of $S_n$
because $\mathbb{C}^{n^k}$ is the $k$-order tensor defined and worked with in papers such as [Maron et al., 2019] and [Thiede et al., 2020].
However, what was not made clear until now is that the $k$-order tensor is actually the $k$-tensor power of the permutation representation of $S_n$ of dimension $n$.

§.§ Permutation Equivariant Neural Networks

Permutation equivariant neural networks are constructed by alternately composing linear and non-linear permutation equivariant maps between representations of the symmetric group.
We define permutation equivariance below:

Suppose that $(V, \rho_{V})$ and $(W, \rho_{W})$

are two representations of $S_n$.

A map $\phi : V \rightarrow W$ is said to be permutation equivariant if

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

We denote the set of all linear permutation equivariant maps between $V$ and $W$ by $\Hom_{S_n}(V,W)$.

When $V = W$, we write this set as $\End_{S_n}(V)$.

It can be shown that $\Hom_{S_n}(V,W)$ is a vector space over $\mathbb{C}$, and that $\End_{S_n}(V)$ is an algebra over $\mathbb{C}$.
See [Segal, 2014] for more details.

A special case of permutation equivariance is permutation invariance:

The map $\phi$ given in Definition <ref> is said to be permutation invariant if $\rho_{W}$ is defined to be the $d$-dimensional trivial representation of $S_n$.

Since the $d$-dimensional trivial representation of $S_n$ can be decomposed into a direct sum of $d$ irreducible representations of $S_n$, each of

which is the irreducible $1$-dimensional trivial representation of $S_n$, we choose in the following to focus on permutation invariant functions that map to the $1$-dimensional trivial representation $\mathbb{C}$.

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

An $L$-layer permutation equivariant ($S_n$-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 $S_n$

\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{layerfidefn}
f_l \coloneqq \sigma_l \circ \phi_l
\end{equation}

of a learnable, linear, permutation equivariant function $\phi_l : (V_{l-1}, \rho_{l-1}) \rightarrow (V_l, \rho_l)$ together with
a fixed, non-linear activation function $\sigma_l: (V_l, \rho_l) \rightarrow (V_l, \rho_l)$
such that

* $\sigma_l$ is a permutation 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, permutation equivariant functions

in this paper, since the non-linear functions are fixed.

Permutation Equivariant Neural Networks.

The entire neural network $f_{\mathit{NN}}$ is itself a permutation equivariant function because

it can be shown that
the composition of any number of permutation equivariant functions is itself permutation equivariant.

One way of making

a neural network of the form given in Definition <ref>

permutation invariant

is by choosing the representation in the final layer

to be the $d$-dimensional trivial representation of $S_n$.

Figure <ref> highlights the equivariance property of a permutation equivariant neural network.

Specifically, the figure shows that if some $v_0 \in V_0$ is passed through the neural network (as represented by the left hand dotted box) with output equal to some $v_L \coloneqq f_{\mathit{NN}}(v_0) \in V_L$, then if $\rho_0(g)[v_0]$, for any $g \in S_n$, is passed through the same neural network (as represented by the right hand dotted box), the output will be

\begin{equation}
\rho_L(g)[f_{\mathit{NN}}(v_0)]
\rho_L(g)[v_L]
\end{equation}

that is, the neural network respects the action of the symmetric group on both its input and its output.

It is important to emphasise that each dotted box in Figure <ref> represents the same neural network $f_{\mathit{NN}}$, that is, the network architecture itself does not change between the dotted boxes.

As discussed in the Introduction,
we are interested in

calculating the exact form of any permutation equivariant neural network whose layers are some tensor power of the permutation representation of dimension $n$ of $S_n$, where the tensor power can be different for different layers of the network.
These representations were introduced in Section <ref>.
We are interested in understanding not only the representations themselves but also the learnable, linear, permutation equivariant layer functions between them.

Specifically, we want not only

to calculate the number of weight parameters for each of

* a $k$-order permutation equivariant layer function, $M_n^{\otimes k} \rightarrow M_n^{\otimes k}$,

* a $k$-order to $l$-order permutation equivariant layer function, $M_n^{\otimes k} \rightarrow M_n^{\otimes l}$, and

* a $k$-order permutation invariant layer function, $M_n^{\otimes k} \rightarrow M_n^{\otimes 0}$,

but also to find the matrix form of each such layer function in the standard basis of $M_n$, so that any permutation equivariant neural network of this type can be implemented in practice.

By Definition <ref>, we see that the spaces we are interested in are

* $\End_{S_n}(M_n^{\otimes k})$

* $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$

* $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$

We can use standard representation theoretic results to show that each of these spaces is an $S_n$-invariant of some tensor space of $M_n$.
Indeed, given that, for any representation $V$ of $S_n$, $\End(V) \cong V \otimes V^{*}$, and
that $M_n$ is isomorphic to its dual, $M_n^{*}$, we see that

\begin{equation} \label{EndMnktoMn2k}
\End(M_n^{\otimes k})
\cong
M_n^{\otimes k} \otimes (M_n^{\otimes k})^{*}
\cong
M_n^{\otimes k} \otimes (M_n^{*})^{\otimes k}
\cong
M_n^{\otimes 2k}
\end{equation}

as representations of $S_n$.

Consequently, since $\End_{S_n}(M_n^{\otimes k})$
is the invariant subrepresentation $(\End(M_n^{\otimes k}))^{S_n}$
of $\End(M_n^{\otimes k})$, we have that

\begin{equation} \label{EndSnMnktoMn2k}
\End_{S_n}(M_n^{\otimes k})
\cong
(M_n^{\otimes 2k})^{S_n}
\end{equation}

Similarly, we can also show that

\begin{equation} \label{HomSnMnktoMnl}
\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})
\cong
(M_n^{\otimes k+l})^{S_n}
\end{equation}

and so

\begin{equation} \label{HomSnMnktoMn0}
\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0}) \cong (M_n^{\otimes k})^{S_n}
\end{equation}

Instead of studying these $S_n$-tensor space invariants further, we show how we can use simple combinatorial methods to understand these spaces better.

We assume throughout most of the paper that the feature dimension for all of our representations is one.
This is because the symmetric group does not act on the feature space in most of the cases that we consider.
We relax this assumption in Section <ref>.
Furthermore, only in Section <ref>
do we explore the possibility of the symmetric group acting on the space of features too, in which case we make it clear what the dimension of the feature space is for each layer.

Also, the layer functions under consideration do not take into account any bias terms, but we will show in Section <ref> that these can be easily introduced.

§ HOW WALKING ON A GRAPH RESULTS IN A TENSOR POWER REPRESENTATION

Let $V$ be a finite-dimensional $S_n$-module over $\mathbb{C}$.

Recall that a quiver $Q = (Q_0, Q_1, s, e)$, where $Q_0$, $Q_1$ are sets, and $s, e$ are maps $Q_1 \rightarrow Q_0$, is just a directed graph with potentially multiple arrows and loops: the elements of $Q_0$ are called nodes, the elements of $Q_1$ are called arrows, and if $\alpha$ is an arrow, then $s(\alpha)$ is called its start vertex and $e(\alpha)$ is called its end vertex.

The McKay quiver associated with the $S_n$-module $V$, denoted by $Q_V(S_n)$, is a quiver consisting of a set of nodes whose elements are the partitions $\lambda \vdash n$ corresponding to the irreducible $S_n$-modules $\{S_n^{\lambda} \mid \lambda \in \Lambda(S_n)\}$ over $\mathbb{C}$, and a set of arrows where,
for $\lambda, \mu \in \Lambda(S_n)$, there are $\alpha_{\lambda, \mu}$ arrows from $\lambda$ to $\mu$ in $Q_V(S_n)$ if the irreducible $S_n$-module $S_n^{\mu}$ appears with multiplicity $\alpha_{\lambda, \mu}$ in the decomposition of $S_n^{\lambda} \otimes V$ into irreducible $S_n$-modules, that is, if

\begin{equation} \label{tensorwithV}
S_n^{\lambda} \otimes V \cong \bigoplus_{\mu \in \Lambda(S_n)} \alpha_{\lambda, \mu} S_n^{\mu}
\end{equation}

If $\alpha_{\lambda, \mu} = \alpha_{\mu, \lambda}$, then the arrows between $\lambda$ and $\mu \in Q_V(S_n)$ are drawn without arrowheads, that is, there are $\alpha_{\lambda, \mu}$ undirected edges between $\lambda$ and $\mu$ in $Q_V(S_n)$.

The McKay quiver of $V$ is also called the representation graph of $V$ in the literature.
It is worth emphasising that the McKay quiver is associated with a choice of finite-dimensional $S_n$-module, which we have called $V$ in the above: if we choose a different finite-dimensional $S_n$-module, say $W$, then in general we obtain a different quiver.

An adjacency matrix $A_V$ can be associated to each McKay quiver $Q_V(S_n)$:
the rows and columns are indexed by the nodes of $Q_V(S_n)$, and the $(\lambda, \mu)$-entry of $A_V$

is given by the number of arrows from $\lambda$ to $\mu$ in $Q_V(S_n)$, that is, the value $\alpha_{\lambda, \mu}$ as defined in (<ref>).

We can walk on a McKay quiver $Q_V(S_n)$ in the following sense.
Suppose that $\lambda, \mu$ are two nodes of $Q_V(S_n)$.
We say that there is a walk of $k$ steps from $\lambda$ to $\mu$ if there are exactly $k$ arrows $\alpha_1$, $\dots$, $\alpha_k$ such that

$$\lambda = s(\alpha_1), e(\alpha_1) = s(\alpha_2), \dots, e(\alpha_{k-1}) = s(\alpha_k), \text{ and } e(\alpha_k) = \mu$$

It is clear from this definition that an arrow $\alpha$ from a node $\lambda$ to a node $\mu$ in $Q_V(S_n)$ corresponds to a walk of one step from $\lambda$ to $\mu$.
From (<ref>) it is also clear that walking one step from $\lambda$ corresponds to tensoring $S_n^{\lambda}$ with $V$.

Consequently, if there are $m$ walks of $k$ steps between $\lambda$ and $\mu$, then it is clear that $S_n^{\mu}$ appears in the decomposition of $S_n^{\lambda} \otimes V^{\otimes k}$ into irreducible $S_n$-modules with multiplicity $m$, that is, each step on a walk of $k$ steps corresponds to tensoring with $V$.

This gives us the critical idea in understanding the $S_n$-module $V^{\otimes k}$ in terms of its decomposition into irreducible $S_n$-modules.
Since $V^{\otimes k} \cong S_n^{[n]} \otimes V^{\otimes k}$, where $S_n^{[n]}$ is the one-dimensional trivial $S_n$-module, we see that the multiplicity of the irreducible $S_n$-module $S_n^{\mu}$ in the decomposition of $V^{\otimes k}$ into irreducible $S_n$-modules, denoted by $m_k^{\mu}$, is precisely the number of walks of $k$ steps from $[n]$ to $\mu$ in $Q_V(S_n)$.
That is,

\begin{equation} \label{Votimesk}
V^{\otimes k} \cong \bigoplus_{\mu \in \Lambda(S_n)} m_k^{\mu} S_n^{\mu}
\end{equation}

However, finding the McKay quiver for a generic finite-dimensional $S_n$-module $V$, in order to obtain such a decomposition (<ref>),
is not very easy, since, in most cases, decomposing a tensor product of $S_n$-modules, such as $S_n^{\lambda} \otimes V$, into irreducibles is itself not very easy.
For those choices of $V$ whose decompositions are known – for example, if $V$ is an irreducible $S_n$-module – most cases require the use of characters to obtain the multiplicities $\alpha_{\lambda, \mu}$ as given in (<ref>).

But in the specific case where $V = M_n$, the $n$-dimensional permutation module of $S_n$, we can circumvent the use of characters and calculate its associated McKay quiver $Q_{M_n}(S_n)$ directly using the following tensor identity:

Let $G$ be a finite group, and suppose that $H$ is a subgroup of $G$.
Let $X$ be a finite-dimensional $G$-module, and $Y$ a finite-dimensional $H$-module. Then

\begin{equation}
\Ind^G_H(\Res^G_H(X) \otimes Y) \cong X \otimes \Ind^G_H(Y)
\end{equation}

The map given by

\begin{equation}
g \otimes_{\mathbb{C}[H]} (x \otimes y) \mapsto gx \otimes (g \otimes_{\mathbb{C}[H]} y)
\end{equation}

for all $g \in G, x \in X$ and $y \in Y$ can be used to prove the isomorphism.
See [Halverson and Ram, 2005] for more details.

Indeed, using the Tensor Identity and the fact that

\begin{equation}
\Ind^{S_{n}}_{S_{n-1}}(\Res^{S_n}_{S_{n-1}}(S_n^{[n]}))
\cong \Ind^{S_{n}}_{S_{n-1}}(S_{n-1}^{[n-1]})
\cong S_n^{[n]} \oplus S_n^{[n-1,1]}
\cong M_n
\end{equation}

as a consequence of the branching rules (<ref>), (<ref>) for $S_n$, we see that

\begin{align}
S_n^{\lambda} \otimes M_n & \cong
S_n^{\lambda} \otimes \Ind^{S_{n}}_{S_{n-1}}(\Res^{S_n}_{S_{n-1}}(S_n^{[n]})) \\
& \cong
\Ind^{S_{n}}_{S_{n-1}}(\Res^{S_n}_{S_{n-1}}(S_n^{\lambda}) \otimes \Res^{S_n}_{S_{n-1}}(S_n^{[n]})) \\
& \cong
\Ind^{S_{n}}_{S_{n-1}}(\Res^{S_n}_{S_{n-1}}(S_n^{\lambda}) \otimes S_{n-1}^{[n-1]}) \\
& \cong
\Ind^{S_{n}}_{S_{n-1}}(\Res^{S_n}_{S_{n-1}}(S_n^{\lambda})) \label{resindmckay} \\
& \cong
\bigoplus_{\substack{x \vdash n-1: x \leftarrow \lambda \\ \mu \vdash n: x \leftarrow \mu}} \alpha_{\lambda, \mu} S_{n}^\mu \label{downupmckay}
\end{align}

that is, there are $\alpha_{\lambda, \mu}$ arrows from the node $\lambda$ to the node $\mu$ in the McKay quiver
$Q_{M_n}(S_n)$ for those partitions $\mu \vdash n$ that can be obtained from $\lambda$ by removing a box from $\lambda$ and then adding a box to its result, where,
crucially, $\alpha_{\lambda, \mu}$ here is a count of the total number of ways in which this can be done.

Said in a different way, choosing $V = M_n$ has reduced the decomposition into irreducible $S_n$-modules of the tensor product $S_n$-module $S_n^{\lambda} \otimes M_n$ to merely applying removal and addition operations to the boxes of the Young frame corresponding to the partition $\lambda \vdash n$.

Consequently, we can express $M_n^{\otimes k}$ in terms of its decomposition into irreducible $S_n$-modules by applying (<ref>).

By considering all walks of exactly $k$ steps from the node $[n]$ of $Q_{M_n}(S_n)$, we see that

\begin{equation} \label{Mnotimesk}
M_n^{\otimes k} \cong \bigoplus_{\mu \in \Lambda(S_n)} m_k^{\mu} S_n^{\mu}
\end{equation}

as an $S_n$-module, where $m_k^{\mu}$ is the number of walks of $k$ steps from $[n]$ to $\mu$ in $Q_{M_n}(S_n)$.

Figure <ref> shows an example of a McKay quiver for the group $S_6$ and its permutation representation $M_6$, and Figure <ref> gives its associated adjacency matrix.

The McKay quiver, or representation graph, for the group $S_6$ and its permutation representation $M_6$, $Q_{M_6}(S_6)$.

\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\renewcommand{\arraystretch}{1.5}
\begin{bNiceArray}{*{11}{c}}[first-row,first-col]
& \bm{(6)} 	& \bm{(5,1)}	& \bm{(4,2)}	& \bm{(4, 1^2)} & \bm{(3^2)} & \bm{(3,2,1)} & \bm{(3,1^3)} & \bm{(2^3)}
& \bm{(2^2, 1^2)} & \bm{(2,1^4)} & \bm{(1^6)} \\
\bm{(6)}		& 1	& 1	& 0	& 0	& 0	& 0	& 0	& 0	& 0	& 0	& 0	\\
\bm{(5,1)}		& 1	& 2	& 1	& 1	& 0	& 0	& 0	& 0	& 0	& 0	& 0	\\
\bm{(4,2)}		& 0	& 1	& 2	& 1	& 1	& 1	& 0	& 0	& 0	& 0	& 0	\\
\bm{(4,1^2)}		& 0	& 1	& 1	& 2	& 0	& 1	& 1	& 0	& 0	& 0	& 0	\\
\bm{(3^2)}		& 0	& 0	& 1	& 0	& 1	& 1	& 0	& 0	& 0	& 0	& 0	\\
\bm{(3,2,1)}		& 0	& 0	& 1	& 1	& 1	& 3	& 1	& 1	& 1	& 0	& 0	\\
\bm{(3,1^3)}		& 0	& 0	& 0	& 1	& 0	& 1	& 2	& 0	& 1	& 1	& 0	\\
\bm{(2^3)}		& 0	& 0	& 0	& 0	& 0	& 1	& 0	& 1	& 1	& 0	& 0	\\
\bm{(2^2, 1^2)}		& 0	& 0	& 0	& 0	& 0	& 1	& 1	& 1	& 2	& 1	& 0	\\
\bm{(2, 1^4)}		& 0	& 0	& 0	& 0	& 0	& 0	& 1	& 0	& 1	& 2	& 1	\\
\bm{(1^6)}		& 0	& 0	& 0	& 0	& 0	& 0	& 0	& 0	& 0	& 1	& 1
\end{bNiceArray}
The adjacency matrix for the McKay quiver $Q_{M_6}(S_6)$.

For each node $\mu$ in $Q_{M_n}(S_n)$, we still need to show how to find $m_k^{\mu}$, the number of walks of $k$ steps from $[n]$ to $\mu$.
There are a number of methods for doing so.

The first involves using character theory. See [Benkart, 2016] for more details.

The second uses the adjacency matrix directly: take the row of $A_{M_n}$ that is indexed by $[n]$ and post-apply $A_{M_n}$ to it $k-1$ times using matrix multiplication to obtain another row vector where the column indexed by $\mu$ gives all $k$ length walks from $[n]$ to $\mu$.

The third is motivated by the Tensor Identity for $S_n^{\lambda} \otimes M_n$, specifically (<ref>).
We can, in effect, unroll the McKay quiver to build what is known as the restriction–induction Bratteli diagram $B(S_n, S_{n-1})$.
The diagram is constructed as follows: it consists of an infinite number of rows that are indexed by the non-negative half integers, and each row contains a number of vertices.

* The vertices in row $k$, $k \in \mathbb{Z}_{\geq 0}$, are the elements of $\Lambda(S_n)$ corresponding to the irreducible $S_n$-modules that occur with multiplicity at least one in $M_n^{\otimes k}$.
Denote this subset by $\Lambda_{k}(S_{n})$.

* The vertices in row $k+\frac{1}{2}$, $k \in \mathbb{Z}_{\geq 0}$, are the elements of $\Lambda(S_{n-1})$ corresponding to the irreducible $S_{n-1}$-modules that occur with multiplicity at least one in $\Res^{S_n}_{S_{n-1}}(M_n^{\otimes k})$.
Denote this subset by $\Lambda_{k + \frac{1}{2}}(S_{n-1})$.
This subset can be found more easily from $\Lambda_{k}(S_{n})$, by applying the restriction version of the branching rule to each element in $\Lambda_{k}(S_{n})$ and forming a set from the resulting partitions of $n-1$.

For example, row $0$ consists only of the partition $[n]$ corresponding to the irreducible $S_n$-module $S_n^{[n]}$, and row $\frac{1}{2}$ consists only of the partition $[n-1]$ corresponding to the irreducible $S_{n-1}$-module $S_{n-1}^{[n-1]}$.

Edges can only be formed between vertices in adjacent rows in the following way:

* There is an edge between $\lambda \in \Lambda_k(S_n)$ and $\mu \in \Lambda_{k + \frac{1}{2}}(S_{n-1})$ if $S_{n-1}^{\mu}$ appears in the restriction version of the branching rule for $S_n^{\lambda}$ (see (<ref>)).

* Likewise, there is an edge between $\mu \in \Lambda_{k + \frac{1}{2}}(S_{n-1})$ and $\nu \in \Lambda_{k+1}(S_n)$ if $S_n^{\nu}$ appears in the induction version of the branching rule for $S_{n-1}^{\mu}$ (see (<ref>)).

Consequently, $m_k^{\mu}$, the multiplicity of $S_n^{\mu}$ in $M_n^{\otimes k}$ as an $S_n$-module, or equivalently, the number of walks of $k$ steps from $[n]$ to $\mu$ in $Q_{M_n}(S_n)$, equals the number of paths from $[n]$ on level $0$ to $\mu \in \Lambda_k(S_n)$ on level $k$.
The multiplicities for a partition $\lambda$ on a given level can be computed iteratively from the previous level by adding the multiplicities for those partitions $\mu$ that have an edge with $\lambda$.

Figure <ref> shows the restriction–induction Bratteli diagram $B(S_6, S_5)$.
The highlighted gaps and numbers that appear in the figure relate to the fact that there is a bijection between the indexing of the irreducibles of the symmetric group appearing in the restriction–induction Bratteli diagram $B(S_n, S_{n-1})$ and the irreducibles of the partition algebra as a consequence of Schur–Weyl duality.
The gaps are those irreducibles of the partition algebra that would be missing if we converted the restriction–induction Bratteli diagram $B(S_6, S_5)$ into its partition algebra form, and the highlighted numbers are the result of those irreducibles of the partition algebra not being present in their symmetric group form (since they would not be valid tableaux).
[Halverson and Ram, 2005] or [Halverson and Jacobson, 2020]
for more details.

The restriction–induction Bratteli diagram $B(S_6, S_5)$.

§ SCHUR–WEYL DUALITY AND CENTRALISER ALGEBRAS

We have shown in Section <ref> how $M_n^{\otimes k}$ decomposes as an $S_n$-module by using the McKay quiver for $M_n$, and how to calculate the multiplicities of each irreducible appearing in its decomposition.
However, we can go further in understanding the structure of $M_n^{\otimes k}$ by delving briefly into the theory of semisimple algebras.

The most important result required is the Double Centraliser Theorem
<cit.>, which says:

Let $V$ be a finite-dimensional vector space, let $A$ be a semisimple subalgebra of $\End(V)$, and let $B := \End_A(V)$.	Then

* $B$ is a semisimple algebra.

* $A = \End_B(V)$, i.e, the centraliser of the centraliser of $A$ is $A$.

* As a module of $A \otimes B$, we have that

V \cong \bigoplus_i U_i \otimes W_i

where $U_i$ are all the simple modules of $A$ and $W_i := \Hom_A(U_i, V)$ are all the simple modules of $B$.

Choosing $A = \mathbb{C}[S_n]$, the group algebra of $S_n$, which is a semisimple algebra by Maschke's Theorem, and $V = M_n^{\otimes k}$, which is a finite dimensional vector space over $\mathbb{C}$ of dimension $n^k$, we see that $B = \End_{S_n}(M_n^{\otimes k})$ is a semisimple algebra and, most importantly, since $\{S_n^{\lambda} \mid \lambda \in \Lambda(S_n)\}$ are all the simple $\mathbb{C}[S_n]$-modules, we have that, as a module of $\mathbb{C}[S_n] \otimes \End_{S_n}(M_n^{\otimes k})$,

\begin{equation} \label{Mnotimesktensor}
%M_n^{\otimes k} \cong \bigoplus_{\lambda \in \Lambda(S_n)} S_n^{\lambda} \otimes Z_k^{\lambda}(S_n)
M_n^{\otimes k} \cong \bigoplus_{\lambda \in \Lambda(S_n)} S_n^{\lambda} \otimes Z_{k,n}^{\lambda}
\end{equation}

that is, that all the simple modules

$\{Z_{k,n}^{\lambda} \mid \lambda \in \Lambda(S_n)\}$
of $\End_{S_n}(M_n^{\otimes k})$ can be indexed by the partitions of $n$, and so $S_n$ is in Schur–Weyl duality with its centraliser algebra on $M_n^{\otimes k}$, $\End_{S_n}(M_n^{\otimes k})$.

Hence we see that the multiplicity of the irreducible $S_n$-module $S_n^{\lambda}$ in $M_n^{\otimes k}$ (see (<ref>)) is really the dimension of the
the irreducible $\End_{S_n}(M_n^{\otimes k})$-module $Z_{k,n}^{\lambda}$, and so $Z_{k,n}^{\lambda}$ acts as the multiplicity space for $S_n^{\lambda}$ in the decomposition of $M_n^{\otimes k}$ into irreducibles of $S_n$.

§ UNDERSTANDING PERMUTATION EQUIVARIANT NEURAL NETWORKS THROUGH THE IRREDUCIBLES OF THE SYMMETRIC GROUP

The previous two sections have revealed much about the structure of $M_n^{\otimes k}$, ultimately as a result of $S_n$ and its centraliser algebra on $M_n^{\otimes k}$, $\End_{S_n}(M_n^{\otimes k})$, being in Schur–Weyl duality.

In this section we focus on the consequences of this result for permutation equivariant neural networks and their layer functions.

We summarise what we have shown so far for $M_n^{\otimes k}$.

The following are the same:

* The multiplicity of the irreducible $S_n$-module $S_n^{\lambda}$ in $M_n^{\otimes k}$ (see (<ref>)).

* The number of walks of $k$ steps from the node $[n]$ to the node $\lambda$ in $Q_{M_n}(S_n)$.

* The $([n], \lambda)$-entry in $A_{M_n}^k$, the $k^{\text{th}}$ power of the adjacency matrix $A_{M_n}$ for $Q_{M_n}(S_n)$.

* The number of paths from $[n]$ on level $0$ to $\lambda \in \Lambda_k(S_n)$ on level $k$ in the restriction–induction Bratteli diagram $B(S_n, S_{n-1})$.

* The dimension of the irreducible $\End_{S_n}(M_n^{\otimes k})$-module $Z_{k,n}^{\lambda}$ (see (<ref>)).

We denote this value by $m_k^{\lambda}$ in what follows.

Using Theorem <ref>, we can calculate the number of weights for different types of layer functions in a permutation equivariant neural network from the irreducibles of the symmetric group.

§.§ The Number of Weights in a $k$-order Permutation Equivariant Layer Function

Firstly, we recall from Section <ref> that the number of weights in a $k$-order permutation equivariant layer function is equal to $\dim \End_{S_n}(M_n^{\otimes k})$, by the definition of such a function.

A direct method for calculating this dimension is to use the decomposition (<ref>), the distribution of $\Hom_{S_n}$ over $\oplus$, and Schur's Lemma to get that

\begin{equation} \label{dimMnotimeskirreps}
\dim \End_{S_n}(M_n^{\otimes k})
= \sum_{\lambda \in \Lambda_k(S_n)} (m_k^{\lambda})^2
\end{equation}

However, we can also understand the equality (<ref>) by using a combinatorial approach.
From Theorem <ref> part 2., we see that $\dim \End_{S_n}(M_n^{\otimes k})$ is the sum over all $\lambda \vdash n$ of all pairs of walks of $k$ steps from the node $[n]$ to the node $\lambda$ in $Q_{M_n}(S_n)$.
By reversing the second walk in each pair, and concatenating it with the first, we see that this dimension is the sum over all $\lambda \vdash n$ of all walks of $2k$ steps in $Q_{M_n}(S_n)$ that start and end at node $[n]$

and which pass through $\lambda$ on the $k^\text{th}$ step.
Since we are summing over all nodes $\lambda$ in $Q_{M_n}(S_n)$, this means that

The number of weights in a $k$-order permutation equivariant layer function, $\dim \End_{S_n}(M_n^{\otimes k})$, is equal to the number of walks of length $2k$ that start and end at $[n]$ in $Q_{M_n}(S_n)$.

Consequently, by Theorem <ref>, we also have that $\dim \End_{S_n}(M_n^{\otimes k})$ is equal to

* The multiplicity of the irreducible $S_n$-module $S_n^{[n]}$ in $M_n^{\otimes 2k}$.

* The $([n], [n])$-entry in $A_{M_n}^{2k}$, the $2k^{\text{th}}$ power of the adjacency matrix $A_{M_n}$ for $Q_{M_n}(S_n)$.

* The number of paths from $[n]$ on level $0$ to $[n] \in \Lambda_{2k}(S_n)$ on level $2k$ in the restriction–induction Bratteli diagram $B(S_n, S_{n-1})$.

* The dimension of the irreducible $\End_{S_n}(M_n^{\otimes 2k})$-module $Z_{2k,n}^{[n]}$.

All of these results make sense when we recall from (<ref>)
that $\End_{S_n}(M_n^{\otimes k}) \cong (M_n^{\otimes 2k})^{S_n}$,
since the latter is precisely the multiplicity of the irreducible $S_n$-module $S_n^{[n]}$ in $M_n^{\otimes 2k}$!

§.§ The Number of Weights in a $k$-order to $l$-order Permutation Equivariant Layer Function

Firstly, we recall from Section <ref>

that the number of weights in a $k$-order to $l$-order permutation equivariant layer function is equal to $\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$, by the definition of such a function.

We adapt the entire argument presented in Section <ref>

to see, firstly, that

\begin{equation} \label{dimMnotimeskMnotimeslirreps}
\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})
= \sum_{\lambda \in \Lambda_{\min(k,l)}(S_n)} m_k^{\lambda}m_l^{\lambda}
\end{equation}

and so, by

summing over $\lambda \vdash n$ all pairs of walks in $Q_{M_n}(S_n)$ where the first element in each pair is a walk of $k$ steps from the node $[n]$ to the node $\lambda$, and the second is a walk of $l$ steps from the node $[n]$ to the node $\lambda$, and then by applying the argument where we reverse the second walk in each pair and concatenate it to the first walk, we see that

The number of weights in a $k$-order to $l$-order permutation equivariant layer function,
$\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$,
is equal to the number of walks of length $k+l$ that start and end at $[n]$ in $Q_{M_n}(S_n)$.

Consequently, by Theorem <ref>, we also have that
$\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$
is equal to

* The multiplicity of the irreducible $S_n$-module $S_n^{[n]}$ in $M_n^{\otimes k+l}$.

* The $([n], [n])$-entry in $A_{M_n}^{k+l}$, the $(k+l)^{\text{th}}$ power of the adjacency matrix $A_{M_n}$ for $Q_{M_n}(S_n)$.

* The number of paths from $[n]$ on level $0$ to $[n] \in \Lambda_{k+l}(S_n)$ on level $k+l$ in the restriction–induction Bratteli diagram $B(S_n, S_{n-1})$.

* The dimension of the irreducible $\End_{S_n}(M_n^{\otimes k+l})$-module $Z_{k+l,n}^{[n]}$.

Again, all of these results make sense when we recall from (<ref>) that
$\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l}) \cong (M_n^{\otimes k+l})^{S_n}$,
since the latter is precisely the multiplicity of the irreducible $S_n$-module $S_n^{[n]}$ in $M_n^{\otimes k+l}$.

§.§ The Number of Weights in a $k$-order Permutation Invariant Layer Function

As the number of weights in a $k$-order permutation invariant layer function is equal to $\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$, by the definition of such a function, we see, by considering $l = 0$ in (<ref>), that

\begin{equation} \label{dimMnotimeskMnotimes0irreps}
\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})
\end{equation}

and so, by setting $l = 0$ in Theorem <ref>, we have that

The number of weights in a $k$-order permutation invariant layer function,
$\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$,
is equal to the number of walks of length $k$ that start and end at $[n]$ in $Q_{M_n}(S_n)$.

Consequently, by Theorem <ref>, we also have that
$\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$
is equal to

* The multiplicity of the irreducible $S_n$-module $S_n^{[n]}$ in $M_n^{\otimes k}$.

* The $([n], [n])$-entry in $A_{M_n}^{k}$, the $k^{\text{th}}$ power of the adjacency matrix $A_{M_n}$ for $Q_{M_n}(S_n)$.

* The number of paths from $[n]$ on level $0$ to $[n] \in \Lambda_{k}(S_n)$ on level $k$ in the restriction–induction Bratteli diagram $B(S_n, S_{n-1})$.

* The dimension of the irreducible $\End_{S_n}(M_n^{\otimes k})$-module $Z_{k,n}^{[n]}$.

As before, this is no surprise given that, from (<ref>),
$\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0}) \cong (M_n^{\otimes k})^{S_n}$,
and the latter is precisely the multiplicity of the irreducible $S_n$-module $S_n^{[n]}$ in $M_n^{\otimes k}$.

In each case, we have shown that the structure inherent in the McKay quiver and its related restriction–induction Bratteli diagram is linked to the construction of permutation equivariant neural networks.
We could, for example, go on to show how the Schur–Weyl duality for $M_n^{\otimes 2k}$ gives us a basis of $\End_{S_n}(M_n^{\otimes k}) \subset \End(M_n^{\otimes k})$ by choosing a basis for $M_n^{\otimes 2k}$ formed from the basis of standard Young tableaux for each irreducible of $S_n$ appearing in the Schur–Weyl decomposition of $M_n^{\otimes 2k}$.

Instead, in the remainder of this paper, we take a different approach, one that shows how a series of basic combinatorial diagrams gives us the form of the weight matrices in the standard basis of $M_n$, for each of the cases presented in this section.

$k$ 		    $\Bell(2k, 2)$ 	    $\Bell(2k, 3)$ 	    $\Bell(2k, 4)$ 	    $\Bell(2k, 5)$ 	    $\Bell(2k, 6)$ 	    $\Bell(2k, 7)$ 	    $\Bell(2k, 8)$ 	    $\Bell(2k)$

$0$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$

$1$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$

$2$ 		    $8$ 		    $14$ 		    $15$ 		    $15$ 		    $15$ 		    $15$ 		    $15$ 		    $15$

$3$ 		    $32$ 		    $122$ 	    $187$ 	    $202$ 	    $203$ 	    $203$ 	    $203$ 	    $203$

$4$ 		    $128$ 	    $1094$ 	    $2795$ 	    $3845$ 	    $4111$ 	    $4139$ 	    $4140$ 	    $4140$

$5$ 		    $512$ 	    $9842$ 	    $43947$ 	    $86472$ 	    $109299$ 	    $115179$ 	    $115929$ 	    $115975$

$6$ 		    $2048$ 	    $88574$ 	    $700075$ 	    $2079475$ 	    $3403127$ 	    $4030523$ 	    $4189550$ 	    $4213597$

A table showing the restricted Bell numbers $\Bell(2k,n)$ for various $k$ and $n$, which are the number of parameters appearing in the weight matrix corresponding to a $k$-order $S_n$-equivariant layer function. The Bell numbers $\Bell(2k)$ are provided for comparison.

$k$ 		    $\Bell(k, 2)$ 	    $\Bell(k, 3)$ 	    $\Bell(k, 4)$ 	    $\Bell(k, 5)$ 	    $\Bell(k, 6)$ 	    $\Bell(k, 7)$ 	    $\Bell(k, 8)$ 	    $\Bell(k)$

$1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$ 		    $1$

$2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$ 		    $2$

$3$ 		    $4$ 		    $5$ 		    $5$ 		    $5$ 		    $5$ 		    $5$ 		    $5$ 		    $5$

$4$ 		    $8$ 		    $14$ 		    $15$ 		    $15$ 		    $15$ 		    $15$ 		    $15$ 		    $15$

$5$ 		    $16$ 		    $41$ 		    $51$ 		    $52$ 		    $52$ 		    $52$ 		    $52$ 		    $52$

$6$ 		    $32$ 		    $122$ 	    $187$ 	    $202$ 	    $203$ 	    $203$ 	    $203$ 	    $203$

$7$ 		    $64$ 		    $365$ 	    $715$ 	    $855$ 	    $876$ 	    $877$ 	    $877$ 	    $877$

$8$ 		    $128$ 	    $1094$ 	    $2795$ 	    $3845$ 	    $4111$ 	    $4139$ 	    $4140$ 	    $4140$

A table showing the restricted Bell numbers $\Bell(k,n)$ for various $k$ and $n$, which are the number of parameters appearing in the weight matrix corresponding to a $k$-order $S_n$-invariant layer function. The Bell numbers $\Bell(k)$ are provided for comparison.

§ THE PARTITION ALGEBRA AND ITS CONSEQUENCES FOR $K$-ORDER PERMUTATION EQUIVARIANT LAYER FUNCTIONS

In this section,

we construct an algebra $P_k(n)$, known as the partition algebra, which we show has a basis of combinatorial diagrams, called the orbit basis, that correspond bijectively to all possible partitions of a set of $2k$ elements.
We show that by considering certain orbit basis diagrams of $P_k(n)$, we can calculate the standard basis matrices of $\End_{S_n}(M_n^{\otimes k})$, the algebra of $k$-order permutation equivariant layer functions.

The argument presented in this section has been adapted from [Benkart and Halverson, 2019, Benkart and Halverson, 2019].

Also, the argument given in Section <ref> is an expansion of the argument first seen in [Jones, 1994].
[Jones, 1994] was also the first to find the algebra homomorphism given in Section <ref>.

§.§ The Partition Algebra, $P_k(n)$

Consider the set $\{1, \dots, 2k\}$ of $2k$ elements, which we denote in the following by $[2k]$.
We can create a set partition of $[2k]$ by partitioning it into a number of subsets.
We call the subsets of a set partition blocks.

Let $\Pi_{2k}$ be the set of all set partitions of $[2k]$.
It will also be useful to define the set $\Pi_{2k, n}$, which is the subset of $\Pi_{2k}$ consisting of all set partitions of $[2k]$ consisting of at most $n$ blocks.

As the number of set partitions in $\Pi_{2k}$ 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_{2k}$ is equal to $\Bell(2k)$, the $2k^{\text{th}}$ Bell number, and that the number of elements in $\Pi_{2k,n}$ is therefore equal to

\sum_{t=1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
= \Bell(2k,n)

the $n$-restricted $2k^{\text{th}}$ Bell number.

For example, we see that

\begin{equation} \label{setpartex1}
%\pi := \{1, 2' \mid 2, 5' \mid 3, 5, 7, 9, 3' \mid 4, 8, 6', 9' \mid 6 \mid 10, 8', 10' \mid 1' \mid 4' \mid 7'\}
\pi := \{11, 2 \mid 12, 5 \mid 13, 15, 17, 19, 3 \mid 14, 18, 6, 9 \mid 16 \mid 20, 8, 10 \mid 1 \mid 4 \mid 7\}
\end{equation}

is a set partition in $\Pi_{20}$ with $9$ blocks, hence $\pi \in \Pi_{20,n}$ for all $n \geq 9$.

For each set partition $\pi$ in $\Pi_{2k}$ we can define a diagram $d_{\pi}$ consisting of two rows of $k$ vertices and a number of edges between vertices.

There are a number of different possible choices for how to label these vertices, but we make an intentional decision to label the top row by $1, \dots, k$ and the bottom row by $k+1, \dots, 2k$.
We will see in what follows why labelling the vertices in this manner is helpful in obtaining the standard basis matrices of $\End_{S_n}(M_n^{\otimes k})$.

We draw edges between vertices in any manner such that the connected components that appear in the diagram $d_{\pi}$ correspond to the blocks of $\pi$.
As a result, $d_{\pi}$ represents the equivalence class of all diagrams with connected components equal to the blocks of $\pi$.
Figure <ref> shows the diagram $d_{\pi}$ corresponding to the partition $\pi$ given in (<ref>).

The diagram $d_{\pi}$ corresponding to the partition $\pi$ given in (<ref>).

We can concatenate diagrams $d_{\pi_1}$ and $d_{\pi_2}$, written $d_{\pi_1} \circ d_{\pi_2}$, as follows:
put $d_{\pi_1}$ on top of $d_{\pi_2}$, concatenate the edges in the middle row of vertices, and remove all connected components that lie entirely in the middle row of the joined diagrams.
Figure <ref> gives an example of the concatenation of two diagrams.

We now define the partition algebra $P_k(n)$, for any $n \in \mathbb{Z}_{\geq 1}$ and $k \in \mathbb{Z}_{\geq 0}$.
Let $P_0(n) = \mathbb{C}$. Otherwise, define $P_k(n)$ to be
the $\mathbb{C}$-linear span of the set of all diagrams corresponding to a set partition in $\Pi_{2k}$, with the algebra product defined on the basis elements as follows:

\begin{equation} \label{algebraprod}
d_{\pi_1}d_{\pi_2} = n^{c(d_{\pi_1}, d_{\pi_2})} (d_{\pi_1} \circ d_{\pi_2})
\end{equation}

where $c(d_{\pi_1}, d_{\pi_2})$ is the number of connected components that are removed from the middle row in the concatenation of $d_{\pi_1}$ and $d_{\pi_2}$.
It is clear that this product is associative, and that the algebra has an identity element corresponding to the set partition $\pi := \{1, k+1 \mid 2, k+2 \mid \dots \mid k, 2k\}$.

For example, the product in $P_{10}(n)$ of the two diagrams given in Figure <ref> is

\begin{equation}
d_{\pi_1}d_{\pi_2} = n (d_{\pi_1} \circ d_{\pi_2})
\end{equation}

since only one connected component is removed from the middle in the concatenation of the two diagrams.

The concatenation $d_{\pi_1} \circ d_{\pi_2}$ of diagrams $d_{\pi_1}$ and $d_{\pi_2}$.

It is clear by construction that the dimension of $P_k(n)$ is equal to the number of elements in $\Pi_{2k}$, which we saw was equal to $\Bell(2k)$.

§.§ The Orbit Basis of $P_k(n)$

We constructed $P_k(n)$

from the set of all diagrams corresponding to a set partition in $\Pi_{2k}$.
We call this basis set the diagram basis.

We can construct another basis of $P_k(n)$

in the following way:

First, we define a partial ordering on the set partitions in $\Pi_{2k}$ (for $k \in \mathbb{Z}_{\geq 1}$), denoted by $\preceq$, which states that for all $\pi_1$, $\pi_2 \in \Pi_{2k}$

\begin{equation}
\pi_1 \preceq \pi_2 \text{ if every block of } \pi_1 \text{ is contained in a block of } \pi_2
\end{equation}

Then we can define a set of elements in $P_k(n)$ indexed by the set partitions of $\Pi_{2k}$,

$B_O \coloneqq \{x_\pi \mid \pi \in \Pi_{2k}\}$,

with respect to the diagram basis as

\begin{equation} \label{orbitbasis}
d_\pi = \sum_{\pi \preceq \theta} x_\theta
\end{equation}

To see why the set $B_O$ forms a basis of $P_k(n)$, first,
we form an ordered set of set partitions of $\Pi_{2k}$ by ordering the set partitions by the number of blocks that they have from smallest to largest, with any arbitrary ordering allowed for a pair of set partitions that have the same number of blocks. Call this set $S_{{2k}}$.
Then, because the transition matrix between the diagram basis and the set $B_O$, whose rows and columns are indexed (in order) by the ordered set $S_{{2k}}$, is unitriangular, by (<ref>), and therefore invertible, we get that

$B_O$ forms a basis of $P_k(n)$.

We call $B_O = \{x_\pi \mid \pi \in \Pi_{2k}\}$ the orbit basis of $P_k(n)$.

We will follow the convention given in [Benkart and Halverson, 2019, Benkart and Halverson, 2019] by drawing the elements of the orbit basis with white vertices, and the elements of the diagram basis with black vertices.

For example, the orbit basis diagram in $P_6(n)$

corresponds to the set partition $\pi \coloneqq \{1, 8 \mid 2, 12 \mid 3, 7 \mid 4, 9, 11 \mid 5, 10 \mid 6 \}$ in $\Pi_{12}$ having $6$ blocks.

For more details on the orbit basis, specifically for how to express an orbit basis element as a linear combination of diagram basis elements, see [Benkart and Halverson, 2019, Benkart and Halverson, 2019].

§.§ A Basis of $\End_{S_n}(M_n^{\otimes k})$, Considered as a Subalgebra of $\End(M_n^{\otimes k})$

We now construct a basis of matrices for $\End_{S_n}(M_n^{\otimes k})$, the centraliser algebra, by viewing it as a subalgebra of $\End(M_n^{\otimes k})$

and choosing the standard basis for each copy of $M_n^{\otimes k}$ appearing in $\End(M_n^{\otimes k})$.

Recall from Section <ref> that $M_n$, the $n$-dimensional permutation representation of $S_n$, has a basis consisting of all tabloids of shape $[n-1,1]$, and that we identified

this basis with the basis labelled by $\{v_a \mid a \in [n]\}$ under the isomorphism that maps the tabloid with the number $a$ in the second row to $v_a$.

We also saw that the elements

\begin{equation} \label{tensorelement}
v_I \coloneqq v_{i_1} \otimes v_{i_2} \otimes \dots \otimes v_{i_k}
\end{equation}

over all tuples $I \coloneqq (i_1, i_2, \dots, i_k) \in [n]^k$ form a basis of $M_n^{\otimes k}$,

and that $M_n^{\otimes k}$ is a representation of $S_n$ under the action that maps a basis element of $M_n^{\otimes k}$ of the form (<ref>) to

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

which is extended linearly.
We denoted this representation by $\rho_{k}$.

We begin by recognising that,
as a result of picking the standard basis for each copy of $M_n^{\otimes k}$ appearing in $\End(M_n^{\otimes k})$,
the algebra $\End(M_n^{\otimes k})$ has a standard basis of matrix units

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

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

Hence, for any $v_L \in M_n^{\otimes k}$, where $L \in [n]^k$, we see that

\begin{equation}
E_{I,J}v_L = \delta_{J,L}v_I
\end{equation}

and so, for any $f \in \End(M_n^{\otimes k})$, expressing $f$ in the basis of matrix units as

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

we get that

\begin{equation}
f(v_L) = \sum_{I \in [n]^k} f_{I,L}v_I
\end{equation}

Consequently, given that $\End_{S_n}(M_n^{\otimes k}) \subset \End(M_n^{\otimes k})$ as algebras, we have that

\begin{align}
f \in \End_{S_n}(M_n^{\otimes k})
& \iff
f(\rho_{k}(\sigma)[v_J]) = \rho_{k}(\sigma)[f(v_J)] \text{ for all } \sigma \in S_n, v_J \in M_n^{\otimes k} \\
& \iff
\sum_{I \in [n]^k} f_{I,\sigma(J)}v_I = \sum_{I \in [n]^k} f_{I,J}v_{\sigma(I)} \label{centeq2} \\
& \iff
f_{\sigma(I),\sigma(J)} = f_{I,J} \text{ for all } \sigma \in S_n \text{ and } I, J \in [n]^{k} \label{centeq1}
\end{align}

where in (<ref>) we have equated the coefficients of $v_{\sigma(I)}$ in (<ref>).

Concatenating the pair $I, J \in [n]^{k}$ into a single element $(I, J) \in [n]^{2k}$, we see that (<ref>) tells us that the basis elements of $\End_{S_n}(M_n^{\otimes k})$ are in bijective correspondence with the orbits coming from the action of $S_n$ on $[n]^{2k}$, 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}

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

But each orbit corresponds bijectively to a set partition $\pi$ in $\Pi_{2k}$ having at most $n$ blocks!

Indeed, this bijection can be defined on a class representative $(I,J)$ of an orbit as follows:
replacing momentarily the elements of $J$ by $i_{k+l} \coloneqq j_l$ for all $l \in [k]$,
so that

\begin{equation} \label{pairedblocks}
%(I,L) = (i_1, i_2, \dots, i_k, l_1, l_2, \dots, l_k) = (i_1, i_2, \dots, i_k, i_{k+1}, i_{k+2}, \dots i_{2k})
(I,J) = (i_1, i_2, \dots, i_k, j_1, j_2, \dots, j_k) = (i_1, i_2, \dots, i_k, i_{k+1}, i_{k+2}, \dots i_{2k})
\end{equation}

for indices $x$, $y \in [2k]$, 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}

Notice that the LHS of (<ref>) is checking for an equality on the elements of $[n]$, whereas the RHS is separating the elements of $[2k]$ into blocks, hence there must be at most $n$ such blocks.

Also, the bijection given in (<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}

Hence the basis elements of $\End_{S_n}(M_n^{\otimes k})$ correspond bijectively to all set partitions $\pi$ in $\Pi_{2k}$ having at most $n$ blocks, and so

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

\begin{equation}
\dim \End_{S_n}(M_n^{\otimes k})
\sum_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
\Bell(2k, n)
\end{equation}

where $\Bell(2k,n)$ is the $n$-restricted $2k^{\text{th}}$ Bell number.

This improves upon the result that appears in [Maron et al., 2019].
We can add this result to the list of equivalent ways of calculating $\dim \End_{S_n}(M_n^{\otimes k})$ that is given in Theorem <ref>.

Furthermore, using that each orbit corresponds bijectively to a set partition $\pi$ in $\Pi_{2k,n}$,

and that each such set partition corresponds bijectively to a basis element of $\End_{S_n}(M_n^{\otimes k}) \subset \End(M_n^{\otimes k})$,
we can obtain the basis elements themselves, as follows:

Taking a set partition $\pi$ in $\Pi_{2k,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 [2k]$, and iteratively letting $B_j$, for $1 < j \leq t$, be the block that contains the smallest number in $[2k]$ 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]^{2k}$ by letting the $i^{\text{th}}$ position, $i \in [2k]$, 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}, J_{\pi} \in [n]^{k}$.

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

By obtaining all pairs $(I,J)$ appearing in this orbit, we can form a basis element of $\End_{S_n}(M_n^{\otimes k})$, denoted by $X_{\pi}$,
by summing the matrix units indexed by each pair in the orbit

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

We see that $X_\pi$ is a basis element of $\End_{S_n}(M_n^{\otimes k})$ by (<ref>).

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

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

\begin{equation}
\{X_\pi \mid \pi \in \Pi_{2k,n} \}
%\text{ such that } \pi \text{ has at most } n \text{ blocks}\}
\end{equation}

is a basis of $\End_{S_n}(M_n^{\otimes k})$.

It is clear to see that, if we define

\begin{equation}
O_k(\pi) \coloneqq \{(I,J) \in [n]^{2k} \mid i_x = i_y \iff x, y \text{ are in the same block of } \pi\}
\end{equation}

then, by the construction of $O((I_{\pi},J_{\pi}))$, we have that

\begin{equation} \label{orbitequality}
O_k(\pi) = O((I_{\pi},J_{\pi}))
\end{equation}

We will use these two sets interchangeably in what follows.

As an example of the block labelling for a set partition $\pi \in \Pi_{2k,n}$, let $k = 4$, $n = 5$, and let

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

The blocks of $\pi$ are labelled, in left-to-right order, as $B_1, B_2, B_3, B_5, B_4$.
Hence, the block labelling of $\pi$ is

\begin{equation}
(I_{\pi}, J_{\pi}) = (1, 2, 1, 2, 3, 4, 5, 4)
\end{equation}

which is an element of $[5]^{8}$.

The equation given in (<ref>)

highlights that what we have really shown is that the elements in an orbit $O_k(\pi)$ correspond to all of the possible ways of
labelling the blocks of the corresponding set partition $\pi \in \Pi_{2k,n}$, and that the block labelling we have defined for $\pi$ picks out one such labelling as the preferred method for labelling the blocks of $\pi$.

§.§ The Decomposition of $M_n^{\otimes 2k}$ into Permutation Modules

The construction given above
allows us to decompose

$M_n^{\otimes 2k}$ into permutation modules, as follows.

Using the notation of (<ref>), we see that $M_n^{\otimes 2k}$ has a basis consisting of elements of the form

\begin{equation}
v_{(I,J)} \coloneqq v_{i_1} \otimes v_{i_2} \otimes \dots \otimes v_{i_k} \otimes v_{i_{k+1}} \otimes v_{i_{k+2}} \otimes \dots \otimes v_{i_{2k}}
\end{equation}

Now, for every set partition $\pi$ in $\Pi_{2k}$ having at most $n$ blocks, define

\begin{equation} \label{Mpidefn}
M^{\pi} \coloneqq \text{span}_{\mathbb{C}}\{ v_{(I,J)} \mid (I,J) \in O_k(\pi) \}
\end{equation}

This is an $S_n$-submodule of $M_n^{\otimes 2k}$, by (<ref>) and the fact that the action of $S_n$ on $[n]^{2k}$ preserves its orbits.

We can set up an isomorphism $M^{\pi} \cong M^{[n-t, 1^t]}$, as follows:

Suppose that $\pi$ has exactly $t$ blocks, for some $t \in [n]$.
Label the blocks of $\pi$ in left-to-right order, giving an ordered subset of $\{1, \dots, t\} \subset [n]$. Denote this subset by $A_{\pi}$.
From this subset, we obtain

* The special element in $M^{\pi}$ indexed by the block labelling of $\pi$, that is, $v_{(I_\pi,J_\pi)}$, as before.

* A tabloid $\{t_\pi\}$ of shape $[n-t, 1^t]$, which is constructed by placing the elements of $A_{\pi}$ from left-to-right
into the $t$ singleton boxes from top-to-bottom, and the other elements in $[n]\backslash[t]$ into the first row in any order.

By considering the action of $S_n$ on each of

* $A_{\pi}$, the $t$-size ordered subset of $[n]$, which maps $k \in [n]$ to $\sigma(k) \in [n]$ for all $\sigma \in S_n$

* the block labelling of $\pi$, $(I_\pi,J_\pi)$, with the action defined in (<ref>), and

* the tabloid $\{t_\pi\}$, which replaces each $k$ appearing in $\{t_\pi\}$ ($k \in [n]$) with $\sigma(k) \in [n]$, for each $\sigma \in S_n$

we see that these actions are effectively one and the same, and so
the $t$-size ordered subsets of $[n]$ correspond bijectively to the basis elements of $M^{\pi}$ (by the definition given in (<ref>)), which correspond bijectively to the basis elements of $M^{[n-t, 1^t]}$, that is, all the tabloids of shape $[n-t, 1^t]$.
Hence, $M^{\pi} \cong M^{[n-t, 1^t]}$.

As the number of set partitions $\pi$ in $\Pi_{2k}$ having exactly $t$ blocks, for some $t \in [n]$, is the Stirling number
\begin{Bsmallmatrix}
\end{Bsmallmatrix}
of the second kind, we see that

\begin{equation}
M_n^{\otimes 2k}
\cong
\bigoplus_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
M^{[n-t, 1^t]}
\end{equation}

as $S_n$-modules.

By (<ref>),
we have that

\begin{equation}
\End(M_n^{\otimes k})
\cong
\bigoplus_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
M^{[n-t, 1^t]}
\end{equation}

Hence, by (<ref>),
as $\End_{S_n}(M_n^{\otimes k}) = (\End(M_n^{\otimes k}))^{S_n}$ and $(M^{[n-t, 1^t]})^{S_n} = S_n^{[n]}$
we see that

\begin{equation} \label{EndSnIrrepDecomp}
\End_{S_n}(M_n^{\otimes k})
\cong
\left(
\sum_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
\right)
\end{equation}

Consequently, by taking dimensions, we recover Theorem <ref>.

So, to obtain the basis of Theorem <ref>, what we have really done is we have chosen a basis of each $S_n^{[n]} \subset M^{\pi}$ appearing in (<ref>) in the basis of matrix units of $\End(M_n^{\otimes k})$, that is, under the bijective correspondence $v_{(I,J)} \leftrightarrow E_{I,J}$, recognising that
$S_n^{[n]}$ has a basis consisting solely of the sum of all of the basis elements of $M^{\pi}$.
This justifies, in a different way, why the set given in Theorem <ref> is actually a basis of $\End_{S_n}(M_n^{\otimes k})$.

§.§ A Surjection of Algebras $P_k(n) \rightarrow \End_{S_n}(M_n^{\otimes k})$

Given that $P_k(n)$ has a basis consisting of orbit basis diagrams indexed by the set partitions in $\Pi_{2k}$, and that $\End_{S_n}(M_n^{\otimes k})$ has a basis of matrices as given in Theorem <ref>,

for $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
we can define the map

$\Phi_{k,n} : P_k(n) \rightarrow \End_{S_n}(M_n^{\otimes k})$ on the orbit basis

of $P_k(n)$ and extend linearly, as follows:

\begin{equation} \label{partcentsurj}
\Phi_{k,n}(x_\pi) \coloneqq
\begin{cases}
X_\pi & \text{if $\pi$ has $n$ or fewer blocks} \\
0     & \text{if $\pi$ has more than $n$ blocks}
\end{cases}
\end{equation}

By Theorem <ref>, clearly this map is a surjection for all $k, n \in \mathbb{Z}_{\geq 1}$.
Also, the kernel of this map, $\Ker(\Phi_{k,n})$, is the $\mathbb{C}$-linear span of those orbit basis elements corresponding to set partitions in $\Pi_{2k}$ which have more than $n$ blocks.

Hence, if $n \geq 2k$, the map $\Phi_{k,n}$ is an isomorphism of vector spaces, since a set partition in $\Pi_{2k}$ can have at most $2k$ blocks, and so there are no set partitions with more than $n$ blocks in this case.

In fact, we can say more:

For $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$, the map
$\Phi_{k,n} : P_k(n) \rightarrow \End_{S_n}(M_n^{\otimes k})$
is an algebra homomorphism.

See [Benkart and Halverson, 2019] for more details.

Consequently, we have that

For $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$, if $n \geq 2k$, then

\begin{equation}
P_k(n) \cong \End_{S_n}(M_n^{\otimes k})
\end{equation}

is an isomorphism of algebras of dimension $\Bell(2k)$.

Also, and rather importantly,

For $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$, if $n < 2k$, then

\begin{equation}
P_k(n) \ncong \End_{S_n}(M_n^{\otimes k})
\end{equation}

as algebras, since $\Phi_{k,n}$ has a non-trivial kernel of dimension $\Bell(2k) - \Bell(2k,n)$.

What we have shown is that in order to find the weight matrix of a $k$-order permutation equivariant neural network layer function in the standard basis of $M_n$, all we need to do is to find all of the orbit basis diagrams $x_\pi$ in $P_k(n)$ corresponding bijectively to all of the set partitions $\pi$ in $\Pi_{2k}$ having at most $n$ blocks (that is, the set $\Pi_{2k, n}$), and map them under $\Phi_{k,n}$ to obtain the standard basis matrices of $\End_{S_n}(M_n^{\otimes k})$
(by calculating the block labelling of $\pi$ and its orbit under the action of $S_n$ on $[n]^{2k}$, and then applying (<ref>)).
The $\mathbb{C}$-linear span of these matrices gives the desired weight matrix!

To understand better the power of this method, we see that each row of $k$ vertices in an orbit basis diagram corresponds to a copy of $M_n^{\otimes k}$ (the top row to the $I$ tuples and the bottom row to the $J$ tuples appearing in (<ref>)), and, for those orbit basis diagrams that have at most $n$ blocks, it is the blocks themselves that describe which entries of the corresponding standard basis matrix in $\End_{S_n}(M_n^{\otimes k})$ are the same; that is, they provide the weight sharing scheme for such a layer function.

Finally, we have also shown that, to understand the basis matrices of $\End_{S_n}(M_n^{\otimes k})$, we need to appreciate that there is a relationship betweeen $n$ and $k$.

All of the papers that we have read in the machine learning literature on this topic,
except for [Finzi et al., 2021],
make the same mistake of assuming that $\dim \End_{S_n}(M_n^{\otimes k}) = \Bell(2k)$, that is, that the dimension is independent of $n$, but we have clearly shown that this is not the case!
In fact, the kernel of $\Phi_{k,n}$ can become very large relative to the dimension of $\End_{S_n}(M_n^{\otimes k})$, particularly when $k$ is large and $n$ is small, as can be seen by Theorem <ref> and Figure <ref>.

For more information on the kernel of $\Phi_{k,n}$, see [Benkart and Halverson, 2019].

§.§ An Example Where $\dim \End_{S_n}(M_n^{\otimes k}) = \Bell(2k)$

Consider the case where $k = 1$ and $n = 4$.
As $n \geq 2k$, we have that $P_1(4) \cong \End_{S_4}(M_4)$ as algebras of dimension $\Bell(2) = 2$, by Theorem <ref>.
Consequently, by the definition of $\Phi_{1,4}$, we see that the images of all of the orbit basis diagrams of $P_1(4)$ forms a basis of $\End_{S_4}(M_4)$.

Figure <ref> shows how we calculate the standard basis elements of $\End_{S_4}(M_4) \subset \End(M_4)$ from the orbit basis diagrams of $P_1(4)$.

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

Orbit Basis Diagram
$x_\pi$ 	    Partition
$\pi$ 	    Block Labelling
$(I_{\pi} \mid J_{\pi})$
Standard Basis Element of $\End_{S_4}(M_4)$

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

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

A table showing the orbit basis diagrams of $P_1(4)$ whose images under $\Phi_{1,4}$ make up a basis of $\End_{S_4}(M_4)$.

This means that any element of $\End_{S_4}(M_4)$, in the basis of matrix units of $\End(M_4)$, is of the form

\begin{equation}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\renewcommand{\arraystretch}{1.5}
\begin{bNiceArray}{*{4}{c}}[first-row,first-col]
& 1 		& 2	& 3	& 4 \\
1		& \lambda_1	& \lambda_2	& \lambda_2	& \lambda_2	\\
2		& \lambda_2	& \lambda_1	& \lambda_2	& \lambda_2	\\
3		& \lambda_2	& \lambda_2	& \lambda_1	& \lambda_2	\\
4		& \lambda_2	& \lambda_2	& \lambda_2	& \lambda_1
\end{bNiceArray}
\end{equation}

for scalars $\lambda_1, \lambda_2 \in \mathbb{C}$.

By considering the orbit basis diagrams of $P_1(4)$, we have, in fact, recovered the standard basis matrix form of a Deep Sets layer function $\mathbb{C}^4 \rightarrow \mathbb{C}^4$
(as first posed in Zaheer et al., 2017) that is equivariant to the action of $S_4$.
It is not hard to see that the standard basis matrix form of a Deep Sets layer function that is equivariant to the action of $S_n$, for any positive integer $n$, is an $n \times n$ matrix, with the diagonal entries labelled by the parameter $\lambda_1$ and the off-diagonal entries labelled by the parameter $\lambda_2$.

This example is quite small in that there are only two orbit basis diagrams to consider.
To see the power of this method, see Appendix A

for another example where $\dim \End_{S_n}(M_n^{\otimes k}) = \Bell(2k)$, specifically for $n = 4$ and $k = 2$.

§.§ An Example Where $\dim \End_{S_n}(M_n^{\otimes k}) \neq \Bell(2k)$

Consider the case where $k = 2$ and $n = 2$.
As $n \ngeq 2k$, the map $\Phi_{2,2}$ has a kernel, and so whilst $\dim P_2(2) = \Bell(4) = 15$, in fact $\dim \End_{S_2}(M_2^{\otimes 2}) = \Bell(4,2) = 8$.
Consequently, by the definition of $\Phi_{2,2}$, we see that the images of those orbit basis diagrams with $2$ blocks or less forms a basis of $\End_{S_2}(M_2^{\otimes 2})$.
The calculations are given in Appendix B.

Hence, we have that any element of $\End_{S_2}(M_2^{\otimes 2})$,
in the basis of matrix units of $\End(M_2^{\otimes 2})$,
is of the form

\begin{equation}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\renewcommand{\arraystretch}{1.5}
\begin{bNiceArray}{*{2}{c}|*{2}{c}}[first-row,first-col]
& 1,1 		& 1,2	& 2,1	& 2,2 \\
1,1		& \lambda_1	& \lambda_3	& \lambda_2	& \lambda_6	\\
1,2		& \lambda_5	& \lambda_8	& \lambda_7	& \lambda_4	\\
\hline
2,1		& \lambda_4	& \lambda_7	& \lambda_8	& \lambda_5	\\
2,2		& \lambda_6	& \lambda_2	& \lambda_3	& \lambda_1
\end{bNiceArray}
%\caption{TODO: ADD COLOURS OVER THIS MATRIX: The (flattened) tensor of weights for an $S_2$ equivariant second order layer, or, equivalently, for the space $\End_{S_2}(M_2^{\otimes 2})$.}
\end{equation}

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

§ CONSTRUCTING OTHER PERMUTATION INVARIANT AND EQUIVARIANT LAYER FUNCTIONS THROUGH RELATED PARTITION DIAGRAMS

In this section, we show that the construction behind the relationship between the partition algebra and the algebra of $k$-order permutation equivariant layer functions, $\End_{S_n}(M_n^{\otimes k})$, can be adapted to find the weight matrices for other permutation equivariant layer functions.
In particular, for each case, we construct a vector space consisting of some combinatorial diagrams whose orbit basis can be mapped onto a basis of the vector space of the permutation equivariant layer functions in question.
Since many of the details are similar to those found in the previous section, we only present the key ideas for each case.

$k$–order to $l$–order Permutation Equivariant Neural Network Layer Functions:
$\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$

For $l, k \in \mathbb{Z}_{\geq 0}$, consider the set $[l+k]$ having $l+k$ elements, and 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}$ having at most $n$ blocks.
As before, the size of $\Pi_{l+k}$ is $\Bell(l+k)$, and the size of $\Pi_{l+k, n}$ is $\Bell(l+k,n)$.

We can form a vector space from the $\mathbb{C}$-linear span of a set of diagrams indexed by the elements of $\Pi_{l+k}$,
where each diagram in the set has two rows of vertices and edges between vertices such that there are

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

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

* the edges between the vertices correspond to the connected components of the set partition that indexes the diagram.

Denote this vector space by $P_k^l(n)$. By construction, it has dimension $\Bell(l+k)$.
As before, we call the basis described here the diagram basis.

Note that the partition algebra $P_k(n)$ of Section <ref> is $P_k^k(n)$ as defined here.

We can construct another basis, called the orbit basis, in much the same way as before:
we have a partial ordering on $\Pi_{l+k}$, $\preceq$, and we define a set of elements indexed by the set partitions of $\Pi_{l+k}$,
$\{x_\pi \mid \pi \in \Pi_{l+k}\}$,
with respect to the diagram basis as

\begin{equation} \label{orbitbasislplusk}
d_\pi = \sum_{\pi \preceq \theta} x_\theta
\end{equation}

As before we can show that this set is a basis by considering the transition matrix between the diagram basis and this new set and seeing that it is invertible.
We draw orbit basis diagrams with white nodes.

For example, the orbit basis diagram in $P_5^3(n)$

corresponds to the set partition $\pi \coloneqq \{1, 5 \mid 2, 4 \mid 3, 6, 8 \mid 7 \}$ in $\Pi_{8}$ having $4$ blocks.

In order to find the weight matrices themselves, we can see, by following much the same argument, that the basis elements of $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$ are in bijective correspondence with the orbits coming from the action of $S_n$ on $[n]^{l+k}$, and that each such orbit corresponds bijectively to a set partition of $\Pi_{l+k,n}$.
By applying the block labelling procedure for each set partition $\pi$ in $\Pi_{l+k,n}$, obtaining a pair $(I_\pi, J_\pi)$ that is a representative of each orbit from the action of $S_n$ on $[n]^{l+k}$, where now $I_\pi \in [n]^l$ and $J_\pi \in [n]^k$, we get a basis of $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$ indexed by the elements of $\Pi_{l+k,n}$, namely

\begin{equation} \label{equivbasiselementlplusk}
X_\pi \coloneqq \sum_{(I,J) \in O((I_{\pi},J_{\pi}))} E_{I,J}
\end{equation}

where now $E_{I,J}$ is a matrix unit in $\Hom(M_n^{\otimes k}, M_n^{\otimes l})$.

Consequently, we get that

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}(M_n^{\otimes k}, M_n^{\otimes l})$,
and so

\begin{equation}
\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})
\sum_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
\Bell(l+k, n)
\end{equation}

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

We can adapt the arguments of Section <ref> to show further that

\begin{equation}
\Hom(M_n^{\otimes k}, M_n^{\otimes l})
\cong
M_n^{\otimes l+k}
\cong
\bigoplus_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
M^{[n-t, 1^t]}
\end{equation}

and so

\begin{equation}
\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})
\cong
\left(
\sum_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
\right)
\end{equation}

The critical idea for our purposes is that, for $l, k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
we can set up a map of vector spaces $\Phi_{k,n}^l : P_k^l(n) \rightarrow \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$ by defining it on the orbit basis of $P_k^l(n)$ and extending it linearly, as follows:

\begin{equation} \label{klsurjmap}
\Phi_{k,n}^l(x_\pi) \coloneqq
\begin{cases}
X_\pi & \text{if $\pi$ has $n$ or fewer blocks} \\
0     & \text{if $\pi$ has more than $n$ blocks}
\end{cases}
\end{equation}

By Theorem <ref>, we have that this map is a surjection for all $l, k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$.
Clearly, the kernel of this map, $\Ker(\Phi_{k,n}^l)$, is the $\mathbb{C}$-linear span of those orbit basis elements corresponding to set partitions in $\Pi_{l+k}$ that have more than $n$ blocks.

If $n \geq l+k$, this map is an isomorphism of vector spaces, since a set partition in $\Pi_{l+k}$ can have at most $l+k$ blocks, and so there are no set partitions with more than $n$ blocks in this case:

For $l, k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
if $n \geq l+k$, then

\begin{equation}
P_k^l(n) \cong \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})
\end{equation}

is an isomorphism of vector spaces of dimension $\Bell(l+k)$.

For $l, k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
if $n < l+k$, then

\begin{equation}
P_k^l(n) \ncong \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})
\end{equation}

as vector spaces, since $\Phi_{k,n}^l$ has a non-trivial kernel of dimension $\Bell(l+k) - \Bell(l+k,n)$.

in order to find the weight matrix of a $k$-order to $l$-order permutation equivariant neural network layer function in the standard basis of $M_n$, all we need to do is to find all of the orbit basis diagrams $x_\pi$ in $P_k^l(n)$ corresponding bijectively to all of the set partitions $\pi$ in $\Pi_{l+k}$ having at most $n$ blocks (that is, the set $\Pi_{l+k, n}$), and map them under $\Phi_{k,n}^l$ to obtain the standard basis matrices of $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$
(by calculating the block labelling of $\pi$ and its orbit under the action of $S_n$ on $[n]^{l+k}$, and then applying (<ref>)).
The $\mathbb{C}$-linear span of these matrices gives the desired weight matrix.

As an example, consider the case where $k = 2, l = 1, n = 2$. As $n < l + k$, we expect that $\Phi_{2,2}^1$ has a non-trivial kernel, and by Theorem <ref>, we have that the dimension of $\Hom_{S_2}(M_2^{\otimes 2}, M_2)$ is $\Bell(3,2)$ which equals $4$.

The calculations for finding

the basis matrices of $\Hom_{S_2}(M_2^{\otimes 2}, M_2)$ from the orbit basis elements corresponding to the set partitions of $\Pi_{3,2}$
are given in Appendix C.

Hence, the weight matrix is of the form

\begin{equation} \label{weightiso1}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\renewcommand{\arraystretch}{1.5}
\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{C}$.

$k$–order Permutation Invariant Neural Network Layer Functions:
$\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$

The possible weight matrices corresponding to the $k$-order permutation invariant neural network layer functions is a specific instance of the case given in Section <ref>,
where we now consider the vector space $P_k^0(n)$, that is, we set $l = 0$.
The orbit basis diagrams for this space have $0$ white nodes on the top row, and $k$ white nodes on the bottom row.

We will represent orbit basis diagrams in $P_k^0(n)$ as follows:

This example corresponds to the set partition $\pi \coloneqq \{1,2 \mid 3,4 \mid 5 \}$ in $\Pi_{5}$ having $3$ blocks.

The major results for this case are the same as those given in Theorems <ref>, <ref> and <ref> with $l=0$, noting that the form of $X_\pi$, for $\pi \in \Pi_{k,n}$, is given by

\begin{equation} \label{equivbasiselement0plusk}
X_\pi \coloneqq \sum_{J \in O(J_{\pi})} E_{1,J}
\end{equation}

where now $E_{1,J}$ is a matrix unit in $\Hom(M_n^{\otimes k}, M_n^{\otimes 0})$.

Consequently, we see that
the basis elements of $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$ are in bijective correspondence with the orbits coming from the action of $S_n$ on $[n]^{k}$, and that each such orbit corresponds bijectively to a set partition of $\Pi_{k,n}$.
By applying the block labelling procedure for each set partition $\pi$ in $\Pi_{k,n}$, obtaining the tuple $J_\pi$ that is a representative of each orbit from the action of $S_n$ on $[n]^{k}$, we get a basis of $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$ indexed by the elements of $\Pi_{k,n}$, namely

\begin{equation} \label{equivbasiselement0plusk}
X_\pi \coloneqq \sum_{J \in O(J_{\pi})} E_{1,J}
\end{equation}

where now $E_{1,J}$ is a matrix unit in $\Hom(M_n^{\otimes k}, M_n^{\otimes 0})$.

By Theorem <ref>, we get that

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

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

is a basis of $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$,
and so we see that

\begin{equation}
\dim \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})
\sum_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
\Bell(k, n)
\end{equation}

where $\Bell(k,n)$ is the $n$-restricted $k^{\text{th}}$ Bell number.

Furthermore, we have that

\begin{equation}
\Hom(M_n^{\otimes k}, M_n^{\otimes 0})
\cong
M_n^{\otimes k}
\cong
\bigoplus_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
M^{[n-t, 1^t]}
\end{equation}

and so

\begin{equation}
\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})
\cong
\left(
\sum_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
\right)
\end{equation}

By (<ref>),
for $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
the map of vector spaces $\Phi_{k,n}^0 : P_k^0(n) \rightarrow \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$,
is defined on the orbit basis of $P_k^0(n)$ and extended linearly, as follows:

\begin{equation}
\Phi_{k,n}^0(x_\pi) =
\begin{cases}
X_\pi & \text{if $\pi$ has $n$ or fewer blocks} \\
0     & \text{if $\pi$ has more than $n$ blocks}
\end{cases}
\end{equation}

By Theorem <ref>, we have that this map is a surjection for all $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$.
Clearly, the kernel of this map, $\Ker(\Phi_{k,n}^0)$, is the $\mathbb{C}$-linear span of those orbit basis elements corresponding to set partitions in $\Pi_k$ which have more than $n$ blocks.

If $n \geq k$, this map is an isomorphism of vector spaces, since a set partition in $\Pi_{k}$ can have at most $k$ blocks, and so there are no set partitions with more than $n$ blocks in this case:

For $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
if $n \geq k$, then

\begin{equation}
P_k^0(n) \cong \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})
\end{equation}

is an isomorphism of vector spaces of dimension $\Bell(k)$.

For $k \in \mathbb{Z}_{\geq 0}, n \in \mathbb{Z}_{\geq 1}$,
if $n < k$, then

\begin{equation}
P_k^0(n) \ncong \Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})
\end{equation}

as vector spaces, since $\Phi_{k,n}^0$ has a non-trivial kernel of dimension $\Bell(k) - \Bell(k,n)$.

What we have shown is that in order to find the weight matrix of a $k$-order permutation invariant neural network layer function, all we need to do is to find all of the orbit basis diagrams $x_\pi$ in $P_k^0(n)$ corresponding bijectively to all of the set partitions $\pi$ in $\Pi_{k}$ having at most $n$ blocks (that is, the set $\Pi_{k, n}$) and map them under $\Phi_{k,n}^0$ (by calculating the block labelling of $\pi$ and its orbit under the action of $S_n$ on $[n]^{k}$, and then applying equation (<ref>)) to obtain the standard basis matrices of $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes 0})$.
The $\mathbb{C}$-linear span of these matrices gives the desired weight matrix.

As an example, consider the case where $k = 3$ and $n = 2$. As $n < k$, we expect that $\Phi_{3,2}^0$ has a non-trivial kernel, and by Theorem

we see that the dimension of $\Hom_{S_2}(M_2^{\otimes 3}, M_2^{\otimes 0})$ is $\Bell(3,2)$ which equals $4$.

The calculations for finding

the basis matrices of $\Hom_{S_2}(M_2^{\otimes 3}, M_2^{\otimes 0})$ from the orbit basis elements corresponding to the set partitions of $\Pi_{3,2}$

are given in Appendix C.

Hence, the weight matrix is of the form

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

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

It is no surprise that there is an isomorphism between the weight matrices for the previous two examples, (<ref>) and (<ref>), since there is an isomorphism of vector spaces $P_2^1(2)$ and $P_3^0(2)$ coming from the fact that they are formed from the same set of set partitions $\Pi_3$, which, combined with the surjections $\Phi_{2,2}^1$ and $\Phi_{3,2}^0$,
leads to an isomorphism between $\Hom_{S_2}(M_2^{\otimes 2}, M_2^{\otimes 1})$ and $\Hom_{S_2}(M_2^{\otimes 3}, M_2^{\otimes 0})$.

We can see this more generally: for any $l, k \in \mathbb{Z}_{\geq 1}$ and any $n \in \mathbb{Z}_{\geq 1}$, there is an isomorphism between $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$ and $\Hom_{S_n}(M_n^{\otimes p}, M_n^{\otimes q})$ for any $p, q \in \mathbb{Z}_{\geq 0}$ such that $q + p = l + k$, which comes from the fact that there is an isomorphism between $P_k^l(n)$ and $P_p^q(n)$, since both are formed from the same set of set partitions $\Pi_{l+k}$, combined with the surjections $\Phi_{k,n}^l$ and $\Phi_{p,n}^q$.

There is a rather insightful way of seeing this diagrammatically: we can take any orbit basis diagram in $P_k^l(n)$ and unfold it into a diagram that has $0$ rows on the top, and $l+k$ rows on the bottom, that is, an orbit basis diagram in $P_{l+k}^0(n)$.
By taking the first $q$ nodes from the left of this diagram and folding them back up, we obtain an orbit basis diagram in $P_p^q(n)$.
We can reverse the procedure, leading to the desired isomorphism.

The following shows an example of this procedure for orbit basis diagrams in $P_5^3(2)$ and $P_6^2(2)$.

This means that we could understand all of the spaces $\Hom_{S_n}(M_n^{\otimes p}, M_n^{\otimes q})$ for any $p, q \in \mathbb{Z}_{\geq 0}$ such that $q + p = l + k$ through the one unfolded diagram with $q+p$ nodes on the bottom, perhaps using a line after the $q^\text{th}$ node to represent where the diagram folds, but we prefer our separate diagrams for each $q, p$ (with $q$ nodes on the top and $p$ nodes on the bottom) because the topology of these diagrams respects the form of the matrices in question.

This also means that the non-linear functions that appear in a permutation equivariant neural network where the layers are some tensor power of the permutation representation of $S_n$ are crucial because, without their existence,
a permutation equivariant neural network made up solely of linear layers of this form

would be equivalent to
a permutation equivariant neural network with
just one single linear layer, which wouldn't be much good for learning.

§.§ Adding Features and Biases

This was first considered by [Maron et al., 2019]; here we improve upon their result and provide a clearer sense of what the form of the standard basis matrices are for the spaces under consideration.

§.§.§ Features

In Remark <ref>, we made the assumption that the feature dimension for all of the layers appearing in the neural network was one.
This simplified the analysis for the results seen in Sections <ref> and <ref>.
All of these results can be adapted for the case where the feature dimension of the layers is greater than $1$.

It is enough to note that, if a $k$-order tensor has a feature space of dimension $d$, that is, the space under consideration is $\mathbb{C}^{n^k \times d}$, then it is isomorphic to
$M_n^{\otimes k} \otimes \mathbb{C}^d$
by the isomorphism given in (<ref>).

Consequently, we can adapt Theorem <ref> to get that

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

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

is a basis of
$\Hom_{S_n}(M_n^{\otimes k} \otimes \mathbb{C}^{d_k}, M_n^{\otimes l} \otimes \mathbb{C}^{d_l})$,
where now

\begin{equation} \label{equivbasiselementlpluskfeatures}
X_{\pi,i,j} \coloneqq \sum_{(I,J) \in O((I_{\pi},J_{\pi}))} E_{I,i,J,j}
\end{equation}

Here, $E_{I,i,J,j}$ is a matrix unit in
$\Hom(M_n^{\otimes k} \otimes \mathbb{C}^{d_k}, M_n^{\otimes l} \otimes \mathbb{C}^{d_l})$, for all tuples
$I \in [n]^l$ and $J \in [n]^k$,
and for all $i \in [d_l], j \in [d_k]$.

Hence, we have that

\begin{equation}
\dim \Hom_{S_n}(M_n^{\otimes k} \otimes \mathbb{C}^{d_k}, M_n^{\otimes l} \otimes \mathbb{C}^{d_l})
d_k d_l
\sum_{t = 1}^{n}
\begin{Bmatrix}
\end{Bmatrix}
d_k d_l
\Bell(l+k, n)
\end{equation}

§.§.§ Biases

Including bias terms in the layer functions of a permutation equivariant neural network is harder, but it can be done.
We want to include such a term but still keep the entire layer function permutation equivariant.
We can do this by adapting Definition <ref> by redefining each layer function

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

to be a composition

\begin{equation} \label{layerbiasesdefn}
f_l \coloneqq \sigma_l \circ (\phi_l + \beta_l)
\end{equation}

where $\phi_l$ and $\sigma_l$ are as before, but now $\beta_l : (V_{l-1}, \rho_{l-1}) \rightarrow (V_{l}, \rho_{l})$ is a permutation equivariant function that is constant on all elements of $V_{l-1}$, that is,

\begin{equation}
\beta_l(v) = c \text{ for all } v \in V_{l-1}
\end{equation}

for some constant element $c \in V_l$.

Since the addition of two permutation equivariant functions $(V_{l-1}, \phi_{l-1}) \rightarrow (V_{l}, \phi_{l})$ is still permutation equivariant, this means that the entire neural network composed of these new layer functions (<ref>) is still permutation equivariant.

Considering now the learnable, linear layers, $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$, we see that the permutation equivariance of the bias function,
$\beta : (M_n^{\otimes k}, \rho_k) \rightarrow (M_n^{\otimes l}, \rho_l)$,
needs to satisfy

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

for all $g \in S_n$ and $c \in M_n^{\otimes l}$.

Since any $c \in M_n^{\otimes l}$ satisfying (<ref>) can be viewed as an element of $\Hom_{S_n}(M_n^{\otimes 0}, M_n^{\otimes l})$, to find the matrix form of $c$, all we need to do is find the basis elements of $\Hom_{S_n}(M_n^{\otimes 0}, M_n^{\otimes l})$.

But we saw how to do this in Section <ref>, where we now set $k = 0$, and consider the vector space $P_0^l(n)$.
We will represent orbit basis diagrams in $P_0^l(n)$ as follows:

This example corresponds to the set partition $\pi \coloneqq \{1 \mid 2, 3 \mid 4, 5 \}$ in $\Pi_{5}$ having $3$ blocks.

We give an example of how to find the bias vector for the case $n = 4$ and $k = 2$ in Appendix A.

§ A GENERALISATION TO LAYER FUNCTIONS THAT ARE EQUIVARIANT TO A PRODUCT OF SYMMETRIC GROUPS

We can generalise the results presented in Section <ref> to construct neural networks that are equivariant to a product of symmetric groups $S_{n_1} \times \dots \times S_{n_m}$.
The layers in this case are the (external) tensor product of some $k_r$-order tensor power of the permutation representation $M_{n_r}$ of dimension $n_r$ of the symmetric group $S_{n_r}$, for each $r \in [m]$.
These permutation equivariant neural networks model local symmetries in data, since we can think of there being a total of $n_1 + \dots + n_m$ objects, but the network is constructed such that only the symmetries in each group of $n_r$ objects is respected.

Given groups $G$ and $H$, and representations $\rho_V : G \rightarrow GL(V)$ and $\rho_W : H \rightarrow GL(W)$, we can define the external tensor product representation of the direct product group $G \times H$, namely

\begin{equation}
\rho_{V \boxtimes W} : G \times H \rightarrow GL(V \boxtimes W)
\end{equation}

as follows: as a vector space, $V \boxtimes W = V \otimes W$, and

\begin{equation}
\rho_{V \boxtimes W}(g,h) = \rho_V(g) \otimes \rho_W(h) \text{ for all } g \in G \text{ and } h \in H.
\end{equation}

This definition can be extended in the obvious way to a direct product of any number of groups with their accompanying representations.

It can be shown that a map $f : V_1 \boxtimes W_1 \rightarrow V_2 \boxtimes W_2$ is $G \times H$-equivariant if and only if it is the tensor product $f_1 \otimes f_2$ of a $G$-equivariant map $f_1 : V_1 \rightarrow W_1$ and an $H$-equivariant map $f_2 : V_2 \rightarrow W_2$, and so, for linear maps, we have that

\begin{equation} \label{externalequiv}
\Hom_{G \times H}(V_1 \boxtimes W_1, V_2 \boxtimes W_2)
\cong
\Hom_{G}(V_1, V_2) \otimes \Hom_{H}(W_1, W_2)
\end{equation}

As a result, we can generalise the construction presented in Section <ref>
to find a basis of

\begin{equation} \label{genericHomspace}
\Hom_{S_{n_1} \times \dots \times S_{n_m}}(M_{n_1}^{\otimes {k_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {k_m}},
M_{n_1}^{\otimes {l_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {l_m}})
\end{equation}

We start by forming the tensor product vector space $P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)$, which has an orbit basis
consisting of $m$-length tuples of orbit basis elements from each of the individual vector spaces $P_{k_r}^{l_r}(n_r)$ in the direct product.

We represent such tuples by placing the orbit basis diagrams from each of the individual vector spaces side-by-side, putting a red demarcation line between each adjacent pair: for example, the diagram

\begin{equation} \label{orbitexternalprodexample}
\scalebox{0.6}{\tikzfig{orbitexternalprodex}}
\end{equation}

is an orbit basis element in $P_{2}^{1}(n_1) \otimes P_{1}^{1}(n_2) \otimes P_{2}^{2}(n_3) \otimes P_{3}^{0}(n_4)$, for any $n_1, n_2, n_3, n_4 \in \mathbb{Z}_{\geq 1}$.

Then the standard matrix basis of the $\Hom$-space given in (<ref>) is simply the images of those orbit basis elements of

\begin{equation}
P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)
\end{equation}

whose $m$-length tuples, for each index $r \in [m]$, consist of only those orbit basis elements of $P_{k_r}^{l_r}(n_r)$ that correspond to a set partition in $\Pi_{l_r + k_r}$ having at most $n_r$ blocks,
under the map

\begin{equation} \label{externalprodmap}
\Phi_{(k_1, \dots, k_m),(n_1, \dots, n_m)}^{(l_1, \dots, l_m)}
\coloneqq
\Phi_{k_1,n_1}^{l_1} \otimes \dots \otimes \Phi_{k_m,n_m}^{l_m}
\end{equation}

that maps $P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)$ onto the $\Hom$-space given in (<ref>).

The map (<ref>) is well defined because the $\Hom$-space given in (<ref>) is isomorphic to

\begin{equation} \label{tensorgenericHomspace}
\bigotimes_{r=1}^{m} \Hom_{S_{n_r}}(M_{n_r}^{\otimes k_r}, M_{n_r}^{\otimes l_r})
\end{equation}

by a repeated application of (<ref>).

It is clear that the standard matrix basis of the $\Hom$-space given in (<ref>) will be the tensor (Kronecker) product of the standard matrix basis elements of the individual $\Hom$-spaces given in (<ref>), and so the dimension of this space is

\begin{equation} \label{dimensionsubspace}
%\dim \Hom_{S_{n_1} \times \dots \times S_{n_m}}(M_{n_1}^{\otimes {k_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {k_m}},
%M_{n_1}^{\otimes {l_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {l_m}})
\prod_{r = 1}^{m} \Bell(l_r + k_r, n_r)
\end{equation}

Clearly, by setting $l_r = 0$ for all $r \in [m]$ in (<ref>), the $S_{n_1} \times \dots \times S_{n_m}$-invariant maps have dimension $\prod_{r = 1}^{m} \Bell(k_r, n_r)$.

In other words, what we have shown is that to find the basis of the $\Hom$-space given in (<ref>), all we need to do is to consider all possible side-by-side combinations of the appropriate orbit basis diagrams for each of the individual vector spaces $P_{k_r}^{l_r}(n_r)$ (those in bijective correspondence with $\Pi_{l_r + k_r, n_r}$), and calculate, for each such combination, each constituent's image under its respective map $\Phi_{k_r, n_r}^{l_r}$, and then finally calculate the tensor (Kronecker) product of the resulting matrices.
This makes for quite a powerful diagrammatic method for finding such a basis.

It can also be shown
that the $\Hom$-space given in (<ref>) is really a subspace of

\begin{equation} \label{genericLargerHomspace}
\Hom_{S_{n_1 + \dots + n_m}}(M_{n_1 + \dots + n_m}^{\otimes ({k_1 + \dots + k_m})},
M_{n_1 + \dots + n_m}^{\otimes ({l_1 + \dots + l_m})})
\end{equation}

This can (loosely) be seen from the orbit basis diagrams of
$P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)$

by noting that if we removed all of the red demarcation lines in such a diagram, we would get an element of
$P_{k_1 + \dots + k_m}^{l_1 + \dots + k_m}(n_1 + \dots + n_m)$,
that is, that

$P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)$
is actually a subspace of
$P_{k_1 + \dots + k_m}^{l_1 + \dots + k_m}(n_1 + \dots + n_m)$.

For example, for the orbit basis diagram given in (<ref>), by removing the demarcation lines, we obtain

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

an orbit basis diagram in $P_{8}^{4}(n_1 + n_2 + n_3 + n_4)$.

We would then have to show that the surjection
$\Phi_{(k_1 + \dots + k_m),(n_1 + \dots + n_m)}^{(l_1 + \dots + l_m)}$
respects the surjection of the subspace
$P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)$
onto the $\Hom$-space given in (<ref>), that is, that the restriction of
$\Phi_{(k_1 + \dots + k_m),(n_1 + \dots + n_m)}^{(l_1 + \dots + l_m)}$
$P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)$
is the map
$\Phi_{(k_1, \dots, k_m),(n_1, \dots, n_m)}^{(l_1, \dots, l_m)}$
defined in

We could start instead with the orbit basis diagrams in
$P_{k_1 + \dots + k_m}^{l_1 + \dots + k_m}(n_1 + \dots + n_m)$,
put in the red demarcation lines, and only consider those orbit basis diagrams where the edges do not cross the red demarcation lines.
The span of these diagrams would be the subspace
$P_{k_1}^{l_1}(n_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m)$.

We note also that the dimension of the subspace given in (<ref>) is less than (and can be significantly less than) the dimension of the $\Hom$-space given in (<ref>).

We could also extend (<ref>) by adding a dimension of features for each of the layers; in this case, the $\Hom$-space under consideration becomes

\begin{equation}
\Hom_{S_{n_1} \times \dots \times S_{n_m}}(M_{n_1}^{\otimes {k_1}} \boxtimes M_{d_{k_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {k_m}} \boxtimes M_{d_{k_m}},
M_{n_1}^{\otimes {l_1}} \boxtimes M_{d_{l_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {l_m}} \boxtimes M_{d_{l_m}})
\end{equation}

and so, using the result of Theorem <ref> together with (<ref>), we see that the overall dimension of this $\Hom$-space is
$\prod_{r = 1}^{m} d_{k_r}d_{l_r}\Bell(l_r + k_r, n_r)$.

§.§ An Example Recovering the Result of

[Hartford et al., 2018]

One immediate consequence of our work is that we can recover the result of [Hartford et al., 2018] through our method and give an explanation that is grounded in the language of the partition algebras as to why their result holds.

In effect, Hartford et al. obtain a standard matrix basis of the $\Hom$-space given in (<ref>) for the case where $l_r = k_r = 1$ and $n_r \geq 2$ for all $r \in [m]$, that is, for

\begin{equation} \label{Hartford}
\End_{S_{n_1} \times \dots \times S_{n_m}}(M_{n_1} \boxtimes \dots \boxtimes M_{n_m})
\end{equation}

Appendix D

shows how to calculate their result for the example $\End_{S_2 \times S_2 \times S_2}(M_2 \boxtimes M_2 \boxtimes M_2)$ using our method, and the resulting matrix is

\begin{equation}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{2}{c}|*{2}{c}|*{2}{c}|*{2}{c}}[first-row,first-col]
%			& \Block{1-4}{1,1,*} & & & & \Block{1-4}{1,2,*} & & & & \Block{1-4}{2,1,*} & & & & \Block{1-4}{2,2,*} & & & \\
%			& 1 	& 2	& 3 	& 4 	& 1 	& 2	& 3 	& 4 	& 1 	& 2	& 3 	& 4	& 1 	& 2	& 3 	& 4 \\
\RowStyle[cell-space-limits=3pt]{\rotate}
& 1,1,1 	& 1,1,2		& 1,2,1 	& 1,2,2		& 2,1,1 	& 2,1,2		& 2,2,1 	& 2,2,2	 \\
1,1,1		& \lambda_1 	& \lambda_2 	& \lambda_3 	& \lambda_4	& \lambda_5	& \lambda_6	& \lambda_7	& \lambda_8	\\
1,1,2		& \lambda_2 	& \lambda_1 	& \lambda_4 	& \lambda_3 	& \lambda_6	& \lambda_5	& \lambda_8	& \lambda_7	\\
\hline
1,2,1		& \lambda_3 	& \lambda_4 	& \lambda_1  	& \lambda_2 	& \lambda_7	& \lambda_8	& \lambda_5	& \lambda_6 	\\
1,2,2		& \lambda_4 	& \lambda_3 	& \lambda_2 	& \lambda_1 	& \lambda_8	& \lambda_7	& \lambda_6	& \lambda_5	\\
\hline
2,1,1		& \lambda_5 	& \lambda_6 	& \lambda_7 	& \lambda_8 	& \lambda_1	& \lambda_2 	& \lambda_3	& \lambda_4	\\
2,1,2		& \lambda_6 	& \lambda_5 	& \lambda_8 	& \lambda_7 	& \lambda_2 	& \lambda_1	& \lambda_4	& \lambda_3	\\
\hline
2,2,1		& \lambda_7 	& \lambda_8 	& \lambda_5 	& \lambda_6 	& \lambda_3	& \lambda_4	& \lambda_1 	& \lambda_2 	\\
2,2,2		& \lambda_8 	& \lambda_7 	& \lambda_6 	& \lambda_5 	& \lambda_4	& \lambda_3	& \lambda_2 	& \lambda_1
\end{bNiceArray}
\end{equation}

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

It is clear to see from Appendix D

that a proper explanation of their result (in this case) is that the standard matrix basis for $\End_{S_2 \times S_2 \times S_2}(M_2 \boxtimes M_2 \boxtimes M_2)$ is actually obtained by mapping the orbit basis of the direct product of partition algebras $P_1(2) \otimes P_1(2) \otimes P_1(2)$ onto this space via the map $\Phi_{(1,1,1),(2,2,2)}^{(1,1,1)}$ as defined in (<ref>).

It is also clear to see that had they removed the red demarcation lines, and considered the standard matrix basis of $\End_{S_6}(M_6^{\otimes 3})$ instead – that is, allowing for the learning of global symmetries rather than local ones – then they would have obtained a $216 \times 216$ weight matrix with $\Bell(6) = 203$ parameters instead, that is, a much larger matrix with many more parameters.
One is not necessarily better than the other, it just depends on the problem at hand.

§.§ An Example where the Dimension is not Equal to

$\prod_{r = 1}^{m} \Bell(l_r + k_r)$

Consider the example $\Hom_{S_2 \times S_4}(M_2^{\otimes 2} \boxtimes M_4, M_2 \boxtimes M_4)$.
Appendix E

the subset of orbit basis elements of $P_2^1(2) \otimes P_1^1(4)$ whose images under
$\Phi_{(2, 1),(2, 4)}^{(1, 1)}$

make up a basis of this $\Hom$-space.
It is clear that the dimension of this space is $\Bell(3,2)\Bell(2,4) = 8$, which does not equal $\Bell(3)\Bell(2) = 10$.
The resulting $8 \times 16$ weight matrix that we obtain is

\begin{equation}
\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{4}{c}|*{4}{c}|*{4}{c}|*{4}{c}}[first-row,first-col]
%			& \Block{1-4}{1,1,*} & & & & \Block{1-4}{1,2,*} & & & & \Block{1-4}{2,1,*} & & & & \Block{1-4}{2,2,*} & & & \\
%			& 1 	& 2	& 3 	& 4 	& 1 	& 2	& 3 	& 4 	& 1 	& 2	& 3 	& 4	& 1 	& 2	& 3 	& 4 \\
\RowStyle[cell-space-limits=3pt]{\rotate}
& 1,1,1 	& 1,1,2	& 1,1,3 	& 1,1,4 	& 1,2,1 	& 1,2,2	& 1,2,3 	& 1,2,4 	& 2,1,1 	& 2,1,2	& 2,1,3 	& 2,1,4	& 2,2,1 	& 2,2,2	& 2,2,3 	& 2,2,4 \\
1,1		& \lambda_1 	& \lambda_2 	& \lambda_2	& \lambda_2	& \lambda_3 	& \lambda_4 	& \lambda_4 	& \lambda_4 	& \lambda_5 	& \lambda_6 	& \lambda_6 	& \lambda_6 	& \lambda_7 	& \lambda_8 	& \lambda_8 	& \lambda_8   \\
1,2		& \lambda_2 	& \lambda_1  	& \lambda_2	& \lambda_2	& \lambda_4 	& \lambda_3 	& \lambda_4 	& \lambda_4 	& \lambda_6 	& \lambda_5 	& \lambda_6 	& \lambda_6 	& \lambda_8 	& \lambda_7 	& \lambda_8	& \lambda_8   \\
1,3		& \lambda_2 	& \lambda_2 	& \lambda_1  	& \lambda_2	& \lambda_4 	& \lambda_4 	& \lambda_3 	& \lambda_4 	& \lambda_6 	& \lambda_6 	& \lambda_5 	& \lambda_6 	& \lambda_8 	& \lambda_8	& \lambda_7 	& \lambda_8   \\
1,4		& \lambda_2 	& \lambda_2 	& \lambda_2	& \lambda_1  	& \lambda_4 	& \lambda_4	& \lambda_4	& \lambda_3	& \lambda_6	& \lambda_6	& \lambda_6	& \lambda_5	& \lambda_8	& \lambda_8	& \lambda_8	& \lambda_7  \\
\hline
2,1		& \lambda_7 	& \lambda_8	& \lambda_8	& \lambda_8	& \lambda_5	& \lambda_6	& \lambda_6	& \lambda_6	& \lambda_3	& \lambda_4	& \lambda_4	& \lambda_4	& \lambda_1 	& \lambda_2 	& \lambda_2 	& \lambda_2   \\
2,2		& \lambda_8 	& \lambda_7 	& \lambda_8	& \lambda_8	& \lambda_6	& \lambda_5	& \lambda_6	& \lambda_6	& \lambda_4	& \lambda_3	& \lambda_4	& \lambda_4	& \lambda_2	& \lambda_1 	& \lambda_2	& \lambda_2  \\
2,3		& \lambda_8 	& \lambda_8 	& \lambda_7 	& \lambda_8	& \lambda_6	& \lambda_6	& \lambda_5	& \lambda_6	& \lambda_4	& \lambda_4	& \lambda_3	& \lambda_4	& \lambda_2	& \lambda_2	& \lambda_1 	& \lambda_2  \\
2,4		& \lambda_8 	& \lambda_8 	& \lambda_8	& \lambda_7 	& \lambda_6	& \lambda_6	& \lambda_6	& \lambda_5	& \lambda_4	& \lambda_4	& \lambda_4	& \lambda_3	& \lambda_2	& \lambda_2	& \lambda_2	& \lambda_1
\end{bNiceArray}
\end{equation}

§.§ Learning Layer Functions that are also Equivariant to the Symmetries of Features

Our method also allows for the learning of layer functions on tensors that have feature spaces greater than one, where we now wish the layer functions to be equivariant also to permutations of the features themselves, that is, we want to find a standard matrix basis of

\begin{equation} \label{layerfeaturesymm}
\Hom_{S_{n_1} \times S_{d_1} \times \dots \times S_{n_m} \times S_{d_m}}
\end{equation}

\begin{equation}
M_{n_1}^{\otimes {k_1}} \boxtimes M_{d_1} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {k_m}} \boxtimes M_{d_m}
\end{equation}

\begin{equation}
M_{n_1}^{\otimes {l_1}} \boxtimes M_{d_1} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {l_m}} \boxtimes M_{d_m}
\end{equation}

Indeed, we can apply the methods of this section to find this basis.

It is clear that (<ref>) is a specific application of the $\Hom$-space given in (<ref>), where we consider all $2m$-length tuples of orbit basis elements of

\begin{equation}
P_{k_1}^{l_1}(n_1) \otimes P_{1}(d_1) \otimes \dots \otimes P_{k_m}^{l_m}(n_m) \otimes P_{1}(d_m)
\end{equation}

such that

* if the vector space under consideration is $P_{k_r}^{l_r}(n_r)$ for some $r \in [m]$, then we only consider those orbit basis elements that correspond to a set partition in $\Pi_{l_r + k_r}$ having at most $n_r$ blocks, and

* if the vector space under consideration is $P_{1}(d_r)$ for some $r \in [m]$, then we only consider those orbit basis elements that correspond to a set partition in $\Pi_{2}$ having at most $d_r$ blocks.

Consequently, it is clear that the dimension of the $\Hom$-space given in (<ref>) is

\begin{equation}
\prod_{r = 1}^{m} \Bell(l_r + k_r, n_r)\Bell(2, d_r)
\end{equation}

and the standard matrix basis

can be found by calculating all possible tensor (Kronecker) products of the standard matrix basis elements of the spaces
$\Hom_{S_{n_r}}(M_{n_r}^{\otimes k_r}, M_{n_r}^{\otimes l_r}) \otimes \End_{S_{d_r}}(M_{d_r})$,
as the $\Hom$-space (<ref>) is isomorphic to

\begin{equation}
\bigotimes_{r=1}^{m} \left[\Hom_{S_{n_r}}(M_{n_r}^{\otimes k_r}, M_{n_r}^{\otimes l_r}) \otimes \End_{S_{d_r}}(M_{d_r})\right]
\end{equation}

Note that setting $d_r = 1$ for all $r \in [m]$, that is, all of the feature spaces have dimension $1$,

recovers the $\Hom$-space given in (<ref>) precisely.

We could also consider layer functions that are permutation equivariant across the entire space, that is

\begin{equation} \label{layeracrosstensorsandfeaturesymm}
\Hom_{S_{n_1 + d_1 + \dots + n_m + d_m}}(
M_{n_1 + d_1 + \dots + n_m + d_m}^{\otimes ({k_1 + \dots + k_m + m})},
M_{n_1 + d_1 + \dots + n_m + d_m}^{\otimes ({l_1 + \dots + l_m + m})})
\end{equation}

This has dimension

$\Bell(2m + \sum_{r = 1}^{m} (l_r + k_r), \sum_{r = 1}^{m} (n_r + d_r))$,
which is a much larger space than the $\Hom$-space given in (<ref>).
A basis of this space can be found by applying Theorem <ref> to the orbit basis elements of $P_{k_1 + \dots + k_m + m}^{l_1 + \dots + l_m + m}(\sum_{r = 1}^{m} (n_r + d_r))$.

It is not hard to see that we could extend (<ref>) to consider layer functions on tensors that have feature spaces that are themselves tensors, where we wish the layer functions to be equivariant to permutations of the features themselves. The $\Hom$-space under consideration is

\begin{equation} \label{layertensorfeaturesymm}
\Hom_{S_{n_1} \times S_{d_1} \times \dots \times S_{n_m} \times S_{d_m}}
(V, W)
\end{equation}

\begin{equation}
V =
M_{n_1}^{\otimes {k_1}} \boxtimes M_{d_1}^{\otimes {p_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {k_m}} \boxtimes M_{d_m}^{\otimes {p_m}}
\end{equation}

\begin{equation}
W =
M_{n_1}^{\otimes {l_1}} \boxtimes M_{d_1}^{\otimes {q_1}} \boxtimes \dots \boxtimes M_{n_m}^{\otimes {l_m}} \boxtimes M_{d_m}^{\otimes {q_m}}
\end{equation}

It is clear that the dimension of the $\Hom$-space (<ref>) is

\begin{equation}
\prod_{r = 1}^{m} \Bell(l_r + k_r, n_r)\Bell(q_r + p_r, d_r)
\end{equation}

and the standard matrix basis

can be found by calculating all possible tensor (Kronecker) products of the standard matrix basis elements of the spaces
$\Hom_{S_{n_r}}(M_{n_r}^{\otimes k_r}, M_{n_r}^{\otimes l_r}) \otimes \Hom_{S_{d_r}}(M_{d_r}^{\otimes p_r}, M_{d_r}^{\otimes q_r})$,
as the $\Hom$-space (<ref>) is isomorphic to

\begin{equation}
\bigotimes_{r=1}^{m} \left[\Hom_{S_{n_r}}(M_{n_r}^{\otimes k_r}, M_{n_r}^{\otimes l_r}) \otimes
\Hom_{S_{d_r}}(M_{d_r}^{\otimes p_r}, M_{d_r}^{\otimes q_r})\right]
\end{equation}

As before, we can generalise (<ref>) to this case, by considering layer functions that are permutation equivariant across the entire space, that is

\begin{equation} \label{layeracrosstensorsandfeaturesymm2}
\Hom_{S_{n_1 + d_1 + \dots + n_m + d_m}}(
M_{n_1 + d_1 + \dots + n_m + d_m}^{\otimes ({k_1 + p_1 + \dots + k_m + p_m})},
M_{n_1 + d_1 + \dots + n_m + d_m}^{\otimes ({l_1 + q_1 + \dots + l_m + q_m})})
\end{equation}

This has dimension

$\Bell(\sum_{r = 1}^{m} (l_r + q_r + k_r + p_r), \sum_{r = 1}^{m} (n_r + d_r))$,
which is a much larger space than the $\Hom$-space given in (<ref>).
A basis of this space can be found by applying Theorem <ref> to the orbit basis elements of $P_{k_1 + p_1 + \dots + k_m + p_m}^{l_1 + q_1 + \dots + l_m + q_m}(\sum_{r = 1}^{m} (n_r + d_r))$.

§ RELATED WORK

The combinatorial representation theory of the partition algebras has been developed over time by
pure mathematicians

since it was first introduced in a series of papers by [Martin, 1990, Martin, 1994, Martin, 1996].

[Jones, 1994] was the first to construct the surjective algebra homomorphism seen in Section <ref> between the partition algebra $P_k(n)$ and the tensor power centraliser algebra $\End_{S_n}(M_n^{\otimes k})$.
The development of much of the theory, however, has been led

by Benkart and Halverson.

[Benkart and Moon, 2018] wrote a paper on the topic of walking on graphs and its connection to the centraliser algebra.
[Benkart, 2014] studied how the McKay quiver relates to Schur–Weyl duality.
[Benkart, 2016] also looked at how to find the McKay quiver for representations of a number of groups using character theory.
[Halverson and Ram, 2005] wrote a seminal paper on the partition algebra, with an emphasis on finding the simple modules of $P_k(n)$ in the case where $P_k(n)$ is semisimple.
[Halverson, 2001] also studied the characters of the partition algebra.
[Bowman et al., 2013] looked at how the partition algebra can be used to describe the Kronecker coefficients coming from the tensor product of two Specht modules.
The papers written by [Benkart and Halverson, 2019, Benkart and Halverson, 2019] and [Benkart et al., 2017], however, are especially important in the context of this paper as they show how

the partition algebra can be used to construct the invariant theory of the symmetric group, with an emphasis on understanding the kernel of Jones' surjective algebra homomorphism when $n < 2k$.
[Halverson, 2019] summarised the main results that appeared in these papers.

Permutation equivariant neural networks, on the other hand, have been a hot topic of study in the artificial intelligence community.
[Zaheer et al., 2017] introduced the first permutation equivariant neural network, called Deep Sets, for learning from sets in a permutation equivariant manner.
Sets of size $n$ can be modelled as a $1$-order tensor of the permutation representation of dimension $n$ of $S_n$.
[Hartford et al., 2018] considered permutation equivariant neural networks that learn the interactions between any number of sets; we saw in Section <ref> that our method is able to recover their results.
[Maron et al., 2019] 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.
For example, the adjacency matrix of a graph with $n$ nodes can be viewed as a $2$-order tensor of the permutation representation of dimension $n$ of $S_n$.
They characterised all of the learnable, linear, permutation equivariant layer functions in $\Hom_{S_n}(M_n^{\otimes k}, M_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.
In fact, the equations they find, in representation theoretic terminology, are actually the equations of the invariant subspace for $M_n^{\otimes l}$, for any $l$, and in obtaining the basis, they repeat, seemingly without knowledge, the construction given in [Jones, 1994].
Our paper is the closest to [Maron et al., 2019]
in terms of the learnable, linear, permutation equivariant layer functions that are the focus of their study;
however, our method for calculating a basis for the layer functions in
$\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$
is different — it is motivated by the Schur–Weyl duality that exists between the partition algebra and the symmetric group.
Moreover, we emphasise that the dimensions of the $\Hom$-spaces $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$ are not independent of $n$, providing an analytic solution for calculating these dimensions, and we show how to obtain a basis for these $\Hom$-spaces for all values of $n$, $k$ and $l$ in the standard basis of $M_n$.
We note that [Finzi et al., 2021] were the first to recognise that the dimensions of the $\Hom$-spaces $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$ are not independent of $n$,
using a numerical algorithm to calculate the correct values for small values of $n$, $k$ and $l$.
We believe that emphasising that the dimensions of the $\Hom$-spaces $\Hom_{S_n}(M_n^{\otimes k}, M_n^{\otimes l})$ are not independent of $n$
is important since we are of the opinion that the most recently published papers in the field do not appreciate that this is the case.
For example, [Pan and Kondor, 2022] consider the form of some of the layer functions that we have studied by looking at how partitions influence the mapping of indices of the layer function, considered as a tensor, but in their analysis they assume that the dimension of the $\Hom$-spaces is independent of $n$.

§ CONCLUSION

We are the first to show how the combinatorial representation theory of the partition algebra and its related vector spaces provides the theoretical background for understanding permutation equivariant neural networks when the layers are some tensor power of the permutation represention of dimension $n$ of $S_n$.
In the first half of the paper, we showed how the McKay quiver for this special representation allows us to decompose any tensor power of the representation into irreducibles of $S_n$;
furthermore, using the fact that $S_n$ (technically, $\mathbb{C}[S_n]$) is in Schur–Weyl duality with the centraliser algebra $\End_{S_n}(M_n^{\otimes k})$ on $M_n^{\otimes k}$, we saw that the multiplicities of the irreducibles appearing in this decomposition are actually the dimensions of all of the simple modules of the centraliser algebra.
We saw how this gave us a number of different ways of calculating the number of weights that appear in the layer functions of the permutation equivariant neural networks in question.
In the second half of the paper, we looked at the problem of actually calculating the form of the layer functions themselves in the standard matrix basis.
We saw how the orbit basis of the partition algebra and its related vector spaces allowed us to find this basis.
We were also able to generalise this diagrammatic approach to layer functions that were equivariant to local symmetries, and we considered layer functions that are equivariant across the feature dimension for all of the tensor spaces.
The critical idea underlying all of these results is that, as a result of the surjection of algebras $\Phi_{k,n} : P_k(n) \rightarrow \End_{S_n}(M_n^{\otimes k})$, we see that $S_n$ is actually in Schur–Weyl duality with the partition algebra $P_k(n)$, and so, ultimately, in this paper, we have used the theory of the partition algebra to understand the structure of permutation equivariant neural networks when the layers are some tensor power of the permutation represention of dimension $n$ of $S_n$.
This leads to the following question, which is one for future research: what other Schur–Weyl dualities exist between a group (algebra) and an algebra of diagrams that would allow us to understand the structure of neural networks that are equivariant to the group?
For example, [Pearce-Crump, 2022] has shown that the Schur–Weyl dualities that exist between
the orthogonal group, $O(n)$, and the Brauer algebra, $B_k(n)$;
the symplectic group, $Sp(n)$, where $n = 2m$, and the Brauer algebra, $B_k(n)$; and
the special orthogonal group, $SO(n)$, and the Brauer–Grood algebra, $D_k(n)$,

results in a full characterisation of

all of the possible group equivariant neural networks for $O(n)$, $Sp(n)$ and $SO(n)$
when the layers are some tensor power of $\mathbb{R}^{n}$.

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.

§ APPENDIX A. THE WEIGHT MATRIX AND BIAS VECTOR FOR $S_4$–EQUIVARIANT LAYER FUNCTIONS $M_4^{\OTIMES 2} \RIGHTARROW M_4^{\OTIMES 2}$

Since $n = 4$ and $k = 2$, we have that $n \geq 2k$, and so, by Theorem <ref>,
we see that the images of all $\Bell(4) = 15$ orbit basis diagrams of $P_2(4)$

under the map $\Phi_{2,4}$ defined in (<ref>)
gives the standard matrix basis of $\End_{S_4}(M_4^{\otimes 2})$.

Consequently, the weight matrix
is of the form

\NiceMatrixOptions{code-for-first-row = \scriptstyle \color{blue},
code-for-first-col = \scriptstyle \color{blue}
\begin{bNiceArray}{*{4}{c}|*{4}{c}|*{4}{c}|*{4}{c}}[first-row,first-col]
%			& \Block{1-4}{1,1,*} & & & & \Block{1-4}{1,2,*} & & & & \Block{1-4}{2,1,*} & & & & \Block{1-4}{2,2,*} & & & \\
%			& 1 	& 2	& 3 	& 4 	& 1 	& 2	& 3 	& 4 	& 1 	& 2	& 3 	& 4	& 1 	& 2	& 3 	& 4 \\
& 1,1 	& 1,2	& 1,3 	& 1,4 	& 2,1 	& 2,2	& 2,3 	& 2,4 	& 3,1 	& 3,2	& 3,3 	& 3,4	& 4,1 	& 4,2	& 4,3 	& 4,4 \\
1,1		& \lambda_1 	& \lambda_5 	& \lambda_5	& \lambda_5	& \lambda_4 	& \lambda_6 	& \lambda_{12} 	& \lambda_{12} 	& \lambda_4 	& \lambda_{12} 	& \lambda_6 	& \lambda_{12} 	& \lambda_4 	& \lambda_{12} 	& \lambda_{12} 	& \lambda_6   \\
1,2		& \lambda_3 	& \lambda_8  	& \lambda_{13}	& \lambda_{13}	& \lambda_7 	& \lambda_2 	& \lambda_{11} 	& \lambda_{11} 	& \lambda_{14} 	& \lambda_{10} 	& \lambda_9 	& \lambda_{15} 	& \lambda_{14} 	& \lambda_{10} 	& \lambda_{15}	& \lambda_9   \\
1,3		& \lambda_3 	& \lambda_{13} 	& \lambda_8  	& \lambda_{13}	& \lambda_{14} 	& \lambda_9 	& \lambda_{10} 	& \lambda_{15} 	& \lambda_7 	& \lambda_{11} 	& \lambda_2 	& \lambda_{11} 	& \lambda_{14} 	& \lambda_{15}	& \lambda_{10} 	& \lambda_9   \\
1,4		& \lambda_3 	& \lambda_{13} 	& \lambda_{13}	& \lambda_8  	& \lambda_{14} 	& \lambda_9	& \lambda_{15}	& \lambda_{10}	& \lambda_{14}	& \lambda_{15}	& \lambda_9	& \lambda_{10}	& \lambda_7	& \lambda_{11}	& \lambda_{11}	& \lambda_2  \\
\hline
2,1		& \lambda_2 	& \lambda_7	& \lambda_{11}	& \lambda_{11}	& \lambda_8	& \lambda_3	& \lambda_{13}	& \lambda_{13}	& \lambda_{10}	& \lambda_{14}	& \lambda_9	& \lambda_{15}	& \lambda_{10} 	& \lambda_{14} 	& \lambda_{15} 	& \lambda_9   \\
2,2		& \lambda_6 	& \lambda_4 	& \lambda_{12}	& \lambda_{12}	& \lambda_5	& \lambda_1	& \lambda_5	& \lambda_5	& \lambda_{12}	& \lambda_4	& \lambda_6	& \lambda_{12}	& \lambda_{12}	& \lambda_4 	& \lambda_{12}	& \lambda_6  \\
2,3		& \lambda_9 	& \lambda_{14} 	& \lambda_{10} 	& \lambda_{15}	& \lambda_{13}	& \lambda_3	& \lambda_8	& \lambda_{13}	& \lambda_{11}	& \lambda_7	& \lambda_2	& \lambda_{11}	& \lambda_{15}	& \lambda_{14}	& \lambda_{10} 	& \lambda_9  \\
2,4		& \lambda_9 	& \lambda_{14} 	& \lambda_{15}	& \lambda_{10} 	& \lambda_{13}	& \lambda_3	& \lambda_{13}	& \lambda_8	& \lambda_{15}	& \lambda_{14}	& \lambda_9	& \lambda_{10}	& \lambda_{11}	& \lambda_7	& \lambda_{11}	& \lambda_2 \\
\hline
3,1		& \lambda_2 	& \lambda_{11}	& \lambda_{7}	& \lambda_{11}	& \lambda_{10}	& \lambda_9	& \lambda_{14}	& \lambda_{15}	& \lambda_{8}	& \lambda_{13}	& \lambda_3	& \lambda_{13}  & \lambda_{10} 	& \lambda_{15} 	& \lambda_{14} 	& \lambda_9   \\
3,2		& \lambda_9 	& \lambda_{10} 	& \lambda_{14}	& \lambda_{15}	& \lambda_{11}	& \lambda_2	& \lambda_7	& \lambda_{11}	& \lambda_{13}	& \lambda_8	& \lambda_3	& \lambda_{13}	& \lambda_{15}	& \lambda_{10} 	& \lambda_{14}	& \lambda_9  \\