11institutetext: Giovanni Bocchi 22institutetext: Department of Environmental
Science and Policy, University of Milan, Italy
22email<EMAIL_ADDRESS>33institutetext: Stefano Botteghi
44institutetext: Department of Mathematics, University of Bologna, Italy
44email<EMAIL_ADDRESS>55institutetext: Martina Brasini
66institutetext: Department of Mathematics, University of Bologna, Italy
66email<EMAIL_ADDRESS>77institutetext: Patrizio Frosini
(Corresponding author)88institutetext: Department of Mathematics, University
of Bologna, Italy
88email<EMAIL_ADDRESS>99institutetext: Nicola Quercioli
1010institutetext: ENEA, Centro Ricerche Bologna, Italy
1010email<EMAIL_ADDRESS>
# On the finite representation of linear group equivariant operators via
permutant measures ††thanks: This research has been partially supported by
INdAM-GNSAGA.

Giovanni Bocchi  Stefano Botteghi  Martina Brasini  Patrizio Frosini  Nicola
Quercioli

###### Abstract

Recent advances in machine learning have highlighted the importance of using
group equivariant non-expansive operators for building neural networks in a
more transparent and interpretable way. An operator is called equivariant with
respect to a group if the action of the group commutes with the operator.
Group equivariant non-expansive operators can be seen as multi-level
components that can be joined and connected in order to form neural networks
by applying the operations of chaining, convex combination and direct product.
In this paper we prove that each linear $G$-equivariant non-expansive operator
(GENEO) can be produced by a weighted summation associated with a suitable
permutant measure, provided that the group $G$ transitively acts on a finite
signal domain. This result is based on the Birkhoff–von Neumann decomposition
of doubly stochastic matrices and some well known facts in group theory. Our
theorem makes available a new method to build all linear GENEOs with respect
to a transitively acting group in the finite setting. This work is part of the
research devoted to develop a good mathematical theory of GENEOs, seen as
relevant components in machine learning.

###### keywords:

Group equivariant operator group equivariant non-expansive operator permutant
permutant measure

Primary: 68T09; Secondary: 15B51, 20C35, 47B38, 55N31, 62R40, 68U05

## Introduction

The development of new mathematical approaches and results for deep learning
is an important goal in the present time. In particular, new methods and
theories are requested in order to understand and control the behavior of
neural networks. In this line of research, the scientific community is
devoting more and more attention to the use of equivariant operators, since
they appear to be of great importance for the progress of machine learning
AnRoPo16 ; cohen2016group ; worrall2017harmonic . We recall that an operator
is called equivariant with respect to a group if the action of the group
commutes with the operator. For example, the operator associating each regular
function $f:\mathbb{R}^{n}\to\mathbb{R}$ to its Laplacian $\Delta f$ commutes
with each Euclidean isometry of $\mathbb{R}^{n}$. The property of equivariance
is of use when we want to mimic the behavior of observers and agents that are
known to respect some symmetries. In fact, the use of equivariant operators
allows us to inject pre-existing knowledge into the system, thus increasing
our control on the costruction of neural networks BeCoVi13 . Furthermore,
invariant and non-expansive operators can be used to reduce data variability
Ma12 ; Ma16 , and in the last years equivariant transformations have been
studied for learning symmetries ZVERP15 ; AERP19 .

Due to the relevance of group actions in deep learning, geometry is giving a
significant contribution to the study of AI BrBrLeSzVa17 . Geometric Deep
Learning is indeed trying to produce a geometric unification of several
approaches to machine learning, focusing on the concepts of symmetry and
invariance. At the intersection between this research field and Topological
Data Analysis, it has been proposed to extend the study of the geometry of the
space of data to the study of the geometry of the space of the
observers/agents that elaborate the data Fr16 ; FrJa16 . This idea is both
natural and relevant, since the interpretation of data depends on the chosen
observers, and the approximation of the agents requires the knowledge of the
topological and geometric properties of the space such agents belong to,
including connectivity, convexity, compactness, curvature and so on.

Recently, the study of group equivariant non-expansive operators (GENEOs) has
been proposed in Bergomi2019  as an interesting topic in machine learning,
since these operators model the concept of data observer. Furthermore, they
could be seen as multi-level components that can be joined and connected to
form neural networks by applying the operations of chaining, convex
combination and direct product, opening the path to a new kind of explainable
“geometric agent engineering”. Therefore, the analysis of the topology and
geometry of the spaces of GENEOs could lead to new theoretical results for
building neural networks in a more transparent and interpretable way. For
example, the use of a suitable topological setting allowed us to prove the
compactness of the space of all GENEOs, under the assumption that the space of
data is compact Bergomi2019 . This result has relevant practical consequences,
since it guarantees the finite approximability of the spaces of GENEOs,
provided that the spaces of data are compact. Incidentally, we stress that the
previously stated compactness does not hold for expansive equivariant
operators, so justifying our interest in GENEOs.

The development of a good topological and geometric theory of the spaces of
GENEOs could indeed produce new methods for approximating external agents in
such spaces, suggest how to change such operators without losing their
equivariance, benefit from their lattice structure with respect to the
operations of maximization and minimization FrQu17 , and allow to manage
relations and conflicts that can arise in intelligent structures
Frosini2009DoesII , just to make a few examples. As for the link between
GENEOs and Topological Data Analysis (with particular reference to _persistent
homology_), we refer the interested reader to FrJa16 ; Bergomi2019 . A central
role in this link is taken by the so-called _natural pseudo-distance_ DoFr04 ;
DoFr07 ; DoFr09 ; FrMu99 .

In summary, the use of GENEOs in machine learning requires to explore the
global structure of the spaces these operators belong to, in order to fully
benefit from their potential. In particular, this paper is devoted to study
the global structure of the space of all linear $G$-equivariant non-expansive
operators transitively acting on a finite signal domain $X$, with respect to
the concept of _permutant measure_.

We already know that every linear $G$-equivariant operator (GEO) can be
represented as a $G$-convolution, provided that the group $G$ is compact and
its action is transitive pmlr-v80-kondor18a . Unfortunately, the computation
of the integral representing such a convolution is usually not trivial since
in many applications the group $G$ is far from being small. In order to solve
this problem, a new technique to build GEOs with respect to a group $G$ has
been recently proposed, based on the concept of _permutant_ CaFrQu18 ;
CoFrQu22 . In plain words, a permutant is a collection of automorphisms of the
domain $X$ of the signals we are interested in, under the assumption that such
a collection is stable for the conjugation action of the group $G$. A
permutant is not required to be a group. When a non-empty permutant $H$ for
$G$ is available, we can define a GEO $F$ for $G$ by setting
$F(\varphi):=\sum_{h\in H}\varphi h^{-1}$ for every admissible signal
$\varphi$. The main benefit of this procedure is that the permutant $H$ can be
much smaller than the group $G$, so that the computation of the GEO defined by
$H$ can be much simpler than the computation of GEOs represented as
$G$-convolutions.

In this paper we extend the definitions of permutant and GEO associated with a
permutant by introducing the definitions of _permutant measure_ and _GEO
associated with a permutant measure_. If $\mu$ is a permutant measure on the
group $\mathrm{Aut}(X)$ of all permutations on $X$, we can define a GEO
$F_{\mu}$ for $G$ by setting
$F_{\mu}(\varphi):=\sum_{h\in\mathrm{Aut}(X)}\varphi h^{-1}\mu(h)$ for every
admissible signal $\varphi$. In our mathematical setting we can study the
relationship between linear GEOs and GEOs associated with permutant measures.
In particular, we can prove that these two concepts coincide, provided that
the group $G$ transitively acts on a finite signal domain $X$. This theorem is
based on the Birkhoff–von Neumann decomposition of doubly stochastic matrices
and some well known facts in group theory. Its statement makes available a new
method to build all linear GEOs with respect to a transitively acting group in
the finite setting. As a final step, we get our main result by adapting the
previous theorem to the case of GENEOs, by taking into account the non-
expansiveness condition.

We stress that this paper is not focused on direct applications of GENEOs, but
on a piece of research functional to the development of a good general theory
of these operators. Our long-term goal is the one of making available
equivariant operators that are both easily computable and predictable in their
behavior, so allowing for their use in geometric deep learning.

The outline of the paper is as follows. In Section 1 we recall the main
definitions in our mathematical setting, and introduce the concept of
permutant measure together with some of its properties. In Section 2 we prove
our main result about GEOs (Theorem 2), which is adapted to GENEOs in Section
3 (Theorem 3). In Section 4 we illustrate a toy example, showing possible
advantages of the use of GENEOs built by permutant measures. In Section 5 we
conclude the paper with a brief discussion.

##  1 Mathematical setting

Let $\mathbb{R}^{X}\cong\mathbb{R}^{n}$ be the vector space of all functions
from a finite set $X=\\{x_{1},\ldots,x_{n}\\}$ to $\mathbb{R}$. We would like
to recall that $\mathbb{R}^{X}$ has the canonical basis
$\\{{\mathds{1}}_{x_{j}}\\}_{j}$, where ${\mathds{1}}_{x}\colon
X\to\mathbb{R}$ is the function taking the value $1$ at $x$ and the value $0$
at every point $y$ with $y\neq x$. We also consider the group
$\mathrm{Aut}(X)$ of all permutations on $X$ and a subgroup $G$ of
$\mathrm{Aut}(X)$. $\mathrm{Aut}(X)$ and $G$ naturally act on $\mathbb{R}^{X}$
by composition on the right. We endow $\mathbb{R}^{X}$ with the
$L^{\infty}$-norm: $\|\varphi\|_{\infty}:=\max\\{|\varphi(x_{i})|:1\leq i\leq
n\\}$.

######  Remark 1.1.

If we endow $X$ with the discrete topology, $\mathbb{R}^{X}$ coincides with
$C^{0}(X,\mathbb{R})$.

In this paper we will use the multiplicative notation to denote the
composition of functions, and the cycle notation to represent permutations.

###  1.1 Group equivariant operators

We give the following definition.

######  Definition 1.1.

A _Group Equivariant Operator_ (GEO) for $(\mathbb{R}^{X},G)$ (with respect to
the identity $\mathrm{id}_{G}\colon g\mapsto g$) is a function
$F\colon{\mathbb{R}^{X}}\longrightarrow{\mathbb{R}^{X}}$ such that $F(\varphi
g)=F(\varphi)g$, for all $\varphi\in{\mathbb{R}^{X}}$ and $g\in G$.

An important subset of the set of GEOs is given by the set of _Group
Equivariant Non-Expansive Operators_ (GENEOs), i.e., GEOs $F$ such that
$\|F(\varphi_{1})-F(\varphi_{2})\|_{\infty}\leq\|\varphi_{1}-\varphi_{2}\|_{\infty}$,
for all $\varphi_{1},\varphi_{2}\in\mathbb{R}^{X}$. In a more general
framework, GEOs and GENEOs can be defined from $(\mathbb{R}^{X},G)$ to
$(\mathbb{R}^{Y},H)$ with respect to a group homomorphism $T\colon G\to H$,
where equivariance means that $F(\varphi g)=F(\varphi)T(g)$, for all
$\varphi\in{\mathbb{R}^{X}}$ and $g\in G$. For further information, we refer
the reader to Bergomi2019 . Obviously, the set of GEOs from
$(\mathbb{R}^{X},G)$ to $(\mathbb{R}^{X},G)$ is not empty because it contains
at least the identity operator
$\mathrm{id}_{\mathbb{R}^{X}}\colon\varphi\mapsto\varphi$.

###  1.2 Permutants and permutant measures

######  Definition 1.2.

A finite signed measure ${\mu}$ on $\mathrm{Aut}(X)$ is called a _permutant
measure_ with respect to $G$ if each subset $H$ of $\mathrm{Aut}(X)$ is
measurable and $\mu$ is invariant under the conjugation action of $G$ (i.e.,
${\mu}(H)={\mu}(gHg^{-1})$ for every $g\in G$). Equivalently, we can say that
a signed measure ${\mu}$ on $\mathrm{Aut}(X)$ is a permutant measure with
respect to $G$ if each singleton $\\{h\\}\subseteq\mathrm{Aut}(X)$ is
measurable and ${\mu}(\\{h\\})={\mu}(\\{ghg^{-1}\\})$ for every $g\in G$.

With a slight abuse of notation, we will denote by ${\mu}(h)$ the signed
measure of the singleton $\\{h\\}$ for each $h\in\mathrm{Aut}(X)$.

######  Example 1.1.

Let us consider a positive integer number $n$ and the finite set

$X:=\left\\{\left(\cos\frac{2\pi k}{n},\sin\frac{2\pi
k}{n}\right)\in\mathbb{R}^{2}:k\in\mathbb{N},0\leq k\leq n-1\right\\}.$

Let $G$ be the group of all rotations of $X$ of an angle $\alpha$ around the
point $(0,0)$, with $\alpha$ multiple of $\frac{2\pi}{n}$. After fixing an
integer number $m$, let us consider the map $\bar{h}\in\mathrm{Aut}(X)$ that
takes each point $\left(\cos\frac{2\pi k}{n},\sin\frac{2\pi k}{n}\right)$ to
the point $\left(\cos\frac{2\pi(k+m)}{n},\sin\frac{2\pi(k+m)}{n}\right)$.
Moreover, we define the function
$\mu_{1}\colon\mathcal{P}(\mathrm{Aut}(X))\to\mathbb{R}$ that takes each
subset $C$ of $\mathrm{Aut}(X)$ to $1$ if $\bar{h}\in C$ and to $0$ if
$\bar{h}\notin C$, where $\mathcal{P}(\mathrm{Aut}(X))$ is the power set of
$\mathrm{Aut}(X)$. Since the orbit of $\bar{h}$ under the conjugation action
of $G$ is the singleton $\\{\bar{h}\\}$, the function $\mu_{1}$ is a permutant
measure. We also observe that while the cardinality of $G$ is $n$, the
cardinality of the support
$\mathrm{supp}(\mu_{1}):=\\{h\in\mathrm{Aut}(X):\mu_{1}(h)\neq 0\\}$ of the
signed measure $\mu_{1}$ is $1$.

######  Example 1.2.

Let us consider the set $X$ of the vertices of a cube in $\mathbb{R}^{3}$, and
the group $G$ of the orientation-preserving isometries of $\mathbb{R}^{3}$
that take $X$ to $X$. Let $\pi_{1},\pi_{2},\pi_{3}$ be the three planes that
contain the center of mass of $X$ and are parallel to a face of the cube. Let
$h_{i}:X\to X$ be the orthogonal symmetry with respect to $\pi_{i}$, for
$i\in\\{1,2,3\\}$. We have that the set $\\{h_{1},h_{2},h_{3}\\}$ is an orbit
under the conjugation action of $G$. We can now define a permutant measure
$\mu_{2}$ on the group $\mathrm{Aut}(X)$ by setting
$\mu_{2}(h_{1})=\mu_{2}(h_{2})=\mu_{2}(h_{3})=c$, where $c$ is a positive real
number, and $\mu_{2}(h)=0$ for any $h\in\mathrm{Aut}(X)$ with
$h\notin\\{h_{1},h_{2},h_{3}\\}$. We also observe that while the cardinality
of $G$ is $24$, the cardinality of the support
$\mathrm{supp}(\mu_{2}):=\\{h\in\mathrm{Aut}(X):\mu_{2}(h)\neq 0\\}$ of the
signed measure $\mu_{2}$ is $3$.

Permutant measures give a simple method to build GEOs, as shown by the
following result.

######  Proposition 1.1.

If $\mu$ is a permutant measure with respect to $G$, then the map
$F_{\mu}:\mathbb{R}^{X}\to\mathbb{R}^{X}$ defined by setting
$F_{\mu}(\varphi):=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\ {\mu}(h)$ is a
linear GEO.

###### Proof.

Since $\mathrm{Aut}(X)$ linearly acts on $\mathbb{R}^{X}$ by composition on
the right, $F_{\mu}$ is linear. Moreover, for every $\varphi\in\mathbb{R}^{X}$
and every $g\in G$

$\displaystyle F_{\mu}(\varphi g)$
$\displaystyle=\sum_{h\in{\mathrm{Aut}(X)}}\varphi gh^{-1}\ {\mu}(h)$ (1.1)
$\displaystyle=\sum_{h\in{\mathrm{Aut}(X)}}\varphi gh^{-1}g^{-1}g\
{\mu}(ghg^{-1})$ $\displaystyle=\sum_{f\in{\mathrm{Aut}(X)}}\varphi f^{-1}g\
{\mu}(f)$ $\displaystyle=F_{\mu}(\varphi)g,$

since $\mu(h)={\mu}(ghg^{-1})$ and the map $h\mapsto f:=ghg^{-1}$ is a
bijection from ${\mathrm{Aut}(X)}$ to ${\mathrm{Aut}(X)}$. ∎

Obviously, $F_{\mu}(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\
{\mu}(h)=\sum_{h\in{\mathrm{supp}(\mu)}}\varphi h^{-1}\ {\mu}(h)$, where
$\mathrm{supp}(\mu):=\\{h\in\mathrm{Aut}(X):\mu(h)\neq 0\\}$. In Examples 1.1
and 1.2 $|\mathrm{supp}(\mu_{i})|\ll|G|$ for $i=1,2$, and hence in those cases
summations on $\mathrm{supp}(\mu_{i})$ are simpler than summations on the
group $G$. The condition $|\mathrm{supp}(\mu)|\ll|G|$ is not rare in examples
and is the main reason to build GEOs by means of permutant measures, instead
of using the representation of GEOs as $G$-convolutions.

######  Example 1.3.

The GEOs associated with the permutant measures defined in Examples 1.1 and
1.2 are respectively $F_{\mu_{1}}(\varphi)=\varphi\bar{h}^{-1}$ and
$F_{\mu_{2}}(\varphi)=c\varphi h_{1}^{-1}+c\varphi h_{2}^{-1}+c\varphi
h_{3}^{-1}$.

It is interesting to observe that the set $\mathrm{PM}(G)$ of permutant
measures with respect to $G$ is a lattice. Indeed, if
$\mu_{1},\mu_{2}\in\mathrm{PM}(G)$, then the measures
$\mu^{\prime},\mu^{\prime\prime}$ on $\mathrm{Aut}(X)$, respectively defined
by setting $\mu^{\prime}(h):=\min\\{\mu_{1}(h),\mu_{2}(h)\\}$ and
$\mu^{\prime\prime}(h):=\max\\{\mu_{1}(h),\mu_{2}(h)\\}$, still belong to
$\mathrm{PM}(G)$. Moreover, if $\mu\in\mathrm{PM}(G)$ then
$|\mu|\in\mathrm{PM}(G)$. Furthermore, $\mathrm{PM}(G)$ is closed under linear
combination. Therefore, $\mathrm{PM}(G)$ has a natural structure of real
vector space. We can compute the dimension of $\mathrm{PM}(G)$ by considering
the conjugation action of $G$ on $\mathrm{Aut}(X)$.

######  Proposition 1.2.

$\dim\mathrm{PM}(G)=\left|\nicefrac{{\mathrm{Aut}(X)}}{{G}}\right|$.

###### Proof.

Consider a permutant measure $\mu$ on $\mathrm{Aut}(X)$. We define the
function $f_{\mu}\colon\nicefrac{{\mathrm{Aut}(X)}}{{G}}\to\mathbb{R}$ by
setting $f_{\mu}(\mathcal{O})=\mu(h)$, where $h\in\mathcal{O}$. Since $\mu$ is
invariant under the conjugation action of $G$, $f_{\mu}$ is well defined. One
could easily check that the map $\mu\mapsto f_{\mu}$ is an isomorphism between
$\mathrm{PM}(G)$ and the space
$\mathbb{R}^{\nicefrac{{\mathrm{Aut}(X)}}{{G}}}$ of all real-valued functions
on $\nicefrac{{\mathrm{Aut}(X)}}{{G}}$. Since
$\\{\mathds{1}_{\mathcal{O}}\\}_{\mathcal{O}\in\nicefrac{{\mathrm{Aut}(X)}}{{G}}}$
is a basis for $\mathbb{R}^{\nicefrac{{\mathrm{Aut}(X)}}{{G}}}$,
$\dim\mathbb{R}^{\nicefrac{{\mathrm{Aut}(X)}}{{G}}}=\left|\nicefrac{{\mathrm{Aut}(X)}}{{G}}\right|$.
Hence, the statement is proved. ∎

Proposition 1.2 and the well-known Burnside’s Lemma imply that
$\dim\mathrm{PM}(G)=\frac{1}{|G|}\sum_{g\in G}|\mathrm{Aut}(X)^{g}|$. We
recall that $\mathrm{Aut}(X)^{g}$ denotes the set of elements fixed by the
action of $g$, i.e.,
$\mathrm{Aut}(X)^{g}:=\\{h\in\mathrm{Aut}(X)|ghg^{-1}=h\\}$.

Let us now recall the concept of permutant CaFrQu18 ; CoFrQu22 , which is
related to the one of permutant measure.

######  Definition 1.3.

We say that a subset $H\subseteq\mathrm{Aut}(X)$ is a _permutant_ for $G$ if
either $H=\emptyset$ or $gHg^{-1}=H$ for every $g\in G$.

Note that a subset $H$ of $\mathrm{Aut}(X)$ is a permutant for $G$ if and only
if $H$ is a union of orbits for the conjugation action of $G$ on
$\mathrm{Aut}(X)$. It follows that the number of permutants for $G$ is equal
to $2^{\left|\frac{\mathrm{Aut}(X)}{G}\right|}$. Let us denote by
$\mathrm{Perm}(G)$ the set of all permutants for $G$. From Proposition 1.2 the
next corollary immediately follows.

######  Corollary 1.1.

$\dim\mathrm{PM}(G)=\log_{2}|\mathrm{Perm}(G)|$.

The following definition extends the one of versatile group (cf. CaFrQu18 )
and is of use in studying permutants.

######  Definition 1.4.

If $k$ is a positive integer, we say that the group
$G\subseteq\mathrm{Aut}(X)$ is _$k$ -weakly versatile_ if for every pair
$(x,z)\in X\times X$ with $x\neq z$ and every subset $S$ of $X$ with $|S|\leq
k$, a $g\in G$ exists such that $g(x)=x$ and $g(z)\notin S$.

The previous definition allows us to highlight an interesting property of
permutants.

######  Lemma 1.1.

If $G$ is $k$-weakly versatile, then every permutant
$H\neq\emptyset,\\{\mathrm{id}_{X}\\}$ has cardinality strictly greater than
$k$.

###### Proof.

By contradiction, let us assume that a non-empty permutant
$H=\\{h_{1},\ldots,h_{r}\\}\neq\\{\mathrm{id}_{X}\\}$ exists, with $1\leq
r\leq k$. Since $H\neq\\{\mathrm{id}_{X}\\}$, we can assume that $h_{1}$ is
not the identity. Let us take a point $x\in X$ such that $h_{1}(x)\neq x$ and
set $z:=h_{1}(x)$, $S:=\\{h_{1}(x),\ldots,h_{r}(x)\\}$. $G$ is $k$-weakly
versatile and hence a $g\in G$ exists, such that $g(x)=x$ and $g(z)\notin S$.
Since $gHg^{-1}=H$, an index $i$ exists such that $gh_{1}=h_{i}g$. It follows
that $g(z)=g(h_{1}(x))=h_{i}(g(x))=h_{i}(x)\in S$, against the assumption that
$g(z)\notin S$. ∎

We stress that when the group $G$ becomes larger and larger the lattice
$\mathrm{PM}(G)$ becomes smaller and smaller. This duality implies that the
method described by Proposition 1.1 is particularly interesting when $G$ is
large. In some sense, this duality is analogous to the one described in
(FrJa16, , Subsection 3.1).

##  2 Representation of linear GEOs via permutant measures

A natural question arises from Proposition 1.1: Which linear GEOs can be
represented as GEOs associated with a permutant measure?

We can prove the following result.

######  Theorem 1.

If $G$ transitively acts on $X$, then for every linear group equivariant
operator $F$ for $(\mathbb{R}^{X},G)$ a permutant measure ${\mu}$ exists such
that

$F(\varphi)=F_{\mu}(\varphi):=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\
{\mu}(h)$

for every $\varphi\in{\mathbb{R}^{X}}$, and
$\sum_{h\in\mathrm{Aut}(X)}{|\mu(h)|}=\max_{\varphi\in\mathbb{R}^{X}\setminus\\{\mathbf{0}\\}}\frac{\|F(\varphi)\|_{\infty}}{\|\varphi\|_{\infty}}$.

In order to prove this statement, let us consider the matrix $B=(b_{ij})$
associated with $F$ with respect to the basis
$\\{{\mathds{1}}_{x_{1}},\ldots,{\mathds{1}}_{x_{n}}\\}$.

######  Remark 2.1.

We observe that ${\mathds{1}}_{x}{h}^{-1}={\mathds{1}}_{{h}(x)}$ for every
$h\in\mathrm{Aut}(X)$ and every $x\in X$.

In the following, for every $g\in G$ we will denote by
$\sigma_{g}:\\{1,\ldots,n\\}\to\\{1,\ldots,n\\}$ the function defined by
setting $\sigma_{g}(j)=i$ if and only if $g(x_{j})=x_{i}$. We observe that
$\sigma_{g^{-1}}=\sigma_{g}^{-1}$.

We need the following lemmas.

######  Lemma 2.1.

An $n$-tuple of real numbers $\alpha=(\alpha_{1},\ldots,\alpha_{n})$ exists
such that each row and each column of ${B}$ can be obtained by permuting
$\alpha$.

###### Proof.

Let us choose a function ${\mathds{1}}_{x_{j}}$ and a permutation $g\in G$. By
equivariance we have that

${F}({\mathds{1}}_{x_{j}}g)={F}({\mathds{1}}_{x_{j}})g.$

The left-hand side of the equation can be rewritten as:

${F}({\mathds{1}}_{x_{j}}g)={F}({\mathds{1}}_{g^{-1}(x_{j})})=\sum_{i=1}^{n}b_{i\sigma_{g}^{-1}(j)}{\mathds{1}}_{x_{i}}.$

On the right-hand side we get

${F}({\mathds{1}}_{x_{j}})g=\left(\sum_{i=1}^{n}b_{ij}{\mathds{1}}_{x_{i}}\right)g=\sum_{i=1}^{n}b_{ij}({\mathds{1}}_{x_{i}}g)=\sum_{i=1}^{n}b_{ij}({\mathds{1}}_{g^{-1}(x_{i})})=\sum_{s=1}^{n}b_{\sigma_{g}(s)j}{\mathds{1}}_{x_{s}}$

by setting $x_{s}=g^{-1}(x_{i})$. Therefore, we obtain the following equation:

$\sum_{i=1}^{n}b_{i\sigma_{g}^{-1}(j)}{\mathds{1}}_{x_{i}}=\sum_{s=1}^{n}b_{\sigma_{g}(s)j}{\mathds{1}}_{x_{s}}.$

This immediately implies that $b_{i\sigma_{g}^{-1}(j)}=b_{\sigma_{g}(i)j}$,
for any $i\in\\{1,\dots,n\\}$. Since this equality holds for any
$j\in\\{1,\dots,n\\}$ and any $g\in G$, we have that
$b_{ij}=b_{\sigma_{g}(i)\sigma_{g}(j)}$ for every $i,j\in\\{1,\dots,n\\}$ and
every $g\in G$.

Now we are ready to show that all the rows of ${B}$ are permutations of the
first row, and all the columns are permutations of the first column. Since $G$
is transitive, for every $p,q\in\\{1,\dots,n\\}$ there exists $g_{pq}\in G$
such that $g_{pq}(x_{p})=x_{q}$. Consider the $\bar{\imath}$-th row of $B$. We
know that
$b_{\bar{\imath}j}=b_{\sigma_{g_{\bar{\imath}1}}(\bar{\imath})\sigma_{g_{\bar{\imath}1}}(j)}=b_{1\sigma_{g_{\bar{\imath}1}}(j)}$,
for any $j\in\\{1,\dots,n\\}$. Since $\sigma_{g_{\bar{\imath}1}}$ is a
permutation, the $\bar{\imath}$-th row is a permutation of the first row. By
the same arguments, we can assert that every column of $B$ is a permutation of
the first column of $B$.

Let us now consider a real number $y$, and denote by $r(y)$ (respectively
$s(y)$) the number of times $y$ occurs in each row (respectively column) of
${B}$. Both $nr(y)$ and $ns(y)$ represent the number of times $y$ appears in
$B$. Since $nr(y)=ns(y)$, each row and column contains the same elements
(counted with multiplicity). Hence, the statement of our lemma is proved. ∎

The following result is well known DKPU18 .

######  Lemma 2.2 (Birkhoff–von Neumann decomposition).

Let $M$ be a $n\times n$ real matrix with non-negative entries, such that both
the sum of the elements of each row and the sum of the elements of each column
is equal to $\bar{c}$. Then for every $h\in{\mathrm{Aut}(X)}$ a non-negative
real number $c(h)$ exists such that $\sum_{h\in{\mathrm{Aut}(X)}}c(h)=\bar{c}$
and $M=\sum_{h\in{\mathrm{Aut}(X)}}c(h)P(h)$, where $P(h)$ is the permutation
matrix associated with $h$.

We recall that the permutation matrix associated with the permutation $h:X\to
X$ is the $n\times n$ real matrix $({p_{ij}(h)})$ defined by setting
${p_{ij}(h)}=1$ if ${h}(x_{j})=x_{i}$ and ${p_{ij}(h)}=0$ if ${h}(x_{j})\neq
x_{i}$. Equivalently, we can define the permutation matrix associated with the
permutation $h:X\to X$ as the $n\times n$ real matrix $P(h)$ such that
$P(h)e_{j}=e_{\sigma_{h}(j)}$ for every column vector
$e_{j}:=\prescript{t}{}{(}0,\ldots,1,\ldots,0)\in\mathbb{R}^{n}$ (where $1$ is
in the $j$-th position).

We observe that $P\left(h^{-1}\right)=P(h)^{-1}$ and
$P(h_{1}h_{2})=P(h_{1})P(h_{2})$ for every
$h,h_{1},h_{2}\in{\mathrm{Aut}(X)}$.

######  Remark 2.2.

In general, the representation ${M}=\sum_{h\in{\mathrm{Aut}(X)}}c(h)P(h)$,
stated in Lemma 2.2, is not unique. As an example, consider the set
$X=\\{1,2,3\\}$ and the group $G=\mathrm{Aut}(X)$. Let
${F}\colon\mathbb{R}^{X}\to\mathbb{R}^{X}$ be the linear application that maps
${\mathds{1}}_{j}$ to $\sum_{i\in X}\mathds{1}_{i}$, for any $j\in X$. One
could easily check that ${F}$ is a linear GEO for $(\mathbb{R}^{X},G)$.
Indeed, we have that
${F}({\mathds{1}}_{j}h)={F}({\mathds{1}}_{j})={F}({\mathds{1}}_{j})h$ for any
$j\in X$ and any $h\in\mathrm{Aut}(X)$. The matrix ${B}$ associated with ${F}$
with respect to the basis $\\{{\mathds{1}}_{j}\\}_{j}$ is:

${B}=\begin{pmatrix}1&1&1\\\ 1&1&1\\\ 1&1&1\end{pmatrix}.$

One could represent ${B}$ at least in two different ways:

${B}=\begin{pmatrix}1&0&0\\\ 0&1&0\\\
0&0&1\end{pmatrix}+\begin{pmatrix}0&1&0\\\ 0&0&1\\\
1&0&0\end{pmatrix}+\begin{pmatrix}0&0&1\\\ 1&0&0\\\ 0&1&0\end{pmatrix}$

and

${B}=\begin{pmatrix}0&0&1\\\ 0&1&0\\\
1&0&0\end{pmatrix}+\begin{pmatrix}0&1&0\\\ 1&0&0\\\
0&0&1\end{pmatrix}+\begin{pmatrix}1&0&0\\\ 0&0&1\\\ 0&1&0\end{pmatrix}.$

We proceed in our proof of Theorem 1 by taking the linear maps
${F^{\oplus}},{F^{\ominus}}:\mathbb{R}^{X}\to\mathbb{R}^{X}$ defined by
setting
${F^{\oplus}}({\mathds{1}}_{x_{j}}):=\sum_{i=1}^{n}\max\\{b_{ij},0\\}{\mathds{1}}_{x_{i}}$
and
${F^{\ominus}}({\mathds{1}}_{x_{j}}):=\sum_{i=1}^{n}\max\\{-b_{ij},0\\}{\mathds{1}}_{x_{i}}$
for every index $j\in\\{1,\ldots,n\\}$. We can easily check that

  1. 1.

${F^{\oplus}},{F^{\ominus}}$ are linear GEOs;

  2. 2.

The matrices associated with ${F^{\oplus}}$ and ${F^{\ominus}}$ with respect
to the basis $\\{{\mathds{1}}_{x_{1}},\ldots,{\mathds{1}}_{x_{n}}\\}$ of
$\mathbb{R}^{X}$ are
${B^{\oplus}}=\left(b^{\oplus}_{ij}\right)=\left(\max\\{b_{ij},0\\}\right)$
and
${B^{\ominus}}=\left(b^{\ominus}_{ij}\right)=\left(\max\\{-b_{ij},0\\}\right)$,
respectively (in particular, ${B^{\oplus}},{B^{\ominus}}$ are non-negative
matrices);

  3. 3.

$F={F^{\oplus}}-{F^{\ominus}}$ and $B={B^{\oplus}}-{B^{\ominus}}$;

  4. 4.

Lemma 2.1 and the definitions of ${B^{\oplus}}$, ${B^{\ominus}}$ imply that
two $n$-tuples of real numbers
$\alpha^{\oplus}=(\alpha^{\oplus}_{1},\ldots,\alpha^{\oplus}_{n})$,
$\alpha^{\ominus}=(\alpha^{\ominus}_{1},\ldots,\alpha^{\ominus}_{n})$ exist
such that each row and each column of ${B^{\oplus}}$ can be obtained by
permuting $\alpha^{\oplus}$, and each row and each column of ${B^{\ominus}}$
can be obtained by permuting $\alpha^{\ominus}$.

From Property (4) and Lemma 2.2 this result follows:

######  Corollary 2.1.

For every $h\in{\mathrm{Aut}(X)}$ two non-negative real numbers
$c^{\oplus}(h),c^{\ominus}(h)$ exist, such that
${F^{\oplus}}(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}{c^{\oplus}(h)}\varphi{h}^{-1}$
and
${F^{\ominus}}(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}{c^{\ominus}(h)}\varphi{h}^{-1}$
for every $\varphi\in{\mathbb{R}^{X}}$.

###### Proof.

Let us start by considering the statement concerning $c^{\oplus}(h)$ and
$F^{\oplus}(h)$. Without loss of generality, since ${F^{\oplus}}$ is linear,
it will suffice to prove the existence of a suitable non-negative function
${c^{\oplus}(h)}$, such that
${F^{\oplus}}({\mathds{1}}_{x_{j}})=\sum_{h\in{\mathrm{Aut}(X)}}{c^{\oplus}(h)}{\mathds{1}}_{x_{j}}{h}^{-1}$,
for any $j\in\\{1,\dots,n\\}$. The column coordinate vector of the function
${F^{\oplus}}({\mathds{1}}_{x_{j}})$ relative to the basis
$\\{{\mathds{1}}_{x_{1}},\ldots,{\mathds{1}}_{x_{n}}\\}$ is
${B^{\oplus}}e_{j}$. Property (4) and Lemma 2.2 imply that for every
$h\in{\mathrm{Aut}(X)}$ a non-negative real number ${c^{\oplus}(h)}$ exists,
such that

${B^{\oplus}}e_{j}=\sum_{h\in{\mathrm{Aut}(X)}}{c^{\oplus}(h)}P(h)e_{j}=\sum_{h\in{\mathrm{Aut}(X)}}{c^{\oplus}(h)}e_{\sigma_{h}(j)}.$

Since the column vector $e_{\sigma_{h}(j)}$ represents the column coordinate
vector of the function ${\mathds{1}}_{h(x_{j})}$ relative to the basis
$\\{{\mathds{1}}_{x_{1}},\ldots,{\mathds{1}}_{x_{n}}\\}$, we can conclude that

${F^{\oplus}}({\mathds{1}}_{x_{j}})=\sum_{h\in{\mathrm{Aut}(X)}}{c^{\oplus}(h)}{\mathds{1}}_{h(x_{j})}=\sum_{h\in{\mathrm{Aut}(X)}}{c^{\oplus}(h)}{\mathds{1}}_{x_{j}}h^{-1}.$

The proof of the statement concerning $c^{\ominus}$ and $F^{\ominus}$ is
analogous. ∎

######  Remark 2.3.

In general, the function $c\colon\mathrm{Aut}(X)\to\mathbb{R}$ associated with
the Birkhoff–von Neumann decomposition does not induce a permutant measure,
i.e., the function $\mu_{c}$ that takes each subset $H$ of $\mathrm{Aut}(X)$
to the value $\mu_{c}(H):=\sum_{h\in H}c(h)$ is not a permutant measure. For
example, let us consider the set $X=\\{1,2,3,4\\}$ and the group $S_{4}$ of
all permutations of $X$. Let us define a linear GEO
$F:\mathbb{R}^{X}\to\mathbb{R}^{X}$ for $(\mathbb{R}^{X},S_{4})$ by setting
$F(\mathds{1}_{j})=\sum_{i\in X}\mathds{1}_{i}$, for every index $j$. After
fixing the basis $\\{\mathds{1}_{j}\\}_{j}$, the matrix $B$ associated with
$F$ has the following form:

$B=\begin{pmatrix}1&1&1&1\\\ 1&1&1&1\\\ 1&1&1&1\\\ 1&1&1&1\\\ \end{pmatrix}.$

As guaranteed by Lemma 2.2, $B$ can be decomposed as follows:

$B=P(\mathrm{id}_{X})+P(\sigma)+P(\sigma^{2})+P(\sigma^{3}),$

where $\sigma=(1\;2\;3\;4)\in S_{4}$, in cycle notation. Let
$\langle\sigma\rangle$ be the cyclic group generated by $\sigma$.  The
function $c:\mathrm{Aut}(X)\to\mathbb{R}$ associated with the previous
decomposition of $B$ is defined as follows: $c({h})=1$ if
$h\in\langle\sigma\rangle$, otherwise $c({h})=0$. Let us now consider the
permutation $g=(1\;2)\in S_{4}$, in cycle notation. Since
$\sigma^{2}=(1\;3)(2\;4)$, we have that:

$c(g\sigma^{2}g^{-1})=c((1\;2)(1\;3)(2\;4)(1\;2))=c((1\;4)(2\;3))=0.$

Since $c(\sigma^{2})=1$, $c$ is not invariant under the conjugation action of
$S_{4}$, and hence $\mu_{c}$ is not a permutant measure.

Let us now go back to the proof of Theorem 1 and consider the functions
${c^{\oplus}},{c^{\ominus}}:{\mathrm{Aut}(X)}\to\mathbb{R}$ introduced in
Corollary 2.1. In order to define the permutant measure ${\mu}$ on
${\mathrm{Aut}(X)}$ we will need the next lemma.

######  Lemma 2.3.

If $g\in G$ then ${B^{\oplus}}P(g)=P(g){B^{\oplus}}$.

###### Proof.

Let us consider a permutation $g\in G$. The function
$R_{g^{-1}}\colon\mathbb{R}^{X}\to\mathbb{R}^{X}$, which maps $\varphi$ to
$\varphi{g^{-1}}$, is a linear application. Furthermore,
$R_{g^{-1}}({\mathds{1}}_{x_{j}})={\mathds{1}}_{x_{j}}{g^{-1}}={\mathds{1}}_{g(x_{j})}$
for every index $j$. Hence, the matrix $N$ associated to $R_{g^{-1}}$ with
respect to the basis $\\{{\mathds{1}}_{x_{1}},\ldots,{\mathds{1}}_{x_{n}}\\}$
verifies the equality $Ne_{j}=e_{\sigma_{g}(j)}$, so that $N=P(g)$ (we set
$e_{j}:=\prescript{t}{}{(}0,\ldots,1,\ldots,0)\in\mathbb{R}^{n}$, where $1$ is
in the $j$-th position). Since ${F^{\oplus}}$ is a GEO, the equality
${F^{\oplus}}R_{g^{-1}}=R_{g^{-1}}{F^{\oplus}}$ holds. This immediately
implies that ${B^{\oplus}}P(g)=P(g){B^{\oplus}}$. ∎

An analogous lemma holds for the matrix ${B^{\ominus}}$.

Lemma 2.3 guarantees that $P(g){B^{\oplus}}P(g)^{-1}={B^{\oplus}}$ for every
$g\in G$. From this equality and Lemma 2.2 it follows that

$\displaystyle{B^{\oplus}}$
$\displaystyle=\overbrace{\frac{1}{|G|}{B^{\oplus}}+\ldots+\frac{1}{|G|}{B^{\oplus}}}^{\text{$|G|$
summands}}$ (2.1) $\displaystyle=\frac{1}{|G|}\sum_{g\in
G}P(g){B^{\oplus}}P(g)^{-1}$ $\displaystyle=\frac{1}{|G|}\sum_{g\in
G}P(g)\left(\sum_{{h\in{\mathrm{Aut}(X)}}}{c^{\oplus}(h)}P(h)\right)P(g)^{-1}$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\sum_{g\in
G}\frac{{c^{\oplus}(h)}}{|G|}P(g)P(h)P(g)^{-1}$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}\sum_{g\in
G}P(ghg^{-1}).$

Therefore, for every index $j$ we have that

$\displaystyle{B^{\oplus}}e_{j}$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}\sum_{g\in
G}P(ghg^{-1})e_{j}$ (2.2)
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}\sum_{g\in
G}e_{\sigma_{ghg^{-1}}(j)}.$

This means that

$\displaystyle{F^{\oplus}}({\mathds{1}}_{x_{j}})$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}\sum_{g\in
G}{\mathds{1}}_{ghg^{-1}(x_{j})}$ (2.3)
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}\sum_{g\in
G}{\mathds{1}}_{x_{j}}gh^{-1}g^{-1}.$

Since ${F^{\oplus}}$ is linear, it follows that

$\displaystyle{F^{\oplus}}(\varphi)$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}\sum_{g\in
G}\varphi g{h}^{-1}g^{-1}$ (2.4)

for every $\varphi\in\mathbb{R}^{X}$.

We observe that the permutations $g{h}^{-1}g^{-1}$ in the previous summation
are not guaranteed to be different from each other, for $g$ varying in $G$ and
$h$ varying in ${\mathrm{Aut}(X)}$.

For each $h\in{\mathrm{Aut}(X)}$, let us consider the orbit $\mathcal{O}(h)$
of $h$ under the conjugation action of $G$ on ${\mathrm{Aut}(X)}$, and set

$\displaystyle{\mu^{\oplus}}(h)$
$\displaystyle:=\sum_{{f}\in\mathcal{O}(h)}\frac{c^{\oplus}({f})}{|\mathcal{O}({f})|}=\sum_{{f}\in\mathcal{O}(h)}\frac{c^{\oplus}({f})}{|\mathcal{O}(h)|}$
$\displaystyle{\mu^{\ominus}}(h)$
$\displaystyle:=\sum_{{f}\in\mathcal{O}(h)}\frac{c^{\ominus}({f})}{|\mathcal{O}({f})|}=\sum_{{f}\in\mathcal{O}(h)}\frac{c^{\ominus}({f})}{|\mathcal{O}(h)|}.$

In other words, we define the measures $\mu^{\oplus}(h),\mu^{\ominus}(h)$ of
each permutation $h$ as the averages of the functions $c^{\oplus},c^{\ominus}$
along the orbit of $h$ under the conjugation action of $G$. Let $G_{h}$ be the
stabilizer subgroup of $G$ with respect to $h$, i.e., the subgroup of $G$
containing the elements that fix $h$ by conjugation. We recall that by
conjugating $h$ with respect to every element of $G$ we obtain each element of
the orbit $\mathcal{O}(h)$ exactly $|G_{h}|$ times, and the well-known
relation $|G_{h}||\mathcal{O}(h)|=|G|$ (cf. aschbacher_2000 ). Let us now set
$\delta({f},h)=1$ if ${f}$ and $h$ belong to the same orbit under the
conjugation action of $G$, and $\delta({f},h)=0$ otherwise.

We observe that the following properties hold for $f,h\in{\mathrm{Aut}(X)}$:

  1. 1.

$G_{h^{-1}}=G_{h}$;

  2. 2.

if ${f}\in\mathcal{O}(h)$ then $G_{{f}}$ is isomorphic to $G_{h}$;

  3. 3.

${f}^{-1}\in\mathcal{O}(h^{-1})\iff{f}\in\mathcal{O}(h)\iff
h\in\mathcal{O}({f})$.

Therefore, equality (2.4) implies

$\displaystyle{F^{\oplus}}(\varphi)$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}|G_{h^{-1}}|\sum_{{f}^{-1}\in\mathcal{O}(h^{-1})}\varphi{{f}}^{-1}$
(2.5)
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}|G_{h}|\sum_{{f}\in\mathcal{O}(h)}\varphi{{f}}^{-1}$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}\frac{{c^{\oplus}(h)}}{|G|}|G_{h}|\sum_{{f}\in{\mathrm{Aut}(X)}}\delta({f},h)\varphi{{f}}^{-1}$
$\displaystyle=\sum_{{{f}\in{\mathrm{Aut}(X)}}}\left(\sum_{h\in{\mathrm{Aut}(X)}}\frac{{c^{\oplus}(h)}}{|G|}|G_{h}|\delta({f},h)\right)\varphi{{f}}^{-1}$
$\displaystyle=\sum_{{{f}\in{\mathrm{Aut}(X)}}}\left(\sum_{h\in{\mathrm{Aut}(X)}}\frac{{c^{\oplus}(h)}}{|\mathcal{O}(h)|}\delta({f},h)\right)\varphi{{f}}^{-1}$
$\displaystyle=\sum_{{{f}\in{\mathrm{Aut}(X)}}}\left(\sum_{h\in\mathcal{O}({f})}\frac{{c^{\oplus}(h)}}{|\mathcal{O}(h)|}\right)\varphi{{f}}^{-1}$
$\displaystyle=\sum_{{{f}\in{\mathrm{Aut}(X)}}}\varphi{{f}}^{-1}\
{\mu^{\oplus}}({f}).$

The definition of ${\mu^{\oplus}}$ immediately implies that
${\mu^{\oplus}}(H)={\mu^{\oplus}}(gHg^{-1})$ for every $g\in G$ and every
subset $H$ of ${\mathrm{Aut}(X)}$. In other words, ${\mu^{\oplus}}$ is a non-
negative permutant measure with respect to $G$. Quite analogously, we can
prove the equality
${F^{\ominus}}(\varphi)=\sum_{{{f}\in{\mathrm{Aut}(X)}}}\varphi{{f}}^{-1}\
{\mu^{\ominus}}({f})$, and that ${\mu^{\ominus}}$ is a non-negative permutant
measure with respect to $G$. As a result, the function
$\mu:={\mu^{\oplus}}-{\mu^{\ominus}}$ is a permutant measure and the equality
${F}(\varphi)=\sum_{{{f}\in{\mathrm{Aut}(X)}}}\varphi{{f}}^{-1}\ {\mu}({f})$
holds, since $F={F^{\oplus}}-{F^{\ominus}}$.

It remains to prove that
$\sum_{h\in\mathrm{Aut}(X)}{|\mu(h)|}=\max_{\varphi\in\mathbb{R}^{X}\setminus\\{\mathbf{0}\\}}\frac{\|F(\varphi)\|_{\infty}}{\|\varphi\|_{\infty}}$.

This statement is trivial if $F\equiv\mathbf{0}$, since in this case $\mu$ is
the null measure. Hence we can assume that $F$ is not the null map and $B$ is
not the null matrix. In order to proceed, we need the next statement.

######  Proposition 2.1.

If $f_{1},f_{2}\in\mathrm{Aut}(X)$ and an index $s\in\\{1,\ldots,n\\}$ exists,
such that $f_{1}(x_{s})=f_{2}(x_{s})$ (i.e.,
$\sigma_{f_{1}}(s)=\sigma_{f_{2}}(s)$), then either $c^{\oplus}(f_{1})=0$, or
$c^{\ominus}(f_{2})=0$, or both.

###### Proof.

By applying the equality
$F^{\oplus}(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}c^{\oplus}(h)\varphi h^{-1}$
for $\varphi=\mathds{1}_{x_{1}}$, we obtain that

$\displaystyle b^{\oplus}_{\sigma_{f_{1}}(s)s}$
$\displaystyle=\left(\sum_{i=1}^{n}b^{\oplus}_{is}{\mathds{1}}_{x_{i}}\right)(x_{\sigma_{f_{1}}(s)})$
(2.6) $\displaystyle={F^{\oplus}}(\mathds{1}_{x_{s}})(x_{\sigma_{f_{1}}(s)})$
$\displaystyle={F^{\oplus}}(\mathds{1}_{x_{s}})({f_{1}}(x_{s}))$
$\displaystyle=\sum_{{h\in{\mathrm{Aut}(X)}}}{c^{\oplus}(h)}\mathds{1}_{x_{s}}{{h}}^{-1}({f_{1}}(x_{s}))$
$\displaystyle\geq{c^{\oplus}({f_{1}})}\mathds{1}_{x_{s}}{{{f_{1}}}}^{-1}({f_{1}}(x_{s}))$
$\displaystyle={c^{\oplus}({f_{1}})}\mathds{1}_{x_{s}}(x_{s})$
$\displaystyle=c^{\oplus}({f_{1}}).$

Analogously, the inequality $b^{\ominus}_{\sigma_{f_{2}}(s)s}\geq
c^{\ominus}({f_{2}})$ holds. Therefore,

$c^{\oplus}({f_{1}})>0\implies b^{\oplus}_{\sigma_{f_{1}}(s)s}>0\implies
b^{\ominus}_{\sigma_{f_{1}}(s)s}=0\implies
b^{\ominus}_{\sigma_{f_{2}}(s)s}=0\implies c^{\ominus}({f_{2}})=0$.

It follows that either $c^{\oplus}(f_{1})=0$, or $c^{\ominus}(f_{2})=0$, or
both. ∎

######  Corollary 2.2.

For every $f\in\mathrm{Aut}(X)$ either $c^{\oplus}(f)=0$, or
$c^{\ominus}(f)=0$, or both.

###### Proof.

Set $f_{1}=f_{2}$ in Proposition 2.1. ∎

Let us now set $c:=c^{\oplus}-c^{\ominus}$. Corollary 2.2 implies that
$|c(h)|=c^{\oplus}(h)+c^{\ominus}(h)$ for every $h\in\mathrm{Aut}(X)$. The
definitions of $\mu^{\oplus}$ and $\mu^{\ominus}$ immediately imply that
$\sum_{{f}\in\mathcal{O}(h)}{\mu^{\oplus}}(f)=\sum_{{f}\in\mathcal{O}(h)}c^{\oplus}({f})$
and
$\sum_{{f}\in\mathcal{O}(h)}{\mu^{\ominus}}(f)=\sum_{{f}\in\mathcal{O}(h)}c^{\ominus}({f})$
for each $h\in\mathrm{Aut}(X)$. It follows that
$\sum_{{f}\in\mathcal{O}(h)}|{\mu}(f)|\leq\sum_{{f}\in\mathcal{O}(h)}{\mu^{\oplus}}(f)+\sum_{{f}\in\mathcal{O}(h)}{\mu^{\ominus}}(f)=\sum_{{f}\in\mathcal{O}(h)}{c^{\oplus}}(f)+\sum_{{f}\in\mathcal{O}(h)}{c^{\ominus}}(f)=\sum_{{f}\in\mathcal{O}(h)}|c({f})|$
for each $h\in\mathrm{Aut}(X)$, and hence

$\sum_{h\in\mathrm{Aut}(X)}|{\mu}(h)|\leq\sum_{h\in\mathrm{Aut}(X)}|c({h})|.$

By setting ${\mathds{1}}_{X}:=\sum_{j=1}^{n}{\mathds{1}}_{x_{j}}$ and
recalling Corollary 2.1, we obtain
$F^{\oplus}({\mathds{1}}_{X})=\left(\sum_{h\in{\mathrm{Aut}(X)}}{c^{\oplus}(h)}\right){\mathds{1}}_{X}$
and
$F^{\ominus}({\mathds{1}}_{X})=\left(\sum_{h\in{\mathrm{Aut}(X)}}{c^{\ominus}(h)}\right){\mathds{1}}_{X}$.
Since any line in $B$ is a permutation of the first row of $B$, we get
$F^{\oplus}({\mathds{1}}_{X})=\left(\sum_{j=1}^{n}b_{1j}^{\oplus}\right){\mathds{1}}_{X}$
and
$F^{\ominus}({\mathds{1}}_{X})=\left(\sum_{j=1}^{n}b_{1j}^{\ominus}\right){\mathds{1}}_{X}$.
As a consequence, the equalities
$\sum_{h\in\mathrm{Aut}(X)}c^{\oplus}({h})=\sum_{j=1}^{n}b_{1j}^{\oplus}$ and
$\sum_{h\in\mathrm{Aut}(X)}c^{\ominus}({h})=\sum_{j=1}^{n}b_{1j}^{\ominus}$
hold, and therefore
$\sum_{h\in\mathrm{Aut}(X)}|c({h})|=\sum_{h\in\mathrm{Aut}(X)}c^{\oplus}({h})+\sum_{h\in\mathrm{Aut}(X)}c^{\ominus}({h})=\sum_{j=1}^{n}b_{1j}^{\oplus}+\sum_{j=1}^{n}b_{1j}^{\ominus}=\sum_{j=1}^{n}|b_{1j}|$.

Let us now consider the function
$\bar{\varphi}:=\sum_{j=1}^{n}\mathrm{sgn}(b_{1j}){\mathds{1}}_{x_{j}}\in\mathbb{R}^{X}\setminus\\{\mathbf{0}\\}$.
By recalling that any line in $B$ is a permutation of the first row of $B$, we
have that
$\sum_{j=1}^{n}|b_{1j}|=|\sum_{j=1}^{n}b_{1j}\mathrm{sgn}\left(b_{1j}\right)|\geq|\sum_{j=1}^{n}b_{ij}\mathrm{sgn}\left(b_{1j}\right)|$
for every index $i$. It follows that

$\|F(\bar{\varphi})\|_{\infty}=\left\|\sum_{i=1}^{n}\left(\sum_{j=1}^{n}b_{ij}\mathrm{sgn}\left(b_{1j}\right)\right){\mathds{1}}_{x_{i}}\right\|_{\infty}=\sum_{j=1}^{n}|b_{1j}|=\sum_{h\in\mathrm{Aut}(X)}|c({h})|\geq\sum_{h\in\mathrm{Aut}(X)}|{\mu}(h)|.$

Since $\|\bar{\varphi}\|_{\infty}=1$,
$\frac{\|F(\bar{\varphi})\|_{\infty}}{\|\bar{\varphi}\|_{\infty}}\geq\sum_{h\in\mathrm{Aut}(X)}|{\mu}(h)|$.

For every function $\varphi\in\mathbb{R}^{X}$ we have that
$F(\varphi)=F_{\mu}(\varphi):=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\
{\mu}(h)$. Hence,
$\|F(\varphi)\|_{\infty}\leq\sum_{h\in{\mathrm{Aut}(X)}}\|\varphi
h^{-1}\|_{\infty}\
|{\mu}(h)|=\|\varphi\|_{\infty}\sum_{h\in{\mathrm{Aut}(X)}}|{\mu}(h)|$.
Therefore,
$\frac{\|F(\varphi)\|_{\infty}}{\|\varphi\|_{\infty}}\leq\sum_{h\in\mathrm{Aut}(X)}{|\mu(h)|}$
for every $\varphi\in\mathbb{R}^{X}\setminus\\{\mathbf{0}\\}$.

In conclusion,
$\sum_{h\in\mathrm{Aut}(X)}{|\mu(h)|}=\max_{\varphi\in\mathbb{R}^{X}\setminus\\{\mathbf{0}\\}}\frac{\|F(\varphi)\|_{\infty}}{\|\varphi\|_{\infty}}$.
∎

######  Example 2.1.

The simplest non-trivial example concerning the statement of Theorem 1 can be
described as follows. Let $X=\\{1,2\\}$ and
$G={\mathrm{Aut}(X)}=\\{\mathrm{id}_{X},(1\;2)\\}$. Let us consider the linear
GEO $F:\mathbb{R}^{X}\to\mathbb{R}^{X}$ defined by setting
$F({\mathds{1}}_{1}):={\mathds{1}}_{1}-{\mathds{1}}_{2}$ and
$F({\mathds{1}}_{2}):={\mathds{1}}_{2}-{\mathds{1}}_{1}$. By defining
$\mu(\mathrm{id}_{X}):=1$ and $\mu((1\;2)):=-1$, we get that $\mu$ is a
permutant measure with respect to $G$ and
${F}(\varphi)=\sum_{{{h}\in{\mathrm{Aut}(X)}}}\varphi{{h}}^{-1}\ {\mu}({h})$
for every $\varphi\in\mathbb{R}^{X}$. Furthermore,
$\sum_{h\in\mathrm{Aut}(X)}{|\mu(h)|}=2=\frac{\|F({\mathds{1}}_{1}-{\mathds{1}}_{2})\|_{\infty}}{\|{\mathds{1}}_{1}-{\mathds{1}}_{2}\|_{\infty}}=\max_{\varphi\in\mathbb{R}^{X}\setminus\\{\mathbf{0}\\}}\frac{\|F(\varphi)\|_{\infty}}{\|\varphi\|_{\infty}}$.

We now observe that the assumption that $G$ transitively acts on $X$ cannot be
removed from Theorem 1.

######  Example 2.2.

Let us consider the set $X=\\{1,2\\}$ and the group
$G=\\{\mathrm{id}_{X}\\}\subseteq\mathrm{Aut}(X)=\\{\mathrm{id}_{X},(1\;2)\\}$.
Take the operator $F\colon{\mathbb{R}^{X}}\to{\mathbb{R}^{X}}$ defined by
setting $F(\mathds{1}_{i})=\mathds{1}_{1}$ for any $i\in X$. Although $F$ is a
linear GEO, there does not exist a permutant measure $\mu$ on $\text{Aut}(X)$,
such that $F(\varphi)=F_{\mu}(\varphi):=\sum_{h\in{\mathrm{Aut}(X)}}\varphi
h^{-1}\ {\mu}(h)$ for every $\varphi\in{\mathbb{R}^{X}}$.

By contradiction, let us assume that such a permutant measure $\mu$ exists.
Then,

$\mathds{1}_{1}=F(\mathds{1}_{1})=\mathds{1}_{1}\mathrm{id}_{X}\mu(\mathrm{id}_{X})+\mathds{1}_{1}(1\;2)\mu((1\;2))=\mathds{1}_{1}\mu(\mathrm{id}_{X})+\mathds{1}_{2}\mu((1\;2)).$

Since $\\{\mathds{1}_{1},\mathds{1}_{2}\\}$ is a basis for $\mathbb{R}^{X}$,
the equalities $\mu(\mathrm{id}_{X})=1$ and $\mu((1\;2))=0$ must hold.

It follows that

$F(\mathds{1}_{2})=\mathds{1}_{2}\mathrm{id}_{X}\mu(\mathrm{id}_{X})+\mathds{2}\mathds{1}_{1}(1\;2)\mu((1\;2))=\mathds{1}_{2}.$

This contradicts the assumption that $F(\mathds{1}_{2})=\mathds{1}_{1}$.

######  Example 2.3.

Let us set $X=\\{1,2,3,4\\}$ and $G={\mathrm{Aut}(X)}$. Let $F$ be a linear
GEO with respect to $G$. Let $B=(b_{ij})$ be the matrix associated with $F$
with respect to the basis
$\\{{\mathds{1}}_{x_{1}},\ldots,{\mathds{1}}_{x_{n}}\\}$. In the proof of
Lemma 2.1 we have seen that $b_{ij}=b_{\sigma_{g}(i)\sigma_{g}(j)}$ for any
$g\in G$. It follows that two values $\alpha,\beta\in\mathbb{R}$ exist, such
that $b_{ij}=\alpha$ if $i=j$ and $b_{ij}=\beta$ if $i\neq j$. By using the
cycle notation, let us set $\sigma=(1\;2\;3\;4)\in{\mathrm{Aut}(X)}$ and
$\langle\sigma\rangle=\\{\mathrm{id}_{X},\sigma,\sigma^{2}=(1\;3)(2\;4),\sigma^{3}=(1\;4\;3\;2)\\}$,
i.e., the cyclic group generated by $\sigma$. We have that $B=\alpha
P(\mathrm{id}_{X})+\beta P(\sigma)+\beta P(\sigma^{2})+\beta P(\sigma^{3})$.
Therefore, by setting $c(\mathrm{id}_{X}):=\alpha$,
$c(\sigma):=c(\sigma^{2}):=c(\sigma^{3}):=\beta$, and $c(h):=0$ for every
$h\not\in\langle\sigma\rangle$, we get
$F(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\ c(h)$.

However, the signed measure $c$ is not a permutant measure, since the orbits
under the conjugation action of $G$ are the sets

$\begin{array}[]{lcl}\mathcal{O}(\mathrm{id}_{X})&=&\\{\mathrm{id}_{X}\\}\\\
\mathcal{O}({\sigma})&=&\\{\sigma=(1\;2\;3\;4),(1\;2\;4\;3),(1\;3\;2\;4),(1\;3\;4\;2),(1\;4\;2\;3),\sigma^{3}=(1\;4\;3\;2)\\}\\\
\mathcal{O}({\sigma^{2}})&=&\\{(1\;2)(3\;4),\sigma^{2}=(1\;3)(2\;4),(1\;4)(2\;3)\\}\\\
\mathcal{O}({(1\;2)})&=&\\{(1\;2),(1\;3),(1\;4),(2\;3),(2\;4),(3\;4)\\}\\\
\mathcal{O}({(1\;2\;3)})&=&\\{(1\;2\;3),(1\;2\;4),(1\;3\;2),(1\;3\;4),(1\;4\;2),(1\;4\;3),(2\;3\;4),(2\;4\;3)\\}\end{array}$

and, according to our definition, $c$ is not constant on the orbits
$\mathcal{O}({\sigma})$ and $\mathcal{O}({\sigma^{2}})$.

Following the proof of Theorem 1, we can get a permutant measure $\mu$ by
computing an average on the orbits. In other words, we can set

$\mu(h):=\begin{cases}c(\mathrm{id}_{X})=\alpha,&\text{if
}h=\mathrm{id}_{X}\\\
\sum_{h\in\mathcal{O}(\sigma)}\frac{c(h)}{|O(\sigma)|}=\sum_{h\in\mathcal{O}(\sigma^{2})}\frac{c(h)}{|O(\sigma^{2})|}=\frac{\beta}{3},&\text{if
}h\in\mathcal{O}({\sigma})\cup\mathcal{O}({\sigma^{2}})\\\
0,&\text{otherwise.}\end{cases}$

By making this choice, the equality
$F(\varphi)=\sum_{g\in{\mathrm{Aut}(X)}}\varphi h^{-1}\ \mu(h)$ holds for
every $\varphi\in\mathbb{R}^{X}$, i.e., $F$ is the linear GEO associated with
the permutant measure $\mu$.

Proposition 1.1 and Theorem 1 immediately imply the following statement.

######  Theorem 2.

Assume that $G\subseteq\mathrm{Aut}(X)$ transitively acts on the finite set
$X$ and $F$ is a map from $\mathbb{R}^{X}$ to $\mathbb{R}^{X}$. The map $F$ is
a linear group equivariant operator for $(\mathbb{R}^{X},G)$ if and only if a
permutant measure ${\mu}$ exists such that
$F(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\ {\mu}(h)$ for every
$\varphi\in{\mathbb{R}^{X}}$.

##  3 Representation of linear GENEOs via permutant measures

Our main result about the representation of linear GEOs can be adapted to
GENEOs.

######  Theorem 3.

Assume that $G\subseteq\mathrm{Aut}(X)$ transitively acts on the finite set
$X$ and $F$ is a map from $\mathbb{R}^{X}$ to $\mathbb{R}^{X}$. The map $F$ is
a linear group equivariant non-expansive operator for $(\mathbb{R}^{X},G)$ if
and only if a permutant measure ${\mu}$ exists such that
$F(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\ {\mu}(h)$ for every
$\varphi\in{\mathbb{R}^{X}}$, and $\sum_{h\in{\mathrm{Aut}(X)}}|\mu(h)|\leq
1$.

###### Proof.

If $F$ is a linear group equivariant non-expansive operator for
$(\mathbb{R}^{X},G)$, then Theorem 1 guarantees that in $\mathrm{PM}(G)$ a
permutant measure ${\mu}$ exists, such that
$F(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\ {\mu}(h)$ for every
$\varphi\in{\mathbb{R}^{X}}$, and
$\sum_{h\in\mathrm{Aut}(X)}{|\mu(h)|}=\max_{\varphi\in\mathbb{R}^{X}\setminus\\{\mathbf{0}\\}}\frac{\|F(\varphi)\|_{\infty}}{\|\varphi\|_{\infty}}$.
Since $F$ is non-expansive, the inequality
$\sum_{h\in{\mathrm{Aut}(X)}}|\mu(h)|\leq 1$ follows. This proves the first
implication in our statement.

Let us now assume that a permutant measure ${\mu}$ exists such that

$F(\varphi)=\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\ {\mu}(h)$

for every $\varphi\in{\mathbb{R}^{X}}$, with
$\sum_{h\in{\mathrm{Aut}(X)}}|\mu(h)|\leq 1$. Then Proposition 1.1 states that
$F$ is a linear group equivariant operator for $(\mathbb{R}^{X},G)$. Moreover,

$\displaystyle\|F(\varphi)\|_{\infty}$
$\displaystyle=\left\|\sum_{h\in{\mathrm{Aut}(X)}}\varphi h^{-1}\
{\mu}(h)\right\|_{\infty}$
$\displaystyle\leq\sum_{h\in{\mathrm{Aut}(X)}}\left\|\varphi
h^{-1}\right\|_{\infty}|{\mu}(h)|$
$\displaystyle=\sum_{h\in{\mathrm{Aut}(X)}}\left\|\varphi\right\|_{\infty}|{\mu}(h)|$
$\displaystyle=\|\varphi\|_{\infty}\left(\sum_{h\in{\mathrm{Aut}(X)}}\
|{\mu}(h)|\right)$ $\displaystyle\leq\|\varphi\|_{\infty}.$

This proves that $F$ is non-expansive, and concludes the proof of the second
implication in our statement. ∎

##  4 How GENEOs based on permutant measures could be used for transforming
data

In this section we will illustrate an example of a possible application of
GENEOs obtained via permutant measures. The framework is the one described in
Example 1.2, with some extensions. We consider a subset
$X\subseteq\mathbb{R}^{3}$ made of points with integer coordinates, belonging
to a cubic lattice and discretizing a cube $C$. Formally, $X$ can be expressed
as the product $X=\\{1,\dots,n\\}^{3}$. We consider again the group $G$ of
orientation-preserving isometries that map $X$ into $X$. As already stated in
Example 1.2, let $\pi_{1},\pi_{2},\pi_{3}$ be the three planes that contain
the center of mass of $C$ and are parallel to a face of the cube $C$. Let
$h_{i}:X\to X$ be the orthogonal symmetry with respect to $\pi_{i}$, for
$i\in\\{1,2,3\\}$. Then $H_{1}=\\{h_{1},h_{2},h_{3}\\}$ is a permutant for
$G$. Let us now introduce two new permutants. First, consider the six planes
$\lambda_{1},\dots,\lambda_{6}$ each one containing a couple of edges of $C$
that are symmetric with respect to the center of mass of $C$. Moreover, let
$\ell_{i}:X\to X$ be the orthogonal simmetry with respect to $\lambda_{i}$ for
$i\in\\{1,2,3,4,5,6\\}$. It is easy to check that
$H_{2}=\\{\ell_{1},\dots,\ell_{6}\\}$ is a permutant for $G$. Lastly, it is
trivial to verify that $H_{3}=\\{s\\}$, where $s$ denotes the central symmetry
with respect to the center of mass of the cube, is another permutant for $G$.

Given the permutants $H_{1},H_{2}$ and $H_{3}$, three permutant measures
$\mu_{H_{1}},\mu_{H_{2}},\mu_{H_{3}}$ on $\mathrm{Aut}(X)$ can be defined in
the following way:

$\mu_{H_{i}}(h)=\begin{cases}\frac{1}{|H_{i}|}&\text{if}\,\,h\in H_{i},\\\
0&\text{otherwise.}\end{cases}\quad\text{for}\,\,i\in\\{1,2,3\\}.$

By definition, we have that
$\sum_{h\in\mathrm{Aut}(X)}\mu_{H_{i}}(h)=\sum_{h\in H_{i}}\mu_{H_{i}}(h)=1$
for $i\in\\{1,2,3\\}$. Hence, in force of Theorem 3 we know that the operators
defined as

$F_{i}(\varphi)=\frac{1}{|H_{i}|}\sum_{h\in H_{i}}\varphi h^{-1},\
\quad\text{for}\,\,i\in\\{1,2,3\\},$

are linear GENEOs with respect to $G$.

Now, let us introduce a classification problem that we will tackle with the
help of these GENEOs. We consider functions on X that can be interpreted as 3d
scans of playing dice. We denote each point $x$ of $X$ with its indexes in the
grid: $x=(i,j,k)$. All the functions $\varphi$ that we will take into account,
are such that $\varphi(i,j,k)=0$ if none of the indexes belong to the set
$\\{1,n\\}$. This means that the functions can be non-zero only on the outer
surface of the cube, as we are interested only in the visible part of the die.
We observe that the number of points of $X$ that belong to the outer surface
of the cube $C$ is $n^{3}-(n-2)^{3}$. Furthermore, we model the dots on the
faces of a die as two-dimensional Gaussian spots: in particular, if we
consider the coordinates $(a,b)$ on a face of the cube and we center the dot
at point $c=(\bar{a},\bar{b})\in\\{1,\dots,n\\}^{2}$, we obtain the following
representation:

$\varphi_{c}(a,b)=\begin{cases}e^{-{\frac{(a-\bar{a})^{2}+(b-\bar{b})^{2}}{2}}}&\text{if}\,\,\max{(|a-\bar{a}|,|b-\bar{b}|)}\leq
3\\\ 0&\text{otherwise}\end{cases}.$

We set the standard deviation $\sigma=1$, and hence $\varphi_{c}$ is close to
the Gaussian function when the distance between $(a,b)$ and the center $c$ is
strictly greater than $3$. Lastly, we can obtain every pattern that is
displayed on a face by summing several of such functions with different
centers $c_{i}=(\bar{a}_{i},\bar{b}_{i})$. Therefore, a face that shows $m$
dots located at the points $\\{c_{i}\\}_{i\in\\{1,\dots,m\\}}$ has the
expression:

$\varphi_{m}(a,b)=\sum_{i=1}^{m}k_{i}\,\varphi_{c_{i}}(a,b)$ (4.1)

We introduce the coefficients $k_{i}\in[0,1]$ to model differences of
intensity between the dots. These differences can be seen as noise caused by
the scanning procedure. Therefore, in the end, a data function $\varphi$
vanishes inside the cube and coincides with a function $\varphi_{m}$ for some
$m$ and some $\\{c_{i}\\}_{i\in\\{1,\dots,m\\}}$ on each of the six faces of
the cube.

In the following experimental part we fix $n=25$, $n_{1}=6$, $n_{2}=13$ and
$n_{3}=20$. We report some of the configurations that model the patterns of
standard dice. The reader can easily guess the missing ones:

  * •

One dot: $m=1$ and $c_{1}=(n_{2},n_{2})$.

  * •

Two dots: $m=2$ and $c_{1}=(n_{1},n_{1})$, $c_{2}=(n_{3},n_{3})$.

  * •

…

  * •

Five dots: $m=5$ and $c_{1}=(n_{1},n_{1})$, $c_{2}=(n_{1},n_{3})$,
$c_{3}=(n_{2},n_{2})$, $c_{4}=(n_{3},n_{1})$, $c_{5}=(n_{3},n_{3})$.

  * •

Six dots: $m=6$ and $c_{1}=(n_{1},n_{1})$, $c_{2}=(n_{1},n_{2})$,
$c_{3}=(n_{1},n_{3})$, $c_{4}=(n_{3},n_{1})$, $c_{5}=(n_{3},n_{2})$,
$c_{6}=(n_{3},n_{3})$.

We will consider two classes of dice. The first one will contain exclusively
dice in which the sum of opposite faces always equals seven: this is the class
that contains the standard dice on the market. The second class is made up of
dice where the sum of the number of dots on opposite faces is never equal to
seven: these dice are fake since they do not exist on the market. The two
classes are distinct with respect to the action of $G$, i.e., one die of the
first class cannot be obtained from a die of the other through the action of a
$g\in G$. Moreover, these two classes are distinct also with respect to the
action of the group of all isometries of the cube (not only the ones that
preserve the orientation).

(a) Firts class

(b) Second class

Figure 1: Example plot of two generated functions The left image shows a view
of a die belonging to the first class, i.e., a die where the sum of the number
of dots on opposite faces is always 7, as happens for the dice on the market.
The right image shows a view of a die belonging to the second class, i.e., a
die where the sum of the number of dots on opposite faces is never equal to 7.
These dice are not regular. It is possible to see that not all the dots are
equally vivid: this is due to the presence of the coefficients $k_{i}$. These
values model the noise resulting from the scanning procedure.

We generated a dataset of 10000 dice by means of the following procedure: dice
computed at odd iterations belong to the first class, while the ones computed
at even iterations belong to the second class. At each iteration, a random
arrangement of the faces is obtained according to the selected class. Then,
for each face, the appropriate function $\varphi_{m}$ is computed as the sum
in (4.1) with coefficients $k_{i}$ drawn independently from the uniform
distribution $U([0.6,1])$. Hence, we obtain a function
$\varphi:X\to\mathbb{R}$. Lastly, a random number $p$ in the set
$\\{1,2,3,4,5\\}$ is chosen, and for each index $i\in\\{1,\ldots,p\\}$ a line
$r_{i}$ that is a symmetry axis of the cube $C$ and is orthogonal to two of
its faces is randomly chosen. These choices are made with respect to uniform
probability distributions. Now, for each index $i$ a rotation of angle
$\frac{\pi}{2}$ around $r_{i}$ is applied to the function $\varphi$, and hence
we obtain a new function $\hat{\varphi}:X\to\mathbb{R}$ describing a die. This
ensures that all the possible spatial configurations of a die with a face
placed on a tabletop can be generated. We note that each function representing
a die is characterized by $n^{3}-(n-2)^{3}=3458$ distinct values rather than
the total $n^{3}=15625$ (this is due to the fact that the function vanishes
inside the cube). Figure 1 shows two examples of functions generated by
applying the previously described procedure.

In order to discriminate the data, we designed a pipeline that makes use of
GENEOs, and then we compared it to the analogous pipeline that uses only the
original data. The pipeline is composed as follows:

  1. 1.

A GENEO $F$ is obtained as a convex combination of $F_{1},F_{2},F_{3}$ with
weights $\alpha_{1},\alpha_{2},\alpha_{3}$, and then $F$ is applied to all the
functions of the dataset. (Here we are using the property that the spaces of
GENEOs are convex, provided that the spaces of data are convex Bergomi2019 .)

  2. 2.

Each transformed function $\psi:X\to\mathbb{R}$ is treated as a vector
$v_{\psi}\in\mathbb{R}^{n^{3}-(n-2)^{3}}$, storing the values of $\psi$ at the
points of $X$ belonging to the outer surface of $C$. This allows to identify
each die with a vector in $\mathbb{R}^{3458}$. To reduce the dimensionality of
these data we apply the PCA (Principal Component Analysis), preserving only
the first two PCs.

  3. 3.

With the reduced data, a SVM (Support Vector Machine) classifier with
quadratic kernel is trained in order to discriminate the two classes.

The pipeline that uses the original data skips the first step and feeds to the
PCA directly the vectors associated with the original functions.

To compare the two methods, we randomly split the dataset into a training set
of size 7000 and a test set of size 3000. Both the subsets have been sampled
in order to maintain a balanced distribution of the two classes. This
splitting was used just to evaluate SVM classifiers in the third step, whereas
the PCA was computed using the whole dataset in both cases.

(a) First method (not using GENEOs)

(b) Second method (using GENEOs)

Figure 2: Plots of PCA results This figure shows the results of PCA
dimensionality reduction for both methods. Blue points are associated with
functions belonging to the first class, while orange ones with functions
belonging to the second class. A separation between the mapped points is
clearly more evident in the right figure, which is the one relative to the
method involving GENEOs. Hence GENEOs provide a simpler and more informative
representation of the data.

Figure 2 shows the results of dimensionality reduction for both kinds of data.
It is clear that, for this specific choice, the outputs of the GENEO $F$
provide a clearer representation of the data: points are indeed almost
separated, whereas, with the original data a separation is far less evident.
However, it must be noted that not all the GENEOs obtained as convex
combination of $F_{1},F_{2},F_{3}$ provide such a result. Here the parameters
$\alpha_{1},\alpha_{2},\alpha_{3}$ have been repeatedly sampled from a
Dirichlet distribution to select the ones giving the best results
($\alpha_{1}=0.318$, $\alpha_{2}=0.551$, $\alpha_{3}=0.131$).

The plot also shows that in the right side picture it is reasonable to expect
an almost perfect classification with a quadratic decision boundary. This fact
justifies the third step of the pipeline. The decision boundaries learned by
the SVM classifiers are shown in Figure 3, while Table 1 reports confusion
matrices and accuracy scores for the two methods.

(a) Firts method (not using GENEOs)

(b) Second method (using GENEOs)

Figure 3: Plots of SVM decision boundaries PCA results suggest that the
simpler choice to classify the mapped points is to use a quadratic decision
boundary. These figures show the boundaries learned by the SVM algorithm with
a quadratic kernel for both methods. The right image shows that it is
reasonable to expect better classification scores for the method involving
GENEOs.

| Predicted |
---|---|---
| Class 1 | Class 2 | Total
True | Class 1 | $2350$ | $1150$ | $3500$
Class 2 | $793$ | $2707$ | $3500$
| Total | $3143$ | $3857$ | $7000$
(a) Train CM for original data.
Accuracy = 0.722

| Predicted |
---|---|---
| Class 1 | Class 2 | Total
True | Class 1 | $1030$ | $470$ | $1500$
Class 2 | $345$ | $1155$ | $1500$
| Total | $1375$ | $1625$ | $3000$
(b) Test CM for original data.
Accuracy = 0.728

| Predicted |
---|---|---
| Class 1 | Class 2 | Total
True | Class 1 | $3432$ | $68$ | $3500$
Class 2 | $232$ | $3268$ | $3500$
| Total | $3664$ | $3336$ | $7000$
(c) Train CM for GENEO data.
Accuracy = 0.957

| Predicted |
---|---|---
| Class 1 | Class 2 | Total
True | Class 1 | $1464$ | $36$ | $1500$
Class 2 | $100$ | $1400$ | $1500$
| Total | $1564$ | $1436$ | $3000$
(d) Test CM for GENEO data.
Accuracy = 0.955

Table 1: Confusion Matrices These tables report confusion matrices for both
methods and for both train and test set. The accuracy score is considerably
higher for the method which uses GENEOs both for training and test set. Since
train and test accuracy scores are very near for both methods, we are
confident that the methods perform equally well on unseen data, meaning that
they are not overfitting.

As we expected, the method employing GENEOs has an accuracy score of 0.955 on
the test set, a value significantly higher than the one of the method without
GENEOs, which is 0.728.

This result holds even if we modify some of the hyperameters. For example, we
can change the distribution of the coefficients $k_{i}$. In particular, we can
consider again a uniform distribution but with a smaller range containing 1
(i.e., [0.8, 1.0]). In this way we reduce the randomness of the data. Because
of this, the plots of Figures 2 and 3 tend to show groups of points that are
much more concentrated, and therefore both the methods perform better, even
though there is still a gap between the two. Furthermore, if we change the
number of PCs retained by the PCA, we observe similar results by keeping one
to three PCs. Starting from four PCs onward the two methods perform almost
equally well. Another possibility is to use a different kernel for the SVM
classifiers. For example, one can use a Radial Basis Function (RBF) kernel to
obtain more complex decision boundaries. Models capable of learning more
complex decision boundaries reduce the gap of performances between the two
approaches, nonetheless considering up to two PCs the use of GENEOs is still
highly beneficial. A summary of these experiments is reported in Table 2.

$k_{i}$ distribution |  Number of PCs | SVM kernel |  Accuracy without GENEOs |  Accuracy with GENEOs
---|---|---|---|---
$U([0.8,1.0])$ | 1 | quadratic | 0.580 | 0.839
$U([0.8,1.0])$ | 2 | quadratic | 0.726 | 0.999
$U([0.8,1.0])$ | 3 | quadratic | 0.974 | 0.999
$U([0.8,1.0])$ | 4 | quadratic | 0.981 | 0.999
$U([0.8,1.0])$ | 1 | RBF | 0.685 | 0.915
$U([0.8,1.0])$ | 2 | RBF | 0.916 | 1.000
$U([0.8,1.0])$ | 3 | RBF | 1.000 | 1.000
$U([0.6,1.0])$ | 1 | quadratic | 0.589 | 0.819
$U([0.6,1.0])$ | 2 | quadratic | 0.728 | 0.955
$U([0.6,1.0])$ | 3 | quadratic | 0.915 | 0.956
$U([0.6,1.0])$ | 4 | quadratic | 0.930 | 0.955
$U([0.6,1.0])$ | 1 | RBF | 0.615 | 0.828
$U([0.6,1.0])$ | 2 | RBF | 0.816 | 0.974
$U([0.6,1.0])$ | 3 | RBF | 0.970 | 0.976
$U([0.4,1.0])$ | 1 | quadratic | 0.591 | 0.778
$U([0.4,1.0])$ | 2 | quadratic | 0.718 | 0.902
$U([0.4,1.0])$ | 3 | quadratic | 0.860 | 0.901
$U([0.4,1.0])$ | 4 | quadratic | 0.881 | 0.903
$U([0.4,1.0])$ | 1 | RBF | 0.600 | 0.780
$U([0.4,1.0])$ | 2 | RBF | 0.742 | 0.910
$U([0.4,1.0])$ | 3 | RBF | 0.893 | 0.909
$U([0.4,1.0])$ | 4 | RBF | 0.932 | 0.911
Table 2: Accuracy scores for different hyperparameters This table shows a
comparison between the accuracies of the two methods for different
combinations of the hyperparameters. Using GENEOs is always beneficial when
combined with a quadratic kernel SMV and a PCA with number of PCs less than
four. Otherwise, with a RBF kernel SVM, GENEOs are beneficial up to two or
three PCs, whereas retaining more PCs the two methods tend to perform equally
well.

##  5 Discussion

In our paper we have proved that all linear GEOs and GENEOs can be produced by
means of a dual method based on the concept of permutant measure with respect
to a group $G$, under the assumption that $G$ transitively acts on a finite
set. This method could be particularly useful when we have to deal with a
large group $G$, as frequently happens in real applications. Summations on
large groups can indeed present computational difficulties, while summations
on the supports of permutant measures are often easier. The use of the set of
all permutant measures also benefits of its lattice structure. The
availability of the approach we have studied in this paper could be relevant
for the application of GEOs and GENEOs as multi-level components in deep
learning and make the construction of neural networks more transparent and
interpretable, according to the mathematical framework proposed in Bergomi2019
. The next natural step in this line of research is the extension of our
approach to topological groups. We plan to study this possible extension in a
forthcoming paper.

In Section 4 we have also illustrated an example, showing how GENEOs built by
permutant measures could be used in order to extract relevant properties from
data. In our opinion, GENEOs of this kind could be of great use in machine
learning, since they can inject information about the way data should be
managed on the basis of prior knowledge. In the given example, this knowledge
was represented by the clear relevance of symmetries in data concerning a
cube, leading us to focus our attention on symmetry planes. We are aware of
the toy nature of this example, nonetheless we believe that it is important
for two main reasons: first, it shows that a small network of GENEOs can be
more informative than its single components, secondly, it makes clear that
GENEOs allow to obtain simple and explainable representations of data that are
easier to process in a pipeline with other explainable methods. We know that
this specific example could be managed in many other ways, without the drastic
dimensionality reduction of PCA and with methods more complex than SVM
classifiers. Despite this, we showed that GENEOs can improve the results by
requiring only minimal information. In the near future, we plan to develop
more extended applications of GENEOs built via permutant measures, employing
real world data.

###### Acknowledgements.

This research has been partially supported by INdAM-GNSAGA. The authors thank
Alessandro Achille, Fabio Anselmi and Giovanni Paolini for their helpful
advice. This paper is dedicated to the memory of Dr. Mohamed Mashally.

## Conflict of interest

The authors declare that they have no conflict of interest.

## Authors’ contributions

P.F. devised the project. All authors contributed to the manuscript. All
authors read and approved the final manuscript. The authors of this paper have
been listed in alphabetical order.

## References

  * (1) Anselmi, F., Evangelopoulos, G., Rosasco, L., Poggio, T.: Symmetry-adapted representation learning.  Pattern Recognition 86, 201 – 208 (2019).  https://doi.org/10.1016/j.patcog.2018.07.025.  URL http://www.sciencedirect.com/science/article/pii/S0031320318302620
  * (2) Anselmi, F., Rosasco, L., Poggio, T.: On invariance and selectivity in representation learning.  Information and Inference: A Journal of the IMA 5(2), 134–158 (2016).  10.1093/imaiai/iaw009.  URL http://dx.doi.org/10.1093/imaiai/iaw009
  * (3) Aschbacher, M.: Finite Group Theory, 2 edn.  Cambridge Studies in Advanced Mathematics. Cambridge University Press (2000).  10.1017/CBO9781139175319
  * (4) Bengio, Y., Courville, A., Vincent, P.: Representation learning: A review and new perspectives.  IEEE Transactions on Pattern Analysis and Machine Intelligence 35(8), 1798–1828 (2013)
  * (5) Bergomi, M.G., Frosini, P., Giorgi, D., Quercioli, N.: Towards a topological–geometrical theory of group equivariant non-expansive operators for data analysis and machine learning.  Nature Machine Intelligence 1(9), 423–433 (2019).  10.1038/s42256-019-0087-3.  URL https://doi.org/10.1038/s42256-019-0087-3
  * (6) Bronstein, M.M., Bruna, J., LeCun, Y., Szlam, A., Vandergheynst, P.: Geometric deep learning: Going beyond Euclidean data.  IEEE Signal Processing Magazine 34(4), 18–42 (2017).  10.1109/MSP.2017.2693418
  * (7) Camporesi, F., Frosini, P., Quercioli, N.: On a new method to build group equivariant operators by means of permutants.  In: A. Holzinger, P. Kieseberg, A.M. Tjoa, E. Weippl (eds.) 2nd International Cross-Domain Conference for Machine Learning and Knowledge Extraction (CD-MAKE), _Machine Learning and Knowledge Extraction_ , vol. LNCS-11015, pp. 265–272. Springer International Publishing, Hamburg, Germany (2018).  10.1007/978-3-319-99740-7_18.  URL https://hal.inria.fr/hal-02060057.  Part 4: MAKE-Topology
  * (8) Cohen, T., Welling, M.: Group equivariant convolutional networks.  In: International conference on machine learning, pp. 2990–2999 (2016)
  * (9) Conti, F., Frosini, P., Quercioli, N.: On the construction of group equivariant non-expansive operators via permutants and symmetric functions.  Frontiers in Artificial Intelligence 5 (2022).  10.3389/frai.2022.786091.  URL https://www.frontiersin.org/article/10.3389/frai.2022.786091
  * (10) Donatini, P., Frosini, P.: Natural pseudodistances between closed manifolds.  Forum Math. 16(5), 695–715 (2004).  10.1515/form.2004.032.  URL https://doi-org.ezproxy.unibo.it/10.1515/form.2004.032
  * (11) Donatini, P., Frosini, P.: Natural pseudodistances between closed surfaces.  J. Eur. Math. Soc. (JEMS) 9(2), 331–353 (2007)
  * (12) Donatini, P., Frosini, P.: Natural pseudo-distances between closed curves.  Forum Math. 21(6), 981–999 (2009).  10.1515/FORUM.2009.049.  URL https://doi-org.ezproxy.unibo.it/10.1515/FORUM.2009.049
  * (13) Dufossé, F., Kaya, K., Panagiotas, I., Uçar, B.: Further notes on Birkhoff–von Neumann decomposition of doubly stochastic matrices.  Linear Algebra and its Applications 554, 68 – 78 (2018).  https://doi.org/10.1016/j.laa.2018.05.017.  URL http://www.sciencedirect.com/science/article/pii/S0024379518302568
  * (14) Frosini, P.: Does intelligence imply contradiction?  Cognitive Systems Research 10, 297–315 (2009)
  * (15) Frosini, P.: Towards an observer-oriented theory of shape comparison.  In: A. Ferreira, A. Giachetti, D. Giorgi (eds.) Eurographics Workshop on 3D Object Retrieval. The Eurographics Association (2016).  10.2312/3dor.20161080
  * (16) Frosini, P., Jabłoński, G.: Combining persistent homology and invariance groups for shape comparison.  Discrete Comput. Geom. 55(2), 373–409 (2016).  10.1007/s00454-016-9761-y.  URL http://dx.doi.org/10.1007/s00454-016-9761-y
  * (17) Frosini, P., Mulazzani, M.: Size homotopy groups for computation of natural size distances.  Bull. Belg. Math. Soc. Simon Stevin 6(3), 455–464 (1999).  URL http://projecteuclid.org.ezproxy.unibo.it/euclid.bbms/1103065863
  * (18) Frosini, P., Quercioli, N.: Some remarks on the algebraic properties of group invariant operators in persistent homology.  In: A. Holzinger, P. Kieseberg, A.M. Tjoa, E. Weippl (eds.) 1st International Cross-Domain Conference for Machine Learning and Knowledge Extraction (CD-MAKE), _Machine Learning and Knowledge Extraction_ , vol. LNCS-10410, pp. 14–24. Springer International Publishing, Reggio, Italy (2017).  10.1007/978-3-319-66808-6_2.  URL https://hal.inria.fr/hal-01677132.  Part 1: MAKE Topology
  * (19) Kondor, R., Trivedi, S.: On the generalization of equivariance and convolution in neural networks to the action of compact groups.  In: J. Dy, A. Krause (eds.) Proceedings of the 35th International Conference on Machine Learning, _Proceedings of Machine Learning Research_ , vol. 80, pp. 2747–2755. PMLR, Stockholmsmässan, Stockholm Sweden (2018).  URL http://proceedings.mlr.press/v80/kondor18a.html
  * (20) Mallat, S.: Group invariant scattering.  Communications on Pure and Applied Mathematics 65(10), 1331–1398 (2012).  10.1002/cpa.21413.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/cpa.21413
  * (21) Mallat, S.: Understanding deep convolutional networks.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 374(2065), 20150203 (2016).  10.1098/rsta.2015.0203.  URL https://royalsocietypublishing.org/doi/abs/10.1098/rsta.2015.0203
  * (22) Worrall, D.E., Garbin, S.J., Turmukhambetov, D., Brostow, G.J.: Harmonic networks: Deep translation and rotation equivariance.  In: Proc. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), vol. 2 (2017)
  * (23) Zhang, C., Voinea, S., Evangelopoulos, G., Rosasco, L., Poggio, T.: Discriminative template learning in group-convolutional networks for invariant speech representations.  In: INTERSPEECH-2015. International Speech Communication Association (ISCA), International Speech Communication Association (ISCA), Dresden, Germany (2015).  URL http://www.isca-speech.org/archive/interspeech_2015/i15_3229.html