Geometry of Linear Neural Networks: Equivariance and Invariance under
  Permutation Groups
The set of functions parameterized by a linear fully-connected neural network
is a determinantal variety. We investigate the subvariety of functions that are
equivariant or invariant under the action of a permutation group. Examples of
such group actions are translations or $90^\circ$ rotations on images. We
describe such equivariant or invariant subvarieties as direct products of
determinantal varieties, from which we deduce their dimension, degree,
Euclidean distance degree, and their singularities. We fully characterize
invariance for arbitrary permutation groups, and equivariance for cyclic
groups. We draw conclusions for the parameterization and the design of
equivariant and invariant linear networks in terms of sparsity and
weight-sharing properties. We prove that all invariant linear functions can be
parameterized by a single linear autoencoder with a weight-sharing property
imposed by the cycle decomposition of the considered permutation. The space of
rank-bounded equivariant functions has several irreducible components, so it
can not be parameterized by a single network-but each irreducible component
can. Finally, we show that minimizing the squared-error loss on our invariant
or equivariant networks reduces to minimizing the Euclidean distance from
determinantal varieties via the Eckart-Young theorem.
Kathlén Kohn, Anna-Laura Sattelberger, Vahid Shahverdi
# Geometry of Linear Neural Networks:

###### Abstract

The set of functions parameterized by a linear fully-connected neural network is a determinantal variety. We investigate the subvariety of functions that are equivariant or invariant under the action of a permutation group. Examples of such group actions are translations or \(90^{\circ}\) rotations on images. For such equivariant or invariant subvarieties, we provide an explicit description of their dimension, their degree as well as their Euclidean distance degree, and their singularities. We fully characterize invariance for arbitrary permutation groups, and equivariance for cyclic groups. We draw conclusions for the parameterization and the design of equivariant and invariant linear networks, such as a weight sharing property, and we prove that all invariant linear functions can be learned by linear autoencoders.

###### Contents

* 1 Introduction
* 2 Warm-up and preliminaries
* 3 Invariance under permutation groups
* 4 Equivariance under cyclic subgroups of the symmetric group
* 5 Conclusion and outlook
* 6
Introduction

Neural networks that are equivariant or invariant under the action of a group attract high interest in applications and the theory of machine learning. It is important to thoroughly study their fundamental properties. While invariance is important for classifiers, equivariance typically comes into play in feature extraction tasks. The present article characterizes and investigates linear fully-connected neural networks. For instance, linear encoder-decoder models fit this setup well: they are families of functions \(\{f_{\theta}\}_{\theta\in\Theta}\), parameterized by a set \(\Theta=\mathbb{R}^{n\times r}\times\mathbb{R}^{r\times n}\). For each parameter \(\theta\in\Theta\), the function \(f_{\theta}\) is a composition of linear maps

\[f_{\theta}\colon\,\mathbb{R}^{n}\xrightarrow{f_{1,\theta}}\mathbb{R}^{r} \xrightarrow{f_{2,\theta}}\mathbb{R}^{n}, \tag{1.1}\]

where \(r\leq n\). One commonly visualizes \(f_{\theta}\) as in the figure below.

If \(n=m^{2}\) is a square number, one can think of the input of the network as a quadratic image with \(m\times m\) pixels. If \(n=m^{3}\), the input might be a cubic 3D scenery. In applications, one often aims to learn functions that are equi- or invariant under certain group actions, such as translations, rotations, or reflections.

The function space of a linear fully-connected neural network is a determinantal variety: For natural numbers \(r,m,n\), we write \(\mathcal{M}_{r,m\times n}\) for the subvariety of \(\mathbb{C}^{m\times n}\) whose points are complex \(m\times n\) matrices of rank at most \(r\). In learning tasks, _real_ matrices of rank at most \(r\) are in use; these are precisely the real-valued valued points \(\mathcal{M}_{r,m\times n}(\mathbb{R})\) of \(\mathcal{M}_{r,m\times n}\). Reading the entries of the matrix \(M\) as variables, the variety \(\mathcal{M}_{r,m\times n}\) is the locus of simultaneous vanishing of all \((r+1)\times(r+1)\) minors of \(M\). For a linear fully-connected neural network with input dimension \(n\), output dimension \(m\), and whose smallest layer has width \(r\), the set of functions parameterized by it is exactly \(\mathcal{M}_{r,m\times n}(\mathbb{R})\).

A good understanding of the geometry of the function space of a neural network is not only mathematically interesting per se. It is useful to understand the training process of a network. For instance, it is important for understanding the type of the critical points of the loss function. This behavior typically varies from architecture to architecture. In the case of linear fully-connected networks, critical points often correspond to matrices of rank even lower than \(r\), i.e., they lie in the singular locus of the determinantal variety \(\mathcal{M}_{r,m\times n}(\mathbb{R})\)[15]. Investigating those points is crucial for proving the convergence of such networks to nice minima [13]. The nature of critical points is very different in the case of linear convolutional networks. Here, critical points are almost always smooth points of the function space [10, 11].

Figure 1: A fully-connected network of depth 2.
In the present article, we investigate the subvarieties \(\mathcal{E}^{G}_{r,n\times n}\subset\mathcal{M}_{r,n\times n}\) and \(\mathcal{I}^{G}_{r,m\times n}\subset\mathcal{M}_{r,m\times n}\) of linear functions of bounded rank that are equivariant and invariant under the action of a permutation groups \(G\), respectively. The group \(G\) is a subgroup of the symmetric group \(\mathcal{S}_{n}\) and acts on the input and output space \(\mathbb{R}^{n}\) (or \(\mathbb{R}^{m}\), respectively) by permuting the entries of the input or output vector. For \(m=n\), the subvarieties \(\mathcal{E}^{G}_{r,n\times n}\) and \(\mathcal{I}^{G}_{r,n\times n}\) encode the part of the function space of a linear autoencoder that is equi- and invariant under the action of \(G\), respectively. Our main contribution is an algebraic characterization of \(\mathcal{I}^{G}_{r,m\times n}\) for arbitrary permutation groups, and for cyclic subgroups of \(\mathcal{S}_{n}\) in the case of equivariance. Our results allow for implications on the design of equi- and invariant networks. For instance, for invariant autoencoders, we prove a weight sharing property on the encoder and deduce a rank constraint, i.e., a constraint on the width of the middle layer. We prove that the function space of such a constrained autoencoder is exactly \(\mathcal{I}^{G}_{r,n\times n}\). In other words, linear autoencoders with our weight sharing property on the encoder precisely parameterize invariant functions. Taking carbon emissions during the training of models [5] into account, it is important for the role of AI in the climate crisis to encounter the increasing training and hence energy costs. This is also one of the aims that the initiative _Green AI_[14] is thriving for, to which the construction of efficient autoencoders with a low-dimensional middle layer might contribute.

**Related work.** We here give a petite sample of related references, which is by no means claimed to be exhaustive. An overview of equivariant neural networks is provided in the survey [12]. The study of equivariance has roots in pattern recognition [17]. Group-equivariant convolutional networks were introduced by Cohen and Welling in [4], allowing for applications in image analysis [1]. In [2], transitive group actions are considered. Therein, Bekkers proves that, on the level of feature maps, a linear map is equivariant if and only if it is a group convolution. Isometry- and gauge-equivariant CNNs on Riemannian manifolds were investigated in [16]. This geometric perspective has strong connections to physics.

To the best of our knowledge, our article is the first one to tackle the _algebro-geometric_ study of equi- or invariant networks and their function spaces.

**Notation.** By \(\mathcal{F}\), we denote the function space, and by \(\Theta\) the parameter space of a neural network \(F\colon\Theta\to\mathcal{F}\). For a parameter \(\theta\in\Theta\), we denote the function \(F(\theta)\) by \(f_{\theta}\). The symbol \(\mathbb{K}\) denotes one of the fields \(\{\mathbb{R},\mathbb{C}\}\). For an ideal \(I\) in a polynomial ring \(\mathbb{K}[x_{1},\ldots,x_{n}]\), we denote by \(V(I)\) the algebraic variety \(V(I)=\{x\in\mathbb{K}^{n}\,|\,p(x)=0\text{ for all }p\in I\}\). The symbol \(\mathcal{M}_{r,m\times n}\) denotes the determinantal variety in \(\mathbb{C}^{m\times n}\) whose points are complex \(m\times n\) matrices \(M\) of rank at most \(r\), and \(\mathcal{M}_{r,m\times n}(\mathbb{R})\) its real-valued points, i.e., real matrices \(M\) of rank at most \(r\). Its subsets of equi- and invariant subspaces under the action of a group \(G\) will be denoted by \(\mathcal{E}^{G}_{r,m\times n}\) and \(\mathcal{I}^{G}_{r,m\times n}\), respectively. If the letter \(r\) is dropped in the notation, this means that no rank constraint is imposed on the matrices. For fixed \(T\in\operatorname{GL}_{n}(\mathbb{K})\) and any matrix \(M\in\mathcal{M}_{n\times n}(\mathbb{K})\), we write shortly \(M^{\sim_{T}}\coloneqq T^{-1}MT\) for the respective similarity transform. We denote the identity matrix of size \(n\) by \(\mathrm{I}_{n}\), and by \(\mathcal{S}_{n}\) the symmetric group on the set \([n]=\{1,\ldots,n\}\). For a permutation \(\sigma\in\mathcal{S}_{n}\), \(\mathcal{P}(\sigma)\) denotes the partition \(\{A_{1},\ldots,A_{k}\}\) of the set \([n]\) induced by the decomposition \(\sigma=\pi_{1}\circ\cdots\circ\pi_{k}\) of \(\sigma\) into pairwise disjoint cycles \(\pi_{i}\), where we also count trivial cycles, i.e., cycles of length \(1\).
**Outline.** In Section 2, we present motivating examples and present necessary preliminaries from algebraic geometry. Section 3 treats invariance under permutation groups. We characterize invariance and investigate implications on the design of invariant linear autoencoders. Section 4 characterizes equivariance of linear autoencoders under cyclic subgroups of the symmetric group. In Section 5, we present which other groups and further generalizations we are planning to tackle in future work.

## 2 Warm-up and preliminaries

We start with cyclic subgroups \(G\) of the symmetric group \(\mathcal{S}_{n},\) i.e., groups of the form \(G=\left\langle\sigma\right\rangle\) for some permutation \(\sigma\in\mathcal{S}_{n}\). Such groups \(G\) naturally act on the input space \(\mathbb{R}^{n}\) and the output space \(\mathbb{R}^{n}\) of the network (1.1) by permuting the entries of the in- and output vector, respectively, and on linear maps \(f\): \(\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}\) by permuting the columns of the \(m\times n\) matrix representing \(f\).

### Warm-up examples

#### 2.1.1 Rotation-invariance of linear maps for \(m\times m\) pictures

Let \(n=m^{2}\) be a square number and let \(\sigma\) denote the clockwise rotation of the input \(m\times m\) picture by \(90\) degrees, i.e., \(\sigma\) is the following permutation of the pixels \(a_{ij}\):

\[\sigma\colon\ \mathbb{R}^{m\times m}\rightarrow\mathbb{R}^{m\times m},\qquad \begin{pmatrix}a_{11}&a_{12}&\ldots&a_{1m}\\ a_{21}&a_{22}&\ldots&a_{2m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&\ldots&a_{mm}\end{pmatrix}\mapsto\begin{pmatrix}a_{m1}&a_{m-1, 1}&\ldots&a_{11}\\ a_{m2}&a_{m-1,2}&\ldots&a_{12}\\ \vdots&\vdots&\ddots&\vdots\\ a_{mm}&a_{m,m-1}&\ldots&a_{1m}\end{pmatrix}. \tag{2.1}\]

Since square numbers are either \(0\) or \(1\) modulo \(4\), we will distinguish between \(m\) odd and \(m\) even for the identification of \(\mathbb{R}^{m\times m}\) with \(\mathbb{R}^{n}\). If \(m\) is odd, we identify

\[\mathbb{R}^{m\times m}\xrightarrow{\cong}\mathbb{R}^{n},\qquad A\ =\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,m-1}&a_{1,m}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,m-1}&a_{2,m}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{m-1,1}&a_{m-1,2}&\cdots&a_{m-1,m-1}&a_{m-1,m}\\ a_{m,1}&a_{m,2}&\cdots&a_{m,m-1}&a_{m,m}\end{pmatrix}\ \mapsto\ \mathrm{vec}(A)\,, \tag{2.2}\]

where \(\mathrm{vec}(A)=(a_{1,1},a_{1,m},a_{m,m},a_{m,1},a_{1,2},a_{2,m},a_{m,m-1},a_{ m-1,1},\ldots,a_{1,m-1},a_{m-1,m},a_{m,2},a_{2,1},\)\(a_{2,2},a_{2,m-1},a_{m-1,m-1},a_{m-1,2},\ldots,a_{\frac{m+1}{2},\frac{m+1}{2}})^{ \top}.\) The intuition of the choice of vectorization can be described as "passing from corner to corner clockwise, inwards layer by layer". Under this identification, the action of \(\sigma\) is given by the \(n\times n\) block matrix
\[\begin{pmatrix}0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ &&&\cdots\\ &&&&0&0&0&1\\ &&&1&0&0&0\\ &&&&0&1&0&0\\ &&&&0&0&1&0\\ &&&&0&0&1&0\\ &&&&1\end{pmatrix}\,, \tag{2.3}\]

where non-filled entries are \(0\). If \(m\) is even, we use the identification

\[\mathbb{R}^{m\times m}\xrightarrow{\cong}\mathbb{R}^{n},\qquad A\ =\begin{pmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,m-1}&a_{1,m}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,m-1}&a_{2,m}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{m-1,1}&a_{m-1,2}&\cdots&a_{m-1,m-1}&a_{m-1,m}\\ a_{m,1}&a_{m,2}&\cdots&a_{m,m-1}&a_{m,m}\end{pmatrix}\ \mapsto\ \mathrm{vec}(A)\,, \tag{2.4}\]

where \(\mathrm{vec}(A)=(a_{1,1},a_{1,m},a_{m,m},a_{m,1},a_{1,2},a_{2,m},a_{m,m-1},a_{ m-1,1},\ldots,a_{1,m-1},a_{m-1,m},a_{m,2},a_{2,1},\)\(a_{2,2},a_{2,m-1},a_{m-1,m-1},a_{m-1,2},\ldots,a_{\frac{m}{2}},\frac{m}{2},\frac{m}{2},\frac{m}{2}+1,a\frac{m}{2}+1,\frac{m}{2},a\frac{m}{2}+1,\frac{m}{2}+1)^{\top}\,\). Under this identification, \(\sigma\) acts on \(\mathbb{R}^{n}\) by the \(n\times n\) block matrix

\[\begin{pmatrix}0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ &&&&\cdots\\ &&&&0&0&0&1\\ &&&&1&0&0&0\\ &&&&0&1&0&0\\ &&&&0&0&1&0\end{pmatrix}\,. \tag{2.5}\]

Invariance of \(f\colon\mathbb{R}^{n}\to\mathbb{R}^{n}\) under \(\sigma\) hence implies that columns 1-4, 5-8, 9-12, and so on, of the matrix \(M\) representing \(f\) have to coincide. In particular, \(\sigma\)-invariance implies that the rank of \(f\) is at most \(\lceil\frac{m^{2}}{4}\rceil\), where \(\lceil\cdot\rceil\) denotes the ceiling function. Note that the set \(\mathcal{I}_{n\times n}^{\sigma}\) of all linear rotation-invariant maps \(f\colon\mathbb{R}^{n}\to\mathbb{R}^{n}\) is a vector space.

**Remark 2.1**.: Also operations such as rotations, reflections, and shifting the rows of \(A\), all can be seen as special cases of permutations. \(\diamond\)

**Remark 2.2** (Design of rotation-invariant autoencoders).: From what was found above, we deduce that for any linear encoder-decoder \(f\colon\mathbb{R}^{m\times m}\to\mathbb{R}^{r}\to\mathbb{R}^{m\times m}\) that is invariant under \(\sigma\), the number \(r\) can be chosen to be \(\leq\lceil\frac{m^{2}}{4}\rceil\). A rank constraint with \(r\) small imposes moreover that some of the blocks of four consecutive columns coincide, are zero, or linear combinations of each other.
#### 2.1.2 Rotation-equivariance of linear maps for \(3\times 3\) pictures

Consider the set of \(\mathbb{R}\)-linear maps \(f\colon\mathbb{R}^{9}\to\mathbb{R}^{9}\) of rank at most \(3.\) Every such map can be written as a composition of \(\mathbb{R}\)-linear maps

\[\mathbb{R}^{9}\longrightarrow\mathbb{R}^{3}\longrightarrow\mathbb{R}^{9}. \tag{2.6}\]

Those maps are encoded precisely by real \(9\times 9\) matrices \(M=(m_{ij})_{i,j=1,\ldots,9}\in\mathcal{M}_{9\times 9}(\mathbb{R})\) all whose \(4\times 4\) minors vanish. The minors are homogeneous polynomials of degree \(4\) in the entries of the matrix \(M.\) We denote by \(I_{3,9\times 9}\leq\mathbb{C}[\{m_{ij}\}]\) the ideal generated by those polynomials. In more geometric terms, we are looking for the real points of the \(45\)-dimensional variety

\[\mathcal{M}_{3,9\times 9}\,=\,V(I_{3,9\times 9})\,\subset\,\mathbb{C}^{9 \times 9}. \tag{2.7}\]

Denote by \(\sigma\) the clockwise rotation of a \(3\times 3\) matrix by \(90\) degrees, i.e.,

\[\sigma\colon\,\mathbb{R}^{3\times 3}\to\mathbb{R}^{3\times 3},\qquad \begin{pmatrix}a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\end{pmatrix}\,\mapsto\,\begin{pmatrix}a_{31}&a_{21}&a_{ 11}\\ a_{32}&a_{22}&a_{12}\\ a_{33}&a_{23}&a_{13}\end{pmatrix}, \tag{2.8}\]

and let \(G=\langle\sigma\rangle\). This is a finite, cyclic subgroup of \(\mathrm{O}(2)\) which preserves the \(m\times m\) shape of the input matrix, which we interpret as a quadratic image with \(n=9\) real pixels \(a_{ij}\). We are interested in those maps that are equivariant under \(G\), i.e., linear maps \(f\) for which

\[\sigma\circ f\,=\,f\circ\sigma\,. \tag{2.9}\]

Again, we identify \(\mathbb{R}^{3\times 3}\cong\mathbb{R}^{9}\) via

\[\begin{pmatrix}a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\end{pmatrix}\mapsto\begin{pmatrix}a_{11}&a_{13}&a_{33}& a_{31}&a_{12}&a_{23}&a_{32}&a_{21}&a_{22}\end{pmatrix}^{\top}. \tag{2.10}\]

Then \(\sigma(A)\) is represented by the vector \((a_{31}\ a_{11}\ a_{13}\ a_{33}\ a_{21}\ a_{12}\ a_{23}\ a_{32}\ a_{22})^{\top}.\) Under this identification, the rotation is the permutation \(\sigma=(1\,4\,3\,2)(5\,8\,7\,6)\in\mathcal{S}_{9}\) and is represented by

\[\left(\begin{array}{cccc|c}0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\end{array}\right)\qquad\begin{array}{c|c|c}0&&0\\ 0\\ \hline\\ \\ 0&&\begin{array}{cccc|c}0&0&0&1\\ 1&0&0&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&1&0\end{array}\right)\,. \tag{2.11}\]

from Equation (2.3). A map \(f\) is equivariant under \(\sigma\), and hence under \(G\), if and only if its representing matrix \(M\) satisfies

\[P_{\sigma}\cdot M\,=\,M\cdot P_{\sigma}\,. \tag{2.12}\]
We therefore aim to determine all matrices \(M\) that commute with \(P_{\sigma}\). Hence, a matrix \(M\) is equivariant under \(\sigma\) if and only if \(M\) is similar to itself with the permutation matrix of \(\sigma\) as base change. Also condition (2.9) can be expressed as the vanishing of polynomials read from Equation (2.12). Those \(81\) homogeneous binomials of degree \(1\) cut out the vector space \(\mathcal{E}_{9\times 9}^{\sigma}\). We see from (2.11) that the matrices in \(\mathcal{E}_{9\times 9}^{\sigma}\) must be of the form

\[\left(\begin{array}{cccc|cccc|c}\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{4} &\beta_{1}&\beta_{2}&\beta_{3}&\beta_{4}&\varepsilon_{3}\\ \alpha_{4}&\alpha_{1}&\alpha_{2}&\alpha_{3}&\beta_{4}&\beta_{1}&\beta_{2}& \beta_{3}&\varepsilon_{3}\\ \alpha_{3}&\alpha_{4}&\alpha_{1}&\alpha_{2}&\beta_{3}&\beta_{4}&\beta_{1}& \beta_{2}&\varepsilon_{3}\\ \alpha_{2}&\alpha_{3}&\alpha_{4}&\alpha_{1}&\beta_{2}&\beta_{3}&\beta_{4}& \beta_{1}&\varepsilon_{3}\\ \hline\gamma_{1}&\gamma_{2}&\gamma_{3}&\gamma_{4}&\delta_{1}&\delta_{2}& \delta_{3}&\delta_{4}&\varepsilon_{4}\\ \gamma_{4}&\gamma_{1}&\gamma_{2}&\gamma_{3}&\delta_{4}&\delta_{1}&\delta_{2}& \delta_{3}&\varepsilon_{4}\\ \gamma_{3}&\gamma_{4}&\gamma_{1}&\gamma_{2}&\delta_{3}&\delta_{4}&\delta_{1}& \delta_{2}&\varepsilon_{4}\\ \gamma_{2}&\gamma_{3}&\gamma_{4}&\gamma_{1}&\delta_{2}&\delta_{3}&\delta_{4}& \delta_{1}&\varepsilon_{4}\\ \hline\varepsilon_{1}&\varepsilon_{1}&\varepsilon_{1}&\varepsilon_{1}& \varepsilon_{2}&\varepsilon_{2}&\varepsilon_{2}&\varepsilon_{2}&\varepsilon_ {5}\end{array}\right)\,. \tag{2.13}\]

Hence the dimension of the vector space \(\mathcal{E}_{9\times 9}^{\sigma}\) is \(81-60=4\cdot 4+5\cdot 1=21.\) The matrices in this vector space that can be parameterized by the autoencoder (2.6) form the variety \(\mathcal{E}_{3,9\times 9}^{\sigma}\), which is obtained as the intersection of \(\mathcal{E}^{\sigma}\) and \(\mathcal{M}_{3,9\times 9}\), i.e.,

\[\mathcal{E}_{3,9\times 9}^{\sigma}\,=\,\mathcal{M}_{3,9\times 9}\cap \mathcal{E}_{9\times 9}^{\sigma}\,. \tag{2.14}\]

Intersecting with \(\mathcal{M}_{3,9\times 9}\) imposes that at most \(3\) of the \(9\) columns of the matrix in (2.13) are linearly independent.

### Algebraic geometry of similarity transforms

For natural numbers \(m,n\) and \(r\leq\min(m,n)\), the variety \(\mathcal{M}_{r,m\times n}\) of \(m\times n\) matrices of rank at most \(r\) has dimension

\[\dim(\mathcal{M}_{r,m\times n})\,=\,r\cdot(m+n-r)\,, \tag{2.15}\]

cf. [9, Proposition 12.2]. We remind our readers that the dimension of an affine variety is the Krull dimension of its coordinate ring.

**Remark 2.3** (Real vs. complex).: Since all the coefficients of the contributing polynomials are real, the real variety of real-valued points \(\mathcal{M}_{r,m\times n}(\mathbb{R})=\mathcal{M}_{r,m\times n}(\mathbb{C}) \cap\mathbb{R}^{m\times n}\) of \(\mathcal{M}_{r,m\times n}\) has the same dimension as the complex variety \(\mathcal{M}_{r,m\times n}\). The points of \(\mathcal{M}_{r,m\times n}(\mathbb{R})\) are real \(m\times n\) matrices of rank \(\leq r\). \(\diamond\)

As was pointed out in [9, Example 19.10], it is proven in [7, Example 14.4.11] that the degree of \(\mathcal{M}_{r,m\times n}\) is

\[\deg\left(\mathcal{M}_{r,m\times n}\right)\ =\ \prod_{i=0}^{n-r-1}\frac{(m+i)!\, \cdot\!i!}{(r+i)!\,\cdot\!(m-r+i)!}\,. \tag{2.16}\]
**Lemma 2.4**.: _Let \(0<r<n\). A matrix \(M\in\mathcal{M}_{r,m\times n}\) is a singular point of \(\mathcal{M}_{r,m\times n}\) if and only if its rank is strictly smaller than \(r\), i.e., if \(\operatorname{rank}(M)<r\). _

We will also investigate the Euclidean distance degree of [6].

**Definition 2.5**.: The _Euclidean distance (ED) degree_ of an algebraic variety \(\mathcal{X}\) in \(\mathbb{R}^{N}\) is the number of complex critical points of the squared Euclidean distance from \(\mathcal{X}\) to a general point outside the variety. It is denoted by \(\operatorname{deg}_{\operatorname{ED}}(\mathcal{X})\).

**Remark 2.6**.: Consider a linear fully-connected network with input dimension \(n\), output dimension \(m\), and smallest layer of width \(r\). For sufficiently large and generic data, training that network with the squared error loss is equivalent to minimizing the Euclidean distance from the variety \(\mathcal{M}_{r,m\times n}(\mathbb{R})\) to a general matrix in \(\mathcal{M}_{m\times n}(\mathbb{R})\); see [15, Section 3.3]. \(\diamond\)

The ED degree of a variety is a measure for the complexity of determining points of the variety which are closest to a data point of interest. In learning, one might want to find an in-/equivariant function that is "closest" to a learned, arbitrary function. The ED degree is a measure of computational complexity for this problem in the following sense: it is the number of critical points of the distance function from the function space to a generic linear function. Note that the ED degree is not an algebraic invariant of the real variety \(\mathcal{X}\) alone, but it depends on the chosen coordinate system of its ambient space \(\mathbb{R}^{N}\).

**Example 2.7**.: The circle has ED degree 2 and generic ellipses are of ED degree 4. \(\diamond\)

The ED degree of the determinantal variety \(\mathcal{M}_{r,m\times n}(\mathbb{R})\) can be computed from the Eckart-Young Theorem [6, Example 2.3], which gives

\[\operatorname{deg}_{\operatorname{ED}}(\mathcal{M}_{r,m\times n}(\mathbb{R})) \,=\,\binom{\min(m,n)}{r}\,. \tag{2.17}\]

In our investigations, we will commonly perform base changes of the matrices in \(\mathcal{M}_{m\times n}\). For a subvariety \(\mathcal{X}\subset\mathcal{M}_{m\times n}\) and any \(T\in\operatorname{GL}_{n}(\mathbb{C})\), we denote by \(\mathcal{X}^{\cdot T}\) the image of \(\mathcal{X}\) under the linear isomorphism

\[\cdot T\colon\,\mathcal{M}_{m\times n}\longrightarrow\mathcal{M}_{m\times n}, \quad M\mapsto MT\,. \tag{2.18}\]

**Lemma 2.8**.: _Let \(\mathcal{X}\subset\mathcal{M}_{m\times n}\) be a subvariety and let \(T\in\operatorname{GL}_{n}\). Then, \(\dim(\mathcal{X}^{\cdot T})=\dim\mathcal{X}\), \(\operatorname{deg}(\mathcal{X}^{\cdot T})=\operatorname{deg}\mathcal{X}\), \(\operatorname{Sing}(\mathcal{X}^{\cdot T})=\operatorname{Sing}(\mathcal{X})^{ \cdot T}\), and \((\mathcal{X}^{\cdot T})\cap\mathcal{M}_{r,m\times n}=(\mathcal{X}\cap\mathcal{ M}_{r,m\times n})^{\cdot T}\) for any \(r\leq\min(m,n)\)._

Proof.: Since (2.18) is a linear isomorphism, it preserves the dimension and the degree, and maps regular points to regular points. For the last assertion, we observe that every matrix \(M\in\mathcal{M}_{m\times n}\) satisfies that \(\operatorname{rank}(MT)=\operatorname{rank}(M)\), since \(T\) has full rank. 

We point out that the ED degree is in general not preserved by the isomorphism (2.18), as the following example demonstrates.
**Example 2.9**.: Let \(m=1\) and \(n=3\). Consider the circle \(\mathcal{X}\subset\mathcal{M}_{1\times 3}(\mathbb{C})\) defined by the equation \(M_{1,1}^{2}+M_{1,2}^{2}-M_{1,3}^{2}=0\). The ED degree of \(\mathcal{X}(\mathbb{R})\) in the standard Euclidean distance

\[d(0,M)\,\coloneqq\,\|M\|^{2}\,=\,\operatorname{tr}(MM^{\top})\,=\,M_{1,1}^{2}+ M_{1,2}^{2}+M_{1,3}^{2} \tag{2.19}\]

is equal to \(2\). Let us now consider the permutation matrix \(P\coloneqq\left(\begin{smallmatrix}0&0&1\\ 1&0&0\\ 0&1&0\end{smallmatrix}\right)\). To diagonalize it, we use the symmetric Vandermonde matrix

\[T\,\coloneqq\,V(1,\zeta_{3},\zeta_{3}^{2})\,=\,\begin{pmatrix}1&1&1\\ 1&\zeta_{3}&\zeta_{3}^{2}\\ 1&\zeta_{3}^{2}&\zeta_{3}\end{pmatrix},\]

where \(\zeta_{3}\) is any primitive third root of unity. In fact, we obtain \(T^{-1}PT=\operatorname{diag}(1,\zeta_{3}^{2},\zeta_{3})\). The ED degree of \(\mathcal{X}^{\cdot T}(\mathbb{R})\) is not equal to \(2\) anymore. In fact, the ED degree of \(\mathcal{X}^{\cdot T}\) counts the critical points of the function \(d(0,MT-U)\) over all \(M\in\mathcal{X}(\mathbb{R})\) for fixed, generic \(U\). Since \(U\) is generic, we can replace it by \(UT\). Hence, the ED degree of \(\mathcal{X}^{\cdot T}\) under the standard Euclidean distance (2.19) is equal to the ED degree of \(\mathcal{X}\) under the modified Euclidean distance

\[d_{T}(0,M)\,\coloneqq\,d(0,MT)\,=\,3\cdot(M_{1,1}^{2}+2M_{1,2}M_{1,3})\,.\]

A computation in Macaulay2[8] shows that the ED degree of \(\mathcal{X}(\mathbb{R})\) under \(d_{T}\) is \(4\). \(\diamond\)

Depending on whether we study invariance or equivariance, we perform base changes on only one side of the matrices, or on both sides. For the latter, we write \(M^{\sim T}:=T^{-1}MT\) for given matrices \(M\in\mathcal{M}_{n\times n}\) and \(T\in\operatorname{GL}_{n}\).

**Lemma 2.10**.: _Consider the matrices \(M\in\mathcal{M}_{m\times m}\), \(P\in\mathcal{M}_{n\times n}\), and \(T\in\operatorname{GL}_{n}\). Then, \(MP=M\) if and only if \(M^{\cdot T}P^{\sim T}=M^{\cdot T}\). In the case that \(m=n\), we moreover have that \(MP=PM\) if and only if \(M^{\sim T}P^{\sim T}=P^{\sim T}M^{\sim T}\). _

In our investigations, we will make use of presentations of permutation matrices \(P\) in different bases. The strategy is as follows. Step 1 consists in decomposing a permutation \(\sigma\in\mathcal{S}_{n}\) into disjoint cycles \(\pi_{1},\ldots,\pi_{k}\) of lengths \(\ell_{1},\ldots,\ell_{k}\); this brings the permutation matrix \(P_{\sigma}\) of \(\sigma\) into block diagonal form, where each diagonal block is a circulant matrix. The second step is to diagonalize those circulant matrices of sizes \(\ell_{1},\ldots,\ell_{k}\). Step 3 is optional and groups the columns corresponding to the same eigenvalue.

**Procedure 2.11**.:
1. [label=Step 0]
2. Represent \(\sigma\) by the permutation matrix \(P_{\sigma}\in\mathcal{M}_{n\times n}(\{0,1\})\) with respect to the standard basis of \(\mathbb{R}^{n}\), i.e., the \(j\)-th row of \(P_{\sigma}\) is the transpose of the \(\sigma(j)\)-th standard unit vector of \(\mathbb{R}^{n}\).
1. Determine a permutation matrix \(T_{1}\in\mathcal{M}_{n\times n}(\{0,1\})\) such that \(P_{\sigma}^{\sim_{T_{1}}}=T_{1}^{-1}P_{\sigma}T_{1}\) is block diagonal whose blocks are circulant matrices \(C_{1},\ldots,C_{k}\) of the form \[C_{i}\,=\,\begin{pmatrix}0&&&&1\\ 1&0&&&\\ &1&\ddots&\\ &&\ddots&\\ &&&1&0\end{pmatrix}\in\mathcal{M}_{\ell_{i}\times\ell_{i}}(\{0,1\}).\] (2.20) Each \(C_{i}\in\mathcal{M}_{\ell_{i}\times\ell_{i}}(\{0,1\})\) has \(\ell_{i}\)-th roots of unity as eigenvalues, namely \(\zeta_{\ell_{i}}^{j}\), where \(j=0,\ldots,\ell_{i}-1\), and \(\zeta_{n}\) denotes the primitive root of unity \(e^{2\pi i/n}\). Depending on the lengths \(\ell_{i}\) of the cycles, some of \(C_{i}\)'s might share common eigenvalues. Collect the eigenvalues of all the \(C_{i}\)'s in a set \(\{\lambda_{1},\lambda_{2},\ldots,\lambda_{s}\}\) together with their multiplicities \(b_{1},b_{2},\ldots,b_{s}\). Note that one of the \(\lambda_{i}\)'s is equal to \(1\) and for this \(\hat{i}\), \(b_{\hat{i}}=k\).
2. Diagonalize each matrix \(C_{i}\) from (2.20) via a matrix in \(\mathrm{GL}_{n}(\mathbb{C})\); this can be obtained via Vandermonde matrices \(V(1,\zeta_{\ell_{i}},\ldots,\zeta_{\ell_{i}}^{\ell_{i}-1})\) as in Example 2.9. The following block diagonal matrix then diagonalizes the block circulant diagonal matrix \(P_{\sigma}^{\sim_{T_{1}}}\) from Step 1: \[T_{2}\,=\,\begin{pmatrix}V\big{(}1,\zeta_{\ell_{1}},\ldots,\zeta_{\ell_{1}}^{ \ell_{1}-1}\big{)}&&&&\\ &\ddots&\\ &&&V\Big{(}1,\zeta_{\ell_{k}},\ldots,\zeta_{\ell_{k}}^{\ell_{k}-1}\Big{)} \end{pmatrix}\,.\] (2.21)
3. Group identical eigenvalues: determine \(T_{3}\in\mathrm{GL}_{n}(\{0,1\})\) such that the matrix from Step 2 is block diagonal with blocks of the form \(\lambda_{i}\operatorname{I}_{b_{i}}\), i.e., determine \(T_{3}\) such that \[T_{3}^{-1}\cdot\big{(}P_{\sigma}^{\sim_{T_{1}}}\big{)}^{\sim_{T_{2}}}\cdot T_ {3}\ =\ \begin{pmatrix}\lambda_{1}\operatorname{I}_{b_{1}}&&&&\\ &\lambda_{2}\operatorname{I}_{b_{2}}&&\\ &&\ddots&\\ &&&\lambda_{s}\operatorname{I}_{b_{s}}\end{pmatrix}\,.\] (2.22) We demonstrate Steps 0-2 of Procedure 2.11 for an example.

**Example 2.12**.: Consider the permutation \(\sigma=\begin{pmatrix}1&2&3&4&5\\ 3&5&4&1&2\end{pmatrix}\in\mathcal{S}_{5}\). Then

\[P_{\sigma}\,=\,\begin{pmatrix}0&0&1&0&0\\ 0&0&0&0&1\\ 0&0&0&1&0\\ 1&0&0&0&0\\ 0&1&0&0&0\end{pmatrix}\overset{\sim_{T_{1}}}{\mapsto}\,\begin{pmatrix}0&0&1& &0\\ 1&0&0&0&\\ 0&1&0&0&\\ &0&1&0\end{pmatrix}\,\overset{\sim_{T_{2}}}{\mapsto}\,\begin{pmatrix}1&&&\\ &\zeta_{3}^{2}&&\\ &&\zeta_{3}&&\\ &&&1&\\ &&&-1\end{pmatrix}\]
with

\[T_{1}\,=\,\begin{pmatrix}0&0&1&0&0\\ 0&0&0&1&0\\ 0&1&0&0&0\\ 1&0&0&0&0\\ 0&0&0&0&1\end{pmatrix}\in\mathcal{M}_{5\times 5}(\{0,1\})\quad\text{and} \quad T_{2}\,=\,\begin{pmatrix}1&1&1\\ 1&\zeta_{3}&\zeta_{3}^{2}&0\\ 1&\zeta_{3}^{2}&\zeta_{3}\end{pmatrix}\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \,\
**Remark 2.15**.: In the notation of Procedure 2.11, \(\{d_{i}\,|\,i\in\mathbb{N}_{>0},\;d_{i}\neq 0\}=\{b_{1},\dots,b_{s}\}\) as sets. Moreover, \(d_{1}=k\), i.e., the number of disjoint cycles into which \(\sigma\) decomposes. \(\diamond\)

**Lemma 2.16**.: _Let \(\mathbb{F}\subset\mathbb{K}\) be a field extension. Then for any \(n\times n\) matrix \(M\in\mathcal{M}_{n\times n}(\mathbb{F})\), we have \(\dim_{\mathbb{F}}(C_{\mathbb{F}}(M))=\dim_{\mathbb{K}}(C_{\mathbb{K}}(M))\)._

Proof.: Let \(M\) be a matrix in \(\mathcal{M}_{n\times n}(\mathbb{F})\), and let \(Q_{M,\mathbb{F}}:\mathcal{M}_{n\times n}(\mathbb{F})\to\mathcal{M}_{n\times n }(\mathbb{F})\) be a linear map that maps a matrix \(N\) to its commutator with \(M\), namely to \([M,N]=MN-NM\). Since the process of Gaussian elimination is independent of the choice of the field for the linear map \(Q_{M,\cdot}\), it follows that \(\dim_{\mathbb{F}}(\ker(Q_{M,\mathbb{F}}))=\dim_{\mathbb{K}}(\ker(Q_{M, \mathbb{K}}))\). 

**Corollary 2.17**.: _Lemma 2.14 holds true as well as when the base field \(\mathbb{F}\) is \(\mathbb{R}\) or \(\mathbb{Q}\). _

**Example 2.18**.: The blocks of the matrix in (2.11) represent the three disjoint cycles \((1\,2\,3\,4)\), \((5\,6\,7\,8)\), and \((9)\) of length \(4\), \(4\), and \(1\), respectively. Hence the only non-zero \(d_{i}\)'s are \(d_{1}=k=3\), \(d_{2}=2\), and \(d_{4}=2\). Therefore, by Lemma 2.14 and Corollary 2.17, we have \(\dim(C(P_{\sigma}))=\varphi(1)\cdot 3^{2}+\varphi(2)\cdot 2^{2}+\varphi(4) \cdot 2^{2}=9+4+8=21\), in coherence what was obtained in Section 2.1.2. After the full base change in Procedure 2.11 such that \(P_{\sigma}\) is the diagonal matrix in Equation (2.22), the matrices in \(C(P_{\sigma})\) are those of the form

\[\left(\begin{array}{cccc|c|c|c}\alpha_{11}&\alpha_{12}&\alpha_{13}&&&\\ \alpha_{21}&\alpha_{22}&\alpha_{23}&0&0&0\\ \alpha_{31}&\alpha_{32}&\alpha_{33}&&&\\ \hline 0&&&\beta_{11}&\beta_{12}&0&0\\ &&&\beta_{21}&\beta_{22}&\\ \hline 0&&&\gamma_{11}&\gamma_{12}&0\\ &&&\gamma_{21}&\gamma_{22}&\\ \hline 0&&&0&0&\delta_{11}&\delta_{12}\\ &&&\delta_{21}&\delta_{22}\\ \end{array}\right), \tag{2.24}\]

with scalars \(\alpha_{ij}\), \(\beta_{ij}\), \(\gamma_{ij}\), \(\delta_{ij}\). \(\diamond\)

## 3 Invariance under permutation groups

We here study linear maps \(f\colon\mathbb{R}^{n}\to\mathbb{R}^{m}\) and are going to deal with determinantal subvarieties of \(\;\mathcal{M}_{m\times n}\). For invariance, the action of the considered group is required on the input space \(\mathbb{R}^{n}\) only. Let \(G\leq\mathcal{S}_{n}\) be an arbitrary subgroup of the symmetric group. The linear map \(f\) is _invariant under \(G\)_ if

\[f\circ\sigma\,=\,f \tag{3.1}\]

for all permutations \(\sigma\in G\).
### Reduction to cyclic groups

For a decomposition \(\sigma=\pi_{1}\circ\cdots\circ\pi_{k}\in\mathcal{S}_{n}\) into disjoint cycles, we denote by \(\mathcal{P}(\sigma)=\{A_{1},\ldots,A_{k}\}\) its induced partition of the set \([n]\). The \(A_{i}\subset[n]\) fulfill \(\cup_{i=1}^{k}A_{i}=[n]\) and \(A_{i}\cap A_{j}=\emptyset\) whenever \(i\neq j\).

**Example 3.1**.: Let \(\sigma=(1\,3\,4)(2\,5)\in\mathcal{S}_{5}.\) Its induced partition of \([5]=\{1,2,3,4,5\}\) is \(\mathcal{P}(\sigma)=\{\{1,3,4\},\{2,5\}\}.\) Note that different permutations might induce the same partition: the permutation \(\eta=(1\,4\,3)(2\,5)\neq\sigma\) gives rise to the partition \(\mathcal{P}(\eta)=\mathcal{P}(\sigma)\) of the set \([5]\). \(\diamond\)

**Proposition 3.2**.: _Let \(G=\langle\sigma\rangle\leq\mathcal{S}_{n}\) be cyclic and \(\sigma=\pi_{1}\circ\cdots\circ\pi_{k}\) a decomposition of \(\sigma\) into \(k\) disjoint cycles \(\pi_{1},\ldots,\pi_{k}\). The dimension of \(\mathcal{I}_{m\times n}^{G}\) is \(m\cdot k\)._

Proof.: Consider the partition \(\mathcal{P}(\sigma)=\{A_{1},\ldots,A_{k}\}\) of \([n]\) induced by the decomposition \(\sigma=\pi_{1}\circ\cdots\circ\pi_{k}\). Assuming invariance of \(M\) under \(\sigma\), each cycle \(\pi_{i}\) of \(\sigma\) forces some of the columns of \(M\) to coincide, namely the columns indexed by \(A_{i}\subset[n]\). For each \(A_{i}\in\mathcal{P}(\sigma)\), we need to remember only one column \(m_{A_{i}}\) of \(M\). For each \(i\), \(\operatorname{length}(\pi_{i})\) many identical copies of \(m_{A_{i}}\) are listed as columns in \(M\). For each of the \(m_{A_{i}}\), there are \(m\) degrees of freedom to fill its entries, which results in \(\dim(\mathcal{I}_{m\times n}^{\sigma})=mk\). 

From the proof, we deduce that invariance under a permutation \(\sigma\) depends only on \(\mathcal{P}(\sigma)\). We also deduce a rank constraint on \(\sigma\)-invariant linear functions.

**Corollary 3.3**.: _If a linear function \(f\colon\mathbb{R}^{n}\to\mathbb{R}^{m}\) is invariant under \(\sigma\in\mathcal{S}_{n}\), then its rank is at most \(k\), the number of disjoint cycles into which \(\sigma\) decomposes. _

Invariance under a permutation group \(G\) with arbitrarily many generators can be reduced to invariance under cyclic groups, which we make precise in the following proposition.

**Proposition 3.4**.: _Let \(G=\langle\sigma_{1},\ldots,\sigma_{g}\rangle\leq\mathcal{S}_{n}\) be a permutation group. There exists \(\sigma\in\mathcal{S}_{n}\) such that \(\mathcal{I}_{m\times n}^{G}=\mathcal{I}_{m\times n}^{\sigma}\)._

Proof.: Decompose each \(\sigma_{i}\) into pairwise disjoint cycles \(\pi_{i,1}\circ\cdots\circ\pi_{i,k_{i}}.\) Invariance of a matrix \(M\) under \(\sigma_{i}\) forces some of the columns of \(M\) to coincide and depends only on the partition \(\mathcal{P}(\sigma_{i})\) of \([n]\). Any additional \(\sigma_{j}\), \(j\neq i\), forces further columns of \(M\) to coincide. Invariance of \(M\) under \(G\) is hence described by the finest common coarsening of \(\mathcal{P}(\sigma_{1}),\ldots,\mathcal{P}(\sigma_{k})\). 

We deduce from the proof that \(\mathcal{I}_{m\times n}^{G}=\mathcal{I}_{m\times n}^{\sigma}\) for any \(\sigma\in\mathcal{S}_{n}\) whose induced partition \(\mathcal{P}(\sigma)\) is the finest common coarsening of \(\{\mathcal{P}(\sigma_{1}),\ldots,\mathcal{P}(\sigma_{k}\}\).

### Characterization of \(\mathcal{I}_{r,m\times n}^{G}\)

By omitting repeated columns, we see that \(\mathcal{I}_{r,m\times n}^{G}\) is linearly isomorphic to \(\mathcal{M}_{\min(r,k),m\times k}\). We formulate this key observation as a proposition.

**Proposition 3.5**.: _Let \(G=\langle\sigma\rangle\leq\mathcal{S}_{n}\) be cyclic, and \(\sigma=\pi_{1}\circ\cdots\circ\pi_{k}\) its decomposition into pairwise disjoint cycles \(\pi_{i}\). The variety \(\mathcal{I}_{r,m\times n}^{\sigma}\) is isomorphic to the determinantal variety \(\mathcal{M}_{\min(r,k),m\times k}\) via a linear morphism that deletes repeated columns:_

\[\psi_{\mathcal{P}(\sigma)}\colon\,\mathcal{I}_{r,m\times n}^{\sigma}\to \mathcal{M}_{\min(r,k),m\times k}\,. \tag{3.2}\]
Proof.: For each \(A_{i}\in\mathcal{P}(\sigma)\), \(\Psi_{\mathcal{P}(\sigma)}\) remembers the column \(m_{A_{i}}\) of \(M\). Intersecting with \(\mathcal{M}_{r,m\times n}\) imposes linear dependencies on the columns of \(M\). This mapping rule is linear in the entries of \(M\). To invert \(\psi_{\mathcal{P}(\sigma)}\), one needs to remember \(\mathcal{P}(\sigma)\) as datum. 

**Example 3.6** (\(m=2\), \(n=5\), \(r=1\)).: Let \(\sigma=(1\,3\,4)(2\,5)\in\mathcal{S}_{5}\) and hence \(k=2\). Any invariant matrix \(M\in\mathcal{M}_{2\times 5}(\mathbb{R})\) is of the form \(\left(\begin{smallmatrix}\alpha&\gamma&\alpha&\alpha&\gamma\\ \beta&\delta&\beta&\beta\end{smallmatrix}\right)\) for some \(\alpha,\beta,\gamma,\delta\in\mathbb{R}\). The rank constraint \(r=1\) imposes that \((\gamma,\delta)=\lambda\cdot(\alpha,\beta)^{\top}\) for some \(\lambda\in\mathbb{R}\), where we assume w.l.o.g. that \((\alpha,\beta)\neq(0,0)\) in the case of rank one. The morphism (3.2) hence is

\[\psi_{\mathcal{P}(\sigma)}\colon\begin{pmatrix}\alpha&\lambda\alpha&\alpha& \alpha&\lambda\alpha\\ \beta&\lambda\beta&\beta&\beta&\lambda\beta\end{pmatrix}\mapsto\begin{pmatrix} \alpha&\lambda\alpha\\ \beta&\lambda\beta\end{pmatrix}\,. \tag{3.3}\]

To invert the morphism \(\psi_{\mathcal{P}(\sigma)}\), one reads from \(\mathcal{P}(\sigma)\) how to copy and paste the columns \((\alpha,\beta)^{\top}\) and \((\lambda\alpha,\lambda\beta)^{\top}\) to recover the \(2\times 5\) matrix one started with. \(\diamond\)

**Corollary 3.7**.: _In the setup of Proposition 3.5, one has_

\[\dim\left(\mathcal{I}^{\sigma}_{r,m\times n}\right) =\;\min(r,k)\cdot(m+k-\min(r,k))\,,\] \[\deg\left(\mathcal{I}^{\sigma}_{r,m\times n}\right) =\;\prod_{i=0}^{k-\min(r,k)-1}\frac{(m+i)!\,\cdot\!i!}{(\min(r,k) +i)!\,\cdot\!(m-(\min(r,k)+i)!}\,, \tag{3.4}\] \[\operatorname{Sing}(\mathcal{I}^{\sigma}_{r,m\times n}) =\;\psi_{\mathcal{P}(\sigma)}^{-1}\left(\mathcal{M}_{\min(r,k)-1, m\times k}\right)\,.\]

Proof.: The statements are an immediate consequence of Lemma 2.8 combined with Equations (2.15) and (2.16), and Lemma 2.4. 

The following statement is non-trivial in light of Example 2.9.

**Proposition 3.8**.: _The ED degree of \(\mathcal{I}^{\sigma}_{r,m\times n}(\mathbb{R})\) is_

\[\deg_{\mathrm{ED}}\left(\mathcal{I}^{\sigma}_{r,m\times n}(\mathbb{R})\right) \,=\,\deg_{\mathrm{ED}}\left(\mathcal{M}_{\min(r,k),m\times k}(\mathbb{R}) \right). \tag{3.5}\]

Proof.: Let \(\sigma\in\mathcal{S}_{n}\) consist of \(k\) disjoint cycles \(\pi_{1},\ldots,\pi_{k}\) of lengths \(\ell_{1},\ldots,\ell_{k}\). After re-ordering the columns of \(M\in\mathcal{I}^{\sigma}_{m\times n}\) according to the cycle decomposition, the matrices \(M\) are those whose first \(\ell_{1}\) many columns are equal, and whose following \(\ell_{2}\) many columns are equal, and so on. Given any data matrix \(U\in\mathcal{M}_{m\times n}\), when minimizing its Euclidean distance to \(\mathcal{I}^{\sigma}_{r,m\times n}\), we can assume without loss of generality that \(U\) is contained in the linear space \(\mathcal{I}^{\sigma}_{m\times n}\) by orthogonally projecting \(U\) onto that linear space. The squared Euclidean distance from \(M\) to such \(U\) then becomes

\[\sum_{i=1}^{m}\sum_{j=1}^{k}\,\ell_{j}\cdot\left(M_{i,l(j)}-U_{i,l(j)}\right)^{ 2}, \tag{3.6}\]

where the \(l(j)\coloneqq\ell_{1}+\cdots+\ell_{j-1}+1\) index the pairwise different columns of \(M\) resp. \(U\). In other words, only keeping the columns indexed by the \(l(j)\) is exactly the linear projection from \(\mathcal{I}^{\sigma}_{r,m\times n}\) onto \(\mathcal{M}_{\min(r,k),m\times k}\). Hence, (3.6) is a _weighted_ Euclidean distance from
to a data matrix. Such weighted Euclidean distances and low-rank matrix problems are discussed in Chapter 2 of the upcoming textbook [3]. Denoting by \(\tilde{M}\) and \(\tilde{U}\) the \(m\times k\) matrices with columns indexed by the \(l(j)\), we can express our ED problem explicitly as

\[\min_{\tilde{M}\,\in\,\mathcal{M}_{\min(r,k),m\times k}}\,\sum_{i=1}^{m}\sum_{j =1}^{k}\,\ell_{j}\cdot\left(\tilde{M}_{i,j}-\tilde{U}_{i,j}\right)^{2}. \tag{3.7}\]

In general, introducing weights changes the ED degree. However, the weights in (3.7) are special, since the entries in column \(j\) are all affected by the _same_ weight \(\ell_{j}\). Since scaling the columns of a matrix \(\tilde{M}\) by non-zero scalars--here \(\sqrt{\ell_{j}}\)--is an automorphism on \(\mathcal{M}_{\min(r,k),m\times k}\), we can rewrite (3.7) as

\[\min_{\tilde{M}\in\mathcal{M}_{\min(r,k),m\times k}}\,\sum_{i=1}^{m}\sum_{j=1 }^{k}\left(\sqrt{\ell_{j}}\tilde{M}_{i,j}-\sqrt{\ell_{j}}\tilde{U}_{i,j} \right)^{2}\;=\min_{\tilde{M}\in\mathcal{M}_{\min(r,k),m\times k}}\sum_{i=1}^{ m}\sum_{j=1}^{k}\left(\tilde{M}_{i,j}-\sqrt{\ell_{j}}\tilde{U}_{i,j} \right)^{2}\,.\]

From the latter reformulation, we conclude that the ED degree of \(\mathcal{M}_{\min(r,k),m\times k}(\mathbb{R})\) coincides with the ED degree of \(\mathcal{I}^{\sigma}_{r,m\times n}(\mathbb{R})\). 

### Parameterizing invariance and network design

In this section, we investigate which implications imposing invariance has on the individual layers of a linear autoencoder. Recall that a matrix \(M\in\mathcal{M}_{n\times n}(\mathbb{K})\) has rank \(r\leq n\) if and only if there exist rank-\(r\) matrices \(A\in\mathcal{M}_{n\times r}(\mathbb{K})\) and \(B\in\mathcal{M}_{r\times n}(\mathbb{K})\) such that \(M=AB\). The factors of an invariant matrix do not need to be invariant, as the following example demonstrates. To be more precise, this questions makes sense to be asked a priori only for the first layer, \(B\), since the group \(G\) acts on \(\mathbb{R}^{n}\) only.

**Example 3.9**.: Let \(\sigma=(1\,2)\in\mathcal{S}_{3}\) and consider

\[A\,=\,\begin{pmatrix}1&1\\ 1&1\\ 0&0\end{pmatrix}\quad\text{and}\quad B\,=\,\begin{pmatrix}1&2&1\\ 2&1&1\end{pmatrix}. \tag{3.8}\]

Observe that \(B\) is not invariant under \(\sigma\), but the product \(AB\) is. \(\diamond\)

**Proposition 3.10** ([15, Proposition 22]).: _Let \(r\leq n\). Denote by \(\mu\colon\mathcal{M}_{n\times r}\times\mathcal{M}_{r\times n},\;(A,B)\mapsto A \cdot B,\) the multiplication map. If \(\operatorname{rank}(M)=r\) and \(M=\mu(A,B)\), then its fiber is_

\[\mu^{-1}(M)\,=\,\left\{\left(AT^{-1},TB\right)\,|\,T\in\operatorname{GL}_{r}( \mathbb{K})\right\}\,\subset\,\mathcal{M}_{n\times r}\times\mathcal{M}_{r \times n}\,. \tag{3.9}\]

**Proposition 3.11**.: _Any matrix \(M\in\mathcal{M}_{n\times n}\) that is invariant under a permutation \(\sigma\in\mathcal{S}_{n}\) with \(k\) pairwise disjoint cycles factorizes as_

\[M\ =\ M_{1}\cdot(e_{i_{1}}|\cdots|e_{i_{n}})\, \tag{3.10}\]

_where the \(M_{1}\in\mathcal{M}_{n\times k}\) and the \(e_{i_{j}}\), for \(j=1,\ldots,n\), are standard basis vectors of \(\mathbb{R}^{k}\) with repetitions being allowed._
Proof.: Let \(M\) be invariant under \(\sigma\in\mathcal{S}_{n}\). For each \(A_{i}\in\mathcal{P}(\sigma)\), remember the column \(m_{A_{i}}\) and collect them as the columns of the \(m\times k\) matrix \(M_{1}\coloneqq(m_{A_{1}}|\cdots|m_{A_{k}}).\) The remaining columns of \(M\) are copies of columns of \(M_{1}\), hence \(M=M_{1}\cdot(e_{i_{1}}|\cdots|e_{i_{n}})\) for standard basis vectors \(e_{i_{j}}\) of \(\mathbb{R}^{k}\), with repetitions being allowed. 

**Example 3.12** (\(n=4\)).: Let \(\sigma=(1\,3)\in\mathcal{S}_{4}\), so that \(k=3\). The matrix

\[M\,=\,\begin{pmatrix}1&0&1&1\\ 2&4&2&1\\ 3&4&3&1\\ 0&2&0&1\end{pmatrix}\,=\,\begin{pmatrix}1&0&1\\ 2&4&1\\ 3&4&1\\ 0&2&1\end{pmatrix}\cdot\begin{pmatrix}1&0&1&0\\ 0&1&0&0\\ 0&0&0&1\end{pmatrix} \tag{3.11}\]

is invariant under \(\sigma\) and factorizes as claimed in Proposition 3.11. 

**Proposition 3.13**.: _Let \(M\) be invariant under \(\sigma\) and of maximal possible rank, i.e., of \(\operatorname{rank}(M)=k\). Then every factorization \(M=AB\) of \(M\) is of the form_

\[(A,B)\,\in\,\left\{\left(M_{1}T^{-1},T\cdot(e_{i_{1}}|\cdots|e_{i_{n}})\right) \,|\,T\in\operatorname{GL}_{k}\right\}\,. \tag{3.12}\]

Proof.: The statement is an immediate consequence of Propositions 3.10 and 3.11. 

This statement tells us that linear autoencoders are well-suited for expressing invariance when one imposes appropriate weight sharing on the encoder. More precisely, the decoder factor \(M_{1}T^{-1}\) in (3.12) is an arbitrary matrix, but the encoder factor \(T\cdot(e_{i_{1}}|\cdots|e_{i_{n}})\) has repeated columns. We impose this repetition pattern via weight sharing on the encoder. Proposition 3.13 states that invariant matrices naturally lie in the function space of such an autoencoder. Given any permutation \(\sigma\in\mathcal{S}_{n}\), we say that an encoder \(\mathbb{R}^{n}\to\mathbb{R}^{r}\) has _\(\sigma\)-weight sharing_ if its representing matrices satisfy the following: for every set \(S\in\mathcal{P}(\sigma)\), the columns indexed by the elements in \(S\) coincide, and no additional weight sharing is imposed.

**Example 3.14**.: We revisit Example 2.12. The invariance of a matrix \(M=A\cdot B\in\mathcal{I}_{2,5\times 5}^{\sigma}\) forces the encoder factor \(B\) to fulfill the following weight sharing property:

Which weights have to coincide is to be read from the color labeling in the figure above. \(\diamond\)

**Proposition 3.15**.: _Let \(\sigma\in\mathcal{S}_{n}\) be a permutation consisting of \(k\) disjoint cycles, and let \(r\leq k\). Consider the linear autoencoder \(\mathbb{R}^{n}\to\mathbb{R}^{r}\to\mathbb{R}^{n}\) with fully-connected dense decoder \(\mathbb{R}^{r}\to\mathbb{R}^{n}\) and encoder \(\mathbb{R}^{n}\to\mathbb{R}^{r}\) with \(\sigma\)-weight sharing. Its function space is \(\mathcal{I}_{r,n\times n}^{\sigma}(\mathbb{R})\)._

Figure 2: The \(\sigma\)-weight sharing property imposed on the encoder by \(\sigma=(1\,3\,4)(2\,5)\).
Proof.: Every matrix in the function space of the autoencoder is of the form \(AB\) such that the encoder factor \(B\in\mathcal{M}_{r\times n}\) has repeated columns according to \(\mathcal{P}(\sigma).\) Therefore, the product \(AB\) has the same repetition in its columns, i.e., \(AB\in\mathcal{I}_{n\times n}^{\sigma}\). Since \(\operatorname{rank}(AB)\leq\operatorname{rank}(B)\leq r\), we conclude that \(AB\in\mathcal{I}_{r,n\times n}^{\sigma}(\mathbb{R})\). For the converse direction, consider \(M\in\mathcal{I}_{r,n\times n}^{\sigma}(\mathbb{R})\). By Proposition 3.11, that matrix can be factorized as \(M=M_{1}\cdot(e_{i_{1}}|\cdots|e_{i_{n}})\), where \(M_{1}\in\mathcal{M}_{n\times k}\). If \(r=k\), that factorization is compatible with the autoencoder and we are done. Thus, it is left to consider the case \(r<k\). Note that the factor \((e_{i_{1}}|\cdots|e_{i_{n}})\) has full rank \(k\) by construction since the standard basis vectors in the columns of that matrix correspond to the \(k\) cycles of \(\sigma\). Hence, we have that \(\operatorname{rank}(M_{1})=\operatorname{rank}(M)=r\). Therefore, we can factorize \(M_{1}=A_{1}B_{1}\), where \(A_{1}\in\mathcal{M}_{n\times r}\) and \(B_{1}\in\mathcal{M}_{r\times k}\). The factorization \(M=A_{1}\cdot(B_{1}\cdot(e_{i_{1}}|\cdots|e_{i_{n}}))\) is compatible with the autoencoder. 

### Induced filtration of \(\mathcal{M}_{r,m\times n}\)

If an \(m\times n\) matrix \(M\) is invariant under \(\sigma\in\mathcal{S}_{n}\), then it is also invariant under every permutation \(\eta\in\mathcal{S}_{n}\) whose associated partition \(\mathcal{P}(\eta)\) of \([n]\) is a refinement \(\mathcal{P}(\eta)\prec\mathcal{P}(\sigma)\) of \(\mathcal{P}(\sigma)\). This induces a filtration \(\mathcal{I}_{m\times n}^{\bullet}\) of the variety \(\mathcal{M}_{m\times n}\), which is indexed by partitions of \([n]\), and by intersecting with \(\mathcal{M}_{r,m\times n}\), we obtain a filtration \(\mathcal{I}_{r,m\times n}^{\bullet}\) of the variety \(\mathcal{M}_{r,m\times n}\). The set \(\mathcal{P}([n])\) of partitions of \([n]\) equals \(\mathcal{S}_{n}/{\sim}\), where we identify \(\sigma_{1}\sim\sigma_{2}\) if and only if \(\mathcal{P}(\sigma_{1})=\mathcal{P}(\sigma_{2})\). Here, \(\mathcal{I}_{r,m\times n}^{\mathcal{P}}\) denotes any \(\mathcal{I}_{r,m\times n}^{\sigma}\) for which \(\mathcal{P}(\sigma)=\mathcal{P}\). As we saw earlier on, the variety \(\mathcal{I}_{r,m\times n}^{\sigma}\) depends only on \(\mathcal{P}(\sigma)\), but not on \(\sigma\) itself, hence this notion is well-defined. Together with refinements of partitions, the set of partitions of \([n]\) is a partially ordered set. Define the category \(\underline{\operatorname{Part}}_{[n]}^{\prec}\) whose set of objects is \(\mathcal{P}([n])\), and a morphism from \(\mathcal{P}_{1}\) to \(\mathcal{P}_{2}\) whenever \(\mathcal{P}_{1}\prec\mathcal{P}_{2}\). By \(\underline{\operatorname{Subv}}_{\mathcal{M}_{r,m\times n}}\), we denote the category whose objects are subvarieties of \(\mathcal{M}_{r,m\times n}\), and the inclusion as morphism between \(U_{1},U_{2}\in\underline{\operatorname{Subv}}_{\mathcal{M}_{r,m\times n}}\) whenever \(U_{1}\subset U_{2}\). This formulation gives rise to the functor

\[\underline{\operatorname{Part}}_{[n]}^{\prec}\longrightarrow\underline{ \operatorname{Subv}}_{\mathcal{M}_{r,m\times n}},\quad\mathcal{P}\,\mapsto \,\mathcal{I}_{r,m\times n}^{\mathcal{P}}\,. \tag{3.13}\]

**Remark 3.16**.: The opposite category \(\underline{\operatorname{Part}}_{[n]}^{\prec,\mathrm{op}}\) of \(\underline{\operatorname{Part}}_{[n]}^{\prec}\) is \(\underline{\operatorname{Part}}_{[n]}^{\prec}\), i.e., partitions of \([n]\) with coarsenings \(\succ\) of partitions as morphisms. In this formulation, the finest common coarsening of partitions \(\mathcal{P}_{1},\dots,\mathcal{P}_{k}\) then is their inverse limit. \(\diamond\)

## 4 Equivariance under cyclic subgroups of \(\mathcal{S}_{n}\)

In this section, we address equivariance under cyclic subgroups \(G=\langle\sigma\rangle\leq\mathcal{S}_{n}\). We explore some fundamental algebraic properties of \(\mathcal{E}_{r,n\times n}^{\sigma}\subset\mathcal{M}_{r,n\times n}\) such as its number of irreducible components, their dimension and degree as well as their singular points.

### Characterizing equivariance

#### 4.1.1 In cycle decomposition

We consider a permutation \(\sigma=\pi_{1}\circ\cdots\circ\pi_{k}\in\mathcal{S}_{n}\) with a decomposition into pairwise disjoint cycles of lengths \(\ell_{1},\dots,\ell_{k}\). We reorder the entries in \(\mathbb{R}^{n}\) as in Step 1 of Procedure 2.11
such that the permutation matrix \(P_{\sigma}\) becomes block diagonal with cyclic blocks as in (2.20). Those square blocks have sizes \(\ell_{1},\ldots,\ell_{k}\).

We are interested in matrices \(M\in\mathcal{M}_{n\times n}\) that are equivariant under \(\sigma\). We have already characterized those matrices after a base change that diagonalized \(P_{\sigma}\) in Lemma 2.13. However, in general, that base change involves complex Vandermonde matrices. Since we are mainly interested in real matrices \(M\), we characterize now the equivariant matrices in the basis where \(P_{\sigma}\) is a block diagonal matrix, with cyclic diagonal blocks of sizes \(\ell_{1},\ldots,\ell_{k}\). For that, we divide \(M\in\mathcal{M}_{n\times n}\) into blocks following the same pattern: \(M\) has square diagonal blocks \(M^{(ii)}\) of size \(\ell_{i}\times\ell_{i}\) and rectangular off-diagonal blocks \(M^{(ij)}\) of size \(\ell_{i}\times\ell_{j}\). We now show that the equivariance of \(M\) under \(\sigma\) means that its blocks have to be _(rectangular) circulant matrices_. We can observe this property in our previous example (2.13). We call a (possibly non-square) matrix _circulant_ if each row is a copy of the previous row, cyclically shifted one step to the right, and also each column is a copy of the previous column, cyclically shifted one step downwards. Some examples of such matrices are shown in Equation (4.1). A circulant matrix of size \(\ell_{i}\times\ell_{j}\) has at most \(\gcd(\ell_{i},\ell_{j})\) different entries.

\[\begin{pmatrix}\alpha^{(ij)}&\beta^{(ij)}&\gamma^{(ij)}\\ \gamma^{(ij)}&\alpha^{(ij)}&\beta^{(ij)}\\ \beta^{(ij)}&\gamma^{(ij)}&\alpha^{(ij)}\end{pmatrix},\quad\begin{pmatrix} \alpha^{(ij)}&\alpha^{(ij)}&\alpha^{(ij)}\\ \alpha^{(ij)}&\alpha^{(ij)}&\alpha^{(ij)}\\ \alpha^{(ij)}&\alpha^{(ij)}&\alpha^{(ij)}\\ \alpha^{(ij)}&\alpha^{(ij)}&\alpha^{(ij)}\end{pmatrix}, \tag{4.1}\]

**Proposition 4.1**.: _The matrix \(M\in\mathcal{M}_{n\times n}\) is equivariant under \(\sigma\) if and only if each block \(M^{(ij)}\) of \(M\) is a (possibly non-square) circulant matrix._

Proof.: Since \(P_{\sigma}\) is a block diagonal matrix with cyclic blocks \(C_{1},\ldots,C_{k}\), the equivariance condition \(MP=PM\) means that \(M^{(ij)}C_{j}=C_{i}M^{(ij)}\) for all \(i,j\). The multiplication by \(C_{i}\) from the left cyclically permutes the rows of \(M\), and the multiplication by \(C_{j}\) from the right permutes the columns of \(M\). Since the resulting matrices need to coincide, it follows that the block \(M^{(ij)}\) has to be circulant. 

#### 4.1.2 Irreducible components of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{C})\)

Our focus now shifts to exploring the intriguing algebraic properties arising from the intersection of \(\mathcal{M}_{r,n\times n}\) with \(C(P_{\sigma})\). Both \(\mathcal{M}_{r,n\times n}\) and \(C(P_{\sigma})\) are algebraic spaces, meaning they can be characterized by polynomial equations. Their intersection \(\mathcal{E}^{\sigma}_{r,n\times n}=\mathcal{M}_{r,n\times n}\cap C(P_{\sigma})\) inherits this property and is also an algebraic set. In the following statement, we use the notation from Lemma 2.14.

**Proposition 4.2**.: _There is a one-to-one correspondence between the irreducible components of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{C})\) and the integer solutions \(\mathbf{r}=(r_{l,m})\) of_

\[\sum_{l\geq 1}\sum_{m\,\in\,(\mathbb{Z}/\mathbb{Z})^{\times}}r_{l,m}\ =\ r\,,\quad\text{ where }\,0\leq r_{l,m}\leq d_{l}\,. \tag{4.2}\]
_The dimension of the irreducible component corresponding to such an integer solution \(\mathbf{r}\) is_

\[\sum_{l\geq 1}\sum_{m\,\in\,(\mathbb{Z}/l\mathbb{Z})^{\times}}(2d_{l}-r_{l,m}) \cdot r_{l,m}\,. \tag{4.3}\]

Proof.: By Lemma 2.14, every matrix \(M\in C(P_{\sigma})\) is similar to a complex block-diagonal matrix \(B\) with \(\varphi(l)=|(\mathbb{Z}/l\mathbb{Z})^{\times}|\) many blocks of size \(d_{l}\times d_{l}\) for every \(l\). We will denote these blocks by \(B_{l,m}\) for \(m\in(\mathbb{Z}/l\mathbb{Z})^{\times}\). Imposing a rank constraint on the matrix \(M\) affects the rank of the diagonal blocks of \(B\). Hence, if \(r_{l,m}\) is the rank of the block \(B_{l,m}\), then \(M\) has rank \(r\) if and only if (4.2) holds. This implies that the number of different irreducible components of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{C})\) is exactly the number of solution vectors to (4.2), where \(0\leq r_{l,m}\leq d_{l}\). The second part of the proposition follows directly from (2.15). 

**Example 4.3**.: Let \(\sigma\) again denote the clockwise rotation by \(90\) degrees on images with \(3\times 3\) pixels. The numbers \(d_{l}\) are computed in Example 2.18. For the permutation matrix in (2.11), if \(r=3\) then the number of irreducible components is equal to the number of non-negative integer solutions of the equation \(r_{1,1}+r_{2,1}+r_{4,1}+r_{4,3}=3\), where \(r_{1,1}\leq 3=d_{1}\), \(r_{2,1}\leq 2=d_{2}\), and \(r_{4,1},r_{4,3}\leq 2=d_{4}\). With the stars and bars formula, one finds that there are \(\binom{6}{3}-3=17\) solutions, and hence \(\mathcal{E}^{\sigma}_{3,9\times 9}(\mathbb{C})\) has \(17\) irreducible components. Six of those have dimension \(11\), five have dimension \(9\), and the remaining six have dimension \(7\). The six maximal-dimensional components correspond to the integer solutions \((r_{1,1},r_{2,1},r_{4,1},r_{4,3})\in\{(2,1,0,0),\,(2,0,1,0),\,(2,0,0,1),\,(1,1, 1,0),\,(1,1,0,1),\,(1,0,1,1)\}\). \(\diamond\)

These discussions imply that, in contrast to the case of invariance, autoencoders are not well-suited to parameterize equivariant functions: For a rank constraint \(r<n\), \(\mathcal{E}^{\sigma}_{r,n\times n}\) has many components; the function space of an autoencoder would cover only a single one of them.

Not all irreducible components of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{C})\) have to appear in the real locus \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{R})\). We will see this later in Example 4.8.

**Proposition 4.4**.: _Let \(\mathbf{r}\) be an integer solution of (4.2). The degree of the corresponding irreducible component of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{C})\) is equal to_

\[\prod_{l}\prod_{m\,\in\,(\mathbb{Z}/l\mathbb{Z})^{\times}}\prod_{i=0}^{d_{l}-r _{l,m}-1}\frac{(d_{l}+i)!\,\cdot\,\!i!}{(r_{l,m}+i)!\,\cdot\,\!(d_{l}-r_{l,m}+i )!}. \tag{4.4}\]

Proof.: After the full base change in Procedure 2.11, the irreducible component of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{C})\) corresponding to \(\mathbf{r}\) is the set of block diagonal matrices where the block with label \((l,m)\) has rank \(r_{l,m}\). Now (4.4) follows from (2.16). 

**Proposition 4.5**.: _Let \(1\leq r<n\). The locus of singular points of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{K})\) is \(\mathcal{E}^{\sigma}_{r-1,n\times n}(\mathbb{K})\)._

Proof.: Again, after Procedure 2.11, the irreducible component \(\mathcal{E}^{(\mathbf{r})}\) of \(\mathcal{E}^{\sigma}_{r,n\times n}(\mathbb{C})\) corresponding to an integer solution \(\mathbf{r}\) of (4.2) is the set of block-diagonal matrices such that each block has rank at most \(r_{l,m}\). Therefore, by Lemma 2.4, the singular points of \(\mathcal{E}^{(\mathbf{r})}\) are exactly
\(\mathcal{E}^{(\mathbf{r})}\cap\mathcal{E}^{\sigma}_{r-1,n\times n}\). Finally, since the intersection of two distinct components \(\mathcal{E}^{(\mathbf{r})}\) and \(\mathcal{E}^{(\mathbf{r}^{\prime})}\) is a subset of \(\mathcal{E}^{\sigma}_{r-1,n\times n}\), we get that

\[\operatorname{Sing}(\mathcal{E}^{\sigma}_{r,n\times n})\,=\,\bigcup_{\mathbf{r }}\left(\mathcal{E}^{(\mathbf{r})}\cap\mathcal{E}^{\sigma}_{r-1,n\times n} \right)\,=\,\mathcal{E}^{\sigma}_{r-1,n\times n}\,,\]

concluding the proof. 

### Parameterizing equivariance

We observe already in simple examples that the factors of an equivariant linear map themselves do _not_ need to be equivariant.

**Example 4.6**.: Let \(\sigma=(1\,2)\in\mathcal{S}_{3}\) and \(M\) be the invertible matrix

\[M\,=\,\begin{pmatrix}1&2&0\\ 2&1&0\\ 3&3&4\end{pmatrix}.\]

Indeed, \(MP_{\sigma}=P_{\sigma}M\), hence \(M\) is equivariant under \(\sigma\). Let \(M=QR\) denote the QR decomposition of \(M\); uniqueness of the decomposition is obtained by imposing that \(R\) has positive diagonal entries. One can check that neither \(Q\) nor \(R\) is equivariant under \(\sigma\). \(\diamond\)

**Remark 4.7**.: The question whether the individual layers of an equivariant autoencoder are equivariant, is not well-posed in its naive form. A priori, the group \(G\) acts only on the in- and output space of \(f_{\theta}\colon\mathbb{R}^{n}\to\mathbb{R}^{r}\to\mathbb{R}^{n}\). To address questions about equivariance of the two individual layers, one would first need to define an action of \(G\) on \(\mathbb{R}^{r}\), in a way that is "meaningful" for the considered application. \(\diamond\)

In Section 3.3, we described how linear autoencoders are well-suited to parameterize permutation-invariant maps. We leave the general theory for the case of equivariance for future work. We consider the example for rotation-equivariant maps of rank at most one.

**Example 4.8** (Parameterization of \(\mathcal{E}^{\sigma}_{1,9\times 9}\)).: Let \(\sigma\in\mathcal{S}_{9}\) again denote the rotation of a \(3\times 3\) picture by \(90\) degrees. Denote by \(P\) the matrix obtained by applying Step 1 of Procedure 2.11 to \(P_{\sigma}\), i.e., \(P\) is the block diagonal matrix \(\operatorname{diag}(C_{4},C_{4},C_{1})\). Its eigenvalues are \(\{1,1,1,-1,-1,i,i,-i,-i\}\), here denoted as multiset together with their multiplicities. We chop \(M\) into blocks of sizes determined by the blocks of \(P\), i.e. into blocks of size pattern

\[\left(\begin{array}{c|c|c}4\times 4&4\times 4&4\times 1\\ \hline 4\times 4&4\times 4&4\times 1\\ \hline 1\times 4&1\times 4&1\times 1\end{array}\right).\]

Each of the blocks \(M^{(i,j)}\) is circulant, as spelled out in (2.13). We are now going to describe the set of matrices \(M\) which commutate with \(P\) and are of rank at most \(1\). Imposing \(r=1\) gives rise to three irreducible components of \(\mathcal{E}^{\sigma}_{1,9\times 9}(\mathbb{C})\) of dimension \(3\) and one of dimension \(5\) according to Proposition 4.2. An explicit analysis reveals that the general matrices in the four components of \(\mathcal{E}^{\sigma}_{1,9\times 9}(\mathbb{C})\) take the following forms for scalars \(\alpha,\beta,\gamma,\lambda,\mu\):
\[\left(\begin{array}{cccc|cccc|cccc}\alpha&\alpha&\alpha&\alpha&\alpha&\lambda \alpha&\lambda\alpha&\lambda\alpha&\lambda\alpha&-\lambda\alpha&\lambda\alpha\\ \alpha&\alpha&\alpha&\alpha&\lambda\alpha&\lambda\alpha&\lambda\alpha&\lambda\alpha &\lambda\alpha\\ \alpha&\alpha&\alpha&\alpha&\lambda\alpha&\lambda\alpha&\lambda\alpha&\lambda \alpha&\lambda\alpha\\ \alpha&\alpha&\alpha&\alpha&\lambda\alpha&\lambda\alpha&\lambda\alpha&\lambda \alpha&\lambda\alpha\\ \alpha&\alpha&\alpha&\alpha&\lambda\alpha&\lambda\alpha&\lambda\alpha&\lambda \alpha&\lambda\alpha\\ \hline\beta&\beta&\beta&\beta&\lambda\beta&\lambda\beta&\lambda\beta&\lambda \beta&\lambda\beta&\lambda\beta\\ \beta&\beta&\beta&\beta&\lambda\beta&\lambda\beta&\lambda\beta&\lambda\beta& \lambda\beta\\ \beta&\beta&\beta&\beta&\lambda\beta&\lambda\beta&\lambda\beta&\lambda\beta& \lambda\beta\\ \hline\gamma&\gamma&\gamma&\gamma&\gamma&\lambda\gamma&\lambda\gamma&\lambda \gamma&\lambda\gamma&\mu\gamma\end{array}\right),\]

\[\left(\begin{array}{cccc|cccc|cccc}\alpha&-i\alpha&-\alpha&i\alpha&\lambda \alpha&-i\lambda\alpha&-\lambda\alpha&i\lambda\alpha&\\ i\alpha&\alpha&-i\alpha&-\alpha&i\lambda\alpha&\lambda\alpha&-i\lambda\alpha &-\lambda\alpha&0\\ -\alpha&i\alpha&\alpha&-i\alpha&-\lambda\alpha&i\lambda\alpha&\lambda\alpha&-i \lambda\alpha&0\\ -i\alpha&-\alpha&i\alpha&\alpha&-i\lambda\alpha&-\lambda\alpha&i\lambda\alpha& \lambda\alpha&\alpha\\ \hline\beta&-i\beta&-\beta&i\beta&\lambda\beta&-i\lambda\beta&-i\lambda\beta& -\lambda\beta&0\\ -\beta&i\beta&\beta&-i\beta&-\lambda\beta&i\lambda\beta&\lambda\beta&-i\lambda \beta&0\\ -\beta&i\beta&\beta&-i\beta&-\lambda\beta&i\lambda\beta&\lambda\beta&-i\lambda \beta&0\\ -i\beta&-\beta&i\beta&\beta&-i\lambda\beta&-\lambda\beta&i\lambda\beta&\lambda \beta&0\\ \hline\end{array}\right),\]

or

\[\left(\begin{array}{cccc|cccc|cccc}\alpha&i\alpha&-\alpha&-i\alpha&\lambda \alpha&i\lambda\alpha&-\lambda\alpha&-i\lambda\alpha&\\ -i\alpha&\alpha&i\alpha&-\alpha&-i\lambda\alpha&\lambda\alpha&i\lambda\alpha& -\lambda\alpha\\ -\alpha&-i\alpha&\alpha&i\alpha&-\lambda\alpha&-i\lambda\alpha&\lambda\alpha &i\lambda\alpha\\ i\alpha&-\alpha&-i\alpha&\alpha&i\lambda\alpha&-\lambda\alpha&-i\lambda\alpha &\lambda\alpha&\lambda\alpha\\ \hline\beta&i\beta&-\beta&-i\beta&\lambda\beta&i\lambda\beta&-\lambda\beta& -i\lambda\beta&-i\lambda\beta\\ -i\beta&\beta&i\beta&-\beta&-i\lambda\beta&\lambda\beta&i\lambda\beta&-\lambda \beta\\ -\beta&-i\beta&\beta&i\beta&-\lambda\beta&-i\lambda\beta&\lambda\beta&i\lambda \beta\\ i\beta&-\beta&-i\beta&\beta&i\lambda\beta&-\lambda\beta&-i\lambda\beta&\lambda \beta&\lambda\beta\\ \hline\end{array}\right).\]

Hence, \(\mathcal{E}^{\sigma}_{1,9\times 9}(\mathbb{C})\) has four complex irreducible components, but only the first two of them also appear in the real locus \(\mathcal{E}^{\sigma}_{1,9\times 9}(\mathbb{R})\). Note that in this particular case, all components are vector spaces--but this is a special occurrence for imposing \(r=1\). \(\diamond\)

### Induced filtration of \(\mathcal{M}_{r,n\times n}\)

Let \(\sigma\in\mathcal{S}_{n}\). Whenever a matrix is invariant under \(\sigma\), then it is also invariant under any power of \(\sigma\). Hence, \(\mathcal{E}^{\sigma^{k}}_{n\times n}\subset\mathcal{E}^{\sigma^{l\cdot k}}_{n \times n}\) for all \(k,l\in\mathbb{N}\). Therefore, any \(\sigma\in\mathcal{S}_{n}\) gives rise to an increasing filtration \(\mathcal{E}^{\sigma^{\bullet}}_{n\times n}\) of \(\mathcal{M}\) (and \(\mathcal{E}^{\sigma^{\bullet}}_{r,n\times n}\) of \(\mathcal{M}_{r,n\times n}\)). This filtration is finite, since \(l\cdot k>\mathrm{ord}(\sigma)\) for \(l\) sufficiently large, hence \(\mathcal{E}^{\sigma^{l\cdot k}}_{n\times n}=\mathcal{E}^{id}_{n\times n}= \mathcal{M}_{n\times n}\) for such \(l\). By intersecting with \(\mathcal{M}_{r,n\times n}\), we obtain analogous statements for \(\mathcal{E}^{\sigma^{\bullet}}_{r,n\times n}\).

### Example: equivariance for non-cyclic groups

We here revisit equivariance for \(3\times 3\) pictures. Characterizing equivariance for non-cyclic permutation groups is more complicated than the cyclic case. As a case study, we impose
\(\sigma\) equivariance both under rotation and under reflection, i.e., we consider the group \(G=\langle\sigma,\chi\rangle\) generated by the clock-wise rotation by \(90\) degrees \(\sigma\) as in (2.1), and the reflection

\[\chi\colon\,\begin{pmatrix}a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\end{pmatrix}\,\mapsto\,\begin{pmatrix}a_{13}&a_{12}&a_{ 11}\\ a_{23}&a_{22}&a_{21}\\ a_{33}&a_{32}&a_{31}\end{pmatrix}. \tag{4.5}\]

We will again identify \(\mathbb{R}^{3\times 3}\cong\mathbb{R}^{9}\) via

\[\begin{pmatrix}a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33}\end{pmatrix}\mapsto\begin{pmatrix}a_{11}&a_{13}&a_{33}&a_ {31}&a_{12}&a_{23}&a_{32}&a_{21}&a_{22}\end{pmatrix}^{\top}. \tag{4.6}\]

Then \(\chi(A)\) is represented by the vector \((a_{13}\ a_{11}\ a_{31}\ a_{33}\ a_{12}\ a_{21}\ a_{32}\ a_{23}\ a_{22})^{\top}\). Under this identification, the reflection is \(\chi=(1\,2)(3\,4)(6\,8)\in\mathcal{S}_{9}\) is and is represented by the matrix

\[P_{\chi}\,=\,\left(\begin{array}{cccc|cccc}0&1&0&0&&&&\\ 1&0&0&0&&&&\\ 0&0&0&1&&&&\\ 0&0&1&0&&&&\\ \hline&&&1&0&0&0&&\\ &0&&\begin{array}{cccc|cccc}0&0&0&1&&\\ 0&0&1&0&0\\ 0&1&0&0&&\\ \hline 0&&&0&&1\end{array}&0\\ \hline\end{array}\right). \tag{4.7}\]

Hence, equivariance of a matrix \(M=(m_{ij})_{i,j}\in\mathcal{M}_{9\times 9}\) under both \(\sigma\) and \(\chi\), i.e., \(MP_{\sigma}=P_{\sigma}M\) and \(MP_{\chi}=P_{\chi}M\), implies that \(M\) has to be of the form

\[M\,=\,\left(\begin{array}{cccc|cccc}\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha _{2}&\beta_{1}&\beta_{2}&\beta_{2}&\beta_{1}&\varepsilon_{3}\\ \alpha_{2}&\alpha_{1}&\alpha_{2}&\alpha_{3}&\beta_{1}&\beta_{1}&\beta_{2}& \beta_{2}&\varepsilon_{3}\\ \alpha_{3}&\alpha_{2}&\alpha_{1}&\alpha_{2}&\beta_{2}&\beta_{1}&\beta_{1}& \beta_{2}&\varepsilon_{3}\\ \alpha_{2}&\alpha_{3}&\alpha_{2}&\alpha_{1}&\beta_{2}&\beta_{2}&\beta_{1}& \beta_{1}&\varepsilon_{3}\\ \hline\gamma_{1}&\gamma_{1}&\gamma_{3}&\gamma_{3}&\delta_{1}&\delta_{2}& \delta_{3}&\delta_{2}&\varepsilon_{4}\\ \gamma_{3}&\gamma_{1}&\gamma_{1}&\gamma_{3}&\delta_{2}&\delta_{1}&\delta_{2} &\delta_{3}&\varepsilon_{4}\\ \gamma_{3}&\gamma_{3}&\gamma_{1}&\gamma_{1}&\delta_{3}&\delta_{2}&\delta_{1} &\delta_{2}&\varepsilon_{4}\\ \gamma_{1}&\gamma_{3}&\gamma_{3}&\gamma_{1}&\delta_{2}&\delta_{3}&\delta_{2} &\delta_{1}&\varepsilon_{4}\\ \hline\varepsilon_{1}&\varepsilon_{1}&\varepsilon_{1}&\varepsilon_{1}& \varepsilon_{2}&\varepsilon_{2}&\varepsilon_{2}&\varepsilon_{2}&\varepsilon_ {5}\end{array}\right)\,. \tag{4.8}\]

Therefore, \(\dim(\mathcal{E}^{G}_{9\times 9})=81-66=2\cdot 3+2\cdot 2+5\cdot 1=15\). In comparison to matrices that are required to be equivariant under the rotation \(\sigma\) only (see (2.13)), the entries \(\alpha_{4}\), \(\beta_{3}\), \(\beta_{4}\), \(\gamma_{2}\), \(\gamma_{4}\), and \(\delta_{4}\) can no longer be chosen freely, which drops the dimension by \(6\).

Let us add the action of another permutation on \(3\times 3\) pictures, namely shifting each row by one to the right, i.e., for \(i=1,2,3\), \(a_{i,j}\mapsto a_{i,j+1}\) for \(j=1,2\), and \(a_{i,3}\mapsto a_{i,1}\). In the choice from above, the shift corresponds to the permutation \((1\,5\,2)(3\,4\,7)(6\,8\,9)\in\mathcal{S}_{9}\). All
\(9\times 9\) matrices that are equivariant under rotation, reflection, and shift, are of the following form, with only 3 degrees \(\alpha_{1},\alpha_{2},\alpha_{3}\) of freedom:

\[M\,=\,\left(\begin{array}{cccc|cccc}\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{ 2}&\alpha_{2}&\alpha_{3}&\alpha_{3}&\alpha_{2}&\alpha_{3}\\ \alpha_{2}&\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{2}&\alpha_{2}&\alpha_{3} &\alpha_{3}&\alpha_{3}\\ \alpha_{3}&\alpha_{2}&\alpha_{1}&\alpha_{2}&\alpha_{3}&\alpha_{2}&\alpha_{2} &\alpha_{3}&\alpha_{3}\\ \alpha_{2}&\alpha_{3}&\alpha_{3}&\alpha_{1}&\alpha_{3}&\alpha_{3}&\alpha_{2} &\alpha_{2}&\alpha_{3}\\ \hline\alpha_{2}&\alpha_{2}&\alpha_{3}&\alpha_{3}&\alpha_{1}&\alpha_{3}& \alpha_{2}&\alpha_{3}&\alpha_{2}\\ \alpha_{3}&\alpha_{2}&\alpha_{2}&\alpha_{3}&\alpha_{3}&\alpha_{1}&\alpha_{3} &\alpha_{2}&\alpha_{2}\\ \alpha_{3}&\alpha_{3}&\alpha_{2}&\alpha_{2}&\alpha_{2}&\alpha_{3}&\alpha_{1} &\alpha_{3}&\alpha_{2}\\ \alpha_{2}&\alpha_{3}&\alpha_{3}&\alpha_{2}&\alpha_{3}&\alpha_{2}&\alpha_{3} &\alpha_{1}&\alpha_{2}\\ \hline\alpha_{3}&\alpha_{3}&\alpha_{3}&\alpha_{3}&\alpha_{2}&\alpha_{2}& \alpha_{2}&\alpha_{2}&\alpha_{2}&\alpha_{1}\end{array}\right). \tag{4.9}\]

To understand the general behavior, one will need to engage in combinatorial tailoring.

## 5 Conclusion and outlook

We investigated linear neural networks through the lens of algebraic geometry, with an emphasis on linear autoencoders. Their function spaces are determinantal varieties \(\mathcal{M}_{r,n\times n}\) in a natural way. We considered permutation groups \(G\) and fully characterized the elements of the function space which are invariant under the action of \(G\). They form an algebraic variety \(\mathcal{I}^{G}_{r,n\times n}\subset\mathcal{M}_{r,n\times n}\) for which we computed the dimension, singular points, degree, as well as the ED degree. The latter is a measure of complexity for training invariant networks, as well as finding nearest invariant networks post-training. We proved implications for the design of neural networks, such as a dimensional constraint on the middle layer of the autoencoder, as well as a weight sharing property of the encoder. Moreover, we proved that all \(G\)-invariant functions can be learned by a linear autoencoder. For equivariance, we treated cyclic subgroups \(G=\langle\sigma\rangle\) of permutation groups. Also in this case, the resulting part of the function space is an algebraic variety \(\mathcal{E}^{\sigma}_{r,n\times n}\subset\mathcal{M}_{r,n\times n}\), for which we computed the dimension, degree, and singular points over \(\mathbb{C}\). The computation of the ED degree is more intricate in the case of equivariance, as well as the generalization to non-cyclic groups. We plan to tackle both problems in follow-up work. We constructed a parameterization of \(\mathcal{E}^{\sigma}_{1,9\times 9}\) as a starting point, and leave the parameterization of \(\mathcal{E}^{G}_{r,n\times n}\) for future work.

One should also address groups other than permutation groups, such as non-discrete groups. Another natural step to take is to generalize the network architecture to a bigger number of layers as well as to allowing non-trivial activation functions, such as ReLU. For the latter, we expect that tropical expertize will be helpful to study the resulting geometry of the function space, which we will tackle in future work. Having the geometry of the function spaces understood, one should also investigate the types of critical points during training processes and how they compare to networks without imposed equi- or invariance.

**Acknowledgments.**

KK and ALS were partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.