  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.
