Densely Connected $G$-invariant Deep Neural Networks with Signed
  Permutation Representations
We introduce and investigate, for finite groups $G$, $G$-invariant deep
neural network ($G$-DNN) architectures with ReLU activation that are densely
connected-- i.e., include all possible skip connections. In contrast to other
$G$-invariant architectures in the literature, the preactivations of
the$G$-DNNs presented here are able to transform by \emph{signed} permutation
representations (signed perm-reps) of $G$. Moreover, the individual layers of
the $G$-DNNs are not required to be $G$-equivariant; instead, the
preactivations are constrained to be $G$-equivariant functions of the network
input in a way that couples weights across all layers. The result is a richer
family of $G$-invariant architectures never seen previously. We derive an
efficient implementation of $G$-DNNs after a reparameterization of weights, as
well as necessary and sufficient conditions for an architecture to be
``admissible''-- i.e., nondegenerate and inequivalent to smaller architectures.
We include code that allows a user to build a $G$-DNN interactively
layer-by-layer, with the final architecture guaranteed to be admissible. We
show that there are far more admissible $G$-DNN architectures than those
accessible with the ``concatenated ReLU'' activation function from the
literature. Finally, we apply $G$-DNNs to two example problems -- (1)
multiplication in $\{-1, 1\}$ (with theoretical guarantees) and (2) 3D object
classification -- % finding that the inclusion of signed perm-reps
significantly boosts predictive performance compared to baselines with only
ordinary (i.e., unsigned) perm-reps.
Devanshu Agrawal, James Ostrowski
Densely Connected \(\boldsymbol{G}\)-invariant Deep Neural Networks with Signed Permutation Representations

###### Abstract

We introduce and investigate, for finite groups \(\boldsymbol{G}\), \(\boldsymbol{G}\)-invariant deep neural network (\(\boldsymbol{G}\)-DNN) architectures with ReLU activation that are densely connected- i.e., include all possible skip connections. In contrast to other \(\boldsymbol{G}\)-invariant architectures in the literature, the preactivations of the\(\boldsymbol{G}\)-DNNs presented here are able to transform by _signed_ permutation representations (signed perm-reps) of \(\boldsymbol{G}\). Moreover, the individual layers of the \(\boldsymbol{G}\)-DNNs are not required to be \(\boldsymbol{G}\)-equivariant; instead, the preactivations are constrained to be \(\boldsymbol{G}\)-equivariant functions of the network input in a way that couples weights across all layers. The result is a richer family of \(\boldsymbol{G}\)-invariant architectures never seen previously. We derive an efficient implementation of \(\boldsymbol{G}\)-DNNs after a reparameterization of weights, as well as necessary and sufficient conditions for an architecture to be "admissible"- i.e., nondegenerate and inequivalent to smaller architectures. We include code that allows a user to build a \(\boldsymbol{G}\)-DNN interactively layer-by-layer, with the final architecture guaranteed to be admissible. Finally, we apply \(\boldsymbol{G}\)-DNNs to two example problems--(1) multiplication in **{-1,1}** (with theoretical guarantees) and (2) 3D object classification--finding that the inclusion of signed perm-reps significantly boosts predictive performance compared to baselines with only ordinary (i.e., unsigned) perm-reps.

deep learning, group theory, neural network, skip connection, symmetry

## 1 Introduction

When fitting a deep neural network (DNN) to a target function that is known to be \(\boldsymbol{G}\)-invariant with respect to a group \(\boldsymbol{G}\), it only makes sense to enforce \(\boldsymbol{G}\)-invariance on the DNN as prior knowledge. With the rise of geometric deep learning (Bronstein et al., 2021), this is becoming an increasingly common practice, finding applications in various domains including computer vision, where the class of an object in an image may be independent of its orientation (Veeling et al., 2018), or point clouds that are permutation-invariant (Qi et al., 2017). In general-purpose \(\boldsymbol{G}\)-invariant and \(\boldsymbol{G}\)-equivariant architectures such as \(\boldsymbol{G}\)-equivariant convolutional neural networks (\(\boldsymbol{G}\)-CNNs) (Cohen and Welling, 2016) and \(\boldsymbol{G}\)-equivariant graph neural networks (Maron et al., 2019), it is standard to require every linear layer to be \(\boldsymbol{G}\)-equivariant. Moreover, in case of the rectified linear unit (ReLU) activation, every linear layer is \(\boldsymbol{G}\)-equivariant only with respect to permutation representations. It is
commonly assumed that the \(\mathbf{G}\)-invariant architectures constructed in this way are sufficient for consideration (Cohen et al., 2019), but it is unclear if this layerwise construction covers all possible ways of enforcing \(\mathbf{G}\)-invariance on a fully-connected feedforward DNN, and it remains an open conjecture (Kondor and Trivedi, 2018). While these architectures and others are certainly sufficient for universal approximation of \(\mathbf{G}\)-invariant functions (Maron et al., 2019; Ravanbakhsh, 2020; Kicki et al., 2020), the way in which \(\mathbf{G}\)-invariance is enforced is an aspect of the neural architecture and thus likely plays a key role in determining the inductive bias of the model and hence its generalization power on a given problem.

It has recently been discovered that there are, in fact, more ways to enforce \(\mathbf{G}\)-invariance on shallow ReLU neural networks than just permutations on the hidden neurons (Agrawal and Ostrowski, 2022). In their work, Agrawal and Ostrowski (2022) exploit the identity

\[\text{ReLU}(\mathbf{-}\mathbf{x})=\text{ReLU}(\mathbf{x})-\mathbf{x} \tag{1}\]

to show that \(\mathbf{G}\)-invariance can be achieved even if \(\mathbf{G}\) acts on the hidden neurons via a "signed permutation representation" (signed perm-rep), resulting in novel \(\mathbf{G}\)-invariant shallow architectures previously unknown. In an attempt towards a generalization to deep architectures, we observe that the linear term in Eq. (1) can be interpreted as a skip connection; this suggests that skip connections may be the key to novel deep \(\mathbf{G}\)-invariant architectures.

In this paper, as a partial generalization of the work of Agrawal and Ostrowski (2022), we investigate \(\mathbf{G}\)-invariant deep neural network (\(\mathbf{G}\)-DNN) architectures that are "densely connected"- i.e., include all possible skip connections. We note that (non-\(\mathbf{G}\)-invariant) densely connected neural networks exist in the literature and have found immense success especially in medical imaging (Huang et al., 2017). We use ReLU activation, and every preactivation layer is still a \(\mathbf{G}\)-equivariant function of the network input; however, in contrast to previous architectures such as the \(\mathbf{G}\)-CNN, the individual weight matrices of a \(\mathbf{G}\)-DNN need not be \(\mathbf{G}\)-equivariant. Instead, in each layer, only the concatenation of the weight matrix with all skip connections from previous layers need be \(\mathbf{G}\)-equivariant. This dense structure allows us to use _signed_ perm-reps to enforce\(\mathbf{G}\)-equivariance on the preactivation layers, thus granting us access to a much larger family of \(\mathbf{G}\)-invariant architectures than seen previously. Practically, we hypothesize the existence of real-world problems for which some of these novel \(\mathbf{G}\)-DNN architectures encode useful inductive bias.

Implementation of \(\mathbf{G}\)-DNNs is nontrivial, as the group representation by which the weight matrix (concatenated with all skip connections) in each layer transforms is itself a function of the weights in previous layers. That is, due to the skip connections and in contrast to previous architectures such as the \(\mathbf{G}\)-CNN, \(\mathbf{G}\)-invariance is enforced in a way that couples weights across layers. We show, however, that there is a reparameterization of \(\mathbf{G}\)-DNNs in which the equivariance conditions of the weight matrices decouple and admit a simple implementation (Thm. 6 (a)). For efficiency, rather than transforming back to the original weights, we express and implement the forward pass of a \(\mathbf{G}\)-DNN directly in terms of these reparameterized weights (Thm. 6 (b)).

The remainder of the paper is organized as follows: In Sec. 2, we review signed perm-reps and state our central hypothesis with some theoretical support. In Sec. 3, we introduce and describe the implementation of \(\mathbf{G}\)-DNN architectures. We additionally derive necessary and sufficient conditions for a \(\mathbf{G}\)-DNN architecture to be "admissible" or nondegenerate (Thm. 7), in the sense that (1) no neuron is missing an input and (2) no two ReLU neurons
can be combined into a single ReLU neuron or a skip connection. We include code1 that allows a user to build a \(\G\)-DNN interactively such that the final architecture is guaranteed to be admissible. We also verify that batch normalization placed after ReLU is compatible with \(\G\)-DNNs out-of-the-box. In Sec. 4, we test \(\G\)-DNNs on two examples--(1) a simple mathematical function and (2) a real-world computer vision problem--and demonstrate that signed perm-reps can, in fact, carry useful inductive bias. Finally, in Sec. 5, we end with conclusions, implications, and future outlook.

Footnote 1: Code for our implementation and for reproducing all results in this paper is available at: [https://github.com/dagrawa2/gdnm_code](https://github.com/dagrawa2/gdnm_code).

## 2 Signed permutation representations

### Preliminaries

We begin by introducing some notions and notation that will be used throughout this paper. This section is an abbreviation of Secs. 2.1-2.2 of Agrawal and Ostrowski (2022), and we refer readers to all of Sec. 2 of that paper for details of the below material.

Throughout this paper, let \(\G\) be a finite group of \(m\times m\) orthogonal matrices. Let \(\P(n)\) be the group of \(n\times n\) permutation matrices and \(\Z(n)\) the group of \(n\times n\) diagonal matrices with diagonal entries \(\pm 1\). Let \(\PZ(n)=\PZ(n)\times\Z(n)\), which is the group of _signed permutations_- i.e., the group of all permutations and reflections of the standard orthonormal basis \(\{e_{1},\ldots,e_{n}\}\). This group is also called the hyperoctahedral group in the literature (Baake, 1984).

A _signed permutation representation_ (signed perm-rep) of degree \(n\) of \(\G\) is a homomorphism \(\rho:\G\mapsto\PZ(n)\). Two signed perm-reps \(\rho,\rho^{\prime}\) are said to be _equivalent_ or _conjugate_ if there exists \(A\in\PZ(n)\) such that \(\rho^{\prime}(g)=A\rho(g)A^{-1}\forall g\in G\)- i.e., if they are related by a change of basis. A signed perm-rep \(\rho\) is said to be _reducible_ if it is equivalent to a direct sum of signed perm-reps of smaller degrees- i.e., if there exists \(A\in\PZ(n)\) such that \(A\rho(\cdot)A^{-1}\) is simultaneously block-diagonal with at least two blocks. The signed perm-rep is said to be _irreducible_ (signed perm-irrep for short) otherwise.2

Footnote 2: A useful characterization is that a signed perm-rep \(\rho\) is irreducible iff for every \(i,j=1,\ldots,n\), there exists \(g\in G\) such that \(\rho(g)e_{i}=\pm e_{j}\).

The signed perm-irreps of \(\G\) can be completely classified up to equivalence in terms of certain pairs of subgroups of \(\G\). For every pair of subgroups \(K\leq H\leq G\), \(|H:K|\leq 2\), define the signed perm-rep \(\rho_{HK}:G\mapsto\PZ(n)\), \(n=|G/H|\), to be the induced representation

\[\rho_{HK}=I_{H}^{G}\sigma,\text{ where }\sigma:H\mapsto\{-1,1\}\mid\ker( \sigma)=K.\]

Then \(\rho_{HK}\) is irreducible, and every signed perm-irrep is equivalent to some \(\rho_{HK}\). Moreover, \(\rho_{HK}\) and \(\rho_{H^{\prime}K^{\prime}}\) are equivalent iff \((H^{\prime},K^{\prime})=(gHg^{-1},gKg^{-1})\) for some \(g\in G\). We can thus always understand a "signed perm-irrep" to mean \(\rho_{HK}\) for some appropriate subgroups \(H\) and \(K\), and conversely we will always understand the notation \(\rho_{HK}\) to mean the above construction. For alternative (but equivalent) ways to think about the \(\rho_{HK}\), see Sec. 2 of Agrawal and Ostrowski (2022).

Every signed perm-irrep is either type 1 or type 2. A signed perm-rep is _type 1_ if it is equivalent to an _ordinary permutation representation_ (ordinary perm-rep) \(\pi:G\mapsto\PZ(n)\);
it is _type 2_ otherwise. Sign flips in a type 1 signed perm-rep are thus artifacts as they can be removed by a change of basis. An important characterization is that a signed perm-irrep \(\rho_{HK}\) has type \(|H:K|\).

Finally, as general notation, throughout this paper let \(I_{n}\) denote the \(n\times n\) identity matrix and \(\bar{\mathsf{0}}_{n}\) (resp. \(\bar{\mathsf{1}}_{n}\)) the \(n\)-dimensional vector with all elements \(\mathbf{0}\) (resp. \(\mathbf{1}\)).

### Central hypothesis

Previous works in the equivariant deep learning literature, to our knowledge, primarily employ type 1 signed perm-reps--and in particular, ordinary perm-reps--to enforce layer-wise \(G\)-equivariance in ReLU networks. The purpose of this paper is to show that type 2 signed perm-reps can also be implemented for this purpose (although it is trickier as it requires layers to be coupled), and the central hypothesis of this work is that type 2 signed perm-reps can indeed be beneficial for DNN performance. In this section, we motivate this hypothesis with theory and discussions that suggest that type 2 signed perm-reps can help boost expressive power without necessarily sacrificing generalization power.

Our first theorem states that two inequivalent signed perm-irreps induced from different reps of the same subgroup \(H\leq G\) correspond to \(G\)-equivariant matrices that are in a sense orthogonal.3

Footnote 3: All proofs can be found in the supplementary material.

**Theorem 1** (Corollary to Prop. 6 of Agrawal and Ostrowski (2022)): _Let \(\rho_{HK_{1}}\) and \(\rho_{HK_{2}}\) be inequivalent signed perm-irreps of degree \(n\) of \(G\). For each \(i\in\{1,2\}\), let \(W_{i}\in\mathbb{R}^{n\times m}\) such that \(\rho_{HK_{i}}W_{i}=W_{i}g\forall g\in G\). Then there exists \(P\in P(n)\) such that_

\[\operatorname{diag}(PW_{1}W_{2}^{\top})=0.\]

Our second theorem describes how a signed perm-rep can be "unraveled" into an ordinary perm-rep of twice the degree, by essentially mapping sign flips to transpositions of two dimensions. This unraveling is particularly meaningful for type 2 signed perm-irreps, which remain irreducible even after unraveling; in contrast, type 1 signed perm-irreps merely unravel into reducible copies of themselves. Let \(\mathcal{H}\) be the elementwise Heaviside step function, where we let \(\mathcal{H}(0)=0\).

**Theorem 2**: _Let \(\rho:G\mapsto PZ(n)\) be a signed perm-rep. Then:_

1. _The function_4__ Footnote 4: In the expression for \(\pi_{\rho}\), the operation \(\mathfrak{G}\) is the Kronecker product. \[\pi_{\rho}(g)=\mathcal{H}\left(\begin{bmatrix}1&-1\\ -1&1\end{bmatrix}\otimes\rho(g)\right)\] _defines an ordinary perm-rep_ \(\pi_{\rho}:G\mapsto P(2n)\)_._ Footnote 5: In the expression for \(\pi_{\rho}\), the operation \(\mathfrak{G}\) is the Kronecker product.
2. _Let_ \(W\in\mathbb{R}^{n\times m}\) _such that_ \(\rho(g)W=Wg\forall g\in G\)_. Then_ \[\pi_{\rho}(g)\left[\begin{bmatrix}W\\ -W\end{bmatrix}=\begin{bmatrix}W\\ -W\end{bmatrix}g\forall g\in G.\]
3. _Suppose_ \(\rho\) _is irreducible. Then_ \(\pi_{\rho}\) _is irreducible iff_ \(\rho\) _is type 2._
4. _Suppose_ \(\rho\) _is type 2 irreducible and_ \(\rho=\rho_{HK}\)_. Then_ \(\pi_{\rho}=\rho_{KK}\)_._

To understand Thms. 1-2 and their implications for the expressive and generalization powers of a \(G\)-DNN with type 2 signed perm-reps, consider the example group \(G\) of all \(6\times 6\) cyclic permutation matrices (see Sec. 4.1 of Agrawal and Ostrowski (2022) for a detailed discussion of this example). For this example, the signed perm-irreps of \(G\) are completely characterized in terms of their degrees and types; we thus let \(\rho_{(n,t)}\) denote the irrep \(\rho_{HK}\) where \(n=\frac{6}{|H|}\) is the degree and \(t=|H:K|\) is the type. Alternatively, if \(G\cong\mathbb{Z}_{6}\), then \(\rho_{(n,t)}\) denotes the irrep \(\rho_{HK}\) where \(H\cong\mathbb{Z}_{\frac{6}{n}}\) and \(K\cong\mathbb{Z}_{\frac{6}{n!}}\). In this notation, the signed perm-irreps of \(G\) are \(\rho_{(6,1)}\), \(\rho_{(3,1)}\), \(\rho_{(3,2)}\), \(\rho_{(2,1)}\), \(\rho_{(1,1)}\), and \(\rho_{(1,2)}\).

For each irrep \(\rho_{(n,t)}\), let \(W_{(n,t)}\in\mathbb{R}^{n\times m}\) such that \(\rho_{(n,t)}W_{(n,t)}=W_{(n,t)}\forall G\in G\). The irreps \(\rho_{(3,1)}\) and \(\rho_{(3,2)}\) satisfy the hypotheses of Thm. 1, and indeed we see--in terms of their weigthsharing patterns--each row of \(W_{(3,1)}\) is orthogonal to the corresponding row of \(W_{(3,2)}\) (Fig. 1). In practice, this means if we were given a dataset sampled from a \(G\)-invariant shallow neural network (\(G\)-SNN)

\[f(x)=a\mathbb{I}^{\top}\operatorname{ReLU}(Wx+b\mathbb{I})+c^{\top}x+d,\]

with \(W=W_{(3,2)}\) as the ground truth weight matrix, then a \(G\)-SNN with weight matrix with the weigthsharing pattern of \(W_{(3,1)}\) would not have the expressive power to fit the ground truth, regardless of the number of "channels" (i.e., independent copies of \(W_{(3,1)}\)) used. With a limited budget of three hidden neurons per channel, type 2 signed perm-reps thus help to increase expressive power.

On the other hand, if we double our budget of hidden neurons, then Thm. 2 suggests \(W_{(6,1)}\) has the capacity to express \(W_{(3,2)}\); indeed, if we constrain the first row of \(W_{(6,1)}\)

Figure 1: Weightsharing patterns of equivariant matrices for three example signed perm-irreps of the group \(G\) of \(6\times 6\) cyclic permutation matrices (see main text for details). In each pattern, weights of the same color and texture (solid vs. hatched) are constrained to be equal; weights of the same color but different texture are constrained to be opposites (colors should not be compared across different matrices).
to have the same weightsharing pattern as the first row of \(\mathbf{W_{(3,2)}}\) (Fig. 1), then \(\mathbf{W_{(6,1)}}\) effectively becomes equivalent to \(\mathbf{W_{(3,2)}}\). The problem is, however, that \(\mathbf{W_{(6,1)}}\) can similarly be constrained to match \(\mathbf{W_{(3,1)}}\), and with probability \(\mathbf{1}\) (e.g., under a Gaussian), \(\mathbf{W_{(6,1)}}\) is equivalent to neither \(\mathbf{W_{(3,1)}}\) nor \(\mathbf{W_{(3,2)}}\). Thus, while this approach allows us to use a type 1 signed perm-rep with the capacity to express the ground truth, it comes at the cost of generalization power, as \(\mathbf{W_{(6,1)}}\) may have multiple configurations consistent with a finite training set.

In sum, type 2 signed perm-reps may help to refine the range of expressive powers available to us; they help to express functions different from type 1 signed perm-reps of the same degree without sacrificing generalization power the way larger type 1 signed perm-reps would.

## 3 \(\mathbf{G}\)-invariant deep neural networks

### Parameterization redundancies

In this section, we define densely connected deep neural networks, or simply deep neural networks, and we list some of the so-called parameterization redundancies of such networks that will be key to enforcing \(\mathbf{G}\)-invariance. All notation introduced here will persist throughout the paper.

Let \(f:\mathbb{R}^{m}\xrightarrow{}\mathbb{R}\) be a _deep neural network_ (DNN) of depth \(\mathbf{d}\) constructed as follows: Let \(\{\mathbf{n_{1}},\ldots,\mathbf{n_{d+1}}\}\) be a set of \(\mathbf{d+1}\) positive integers where5\(n_{1}=m\) and \(n_{\mathbf{d+1}}=\mathbf{1}\), and let \(\mathbf{N}_{i}=n_{1}+\cdots+n_{i}\) for every \(i\in\{\mathbf{1},\ldots,\mathbf{d}\}\). Let \(\mathbf{W^{(l)}}\in\mathbb{R}^{n_{i+1}\times\mathbf{N}_{i}}\) and \(\mathbf{b^{(l)}}\in\mathbb{R}^{n_{i+1}}\) for every \(i\in\{\mathbf{1},\ldots,\mathbf{d}\}\). Define \(\mathbf{f^{(1)}}:\mathbb{R}^{m}\xrightarrow{}\mathbb{R}^{n_{1}}\) by \(\mathbf{f^{(1)}(x)}=\mathbf{x}\). For every \(i\in\{\mathbf{1},\ldots,\mathbf{d-1}\}\), define \(\mathbf{f^{(i+1)}}:\mathbb{R}^{m}\xrightarrow{}\mathbb{R}^{N_{i+1}}\) by

Footnote 5: Note the input dimension \(n_{1}=m\) is the same number as the degree of the matrix group \(\mathbf{G}\) in Sec. 2.

\[\mathbf{f^{(i+1)}(x)}=\begin{bmatrix}\mathsf{ReLU}(\mathbf{W^{(l)}}\mathbf{f^{(l)}(x)}+ \mathbf{b^{(l)}})\\ \mathbf{f^{(l)}(x)}\end{bmatrix}. \tag{2}\]

Then, let \(\mathbf{f(x)}=\mathbf{W^{(\mathbf{d})}}\mathbf{f^{(\mathbf{d})}(x)}+\mathbf{b^{(\mathbf{d})}}\).

We thus define a DNN to be a feedforward ReLU network having all possible _skip connections_. We call the \(\mathbf{W^{(i)}}\)_weight matrices_, their rows _weight vectors_, and the \(\mathbf{b^{(l)}}\)_bias vectors_. The numbers \(n_{2},\ldots,\mathbf{n_{d}}\) are the widths of the hidden layers, and the numbers \(\mathbf{N_{2}},\ldots,\mathbf{N_{d}}\) are the cumulative widths accounting for the skip connections. Note the traditional definition of a DNN can be recovered by setting all skip connections to zero.

Our first proposition below establishes a set of parameterization redundancies (i.e., reparameterizations of the DNN leaving the input-output function invariant) enjoyed by the above DNN architecture. For every positive integer \(n\), let \(\mathcal{C}(n)\) be the group of \(n\times n\) diagonal matrices with positive diagonal entries.
**Proposition 3**: _Let \(i\in\{1,\ldots,d-1\}\), \(C\in\mathcal{C}(n_{i+1})\), \(P\in\mathcal{P}(n_{i+1})\), and \(Z\in\mathcal{Z}(n_{i+1})\). Then the DNN \(f\) is invariant under the transformation_

\[W^{(i)} \rightarrow CPZW^{(i)}\] \[b^{(i)} \rightarrow CPZb^{(i)}\] \[W^{(i+1)} \rightarrow W^{(i+1)}\begin{bmatrix}(CP)^{-1}&\mathcal{H}(-Z)W^{(i)}\\ 0&I_{N_{i}}\end{bmatrix}\] \[b^{(i+1)} \rightarrow b^{(i+1)}+W^{(i+1)}\begin{bmatrix}\mathcal{H}(-Z)b^{(i)}\\ 0\end{bmatrix}.\]

Proposition 3 is the key to understanding how signed perm-reps can be used in \(\mathsf{G}\)-DNNs. Specificly, if we want the parameters \((W^{(i)},b^{(i)})\) of the \(i\)th layer to transform by a signed perm-rep, then the parameters \((W^{(i+1)},b^{(i+1)})\) of the subsequent layer must transform as in Prop. 3 to compensate and maintain invariance. This idea is the basis of the next section.

### \(\mathsf{G}\)-invariant architectures

The following lemma gives a sufficient condition for each \(f^{(i)}\) (the subnetwork comprising the first \(i-1\) layers of \(f\) and acting as input of the \(i\)th layer) to be \(\mathsf{G}\)-equivariant; the sufficient condition takes the form of equivariant constraints on the network parameters.

**Lemma 4**: _Let \(\{\rho^{(1)},\ldots,\rho^{(d)}\}\) be a set of signed perm-reps \(\rho^{(i)}:\mathsf{G}\rightarrow\mathsf{PZ}(n_{i+1})\) with \(\rho^{(d)}\) the trivial rep. For each \(i\in\{1,\ldots,d\}\), let \(\pi^{(i)}:\mathsf{G}\rightarrow\mathcal{P}(n_{i+1})\) and \(\zeta^{(i)}:\mathsf{G}\rightarrow\mathcal{Z}(n_{i+1})\) be the unique functions such that \(\rho^{(i)}(g)=\pi^{(i)}(g)\zeta^{(i)}(g)\forall g\in G\). Let \(\{\psi^{(1)},\ldots,\psi^{(d)}\}\) be a set of reps \(\psi^{(i)}:\mathsf{G}\rightarrow\mathcal{GL}(N_{i})\) defined as:_

\[\psi^{(1)}(g) =g\] \[\psi^{(i+1)}(g) =\begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}\psi^{(i)}(g)- \pi^{(i)}(g)W^{(i)})\\ 0&\psi^{(i)}(g)\end{bmatrix}\forall i\in\{1,\ldots,d-1\}.\]

_Suppose \(\rho^{(i)}(g)W^{(i)}=W^{(i)}\psi^{(i)}(g)\) and \(\rho^{(i)}(g)b^{(i)}=b^{(i)}\) for all \(g\in G\) and \(i\in\{1,\ldots,d\}\). Then \(f^{(i)}(g\mathsf{x})=\psi^{(i)}(g)f^{(i)}(\mathsf{x})\) for all \(g\in G\), \(\mathsf{x}\in\mathbb{R}^{m}\), and \(i\in\{1,\ldots,d\}\)._

Since \(f^{(d)}(g\mathsf{x})=\psi^{(d)}f^{(d)}(\mathsf{x})\) and \(W^{(d)}\psi^{(d)}(g)=W^{(d)}\) for all \(g\in G\) and \(\mathsf{x}\in\mathbb{R}^{m}\), then we see that Lemma 4 gives a sufficient condition for \(f\) to be a \(\mathsf{G}\)_-invariant deep neural network_ (\(\mathsf{G}\)-DNN). Note the sequence of signed perm-reps \(\{\rho^{(1)},\ldots,\rho^{(d)}\}\) completely determines the \(\mathsf{G}\)-DNN architecture (i.e., depth, number of hidden neurons per layer, and weightsharing patterns), and hence we will also refer to such sequences of reps as \(\mathsf{G}\)_-DNN architectures_. Observe that the rep \(\psi^{(i)}\) depends on the weight matrix \(W^{(i-1)}\), and hence the equivariance condition on \(W^{(i)}\) introduces a coupling between \(W^{(i-1)}\) and \(W^{(i)}\). This coupling makes it difficult to implement the equivariance constraints on the weight matrices directly, and we thus proceed to find a reparameterization admitting uncoupled equivariant weight matrices. To do this, we first state another lemma below, which gives an explicit formula for the reps \(\psi^{(i)}\) (as opposed to a recursive formula) and shows each \(\psi^{(i)}\) to be equivalent to a direct sum of layerwise reps.
For every \(i\in\{1,\ldots,d\}\), decompose \(W^{(i)}\) into blocks as

\[W^{(i)}=\left[W^{(1)}_{i}\ \ \ W^{(1)}_{i-1}\ \ \cdots\ \ W^{(1)}_{1}\right],\]

where \(W^{(i)}_{j}\in\mathbb{R}^{n_{i+1}\times n_{j}}\). Define the block matrix

\[A^{(i)}=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(1)}_{i}&-\frac{1}{2}W^{(1) }_{i-1}&\cdots&-\frac{1}{2}W^{(1)}_{1}\\ \mathbf{0}&I_{n_{i}}&-\frac{1}{2}W^{(i-1)}_{i-1}&\cdots&-\frac{1}{2}W^{(i-1)}_ {1}\\ \mathbf{0}&0&I_{n_{i-1}}&\cdots&-\frac{1}{2}W^{(i-2)}_{1}\\ \mathbf{0}&0&0&\ddots&\vdots\\ \mathbf{0}&\mathbf{0}&\mathbf{0}&\mathbf{0}&I_{n_{1}}\end{bmatrix}.\]

Define the rep \(\Pi^{(i)}:G\mapsto\mathcal{O}(N_{i+1})\) by

\[\Pi^{(i)}(g)=\operatorname{diag}(\pi^{(i)}(g),\,\pi^{(i-1)}(g),\,\ldots,\, \pi^{(1)}(g),g).\]

**Lemma 5**: _For every \(i\in\{1,\ldots,d-1\}\), we have6_

Footnote 6: The notation \(A^{(i)-1}\) is shorthand for \((A^{(i)})^{-1}\), the matrix inverse of \(A^{(i)}\).

\[\psi^{(i+1)}(g)=A^{(0-1)}\Pi^{(i)}(g)A^{(0)}\forall g\in G.\]

Let \(\pi^{(0)}:G\mapsto\mathcal{P}(n_{1})\) be the trivial rep, and let \(A^{(0)}=I_{n_{1}}\). Then Lemma 5 holds for \(i=0\) as well.

We are now ready to state this section's key theorem, which gives a reparameterization of a \(G\)-DNN in which it admits uncoupled equivariant weight matrices.

**Theorem 6**: _Let \(f\) be \(G\)-invariant, with its parameters \(\{(W^{(1)},b^{(1)}),\ldots,(W^{(d)},b^{(d)})\}\) satisfying the conditions of Lemma 4 with respect to the signed perm-reps \(\{\rho^{(1)},\ldots,\rho^{(d)}\}\)._

1. _For every_ \(i\in\{1,\ldots,d\}\)_, there exists_ \(V^{(i)}\in\mathbb{R}^{n_{i+1}\times N_{i}}\) _with block structure_ \[V^{(i)}=\left[V^{(i)}_{i}\ \ \ V^{(i)}_{i-1}\ \ \cdots\ \ V^{(1)}_{1}\right]\] _where_ \(V^{(i)}_{j}\in\mathbb{R}^{n_{i+1}\times n_{j}}\) _such that_ \[\rho^{(i)}(g)V^{(i)}_{j} =V^{(i)}_{j}\pi^{(i-1)}(g)\forall g\in G\] \[W^{(i)} =V^{(i)}A^{(i-1)}.\]
2. _For every_ \(i\in\{1,\ldots,d\}\)_, define_ \(g^{(i)}:\mathbb{R}^{m}\mapsto\mathbb{R}^{n_{i+1}}\) _by_ \(g^{(i)}(x)=W^{(i)}f^{(i)}(x)\) _and_ \(h^{(i)}:\mathbb{R}^{m}\mapsto\mathbb{R}^{N_{i}}\) _by_ \(h^{(i)}(x)=A^{(i-1)}f^{(i)}(x)\)_. Then we have the recursion_ \[g^{(i)}(x) =V^{(i)}h^{(i)}(x)\forall i\in\{1,\ldots,d\}\] \[h^{(i+1)}(x) =\left[\begin{matrix}\operatorname{Re}\!\operatorname{LU}(g^{(i)} (x)+b^{(i)})-\frac{1}{2}g^{(i)}(x)\\ h^{(i)}(x)\end{matrix}\right]\forall i\in\{1,\ldots,d-1\}.\]
The \(\boldsymbol{V^{(l)}}\) are the latent weight matrices, and in Thm. 6 (a) we see that each \(\boldsymbol{V^{(l)}}\) satisfies an equivariant condition that is easy to implement. The apparent weight matrices \(\boldsymbol{W^{(l)}}\) can then be reconstructed as \(\boldsymbol{W^{(l)}}=\boldsymbol{V^{(l)}}\boldsymbol{A^{(i-1)}}\). In practice, however, there is no need to perform this reconstruction; instead, we implement the recursion in Thm. 6 (b) as the forward pass of the \(\boldsymbol{G}\)-DNN, where the final network output is \(\boldsymbol{f(x)}=\boldsymbol{g^{(d)}(x)}+\boldsymbol{b^{(d)}}\). Observe that the recursion is given directly in terms of the \(\boldsymbol{V^{(l)}}\) as opposed to the \(\boldsymbol{W^{(l)}}\). This recursion leverages the block-triangular structure of \(\boldsymbol{A^{(i-1)}}\) in the transformation \(\boldsymbol{W^{(l)}}=\boldsymbol{V^{(l)}}\boldsymbol{A^{(i-1)}}\).

### Admissible architectures

Theorem 6 tells us how to construct a \(\boldsymbol{G}\)-DNN, but it first requires us to select a sequence of reps or "architecture" \(\boldsymbol{\rho^{(1)}},\ldots,\boldsymbol{\rho^{(d)}}\). Selecting the optimal sequence is the problem of \(\boldsymbol{G}\)-invariant neural architecture design, which is beyond the scope of this work. At the very least, however, we would like to avoid sequences that correspond to "degenerate" network architectures. In particular, we require that (1) every row of each weight matrix \(\boldsymbol{W^{(l)}}\) be nonzero and (2) no two rows of the augmented weight matrix \([\boldsymbol{W^{(l)}}\mid\boldsymbol{b^{(l)}}]\) be parallel. The first condition ensures there are no neurons disconnected from all previous layers, and the second condition ensures no two hidden neurons in a given layer can be combined into a single hidden neuron or skip connection. We call a sequence of reps \(\boldsymbol{\rho^{(1)}},\ldots,\boldsymbol{\rho^{(d)}}\) an _admissible architecture_ if it admits a \(\boldsymbol{G}\)-DNN with weight matrices satisfying these two conditions. Below, Thm. 7 provides a characterization of admissible architectures that we implement in practice. First, however, we introduce additional notions and notation.

For every \(\boldsymbol{A}\in\mathbb{R}^{m\times m}\), let \(\mathtt{St}_{\boldsymbol{G}}\)(\(\boldsymbol{A}\)) be the stabilizer subgroup

\[\mathtt{St}_{\boldsymbol{G}}(\boldsymbol{A})=\{g\in\boldsymbol{G}:g \boldsymbol{A}=\boldsymbol{A}\},\]

and for every finite orthogonal matrix group \(\Gamma\), let \(P_{\Gamma}\) be the orthogonal projection operator onto the vector subspace pointwise-invariant under the action of \(\Gamma\):

\[P_{\Gamma}=\frac{1}{|\Gamma|}\sum_{g\in\Gamma}g.\]

Let \(\mathcal{S}(\boldsymbol{G})\) denote the set of all subgroups of \(\boldsymbol{G}\). Then, we define the function \(\boldsymbol{\theta}:\{(H,K,J)\in\mathcal{S}(\boldsymbol{G})^{3}:|H:K|\leq 2 \}\mapsto\mathcal{S}(\boldsymbol{G})\) by

\[\boldsymbol{\theta}(H,K,J) =\pi_{J}^{-1}[\mathtt{st}_{\pi_{J}(G)}(P_{\pi_{J}(K)}-(|H:K|-1)P_ {\pi_{J}(H)})]\] \[=\{g\in\boldsymbol{G}:\pi_{J}(g)(P_{\pi_{J}(K)}-(|H:K|-1)P_{\pi_{J }(H)})=P_{\pi_{J}(K)}-(|H:K|-1)P_{\pi_{J}(H)}\},\]

where the ordinary perm-rep \(\pi_{J}:G\mapsto\mathcal{P}(|G/|J|)\) is defined as usual- i.e., defined to be equivalent to the action of \(\boldsymbol{G}\) on \(G/J\). Note \(\pi_{J}\) is defined only up to conjugation by a perm-matrix, since no ordering on the cosets in \(G/J\) is specified. It turns out, however, that \(\boldsymbol{\theta}\) is invariant under conjugation of \(\pi_{J}\), and more generally \(\boldsymbol{\theta}\) is invariant and equivariant with respect to certain conjugations of the input subgroups (see Prop. 8 in App. B.3).

Let \(\boldsymbol{f}:\mathbb{R}^{m}\mapsto\mathbb{R}\) be a \(\boldsymbol{G}\)-DNN with sequence of signed perm-reps \(\boldsymbol{\rho^{(1)}},\ldots,\boldsymbol{\rho^{(d)}}\). For every \(i\in\{1,\ldots,d\}\), the signed perm-rep \(\boldsymbol{\rho^{(i)}}\) admits the following decomposition into irreducibles:

\[\boldsymbol{\rho^{(i)}}=\bigoplus_{j=1}^{r^{(0)}}\kappa_{j}^{(i)}\boldsymbol{ \rho^{(i)}_{j}},\quad\boldsymbol{\rho^{(i)}_{j}}=\boldsymbol{\rho^{(i)}_{\mu_{ j}^{(0)}}\kappa_{j}^{(i)}}.\]
The irreps \(\rho^{(\mathbf{0})}_{\mathbf{1}},\ldots,\rho^{(\mathbf{i})}_{r^{(\mathbf{i})}}\) are inequivalent, and each \(k^{(\mathbf{i})}_{j}\) is a positive integer where we define the notation

\[k^{(\mathbf{i})}_{j}\rho^{(\mathbf{i})}_{j}=\bigoplus_{k=\mathbf{1}}^{k^{(\mathbf{i})}_{j}}\rho^{ (\mathbf{i})}_{j}.\]

We say the \(i\)th layer of the \(G\)-DNN \(f\) has \(r^{(\mathbf{i})}\) distinct _irreps_ and \(k^{(\mathbf{i})}_{\mathbf{1}}+\cdots+k^{(\mathbf{i})}_{r^{(\mathbf{i})}}\)_channels_. Now for every \(i\in\{\mathbf{1},\ldots,\mathbf{d}\}\), we define the functions \(\phi^{(\mathbf{i})}:\{(H,K)\in S(\mathbf{G})^{2}:|H:K|\leq\mathbf{2}\}\mapsto S(\mathbf{G})\) recursively by

\[\phi^{(\mathbf{1})}(H,K) =\operatorname{st}_{G}(P_{K}-(|H:K|-1)P_{H})\] \[\phi^{(i+1)}(H,K) =\phi^{(\mathbf{i})}(H,K)\cap\bigcap_{j=1}^{r^{(\mathbf{i})}}\phi(H,K,H^{ (\mathbf{i})}_{j})\forall i\in\{1,\ldots,\mathbf{d}-1\}.\]

Following from the equivariance of \(\theta\) (Prop. 8) and that inner automorphisms respect subgroup intersection, we have the important property that each \(\phi^{(\mathbf{i})}\) is equivariant with respect to pairwise conjugation:

\[\phi^{(\mathbf{i})}(gHg^{-1},gKg^{-1})=g\phi^{(\mathbf{i})}(H,K)g^{-1}\forall g\in G.\]

We are ready to state the theorem characterizing single-channel admissible architectures; note the following is a generalization of Thm. 4a of Agrawal and Ostrowski (2022).

**Theorem 7**: _Maintain the notation introduced in the last paragraph, and suppose \(k^{(\mathbf{i})}_{j}=\mathbf{1}\forall i,j\) (single-channel architecture). Then the architecture7\(\{\rho^{(\mathbf{1})},\ldots,\rho^{(\mathbf{d})}\}\) is admissible iff the following conditions hold:_

Footnote 7: By definition of \(G\)-DNN architecture, \(\rho^{(\mathbf{d})}\) is trivial; see Lemma 4 and the discussion immediately proceeding it.

1. \(\phi^{(\mathbf{i})}(H^{(\mathbf{i})}_{j},K^{(\mathbf{i})}_{j})=K^{(\mathbf{i})}_{j}\forall i,j\).
2. _If_ \(H^{(\mathbf{1})}_{j}=G\) _for some_ \(j\)_, then_ \(P_{G}\neq\mathbf{0}\)_._8__

Footnote 8: This condition is trivially satisfied if \(G\) is a permutation matrix group.

Theorem 7 gives us a practical way to build admissible \(G\)-DNN architectures layer-by-layer as follows: Suppose we have already built the first \(i\) layers- i.e., we have selected the signed perm-reps \(\rho^{(\mathbf{1})},\ldots,\rho^{(\mathbf{i})}\) satisfying Thm. 7. Then the function \(\phi^{(i+1)}\) is defined. We enumerate all signed perm-irreps \(\rho_{H\!K}\), up to equivalence,9 such that \(\phi^{(\mathbf{i},K)=K}\), and we then select a subset to comprise \(\rho^{(\mathbf{i+1})}\). In terms of implementation, the computation of \(\phi^{(\mathbf{i})}(H,K)\) boils down to the computation of \(\theta(H,K,H^{(\mathbf{i-1})}_{j})\) for each \(j\), which can be accomplished using Alg. 1 (see App. B.3 for details). We should think of the outputs \(\theta(H,K,J)\) as entries of a precomputed table with a row for each \((H,K)\) (up to pairwise conjugation) and a column for each \(J\) (up to conjugation). We give additional implementation details in the next section, including how we accomodate multiple input and output channels per layer.
The number of admissible architectures can be significantly less than the total number of architectures. For example, we consider one particular permutation representation of every group of order \(\mathbf{8}\) up to isomorphism, following the constructions described in App. C.1 of Agrawal and Ostrowski (2022). For each group, we only count the architectures corresponding to sequences of irreps of strictly decreasing degree, and we report the fraction of these that are admissible (Table 1). Observe that the reduction from the total number of architectures to only the admissible ones is often significant, which could be exploited perhaps in a future implementation of \(\mathbf{G}\)-invariant neural architecture search. Understanding why all architectures of maximum depth are admissible requires further investigation.

### Additional remarks

ChannelsThe \(\mathbf{G}\)-DNN supports multiple channels in a way generalizing the notion from traditional convolutional neural networks. As already mentioned in Sec. 3.3, the \(i\)th layer of the \(\mathbf{G}\)-DNN \(\mathbf{f}\) is said to have \(\mathbf{k^{(i)}_{j}}\) output channels or copies of the irrep \(\mathbf{\rho^{(i)}_{j}}\) and \(\mathbf{k^{(i-1)}_{j}}\) input channels from the irrep \(\mathbf{\rho^{(i-1)}_{j}}\). As a simpler case, suppose \(\mathbf{\rho^{(i)}}\) contains the same number \(\mathbf{k^{(i)}}\) of copies of each of its constituent irreps, and suppose the input \(\mathbf{x}\) has \(\mathbf{k^{(0)}}\) channels. Then the \(i\)th layer can be said to have \(\mathbf{k^{(i)}}\) output channels and \(\mathbf{k^{(i-1)}}\) input channels. In practice, we implement the \(\mathbf{G}\)-DNN assuming only one copy of each irrep \(\mathbf{\rho^{(i)}_{j}}\), and then we regard each element of the input \(\mathbf{x}\) as a \(\mathbf{k^{(0)}}\)-dimensional vector and each element of the latent weight matrix block \(\mathbf{V^{(i)}_{j}}\) (see Thm. 6 (a) for notation) as a \(\mathbf{k^{(i)}}\mathbf{\times}\mathbf{k^{(i-1)}}\) matrix.

Batch normalizationIt is possible to apply batch normalization (batchnorm) immediately after ReLU in a \(\mathbf{G}\)-DNN without breaking \(\mathbf{G}\)-invariance. That batchnorm is compatible with \(\mathbf{G}\)-DNNs, and in particular type 2 signed perm-reps, out-of-the-box is not obvious, and we verify the compatibility in Prop. 10 (see App. B.4). The proof relies on the facts that (1) the first \(\mathbf{n}_{i}\) columns of \(\mathbf{W^{(0)}}\) and \(\mathbf{V^{(0)}}\) are equal and (2) the first \(\mathbf{n}_{i}\) columns of \(\mathbf{V^{(0)}}\) sum to zero if \(\mathbf{\rho^{(i)}}\) is a type 2 signed perm-irrep.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Depth & \(\mathbf{C_{8}}\) & \(\mathbf{C_{2}\times C_{4}}\) & \(\mathbf{C_{2}^{3}}\) & \(\mathbf{D_{4}}\) & \(\mathbf{Q_{8}}\) \\ \hline
2 & 5/5 & 8/15 & 11/43 & 14/21 & 9/9 \\
3 & 8/8 & 30/62 & 93/434 & 65/104 & 20/20 \\
4 & 4/4 & 48/48 & 392/392 & 84/84 & 12/12 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Ratio of the number of admissible \(\mathbf{G}\)-DNN architectures to the total number of architectures for every depth and every group \(\mathbf{G}\), \(|\mathbf{G}|=\mathbf{8}\), up to isomorphism. Only architectures corresponding to sequences of irreps of strictly decreasing degree are considered.
## 4 Examples

### Binary multiplication

Our first example is an exact result and demonstrates that \(G\)-DNNs with type 2 signed perm-reps occur even in the context of simple mathematical operations.

**Example 1**: _For \(d\geq 3\), let \(m=2^{d}\) and_

\[\mathcal{X}=\{\chi\in\{0,1\}^{m}:\chi_{2i-1}+\chi_{2i}=1\forall i\in\{1,\dots,m/2 \}\}.\]

_For \(\{\mathbf{e_{1},\dots,e_{m}\}\}\) the standard orthonormal basis, Let \(G<\mathcal{P}(m)\) be the subgroup of all even permutation matrices that only transpose \(\mathbf{e_{2i-1}}\) and \(\mathbf{e_{2i}}\). Define the function \(f:\mathcal{X}\mapsto\{-1,1\}\) by_

\[f(x)=\prod_{i=1}^{m/2}(\chi_{2i-1}-\chi_{i}).\]

_Then \(f\) admits an expression as a \(G\)-DNN of depth \(d\) where:_

1. _For_ \(i\in\{1,\dots,d\}\) _and_ \(j\in\{1,\dots,i\}\)_, the blocks_ \(V_{j}^{(i)}\) _of the latent weight matrices (see Thm._ 6 _(a)) are given by_ \[V_{j}^{(i)}=\begin{cases}I_{m/2^{i+1}}\otimes\begin{bmatrix}1&-1&1&-1\\ 1&-1&-1&1\end{bmatrix},&\text{ if }1\leq i=j<d\\ \begin{bmatrix}1&-1\end{bmatrix},&\text{ if }i=j=d\\ 0,&\text{ otherwise.}\end{cases}\]
2. _For_ \(i\in\{1,\dots,d-1\}\)_, the_ \(i\)_th layer transforms by the signed perm-rep_ \[\rho^{(i)}=\begin{cases}\bigoplus_{j=1}^{m/2^{i+1}}\rho_{H_{j}^{(i)}}\kappa_{ j}^{(i)},&\text{ if }i\leq d-2\\ \rho_{H_{1}^{(d-1)}}\kappa_{1}^{(d-1)}\oplus\rho_{H_{1}^{(d-1)}}\kappa_{1}^{(d -1)},&\text{ if }i=d-1,\end{cases}\] _where_ \[K_{j}^{(1)} =\{g\in G:g\nu_{j}=\nu_{j}\}\] \[H_{j}^{(1)} =\{g\in G:g\nu_{j}=\pm\nu_{j}\},\] _where_ \(\nu_{j}=e_{4j-3}-e_{4j-2}+e_{4j-1}-e_{4j}\)_, and_ \[K_{j}^{(i+1)} =H_{2j-1}^{(i)}\cap H_{2j}^{(i)}\] \[H_{j}^{(i+1)} =(H_{2j-1}^{(i)}\cap H_{2j}^{(i)})\cup((G\setminus H_{2j-1}^{(i) })\cap(G\setminus H_{2j}^{(i)})),\] _for_ \(i\in\{1,\dots,d-2\}\)_. The rep_ \(\rho^{(d)}\) _is trivial as usual._
Here, \(\mathbf{f(\times)}\) is the product of \(\frac{m}{2}\) binary elements in \(\{\mathbf{-1,1\}\}\) but where the elements are each represented as 2D one-hot vectors and are then concatenated into the \(m\)-dimensional input \(\mathbf{\mathsf{x}}\). From the perspective of multiplication of elements in \(\{\mathbf{-1,1\}\}\), the group \(\mathbf{G}\) corresponds to an even number of sign flips, which clearly leaves the final product invariant. Example 1 gives an explicit construction of a \(\mathbf{G}\)-DNN that implements the function \(\mathbf{f}\). Each layer of the \(\mathbf{G}\)-DNN partitions its input into pairs and takes each of their products; the network thus iteratively coarsegrains the input until the final scalar product is returned.10 Each latent weight matrix of the \(\mathbf{G}\)-DNN has a block-diagonal structure and no latent skip connections; however, by Thm. 6 (a), the \(\mathbf{G}\)-DNN does have skip connections in terms of the apparent weight matrices. All signed perm-irreps in the network-except \(\mathbf{\rho^{(d)}}\) which must be trivial-are type 2, and the image of each one is isomorphic to the Klein-4 group. The image of the penultimate rep \(\mathbf{\rho^{(d-1)}}\) is also isomorphic to the Klein-4 group, but the rep itself is not irreducible and decomposes into two copies of a type 2 scalar irrep.

Footnote 10: Although \(\mathbf{f}\) is a simple function, we were unable to construct a \(\mathbf{G}\)-DNN—in particular, a shallower \(\mathbf{G}\)-invariant architecture that (1) has \(\mathbf{G}\)-equivariant preactivations and (2) does not have an exponential number of hidden neurons per layer—simpler than the one given in Ex. 1 that fits \(\mathbf{f}\). For example, one could compute \(\mathbf{f(\times)}\) with a shallow network that first maps \(\mathbf{\mathsf{x}}\) linearly into \(\{\mathbf{-1,1\}\}^{\frac{m}{2}}\), then takes the sum \(\mathbbm{1}^{\top}\mathbf{\mathsf{x}}\), and finally returns the parity of the sum using a suitable combination of ReLU neurons; however, the function \(\mathbf{\mathsf{x}}\rightarrow\mathbbm{1}^{\top}\mathbf{\mathsf{x}}\) is not \(\mathbf{G}\)-equivariant.

We investigate Ex. 1 empirically by generating the complete dataset \(\{\mathbf{(\mathsf{x},\mathbf{f(\times)})}:\mathbf{\mathsf{x}}\in\mathbf{\mathsf{x}}\}\) for \(\mathbf{m=16}\). Since \(\mathbf{f(\times)=\pm 1}\), then we regard the estimation of \(\mathbf{f}\) as a binary classification problem. We use a random 20% of the dataset (with class stratification) for training and the rest for validation. We instantiate the "type 2" architecture with the type 2 signed perm-irreps in Ex. 1 (b) and randomly initialize its weights. We compare the type 2 architecture to two type 1 baselines: (1) the "type 1" architecture obtained by sending11\(\mathbf{\rho_{HK}\rightarrow\rho_{HH}}\) (see Thm. 1) and (2) the "unraveled" architecture obtained by sending \(\mathbf{\rho_{HK}\rightarrow\rho_{KK}}\) (seeThm. 2 (d)). The type 1, type 2, and unrave

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Architecture & Initial train & Initial val & Final train & Final val \\ \hline Type 1 & \(\mathbf{5.11\pm 4.68}\) & \(\mathbf{5.11\pm 4.68}\) & \(\mathbf{0.71\pm 0.04}\) & \(\mathbf{0.71\pm 0.04}\) \\
**Type 2** & \(\mathbf{1.33\pm 0.60}\) & \(\mathbf{1.33\pm 0.60}\) & \(\mathbf{0.00\pm 0.00}\) & \(\mathbf{0.00\pm 0.00}\) \\ Unraveled (random init) & \(\mathbf{11.36\pm 12.34}\) & \(\mathbf{11.36\pm 12.34}\) & \(\mathbf{0.71\pm 0.03}\) & \(\mathbf{0.71\pm 0.03}\) \\ Unraveled (type 2 init) & \(\mathbf{1.33\pm 0.60}\) & \(\mathbf{1.33\pm 0.60}\) & \(\mathbf{0.70\pm 0.00}\) & \(\mathbf{0.70\pm 0.00}\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Binary cross-entropy losses (mean and standard deviation over **24** random initialization seeds) of four \(\mathbf{G}\)-DNN architectures (see main text) on the binary multiplication problem. We report both the training loss and validation loss before training (initial) and after **5** epochs of training (final). Training and validation losses are equal because each of the two class labels corresponds to exactly one \(\mathbf{G}\)-orbit, over which each \(\mathbf{G}\)-DNN is constant– regardless of the dataset split. All values correspond to a classification accuracy of **50%**, except the final losses of zero for the type 2 architecture corresponding to 100% accuracy.
thus analogous to the three weightsharing patterns in Fig. 1 (see Sec. 2.2); i.e., the type 1 architecture has the same number of hidden neurons as the type 2 architecture but expresses different functions, and the unraveled architecture has double the number of hidden neurons and the capacity to express both the smaller two architectures as well as much more.

We trained all architectures for \(\mathbf{5}\) epochs with the Adam optimizer with minibatch size \(\mathbf{64}\), learning rate \(\mathbf{0.01}\), and learning rate decay \(\mathbf{0.99}\) per step. Starting at 50% classification accuracy, the type 2 architecture quickly achieves 100% traning and validation accuracy as well as a final binary cross-entropy loss of \(\mathbf{0.00}\) (Table 2). All other architectures remain stuck at 50% accuracy even after training. To explain these results, we first note that in the type 2 architecture, the latent weight matrices for \(i\in\{\mathbf{1},\ldots,d-\mathbf{1}\}\) are constrained to have the form

\[\mathbf{V}_{j}^{(\mathbf{i})}=\begin{cases}I_{m/2^{i+1}}\otimes\begin{bmatrix} u_{j}^{(\mathbf{i})}&-u_{j}^{(\mathbf{i})}&\mathbf{v}_{j}^{(\mathbf{i})}&- \mathbf{v}_{j}^{(\mathbf{i})}\\ u_{j}^{(\mathbf{i})}&-u_{j}^{(\mathbf{i})}&-\mathbf{v}_{j}^{(\mathbf{i})}& \mathbf{v}_{j}^{(\mathbf{i})}\\ \mathbf{0},&\text{if }\mathbf{1}\leq j<i<d,\end{cases}\end{cases},\]

where the \(\mathbf{u}_{j}^{(\mathbf{i})}\) and \(\mathbf{v}_{j}^{(\mathbf{i})}\) are free learnable parameters. In the type 1 architecture, the negative signs in front of \(\mathbf{v}_{j}^{(\mathbf{i})}\) are omitted, and the off-diagonal blocks are no longer zero but are instead constrained in the same way as the diagonal blocks. As a result, the very first linear transformation \(g^{(\mathbf{1})}(\mathbf{x})=\mathbf{V}^{(\mathbf{1})}\mathbf{x}\) in the architecture is invariant to every transposition \((\mathbf{x}_{2i-1},\mathbf{x}_{2i})\to(\mathbf{x}_{2i},\mathbf{x}_{2i-1})\)- not just even numbers of them; the rest of the architecture is thus unable to distinguish the two classes of inputs, resulting in a flat \(\mathbf{50\%}\) accuracy. The type 1 architecture simply does not have the capacity to solve the binary classification problem.

In contrast to the type1 and type 2 architectures, the latent weight matrices \(\mathbf{V}_{i}^{(\mathbf{i})}\) of the unraveled architectures are not even constrained to be block-diagonal, and the \(\mathbf{V}_{j}^{(\mathbf{i})}\) for \(j<i\) are not constrained to be zero. The unraveled architecture thus has about \(\mathbf{6.5\times}\) the number of free learnable parameters compared to the type 2 architecture, and it must learn the block-diagonal weight structure from data alone. Based on the training loss, the complete failure of the unraveled architecture is likely due to a severe trainability issue. To confirm the unraveled architecture indeed has the capacity to express the solution and in particular the type 2 architecture, we loaded the trained weights of the type 2 architecture into the unraveled architecture by an appropriate mapping and confirmed that the resulting architecture indeed achieves 100% training and validation accuracy. To test if the failure to train is due to poor initialization, we implemented the unraveled architecture with both random initialization (called "random init" in Table 2) and with the randomly initialized weights of the type 2 architecture (called "type 2 init" in Table 2). While initialization with the initial weights of the type 2 architecture reduces the initial loss of the unraveled architecture to match the type 2 architecture, it does not solve the trainability issue. We thus conclude the unraveled architecture simply does not have sufficient inductive bias to solve the binary classification problem.
Our second example demonstrates that \(\mathbf{G}\)-DNNs with type 2 signed perm-reps carry inductive bias that can be useful "in the wild". We consider the ModelNet40 dataset(Wu et al., 2015), which contains 9843 training and 2468 validation samples of 3D CAD mesh representations of \(\mathbf{40}\) different objects ranging from airplanes to toilets. The problem is to predict the object class given an input mesh. We preprocess the data in identical fashion to Jiang et al. (2019). Specifically, we first bound each mesh in the unit sphere and discretize the sphere into an icosahedron. To increase resolution, we include the midpoint on each icosahedral edge as a vertex, normalize all vertices to have unit norm, and then repeat once more on the new polyhedron; this yields 112 vertices in all. From each of these vertices, we perform ray-tracing to the origin; we record the distance from the sphere to the mesh as well as the sine and cosine of the incident angle. The representation is further augmented with the three channels corresponding to the convex hull of the input mesh, yielding a \(\mathbf{6}\)-channel input representation over 112 points.

The relevant symmetry group \(\mathbf{G}\) is the symmetry group of the icosahedron, generated by (1) the order-\(\mathbf{3}\) rotation about the normal vector to one of the faces and the order-\(\mathbf{5}\) rotation about one of the vertices; the group has 60 elements and is isomorphic to the alternating group \(\mathbf{A_{5}}\). We consider \(\mathbf{G}\)-DNN architectures with four layers and 16, 32, 64, and 40 output channels per rep in each respective layer. We specify apriori the degrees of the signed perm-irreps to be used in each layer as 30, 15, 10, and 1; we then enumerate the admissible architectures as described after Thm. 7, and we select the following designs: For the "mixed" architecture, we select one type 1 and one type 2 signed perm-irrep in each of the first three layers12we select the trivial rep in the last layer, as always. We compare the mixed architecture to the corresponding "type 1" and "unraveled" architectures, which are constructed exactly as done in Sec. 4.1.

Footnote 12: In each layer, the selected type 1 and type 2 signed perm-irreps are cohomologous as defined in Agrawal and Ostrowski (2022); i.e., they have the forms \(\rho_{\mathbf{HH}}\) and \(\rho_{\mathbf{HK}}\) respectively.

We trained all architectures for 500 epochs with the Adam optimizer with minibatch size 64, learning rate 0.01, and learning rate decay 0.99 per step. We included batchnorm as described in Sec. 3.4 after each ReLU layer. In each run, we performed retroactive early stopping by recording the highest validation accuracy achieved over all epochs. We

Figure 2: Validation classification accuracies (mean and standard deviation over 24 random initialization seeds) for three \(\mathbf{G}\)-DNN architectures (see main text) on the ModelNet40 dataset using different percentages of the full training data. The mixed architecture—the only one including type 2 signed perm-irreps—clearly outperforms the two baselines, with the performance gap increasing as less training data is available.
find that the mixed architecture--the only one containing type 2 signed perm-irreps--significantly outperforms the two baseline architectures in terms of validation accuracy, with the performance gap increasing as less training data is used. This suggests that the mixed architecture carries stronger inductive bias, still consistent with the ground truth, as compared to the baselines.

## 5 Conclusion

We have introduced the \(\boldsymbol{G}\)-DNN, a \(\boldsymbol{G}\)-invariant densely connected DNN architecture. In contrast to previous \(\boldsymbol{G}\)-invariant architectures in the literature such as the \(\boldsymbol{G}\)-CNN (Cohen and Welling, 2016), the \(\boldsymbol{G}\)-DNN is built with _signed_ perm-reps that do not require individual layers of the network to be \(\boldsymbol{G}\)-equivariant. The result is a richer family of \(\boldsymbol{G}\)-invariant architectures never seen before, and we have demonstrated with both theoretical and empirical examples that some of these novel architectures can boost predictive performance.

To be clear, we do not claim the \(\boldsymbol{G}\)-DNN to be a new state-of-the-art (SOTA) for \(\boldsymbol{G}\)-invariant deep learning. Rather, our work is a demonstration that signed perm-reps are mathematically natural and practically useful building blocks for deep \(\boldsymbol{G}\)-invariant architectures, and we think practitioners should be aware of them and know how to use them. Indeed, we suspect practitioners will observe performance boosts in their own models if they incorporate the ideas and structures presented in this paper into their respective domain-specific SOTA \(\boldsymbol{G}\)-invariant architectures.

Even at the domain-agnostic level, however, several open questions remain for future research. First, can we extend \(\boldsymbol{G}\)-DNNs from \(\boldsymbol{G}\)-invariance to \(\boldsymbol{G}\)-equivariance? The only obstacle here is the construction of architectures guaranteed to be admissible. Second, can we perform neural architecture search to find the optimal signed perm-irreps to use in each layer? Third and finally, are there ways of enforcing \(\boldsymbol{G}\)-invariance that go even beyond the \(\boldsymbol{G}\)-DNN architectures described in this paper? A complete classification of _all_\(\boldsymbol{G}\)-invariant architectures would give us the finest possible control on inductive bias, thereby allowing us--in principle--to optimize predictive performance on \(\boldsymbol{G}\)-invariant problems.

## Acknowledgments and Disclosure of Funding

D.A. was supported by NSF award No. 2202990. J.O. was supported by DOE grant DE-SC0018175.

## Appendix A Signed permutation representations

### Central hypothesis

[Proof of Thm. 1] For every \(\boldsymbol{J}\leq\boldsymbol{G}\), let \(P_{\boldsymbol{J}}\) be the \(m\times m\) orthogonal projection operator onto the subspace of \(\mathbb{R}^{m}\) pointwise-invariant under the action of \(\boldsymbol{J}\):

\[P_{\boldsymbol{J}}=\frac{1}{|\boldsymbol{J}|}\sum_{\boldsymbol{g}\in \boldsymbol{J}}\boldsymbol{g}.\]
By Thm. 4b of Agrawal and Ostrowski (2022), there exists \(w_{2}\in\mathsf{ran}(P_{K_{2}}-(|H:K_{2}|-1)P_{H})\) and a transversal \(\{g_{1},\ldots,g_{n}\}\) of \(G/H\) such that

\[W_{2}=\begin{bmatrix}g_{1}w_{2}&g_{2}w_{2}&\cdots&g_{n}w_{2}\end{bmatrix}^{ \mathsf{T}}.\]

Moreover, there exists \(w_{1}\in\mathsf{ran}(P_{K_{1}}-(|H:K_{1}|-1)P_{H})\) and \(P\in P(n)\) such that

\[PW_{1}=\begin{bmatrix}g_{1}w_{1}&g_{2}w_{1}&\cdots&g_{n}w_{1}\end{bmatrix}^{ \mathsf{T}}.\]

(The permutation matrix \(P\) is in general necessary so we can use the same transversal of \(G/H\).) We have

\[\mathsf{diag}(PW_{1}W_{2}^{\mathsf{T}}) =\{(g_{i}w_{1})^{\mathsf{T}}g_{i}w_{2}\}_{i=1}^{n}\] \[=\{w_{1}^{\mathsf{T}}g_{i}^{\mathsf{T}}g_{i}w_{2}\}_{i=1}^{n}\] \[=\{w_{1}^{\mathsf{T}}w_{2}\}_{i=1}^{n}\] \[=0,\]

where the last step follows by Prop. 6 of Agrawal and Ostrowski (2022).

**Proof** [Proof of Thm. 2] (a) Let \(\pi:G\mapsto P(n)\) and \(\zeta:G\mapsto\mathcal{Z}(n)\) be the unique functions satisfying \(\rho(g)=\pi(g)\zeta(g)\forall g\in G\) (note \(\pi\) should not be confused with \(\pi_{\rho}\) appearing in the theorem statement). Evaluating the Kronecker product, the function \(\pi_{\rho}\) can be rewritten as

\[\pi_{\rho}(g) =\mathcal{H}\biggl{(}\begin{bmatrix}\rho(g)&-\rho(g)\\ -\rho(g)&\rho(g)\end{bmatrix}\biggr{)}\] \[=\mathcal{H}\biggl{(}\begin{bmatrix}\pi(g)\zeta(g)&-\pi(g)\zeta(g )\\ -\pi(g)\zeta(g)&\pi(g)\zeta(g)\end{bmatrix}\biggr{)}\] \[=\mathcal{H}\biggl{(}\begin{bmatrix}\pi(g)&0\\ 0&\pi(g)\end{bmatrix}\begin{bmatrix}\zeta(g)&-\zeta(g)\\ -\zeta(g)&\zeta(g)\end{bmatrix}\biggr{)}\] \[=\begin{bmatrix}\pi(g)&0\\ 0&\pi(g)\end{bmatrix}\mathcal{H}\biggl{(}\begin{bmatrix}\zeta(g)&-\zeta(g)\\ -\zeta(g)&\zeta(g)\end{bmatrix}\biggr{)},\]

where in the last step we exploited the permutation-equivariance of elementwise operations. Now since \(\mathcal{H}(z)=\frac{1+z}{2}\) for \(z\in\{-1,1\}\), then we have

\[\pi_{\rho}(g) =\begin{bmatrix}\pi(g)&0\\ 0&\pi(g)\end{bmatrix}\frac{1}{2}\biggl{(}\begin{bmatrix}I_{n}&I_{n}\\ I_{n}&I_{n}\end{bmatrix}+\begin{bmatrix}\zeta(g)&-\zeta(g)\\ -\zeta(g)&\zeta(g)\end{bmatrix}\biggr{)}\] \[=\frac{1}{2}\biggl{(}\begin{bmatrix}\pi(g)&\pi(g)\\ \pi(g)&\pi(g)\end{bmatrix}+\begin{bmatrix}\pi(g)\zeta(g)&-\pi(g)\zeta(g)\\ -\pi(g)\zeta(g)&\pi(g)\zeta(g)\end{bmatrix}\biggr{)}\] \[=\frac{1}{2}\biggl{[}\begin{matrix}\pi(g)+\rho(g)&\pi(g)-\rho(g )\\ \pi(g)-\rho(g)&\pi(g)+\rho(g)\end{matrix}\biggr{]}.(*)\]

Now, let \(\pi(g)_{ij}\) (resp. \(\rho(g)_{ij}\)) be the unique nonzero element in the \(i\)th row of \(\pi(g)\) (resp. \(\rho(g)\)). Since \(\rho(g)_{ij}=\pm\pi(g)_{ij}\), then exactly one of \(\frac{1}{2}[\pi(g)_{ij}\pm\rho(g)_{ij}]\) is unity, while the
other is zero. Thus, every row of (*) is a one-hot vector. The same argument can be made for the columns, and hence (*) is a bona fide permutation matrix; i.e., \(\pi_{\rho}:G\mapsto\mathcal{P}(2n)\) is a well-defined function.

All that remains is to show \(\pi_{\rho}\) is a homomorphism. We rewrite (*) as

\[\pi_{\rho}(g)=\frac{1}{2}\left(\begin{bmatrix}I_{n}\\ I_{n}\end{bmatrix}\pi(g)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}+\begin{bmatrix} I_{n}\\ -I_{n}\end{bmatrix}\rho(g)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right).\]

Then for \(g,h\in G\), it is easy to verify that

\[\pi_{\rho}(g)\pi_{\rho}(h) =\frac{1}{4}\left(\begin{bmatrix}I_{n}\\ I_{n}\end{bmatrix}\pi(g)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}+\begin{bmatrix} I_{n}\\ -I_{n}\end{bmatrix}\rho(g)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right)\left( \begin{bmatrix}I_{n}\\ I_{n}\end{bmatrix}\pi(h)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}\right.\] \[\quad+\begin{bmatrix}I_{n}\\ -I_{n}\end{bmatrix}\rho(h)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right)\] \[=\frac{1}{4}\left(2\begin{bmatrix}I_{n}\\ I_{n}\end{bmatrix}\pi(g)\pi(h)\begin{bmatrix}I_{n}&I_{n}\end{bmatrix}+0+2 \begin{bmatrix}I_{n}\\ -I_{n}\end{bmatrix}\rho(g)\rho(h)\begin{bmatrix}I_{n}&-I_{n}\end{bmatrix}\right)\] \[=\pi_{\rho}(gh).\]

**(b)**: Using (*) from part (a), we have

\[\pi_{\rho}(g)\begin{bmatrix}W\\ -W\end{bmatrix} =\frac{1}{2}\begin{bmatrix}\pi(g)+\rho(g)&\pi(g)-\rho(g)\\ \pi(g)-\rho(g)&\pi(g)+\rho(g)\end{bmatrix}\begin{bmatrix}W\\ -W\end{bmatrix}\] \[=\frac{1}{2}\begin{bmatrix}\pi(g)W+\rho(g)W-\pi(g)W+\rho(g)W\\ \pi(g)W-\rho(g)W-\pi(g)W-\rho(g)W\end{bmatrix}\] \[=\frac{1}{2}\begin{bmatrix}2\rho(g)W\\ -2\rho(g)W\end{bmatrix}\] \[=\rho(g)\begin{bmatrix}W\\ -W\end{bmatrix}\] \[=\begin{bmatrix}W\\ -W\end{bmatrix}g,\]

proving the claim.

**(c)**: For the forward implication, we prove its contrapositive; suppose \(\rho\) is type 1. Then \(\pi=\rho\) so that (*) implies

\[\pi_{\rho}=\frac{1}{2}\begin{bmatrix}2\pi(g)&0\\ 0&2\pi(g)\end{bmatrix}=\begin{bmatrix}\pi(g)&0\\ 0&\pi(g)\end{bmatrix}.\]

which is clearly reducible.

For the reverse implication, suppose \(\rho\) is type 2. To show \(\pi_{\rho}\) is irreducible, we will show it is transitive on the standard orthonormal basis \(\{\omega_{1},\ldots,\omega_{2n}\}\). Let \(i,j\in\{1,\ldots,2n\}\), and without loss of generality suppose \(i\leq n\).

**Case 1:** Suppose \(j\leq n\). Then \(\omega_{i}\) is just \(\mathbf{e}_{i}\) (the \(i\)th standard orthonormal basis vector of dimension \(n\)) concatenated with \(\bar{\bar{\mathbf{0}}}_{n}\), and similar for \(\omega_{j}\). Now since \(\rho\) is irreducible, then
there exists \(g\in G\) such that \(\rho(g)e_{i}=e_{j}\); note \(\pi(g)e_{i}=e_{j}\) as well. We thus have

\[\pi_{\rho}(g)\omega_{i} =\frac{1}{2}\begin{bmatrix}\pi(g)+\rho(g)&\pi(g)-\rho(g)\\ \pi(g)-\rho(g)&\pi(g)+\rho(g)\end{bmatrix}\begin{bmatrix}e_{i}\\ \bar{0}_{n}\end{bmatrix}\] \[=\frac{1}{2}\begin{bmatrix}\pi(g)e_{i}+\rho(g)e_{i}\\ \pi(g)e_{i}-\rho(g)e_{i}\end{bmatrix}\] \[=\frac{1}{2}\begin{bmatrix}e_{j}\\ e_{j}-e_{j}\end{bmatrix}\] \[=\begin{bmatrix}e_{j}\\ \bar{0}_{n}\end{bmatrix}\] \[=\omega_{j},\]

establishing transitivity in this case.

**Case 2:** Suppose instead \(j>n\). Then \(\omega_{j}\) is the concatenation of \(\bar{0}_{n}\) and \(e_{j-n}\). Since \(\rho\) is irreducible, then there exists \(g\in G\) such that \(\rho(g)e_{i}=-e_{n-j}\). The rest of the proof proceeds in analogy to case 1.

**(d)** For every \(v\in\mathbb{R}^{n}\) and linear rep \(\tau:G\mapsto\mathcal{GL}(n,\mathbb{R})\), define the stabilizer subgroup

\[\operatorname{st}_{\tau}(v)=\{g\in G:\tau(g)v=v\}.\]

Since \(\rho=\rho_{HK}\), then \(\operatorname{st}_{\rho}(e_{1})=K\). Since \(\pi_{\rho}\) is an ordinary perm-rep, then all we must show is \(\operatorname{st}_{\pi_{\rho}}(\omega_{1})=K\) to establish the claim. Similar to part (c), \(\operatorname{st}_{\pi_{\rho}}(\omega_{1})\) is the set of all \(g\in G\) such that

\[\pi_{\rho}(g)\omega_{1} =\omega_{1}\] \[\frac{1}{2}\begin{bmatrix}\pi(g)+\rho(g)&\pi(g)-\rho(g)\\ \pi(g)-\rho(g)&\pi(g)+\rho(g)\end{bmatrix}\begin{bmatrix}e_{1}\\ \bar{0}_{n}\end{bmatrix} =\begin{bmatrix}e_{1}\\ \bar{0}_{n}\end{bmatrix}\] \[\frac{1}{2}\begin{bmatrix}\pi(g)e_{1}+\rho(g)e_{1}\\ \pi(g)e_{1}-\rho(g)e_{1}\end{bmatrix} =\begin{bmatrix}e_{1}\\ \bar{0}_{n}\end{bmatrix}.\]

Taking the difference of the two rows, we obtain \(\rho(g)e_{1}=e_{1}\); hence, \(\operatorname{st}_{\pi_{\rho}}(\omega_{1})=\operatorname{st}_{\rho}(e_{1})= \operatorname{\mathsf{K}}\), completing the proof. 

## Appendix B \(G\)-invariant deep neural networks

### Parameterization redundancies

To understand the inclusion of skip connections as a reparameterization, we rewrite Eq. 2 as

\[f^{(i+1)}(x) =\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+b^{(i)}) \\ \operatorname{ReLU}(f^{(i)}(x))-\operatorname{ReLU}(-f^{(i)}(x))\end{bmatrix}\] \[=\begin{bmatrix}I_{n_{i+1}}&0&0\\ 0&I_{N_{i}}&-I_{N_{i}}\end{bmatrix}\operatorname{ReLU}\left(\begin{bmatrix}W ^{(i)}\\ I_{N_{i}}\\ -I_{N_{i}}\end{bmatrix}f^{(i)}(x)+\begin{bmatrix}b^{(i)}\\ 0\\ 0\end{bmatrix}\right).\]
The outer matrix in the last equation can be combined with the matrix in the next layer; the result is a DNN having the same depth as the original--and representing the same input-output function--but with no skip connections, as they have been transformed into additional ReLU neurons.

[Proof of Prop. 3] We will show \(W^{(i+1)}f^{(i+1)}(x)+b^{(i+1)}\) is invariant under the transformation. The function \(f^{(i+1)}\) transforms as

\[f^{(i+1)}(x) \rightarrow\begin{bmatrix}\text{ReLU}(CPZW^{(i)}f^{(1)}(x)+CPZb^ {(i)})\\ f^{(i)}(x)\end{bmatrix}\] \[=\begin{bmatrix}CP&0\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\text{ReLU}(Z(W^{(i)}f^{(1)}(x)+b^{(i)} )\\ f^{(i)}(x)\end{bmatrix}\] \[=\begin{bmatrix}CP&0\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\begin{bmatrix}\text{ReLU}(W^{(i)}f^{( 1)}(x)+b^{(1)})\\ f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\mathcal{H}(-Z)(W^{(i)}f^{(1)}(x)+b^{( 1)})\\ 0\end{bmatrix}\end{bmatrix}\] \[=\begin{bmatrix}CP&0\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H} (-Z)W^{(i)}\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\text{ReLU}(W^{(i)}f^{(1)}(x)+b^{(1)})\\ f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\mathcal{H}(-Z)b^{(1)}\\ 0\end{bmatrix}\end{bmatrix}\] \[=\begin{bmatrix}CP&0\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H} (-Z)W^{(1)}\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\text{ReLU}(W^{(i)}f^{(1)}(x)+b^{(1)})\\ f^{(i)}(x)\end{bmatrix}\] \[\quad-\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H}(-Z)W^{(1)}\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\mathcal{H}(-Z)b^{(1)}\\ 0\end{bmatrix}\end{bmatrix}\] \[=\begin{bmatrix}CP&0\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\mathcal{H}(-Z)W^{(i)}\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}\begin{bmatrix}\text{ReLU}(W^{(i)}f^{( 1)}(x)+b^{(1)})\\ f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\mathcal{H}(-Z)b^{(1)}\\ 0\end{bmatrix}\end{bmatrix}\] \[=\begin{bmatrix}CP&-CP\mathcal{H}(-Z)W^{(1)}\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}f^{(i+1)}(x)-\begin{bmatrix}\mathcal{H} (-Z)b^{(1)}\\ 0\end{bmatrix}\end{bmatrix}.\]

We thus have

\[W^{(i+1)}f^{(i+1)}(x)+b^{(i+1)} \rightarrow W^{(i+1)}\begin{bmatrix}(CP)^{-1}&\mathcal{H}(-Z)W^{(i)}\\ 0&I_{N_{i}}\end{bmatrix}\begin{bmatrix}CP&-CP\mathcal{H}(-Z)W^{(i)}\\ 0&I_{N_{i}}\end{bmatrix}(f^{(i+1)}(x)\] \[\quad-\begin{bmatrix}\mathcal{H}(-Z)b^{(1)}\\ 0\end{bmatrix}\end{bmatrix}+b^{(i+1)}+W^{(i+1)}\begin{bmatrix}\mathcal{H}(-Z)b^ {(1)}\\ 0\end{bmatrix}\] \[=W^{(i+1)}\begin{pmatrix}f^{(i+1)}(x)-\begin{bmatrix}\mathcal{H} (-Z)b^{(1)}\\ 0\end{bmatrix}\end{pmatrix}+W^{(i+1)}\begin{bmatrix}\mathcal{H}(-Z)b^{(1)}\\ 0\end{bmatrix}+b^{(i+1)}\] \[=W^{(i+1)}f^{(i+1)}(x)+b^{(i+1)}.\]

### \(G\)-invariant architectures

[Proof of Lemma 4] Since \(f^{(1)}\) and \(\psi^{(1)}\) are both the identity functions, then the claim is immediate for \(i=1\). Suppose the claim is true for some \(i\in\{1,\ldots,d-1\}\). We
have for all \(g\in G\) and \(x\in\mathbb{R}^{m}\):

\[f^{(i+1)}(gx)= \begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(gx)+b^{(i)})\\ f^{(i)}(gx)\end{bmatrix}\] \[= \begin{bmatrix}\operatorname{ReLU}(W^{(i)}\psi^{(i)}(g)f^{(i)}(x)+ b^{(i)})\\ \psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}\] \[= \begin{bmatrix}\operatorname{ReLU}(\rho^{(i)}(g)W^{(i)}f^{(i)}(x)+ b^{(i)})\\ \psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}\] \[= \begin{bmatrix}\operatorname{ReLU}(\rho^{(i)}(g)W^{(i)}f^{(i)}(x)+ \rho^{(i)}(g)b^{(i)})\\ \psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}\] \[= \begin{bmatrix}\pi^{(i)}(g)\operatorname{ReLU}(\zeta^{(i)}(g)(W^{ (i)}f^{(i)}(x)+b^{(i)}))\\ \psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}\] \[= \begin{bmatrix}\pi^{(i)}(g)\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+ b^{(i)})\\ \psi^{(i)}(g)f^{(i)}(x)\end{bmatrix}-\begin{bmatrix}\pi^{(i)}(g)\mathcal{H}(- \zeta^{(i)}(g))W^{(i)}f^{(i)}(x)\\ 0\end{bmatrix}\] \[-\begin{bmatrix}\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))b^{(i)} \\ 0\end{bmatrix}\] \[= \begin{bmatrix}\pi^{(i)}(g)&-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)} (g))W^{(i)}\\ 0&I_{N_{i}}\end{bmatrix}f^{(i+1)}(x)+\begin{bmatrix}-\pi^{(i)}(g)\mathcal{H}(- \zeta^{(i)}(g))b^{(i)}\\ 0\end{bmatrix}.\]

Note that

\[-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))= -\frac{1}{2}\pi^{(i)}(g)(I_{n_{i+1}}-\zeta^{(i)}(g))\] \[= \frac{1}{2}\pi^{(i)}(g)(\zeta^{(i)}(g)-I_{n_{i+1}})\] \[= \frac{1}{2}(\rho^{(i)}(g)-\pi^{(i)}(g)).\]

We thus have

\[-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))W^{(i)} =\frac{1}{2}(\rho^{(i)}(g)-\pi^{(i)}(g))W^{(i)}\] \[=\frac{1}{2}(\rho^{(i)}(g)W^{(i)}-\pi^{(i)}(g)W^{(i)})\] \[=\frac{1}{2}(W^{(i)}\psi^{(i)}(g)-\pi^{(i)}(g)W^{(i)}).\]

For the bias term, let \(\rho^{(i)}=\rho^{(i)}_{1}\oplus\cdots\oplus\rho^{(i)}_{k}\) be the decomposition of \(\rho^{(i)}\) into irreducibles; decompose \(\pi^{(i)}\) and \(b^{(i)}\) correspondingly. Then we have

\[-\pi^{(i)}(g)\mathcal{H}(-\zeta^{(i)}(g))b^{(i)} =\frac{1}{2}(\rho^{(i)}(g)-\pi^{(i)}(g))b^{(i)}\] \[=\frac{1}{2}\bigoplus_{j=1}^{k}(\rho^{(i)}_{j}(g)-\pi^{(i)}_{j}(g ))b^{(i)}_{j}.\]
If \(\rho_{j}^{(i)}\) is type 1, then \(\rho_{j}^{(i)}=\pi_{j}^{(i)}\) so that the \(j\)th term in the above direct sum is zero. On the other hand, if \(\rho_{j}^{(i)}\) is type 2, then \(\rho_{j}^{(i)}(g)b_{j}^{(i)}=b_{j}^{(i)}\) implies \(b_{j}^{(i)}=0\), so that again the \(j\)th summand is zero. Therefore, \(-\pi^{(i)}(g)\pi(-\zeta^{(i)}(g))b^{(i)}=0\forall g\in G\). We thus have

\[f^{(i+1)}(gx)= \begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}\psi^{(i)}(g)-\pi^ {(i)}(g)W^{(i)})\\ 0&I_{N_{i}}\end{bmatrix}f^{(i+1)}(x)+0\] \[= \psi^{(i+1)}(g)f^{(i+1)}(x).\]

The conclusion follows by induction.

[Proof of Lemma 5] We will verify that \(\psi^{(i+1)}\) defined as claimed satisfies the recursion in Lemma 4. For \(i=1\), we have

\[\psi^{(2)}(g)= \ A^{(1)-1}\Pi^{(1)}(g)A^{(1)}\] \[= \begin{bmatrix}I_{I_{2}}&-\frac{1}{2}W^{(1)}\\ 0&I_{n_{1}}\end{bmatrix}^{-1}\begin{bmatrix}\pi^{(1)}(g)&0\\ 0&g\end{bmatrix}\begin{bmatrix}I_{I_{2}}&-\frac{1}{2}W^{(1)}\\ 0&I_{n_{1}}\end{bmatrix}\] \[= \begin{bmatrix}I_{I_{2}}&\frac{1}{2}W^{(1)}\\ 0&I_{n_{1}}\end{bmatrix}\begin{bmatrix}\pi^{(1)}(g)&0\\ 0&g\end{bmatrix}\begin{bmatrix}I_{I_{2}}&-\frac{1}{2}W^{(1)}\\ 0&I_{n_{1}}\end{bmatrix}\] \[= \begin{bmatrix}\pi^{(1)}(g)&\frac{1}{2}(W^{(1)}g-\pi^{(1)}(g)W^{ (1)})\\ 0&g\end{bmatrix}\] \[= \begin{bmatrix}\pi^{(1)}(g)&\frac{1}{2}(W^{(1)}\psi^{(1)}(g)-\pi^ {(1)}(g)W^{(1)})\\ 0&\psi^{(1)}(g)\end{bmatrix},\]

which indeed agrees with Lemma 4.

Now suppose the claim holds for some \(i\in\{2,\ldots,d-1\}\). Observe that

\[A^{(i)}= \begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\ 0&A^{(i-1)}\end{bmatrix}\] \[\Pi^{(i)}(g)= \begin{bmatrix}\pi^{(i)}(g)&0\\ 0&\Pi^{(i-1)}(g)\end{bmatrix}.\]

We thus have

\[\psi^{(i+1)}(g)= \ A^{(i)-1}\Pi^{(i)}(g)A^{(i)}\] \[= \begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\ 0&A^{(i-1)}\end{bmatrix}^{-1}\begin{bmatrix}\pi^{(i)}(g)&0\\ 0&\Pi^{(i-1)}(g)\end{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\ 0&A^{(i-1)}\end{bmatrix}\] \[= \begin{bmatrix}I_{n_{i+1}}&\frac{1}{2}W^{(i)}A^{(i-1)-1}\\ 0&A^{(i-1)-1}\end{bmatrix}\begin{bmatrix}\pi^{(i)}(g)&0\\ 0&\Pi^{(i-1)}(g)\end{bmatrix}\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\ 0&A^{(i-1)}\end{bmatrix}\] \[= \begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}A^{(i-1)-1}\Pi^{(i -1)}(g)A^{(i-1)}-\pi^{(i)}(g)W^{(i)})\\ 0&A^{(i-1)-1}\Pi^{(i-1)}(g)A^{(i-1)}\end{bmatrix}\] \[= \begin{bmatrix}\pi^{(i)}(g)&\frac{1}{2}(W^{(i)}\psi^{(i)}(g)-\pi^ {(i)}(g)W^{(i)})\\ 0&\psi^{(i)}(g)\end{bmatrix}.\]
The conclusion follows by induction.

**Proof** [Proof of Thm. 6] **(a)** By Lemmas 4-5, we have

\[\rho^{(i)}(g)W^{(i)} =W^{(i)}\psi^{(i)}(g)\] \[\rho^{(i)}(g)W^{(i)} =W^{(i)}A^{(i-1)-1}\mathsf{\Gamma}^{(i-1)}(g)A^{(i-1)}\] \[\rho^{(i)}(g)W^{(i)}A^{(i-1)-1} =W^{(i)}A^{(i-1)-1}\mathsf{\Gamma}^{(i-1)}(g).\]

Let \(V^{(i)}=W^{(i)}A^{(i-1)-1}\). Thus, \(W^{(i)}=V^{(i)}A^{(i-1)}\).

All that is left is to establish equivariance of the blocks of \(V^{(i)}\). We have

\[\rho^{(i)}(g)V^{(i)} =\rho^{(i)}(g)W^{(i)}A^{(i-1)-1}\] \[=W^{(i)}\psi^{(i)}(g)A^{(i-1)-1}\] \[=W^{(i)}A^{(i-1)-1}\mathsf{\Gamma}^{(i-1)}(g)A^{(i-1)}A^{(i-1)-1}\] \[=V^{(i)}\mathsf{\Gamma}^{(i-1)}(g).\]

Since \(\mathsf{\Gamma}^{(i-1)}(g)\) is a block-diagonal matrix, then blockwise equivariance follows.

**(b)** By part (a), we have

\[g^{(i)}(\chi) =W^{(i)}f^{(i)}(\chi)\] \[=V^{(i)}A^{(i-1)}f^{(i)}(\chi)\] \[=V^{(i)}h^{(i)}(\chi).\]

To establish the recursion for \(h^{(i)}\), first observe that \(A^{(i)}\) satisfies the recursion

\[A^{(i)}=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\ 0&A^{(i-1)}\end{bmatrix}.\]

We thus have

\[h^{(i+1)}(\chi) =A^{(i)}f^{(i+1)}(\chi)\] \[=\begin{bmatrix}I_{n_{i+1}}&-\frac{1}{2}W^{(i)}\\ 0&A^{(i-1)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}( \chi)+b^{(i)})\\ f^{(i)}(\chi)\end{bmatrix}\] \[=\begin{bmatrix}\operatorname{ReLU}(W^{(i)}f^{(i)}(\chi)+b^{(i)} )-\frac{1}{2}W^{(i)}f^{(i)}(\chi)\\ A^{(i-1)}f^{(i)}(\chi)\end{bmatrix}\] \[=\begin{bmatrix}\operatorname{ReLU}(g^{(i)}(\chi)+b^{(i)})- \frac{1}{2}g^{(i)}(\chi)\\ h^{(i)}(\chi)\end{bmatrix},\]

which completes the proof.
### Admissible architectures

#### b.3.1 The \(\theta\) function

The following proposition establishes the invariance and equivariance of the function \(\theta\) with respect to certain conjugations.

**Proposition 8**: _The function \(\theta\) satisfies the following properties:_

1. _For every_ \(A\in\mathcal{P}(|G/|)\)_, define the ordinary perm-rep_ \(\pi_{J}^{A}(g)=A\pi_{J}(g)A^{-1}\)_. Then_ \(\theta(\cdot,\cdot,J)\) _is invariant under the conjugation_ \(\pi_{J}\mapsto\pi_{J}^{A}\)_._
2. \(\theta(H,K,gJg^{-1})=\theta(H,K,J)\forall g\in G\)_._
3. \(\theta(gHg^{-1},gKg^{-1},J)=g\theta(H,K,J)g^{-1}\)_._

**Proof (a)** For brevity, let \(\kappa=|H:K|-1\). Define the function \(\theta^{A}\) in identical fashion to \(\theta\), but replace \(\eta_{J}\) with \(\eta_{J}^{A}\). We wish to prove \(\theta^{A}=\theta\). Since the map \(\Gamma\mapsto\rho_{\Gamma}\) from finite orthogonal matrix groups to orthogonal projection operators is equivariant with respect to conjugation, then we have

\[\theta^{A}(H,K,J) =\{g\in G:\pi_{J}^{A}(g)(P_{\pi_{J}^{A}(K)}-\kappa P_{\pi_{J}^{A}( H)})=P_{\pi_{J}^{A}(K)}-\kappa P_{\pi_{J}^{A}(H)}\}\] \[=\{g\in G:A\pi_{J}(g)A^{-1}(P_{A\pi_{J}(K)A^{-1}}-\kappa P_{A\pi_ {J}(H)A^{-1}})=P_{A\pi_{J}(K)A^{-1}}-\kappa P_{A\pi_{J}(H)A^{-1}}\}\] \[=\{g\in G:A\pi_{J}(g)A^{-1}(AP_{\pi_{J}(K)}A^{-1}-\kappa AP_{\pi_ {J}(H)}A^{-1})=AP_{\pi_{J}(K)}A^{-1}\] \[\quad-\kappa AP_{\pi_{J}(H)}A^{-1}\}\] \[=\{g\in G:\pi_{J}(g)(P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)})=P_{\pi_ {J}(K)}-\kappa P_{\pi_{J}(H)}\}\] \[=\theta(H,K,J).\]

**(b)** The theory of ordinary perm-irreps and their correspondence to group action on cosets is well-understood (Burnside, 1911; Bouc, 2000), and it is known that the conjugation of \(J\) in \(\eta_{J}\) is equivalent to the conjugation of \(\eta_{J}\) itself. The claim thus follows by part (a).

**(c)** Let \(\alpha\in G\). We will show \(\theta(\alpha H\alpha^{-1},\alpha K\alpha^{-1},J)=\theta(H,K,J)\). Note \(\kappa=|H:K|-1\) is invariant under the conjugation of \((H,K)\) by \(\alpha\). Also note \(\eta_{J}(\alpha H\alpha^{-1})=\eta_{J}(\alpha)\eta_{J}(H)\eta_{J}(\alpha)^{-1}\) and similar for \(K\). Letting \(A=\eta(\alpha)\) and proceeding in analogy to part (a), we have

\[\theta(\alpha H\alpha^{-1},\alpha K\alpha^{-1},J) =\{g\in G:\pi_{J}(g)(P_{\pi_{J}(\alpha K\alpha^{-1})}-\kappa P_{ \pi_{J}(\alpha H\alpha^{-1})})=P_{\pi_{J}(\alpha K\alpha^{-1})}\] \[\quad-\kappa P_{\eta_{J}(\alpha H\alpha^{-1})}\}\] \[=\{g\in G:\pi_{J}(g)(P_{\pi_{J}^{A}(K)}-\kappa P_{\pi_{J}^{A}(H)} )=P_{\pi_{J}^{A}(K)}-\kappa P_{\pi_{J}^{A}(H)}\}\] \[=\{g\in G:\pi_{J}(g)(AP_{\eta_{J}(K)}A^{-1}-\kappa AP_{\eta_{J}(H) }A^{-1})=AP_{\eta_{J}(K)}A^{-1}\] \[\quad-\kappa AP_{\pi_{J}(H)}A^{-1}\}\] \[=\{g\in G:A^{-1}\pi_{J}(g)A(P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)} )=P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)}\}\] \[=\{g\in G:\pi_{J}(\alpha^{-1}g\alpha)(P_{\pi_{J}(K)}-\kappa P_{\pi _{J}(H)})=P_{\pi_{J}(K)}-\kappa P_{\pi_{J}(H)}\}.\]
By the change of variables \(g\to aga^{-1}\), we have

\[\theta(aHa^{-1},aKa^{-1},J) =\{aga^{-1}\in G:\eta_{j}(g)(P_{\eta_{j}(K)}-\kappa P_{\eta_{j}(H)})= P_{\eta_{j}(K)}-\kappa P_{\eta_{j}(H)}\}\] \[=\alpha\{g\in G:\eta_{j}(g)(P_{\eta_{j}(K)}-\kappa P_{\eta_{j}(H)})= P_{\eta_{j}(K)}-\kappa P_{\eta_{j}(H)}\}\alpha^{-1}\] \[=\alpha\theta(H,K,J)\alpha^{-1},\]

establishing the claim.

```
1:function\(\theta(H,K,J)\)
2:def\(\eta:K\setminus G/J\mapsto\text{power}(G/J)\) by
3:\(\eta(KxJ)=\{kxJ\in G/J:k(K\cap xJx^{-1})\in K/(K\cap xJx^{-1})\}\)
4:if\(|H:K|=2\)then
5:let\(h\in H\setminus K\)
6:\(S\leftarrow\{KxJ\in K\setminus G/J:hx\in KxJ\}\)
7:else
8:\(S\leftarrow\emptyset\)
9:if\(S=\emptyset\)then
10:\(T\leftarrow\{\eta(KxJ):KxJ\in K\setminus G/J\}\)
11:else
12:\(T\leftarrow\{\eta(KxJ):KxJ\in(K\setminus G/J)\setminus S\}\cup\{\bigcup_{KxJ \in S}\eta(KxJ)\}\)
13:return\(\text{st}_{G}(T)\)
```

**Algorithm 1** Implementation of the function \(\theta\) that exploits existing functions in GAP.

Algorithm 1 gives the pseudocode for an implementation of the function \(\theta\) that can be accomplished in the GAP language (GAP) for computational group theory. Although the definition of the \(\theta\) function involves orthogonal projection operators, Alg. 1 completely circumvents these operators by taking a pure group-theoretic approach in terms of double cosets. The following proposition verifies that Alg. 1 is a correct implementation.

**Proposition 9**: _Algorithm 1 correctly implements the function \(\theta\)._

Observe that the function \(\eta\) in Alg. 1 sends each double coset \(KxJ\in K\setminus G/J\) to the set of cosets in \(G/J\) whose disjoint union is \(KxJ\).

Let \(H,K,J\leq G\) such that \(K\leq H\) and \(|H:K|\leq 2\). Let \(w\in\text{ran}(P_{\eta(K)}-(|H:K|-1)P_{\eta(H)})\). We regard \(w\) as a function \(w:G/J\mapsto\mathbb{R}\). Since \(w\in\text{ran}(P_{K})\), then \(w\) is \(K\)-invariant in the sense that \(w(KxJ)=w(xJ)\) for all \(k\in K\) and \(xJ\in G/J\). Thus, \(w\) is constant over the set \(\eta(KxJ)\) for every \(KxJ\in K\setminus G/J\).

If \(|H:K|=2\), then let \(h\in H\setminus K\). Since \(w\in\text{ran}(P_{\eta(K)}-P_{\eta(H)})\), then \(w(hKxJ)=-w(KxJ)\) for every \(KxJ\in K\setminus G/J\). Thus, if \(hKxJ=KxJ\), then \(w(KxJ)=0\). Since \(K\leq H\), then \(hKxJ=KxJ\) is equivalent to \(KhxJ=KxJ\), or just \(hx\in KxJ\). We thus have the constraint

\[w(KxJ)=0\forall KxJ\in K\setminus G/J\mid hx\in KxJ.\]
Now select \(w\) such that it takes a different nonzero value over each \(\eta(KxJ)\) for all \(KxJ\in K\setminus G/J\) such that, if \(|H:K|=2\), then \(hx\notin KxJ\). Then

\[\theta(H,K,J) =\operatorname{st}_{G}(P_{\eta(K)}-(|H:K|-1)P_{\eta(\eta)})\] \[=\operatorname{st}_{G}(w)\] \[=\{g\in G:w(gKxJ)=w(KxJ)\forall KxJ\in K\setminus G/J\}.\]

This means \(\theta(H,K,J)\) is exactly the subgroup of \(G\) that leaves the level sets of \(w\) invariant. Observe, however, that the sets in the collection \(T\) in Alg. 1 are exactly the level sets of \(w\), and hence \(\theta(H,K,J)=\operatorname{st}_{G}(T)\). 

#### b.3.2 The \(\phi\) function

[Proof of Prop. 7] The necessity of condition (2) is only because if \(H^{(1)}_{j}=G\) for any \(j\), then at least one row \(w\) of \(W^{(1)}\) satisfies \(w\in\operatorname{ran}(P_{G})\) by Thm. 4a of Agrawal and Ostrowski (2022). For \(w\) to be nonzero, we thus require \(P_{G}\neq 0\). We assume condition (2) to be satisfied for the remainder of the proof.

Before proving the claim itself, we first derive a closed-form expression for \(\phi^{(i+1)}\). For notational convenience, for every \(K\leq H\leq G\), \(|H:K|\leq 2\), and linear rep \(\tau:G\mapsto\mathcal{GL}(n,\mathbb{R})\), define

\[\theta(H,K;\tau)=\{g\in G:\tau(g)(P_{\tau(K)}-(|H:K|-1)P_{\tau(H)})=P_{\tau(K)} -(|H:K|-1)P_{\tau(H)}\}.\]

Thus, \(\theta(H,K,J)\) can be equivalently written as \(\theta(H,K;\eta)\). For two reps \(\tau_{1}\) and \(\tau_{2}\), observe that \(P_{\tau_{1}\in\tau_{2}}=P_{\tau_{1}}\oplus P_{\tau_{2}}\) and hence

\[\theta(H,K;\tau_{1}\oplus\tau_{2})=\theta(H,K;\tau_{1})\cap\theta(H,K;\tau_{2}).\]

This property extends to more than two reps in the obvious way. With this notation, and recalling the identity rep \(\pi^{(0)}:G\mapsto G\), the function \(\phi^{(i+1)}\) can be rewritten as

\[\phi^{(i+1)}(H,K) =\operatorname{st}_{G}(P_{K}-(|H:K|-1)P_{H})\cap\bigcap_{j=1}^{i }\bigcap_{r=1}^{r^{(l)}}\theta(H,K,H^{(l)}_{r})\] \[=\theta(H,K;\pi^{(0)})\cap\bigcap_{j=1}^{i}\bigcap_{r=1}^{r^{(l)} }\theta(H,K;\pi^{(l)}_{r})\] \[=\theta(H,K;\pi^{(0)})\cap\theta\left(H,K;\bigoplus_{j=1}^{i} \bigoplus_{r=1}^{r^{(l)}}\pi^{(l)}_{r}\right)\] \[=\theta\left(H,K;\pi^{(0)}\oplus\bigoplus_{j=1}^{i}\pi^{(l)}\right)\] \[=\theta\left(H,K;\bigoplus_{j=0}^{i}\pi^{(l)}\right)\] \[=\theta(H,K;\Pi^{(l)}).\]
This is explicitly

\[\phi^{(i+1)}(H,K) =\{g\in G:\Pi^{(i)}(g)(P_{\Pi^{(0)}(K)}-(|H:K|-1)P_{\Pi^{(0)}(H)})=P_{ \Pi^{(0)}(K)}\] \[\qquad-(|H:K|-1)P_{\Pi^{(0)}(H)}\},\]

and it is equivalent to

\[\phi^{(i+1)}(H,K) =\{g\in G:\Pi^{(i)}(g)(P_{\Pi^{(0)}(K)}-(|\Pi^{(i)}(H):\Pi^{(i)}( K)|-1)P_{\Pi^{(0)}(H)})=P_{\Pi^{(0)}(K)}\] \[\qquad-(|\Pi^{(i)}(H):\Pi^{(i)}(K)|-1)P_{\Pi^{(0)}(H)}\}.\] (*)

To see that \(|\Pi^{(i)}(H):\Pi^{(i)}(K)|=|H:K|\), by the First Isomorphism Theorem we have

\[|\Pi^{(i)}(H):\Pi^{(i)}(K)|=\frac{|H|/|H\cap\ker(\Pi^{(0)})|}{|K|/|K\cap\ker( \Pi^{(0)})|}.\]

Since \(\Pi^{(i)}\) includes in its direct sum decomposition the identity rep \(\pi^{(0)}\), then \(\ker(\Pi^{(i)})\) must be trivial, and so the above expression reduces to \(|H|/|K|=|H:K|\).

We finally prove the claim. By definition, the \(G\)-DNN architecture \(\{\rho^{(1)},\ldots,\rho^{(d)}\}\) is admissible iff each row of \(W^{(i)}\) is nonzero and no two rows of \([W^{(i)}\mid b^{(i)}]\) are parallel, for \(i\in\{1,\ldots,d\}\). By Thm. 6 (a), since \(W^{(i)}=V^{(i)}A^{(i-1)}\), then we obtain an equivalent definition if we replace \(W^{(i)}\) with \(V^{(i)}\). Let \(V^{(i)}_{(i)}\) be the submatrix comprising the rows (and all columns) of \(V^{(i)}\) that together transform by \(\rho^{(i)}_{j}\):

\[\rho^{(i)}_{j}(g)V^{(i)}_{(i)}=V^{(i)}_{(i)}\Pi^{(i-1)}(g)\forall g\in G.\]

(We include the parentheses in the subscript of \(V^{(i)}_{(i)}\) to distinguish it from \(V^{(i)}_{j}\) appearing in Thm. 6 (a)). Then Thm. 4a of Agrawal and Ostrowski (2022) implies we have an admissible architecture (specifically, that the rows of \(V^{(i)}_{(j)}\) are nonzero and no two rows of the corresponding augmented weight matrix are parallel) iff

\[\operatorname{St}_{\Pi^{(i-1)}(G)}(P_{\Pi^{(i-1)}(K^{(i)}_{j})}-(|\Pi^{(i-1)} (H^{(i)}_{j}):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{\Pi^{(i-1)}(H^{(i)}_{j})})=\Pi^{ (i-1)}(K^{(i)}_{j}),\]

or equivalently,

\[(\Pi^{(i-1)})^{-1}[\operatorname{st}_{\Pi^{(i-1)}(G)}(P_{\Pi^{(i-1)}(K^{(i)}_{ j})}-(|\Pi^{(i-1)}(H^{(i)}_{j}):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{\Pi^{(i-1)}(H^{(i )}_{j})})=K^{(i)}_{j}\]

\[\{g\in G:\Pi^{(i-1)}(g)(P_{\Pi^{(i-1)}(K^{(i)}_{j})}-(|\Pi^{(i-1)}(H^{(i)}_{j} ):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{\Pi^{(i-1)}(H^{(i)}_{j})})=P_{\Pi^{(i-1)}(K^{( i)}_{j})}\] \[\quad-(|\Pi^{(i-1)}(H^{(i)}_{j}):\Pi^{(i-1)}(K^{(i)}_{j})|-1)P_{ \Pi^{(i-1)}(H^{(i)}_{j})}=K^{(i)}_{j}.\]

Recalling (*), we recognize the last equation as nothing but \(\phi^{(i)}(H^{(i)}_{j},K^{(i)}_{j})=K^{(i)}_{j}\), there proving that condition (1) is (together with condition (2)) is equivalent to admissibility.
### Additional remarks

The following proposition establishes the compatibility of batchnorm with \(\mathsf{G}\)-DNNs.

The addition of batchnorm immediately after any ReLU layer in a \(\mathsf{G}\)-DNN preserves \(\mathsf{G}\)-invariance of the network.

Suppose we apply batchnorm immediately after the \(i\)th ReLU layer of the \(\mathsf{G}\)-DNN \(\mathbf{f}\), for some \(i\in\{1,\ldots,\mathbf{d-1}\}\). Then the activations \(\mathbf{r^{(i)}(x)=\operatorname{ReLU}(W^{(i)}f^{(i)}(x)+\mathbf{b}^{(i)})\) of the \(i\)th ReLU layer transform as

\[\mathbf{r^{(i)}(x)\to\gamma\left(\frac{\mathbf{r^{(i)}(x)-\mu\mathbb{1}}}{\sigma+\mathbf{ \varepsilon}}\right)+\beta\mathbb{1}},\]

where \(\mu\geq 0\), \(\sigma\geq 0\), \(\mathbf{\varepsilon}>0\), \(\gamma\), and \(\beta\) are all scalars. For each \(i\in\{1,\ldots,\mathbf{d}\}\), let \(W^{(i)}_{i}\) and \(V^{(i)}_{i}\) be the blocks comprising the first \(n_{i}\) columns of \(W^{(i)}\) and \(V^{(i)}\) respectively; these represent the weights of the \(i\)th layer without the skip connections. Then the above affine transformation of \(\mathbf{r^{(i)}(x)}\) is equivalent to the transformation

\[W^{(i+1)}_{i+1} \to CW^{(i+1)}_{i+1}\] \[\mathbf{b^{(i+1)}} \to\mathbf{b^{(i+1)}}+\mathbf{D}W^{(i+1)}_{i+1}\mathbb{1},\]

where

\[C =\frac{\gamma}{\sigma+\mathbf{\varepsilon}}\] \[D =\beta-\frac{\gamma\mu}{\sigma+\mathbf{\varepsilon}}.\]

By Thm. 3.2 (a), \(W^{(i+1)}=V^{(i+1)}\mathbf{A^{(i)}}\). Since \(\mathbf{A^{(i)}}\) is upper block-triangular with the top left block \(\mathbf{I}_{n_{i+1}}\), then \(W^{(i+1)}_{i+1}=V^{(i+1)}_{i+1}\). By the above transformation of \(W^{(i+1)}_{i+1}\) under batchnorm, \(V^{(i+1)}_{i+1}\) also transforms only by the scalar factor \(C\), and hence it remains equivariant as in Thm. 3.3.

All that remains is to show the bias \(\mathbf{b^{(i+1)}}\) satisfies the sufficient condition in Lemma 4 even after the batchnorm transformation, and this will establish \(\mathsf{G}\)-invariance of the network with batchnorm.

**Case 1:** Suppose \(\mathbf{\rho^{(i+1)}}\) is type 1 irreducible. Then Lemma 4 implies \(\mathbf{b^{(i+1)}}\) is parallel to \(\mathbb{1}\). Under batchnorm, \(\mathbf{b^{(i+1)}}\) transforms by the addition of \(\mathbf{D}V^{(i+1)}_{i+1}\mathbb{1}\) and thus remains parallel to \(\mathbb{1}\). The claim follows by Lemma 4.

**Case 2:** Suppose \(\mathbf{\rho^{(i+1)}}\) is type 2 irreducible. Then Lemma 4 implies \(\mathbf{b^{(i+1)}=0}\). Under batchnorm, the bias thus transforms to \(\mathbf{0+D}V^{(i+1)}_{i+1}\mathbb{1}\). It turns out, however, that \(V^{(i+1)}_{i+1}\mathbb{1}=0\); to see this, by Thm. 3.2 (a), we have

\[\mathbf{\rho^{(i+1)}(g)V^{(i+1)}_{i+1}=V^{(i+1)}_{i+1}\pi^{(i)}(g)\forall g\in G.}\]
Since \(\mathbf{i\geq 1}\) so that \(\pi^{(\mathbf{i})}\) is type 1, then without loss of generality, by selecting an appropriate basis, we assume \(\pi^{(\mathbf{i})}\) is an ordinary perm-irrep. Averaging both sides over all \(\mathbf{g\in G}\), we obtain

\[P_{\mathbf{\rho}(i+1)}V_{\mathbf{i+1}}^{(\mathbf{i+1})}=V_{\mathbf{i+1}}^{(\mathbf{i+1})}P_{\pi^{( 0)}}.\]

Since \(\mathbf{\rho^{(i+1)}}\) is type 2, then its only fixed point is the zero vector, and hence the orthogonal projection operator \(P_{\mathbf{\rho}^{(i+1)}}\) is itself zero. Moreover, since \(\pi^{(\mathbf{i})}\) is an ordinary perm-irrep and since \(\mathbf{1}\) is fixed under all permutations, then it is fixed under the orthogonal projection operator \(P_{\pi^{(0)}}\) as well- hence \(V_{\mathbf{i+1}}^{(\mathbf{i+1})}\mathbf{1}=\mathbf{0}\).

**Case 3:** Suppose \(\mathbf{\rho^{(i+1)}}\) is reducible. Then decompose it into type1 and type 2 irreps and apply Cases 1-2 separately to each irrep. 

The extension of Prop. 10 to multiple channels is trivial. Batchnorm is typically applied independently to each channel. Thus, if the ReLU activations \(r^{(\mathbf{i})}(\mathbf{\chi})\) had \(\mathbf{c}\) channels (which could be achieved by having \(\mathbf{c}\) copies of every irrep in \(\mathbf{\rho^{(\mathbf{i})}}\)), then the variables \(\mathbf{\mu}\), \(\mathbf{\sigma}\), \(\mathbf{\gamma}\), and \(\mathbf{\beta}\) would be \(\mathbf{c}\)-dimensional vectors. The proof would then proceed by selecting a single arbitrary channel.

## Appendix C Examples

### Binary multiplication

**Proof** [Proof of Ex. 1] **(a)** For \(\mathbf{x_{1},x_{2}\in\{-1,1\}}\), it can be verified by hand that

\[\begin{array}{l}\mathbf{x_{1}x_{2}=[1-1]ReLU\left(\begin{bmatrix}1&1\\ 1&-1\end{bmatrix}[x_{1}]\\ \mathbf{x_{2}}\end{bmatrix}\right)-\mathbf{x_{2}}\\ =[1-10-1]\left[\begin{bmatrix}\ReLU\left(\begin{bmatrix}1&1\\ 1&-1\end{bmatrix}[x_{1}]\\ \mathbf{x_{1}}\end{bmatrix}\right)\right].(*)\end{array}\]

We can extend this to the product of more than two elements as follows: For \(i\in\{1,\ldots,d\}\), define the block-diagonal matrices

\[\begin{array}{l}\mathbf{A}^{(i)}=I_{m/2^{i}}[1-1]\\ \mathbf{B}^{(i)}=I_{m/2^{i}}[0-1]\\ \mathbf{C}^{(i)}=I_{m/2^{i}}\left[\begin{bmatrix}1&1\\ 1&-1\end{bmatrix}\right]\end{array}\]

and define the functions \(\mathbf{\rho^{(\mathbf{i})}}:\mathcal{X}\mapsto\{-1,1\}^{m/2^{i}}\) by

\[\begin{array}{l}\mathbf{\rho^{(\mathbf{1})}}(\mathbf{x})=\mathbf{A}^{(1)}\mathbf{x}\\ \mathbf{\rho^{(\mathbf{i})}}(\mathbf{x})=[\mathbf{A}^{(1)}\quad\mathbf{B}^{(\mathbf{0})}]\left[ \begin{bmatrix}\ReLU(C^{(\mathbf{i})}\mathbf{\rho}^{(i-1)}(\mathbf{x}))\\ \mathbf{\rho}^{(i-1)}(\mathbf{x})\end{bmatrix}\forall i\in\{2,\ldots,d\}.(**)\end{array}\]
The function \(\rho^{(1)}\) maps each pair of elements \((x_{2i-1},x_{2i})\) in the input \(x\) to \(x_{2i-1}-x_{2i}\in\{-1,1\}\). Then \(\rho^{(i)}\) (1) partitions \(\rho^{(1)}(x)\) into blocks, each of two elements; (2) takes the product of each pair of elements using (*); (3) iterates this procedure \(i-1\) times. The output \(\rho^{(d)}(x)\) is then the product of the elements in \(\rho^{(1)}(x)\).

Now for \(i\in\{1,\ldots,d-1\}\), the function \(g^{(i)}\) (as in Thm. 6 (b)) as given by \(g^{(i)}(x)=C^{(i+1)}\rho^{(i)}(x)\). By (**), we thus have

\[g^{(i)}(x) =\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix} \begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))\\ \rho^{(i-1)}(x)\end{bmatrix}\] \[=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix} \begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)+\frac{ 1}{2}g^{(i-1)}(x)\end{bmatrix}\] \[=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix} \begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\ \rho^{(i-1)}(x)\end{bmatrix}\] \[\quad+\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix} \begin{bmatrix}\frac{1}{2}g^{(i-1)}(x)\\ 0\end{bmatrix}\] \[=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix} \begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\ \rho^{(i-1)}(x)\end{bmatrix}+\frac{1}{2}C^{(i+1)}A^{(i)}g^{(i-1)}(x)\] \[=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}\end{bmatrix} \begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\ \rho^{(i-1)}(x)\end{bmatrix}\] \[\quad+\frac{1}{2}C^{(i+1)}A^{(i)}C^{(i)}\rho^{(i-1)}(x)\] \[=\begin{bmatrix}C^{(i+1)}A^{(i)}&C^{(i+1)}B^{(i)}+\frac{1}{2}C^{( i+1)}A^{(i)}C^{(i)}\end{bmatrix}\begin{bmatrix}\operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x) \\ p^{(i-1)}(x)\end{bmatrix}\] \[=\begin{bmatrix}C^{(i+1)}A^{(i)}&0\end{bmatrix}\begin{bmatrix} \operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\ p^{(i-1)}(x)\end{bmatrix}\] \[=\begin{bmatrix}C^{(i+1)}A^{(i)}&0\end{bmatrix}\begin{bmatrix} \operatorname{ReLU}(g^{(i-1)}(x))-\frac{1}{2}g^{(i-1)}(x)\\ h^{(i-1)}(x)\end{bmatrix}.\]

Comparing this to the equations in Thm. 6 (b), we establish the claimed expression for \(V^{(1)}_{j}\) for \(i\in\{1,\ldots,d-1\}\).

For the case \(i=d\), we simply observe that the last weight matrix must be the outer weight vector in (*). The \(G\)-invariance of the constructed DNN is clear; the action of any \(g\in G\) on an input \(x\in\mathcal{X}\) corresponds to an even number of sign flips in \(\rho^{(1)}(x)\), which leaves the parity of the product \(\rho^{(d)}(x)\) invariant. Layerwise \(G\)-equivariance is established next.

**(b)** By part (a), The first weight matrix is

\[C^{(2)}A^{(1)}=I_{m/4}\otimes\begin{bmatrix}\begin{bmatrix}1&-1&1&-1\\ 1&-1&-1&1\end{bmatrix}.\]
The \(j\)th pair of rows in this weight matrix is the \(j\)th channel, whose first row is \(\nu_{j}\) and which transforms by \(\rho_{\mu_{j}^{(1)}}\kappa_{j}^{(1)}\). The expressions for \(H_{j}^{(1)}\) and \(\kappa_{j}^{(1)}\) are thus established by definition.

Now for \(i\in\{1,\ldots,d\}\), part (a) implies

\[\rho_{\mu_{j}^{(i+1)}}\kappa_{j}^{(i+1)}(g)\begin{bmatrix}1&-1&1&-1\\ 1&-1&-1&1\end{bmatrix}=\begin{bmatrix}1&-1&1&-1\\ 1&-1&-1&1\end{bmatrix}\begin{bmatrix}\pi_{\mu_{j-1}^{(0)}}(g)&0\\ 0&\pi_{\mu_{2j}^{(0)}}(g)\end{bmatrix}\forall g\in G,\]

where each \(\pi_{\mu_{k}^{(0)}}\) is the ordinary perm-rep part of \(\rho_{\mu_{k}^{(0)}}\kappa_{k}^{(0)}\). By definition, \(\kappa_{j}^{(i+1)}\) is the subgroup of all \(g\in G\) such that

\[\rho_{\mu_{j}^{(i+1)}}\kappa_{j}^{(i+1)}(g)e_{1}=e_{1}\]

\[\frac{1}{2}\rho_{\mu_{j}^{(i+1)}}\kappa_{j}^{(i+1)}(g)\begin{bmatrix}1&-1&1&- 1\\ 1&-1&-1&1\end{bmatrix}\begin{bmatrix}1\\ 0\\ 1\\ 0\end{bmatrix}=e_{1}\]

\[\frac{1}{2}\begin{bmatrix}1&-1&1&-1\\ 1&-1&-1&1\end{bmatrix}\begin{bmatrix}\pi_{\mu_{2j-1}^{(0)}}(g)&0\\ 0&\pi_{\mu_{2j}^{(0)}}(g)\end{bmatrix}\forall g\in G\begin{bmatrix}1\\ 0\\ 1\\ 0\end{bmatrix}=e_{1}.\]

Since ordinary perm-reps cannot flip signs, then the last equation is equivalent to

\[\pi_{\mu_{2j-1}^{(0)}}e_{1}=e_{1}\text{ and }\pi_{\mu_{2j}^{(0)}}e_{1}=e_{1}.\]

We thus have

\[\begin{split}\kappa_{j}^{(i+1)}&=\{g\in G:\pi_{\mu_{2j-1}^{(0)}}e _{1}=e_{1}\}\cap\{g\in G:\pi_{\mu_{2j}^{(0)}}e_{1}=e_{1}\}\\ &=H_{2j-1}^{(i)}\cap H_{2j}^{(i)}.\end{split}\]

Similarly, by definition we have

\[H_{j}^{(i+1)}=\{g\in G:\rho_{\mu_{j}^{(i+1)}}\kappa_{j}^{(i+1)}(g)e_{1}=\pm e _{1}\}.\]

Proceeding analogously as above, we find that \(g\in G\) is contained in \(H_{j}^{(i+1)}\) iff

\[(\pi_{\mu_{2j-1}^{(0)}}(g)e_{1}=e_{1}\text{ and }\pi_{\mu_{2j}^{(0)}}(g)e_{1}=e_{1}) \text{ or }(\pi_{\mu_{2j-1}^{(0)}}(g)e_{1}=e_{2}\text{ and }\pi_{\mu_{2j}^{(0)}}(g)e_{1}=e_{2}).\]

The first term in the disjunction corresponds to \(H_{2j-1}^{(i)}\cap H_{2j}^{(i)}\), and the second term in the disjunction corresponds to the intersection of the complements, as claimed.

In the case of the \((d-1)\)st layer, the product output \(\rho^{(d-1)}(x)\) is 2D and thus can only transform by \(\pm 1\). The rep \(\rho^{(d-)}\) thus decomposes into two copies of a scalar rep. Finally, that the final rep \(\rho^{(d)}\) is trivial follows from the \(G\)-invariance of the network, thereby completing the proof.