Classifying functions up to suitable pre-composition and/or post-composition

Question

What's a name for a general technique I've seen used many times?

Given any family $\mathcal{F}$ of functions such that $f:X\to Y$ for all $f\in \mathcal{F}$ when one wishes to study in general for an arbitrary $y\in Y$ what (if any) $x\in X$ satisfy $f(x)=y$ it seems often the approach taken is to first find some permutation group $P\subseteq \text{Sym}(Y)$ such that:

$$\forall \sigma\in P\left(f\in \mathcal{F}\implies f\circ \sigma\in \mathcal{F}\right)$$

Then from here viewing this as a right group action of $P$ on $\mathcal{F}$ we form an equivalence relation $\sim$ over $\mathcal{F}$ with each equivalence class an orbit e.g. $\text{Orb}(f)=\{f\circ \sigma\in \mathcal{F}:\sigma\in P\}$ so that we get:

$$f\sim g\iff \text{Orb}(f)=\text{Orb}(g)\iff \exists \sigma\in P:f=g\circ \sigma$$

At this point for every $f\in \mathcal{F}$ given the equation $f(x)=y$ we find a unique "nice" $C_{f}\in \text{Orb}(f)$ (nice in its easier to study what $x\in X$ satisfy $C_f(x)=y$) and let this be a canonical form for our equivalence class $\text{Orb}(f)=[f]_{\sim}$ then our original problem reduces to just studying the family of functions $\mathcal{G}\subseteq \mathcal{F}$ where $\mathcal{G}=\{C_f\in \mathcal{F}:f\in \mathcal{F}\}$. To make this idea more explict here are three examples where I've seen this sort of idea used:

---

A simple first example is the notion of "reduced echelon form" in introductory linear algebra courses where here $\mathcal{F}=\mathcal{M}_{m\times n}(\mathbb{F})$ would be the set of all matrices over some field $\mathbb{F}$ and $P=\text{GL}_n(\mathbb{F})$ would be a general linear group over $\mathbb{F}$. https://en.wikipedia.org/wiki/Row_echelon_form

---

A second example is many techniques used when studying univariate polynomials over again just to make things simple lets say those polynomials with coefficients in $\mathbb{F}$ so we get $\mathcal{F}\subseteq\mathbb{F}[X]$. From here $P$ would take the form of scaling/shifting for example reducing each polynomial to a monic one, or shifting along its input to eliminate a monomial in the resulting composition. E.g. if we have:

$$f(x)=x^n+ax^{n-1}+bx^{n-2}+\cdots+c$$

Then if $\sigma:x\to x-\frac{a}{n}$ expanding $(f\circ \sigma)(x)$ the coefficient on the monomial $x^{n-1}$ vanishes. Where in particular if $1<n<5$ this is specifically named/detailed out here:

When $n=2$: https://en.wikipedia.org/wiki/Completing_the_square#General_description

When $n=3$: https://en.wikipedia.org/wiki/Cubic_function#Reduction_to_a_depressed_cubic

When $n=4$: https://en.wikipedia.org/wiki/Quartic_function#Converting_to_a_depressed_quartic

---

A third example comes when studying positive definite integral binary quadratic forms so that here $\mathcal{F}$ is the set of BQFs and $P=\text{GL}_2(\mathbb{Z})$ thus reducing each $f\in \mathcal{F}$ with $f(x,y)=ax^2+bx+c$ through a linear transformation of its input $(x,y)$ via multiplication by matrices in $\text{GL}_2(\mathbb{Z})$ until we have a BQF satisfying $|2|c|-\sqrt{b^2-4ac}|<b<\sqrt{b^2-4ac}$ is how we get our canonicals also for negative discriminants see: http://mathworld.wolfram.com/ReducedBinaryQuadraticForm.html

---

So to re-iterate my question, does this general "technique" I outlaid at the start have a name? Or is it just seen as an obvious approach/tool to try and use when studying a given family of functions?

Answer 1

The emphasis on finding solutions to equations $f(x) = y$ is a red herring, and note that in your examples your symmetries aren't acting pointwise on $Y$ as in your general explanation (sometimes they are acting on $X$), but that's not particularly important.

More generally, suppose you want to understand anything about the elements of any set $S$ whatsoever; a very common approach to doing this is to find a group $G$ acting on $S$ such that the thing you want to understand is invariant under the action of $G$, then find a nice normal or canonical form under the action of $G$.

Terence Tao calls this spending symmetry; related notions include

• fixing a gauge,
• finding a fundamental domain for a group action.

Here are two quick examples more general than solving equations:

• The spectral theorem says that every orbit under the conjugation action of the unitary group on normal matrices contains a diagonal matrix. This makes it easy, among other things, to exponentiate normal matrices, and more generally can be used to establish functional calculus for matrices.
• The existence of singular value decomposition says that every orbit under the action of $O(n) \times O(m)$ on $n \times m$ real matrices (by left and right multiplication) contains a diagonal matrix with nonnegative entries. This has many applications, for example to describing low rank approximations to matrices; see e.g. this blog post.

Groups naturally appear as changes of coordinates in various senses, so there are lots of examples involving groups, but there are also important examples where something more general than a group action appears; the more general thing might be called reductions.

Again suppose you are trying to understand anything about the elements of any set $S$ whatsoever. Moreover, suppose you can establish "implications" between the elements of $S$, to the effect that if you've understood some $s_1 \in S$, then you've understood some $s_2 \in S$; we can capture these implications in a relation $R$ on $S$ (which, in the group action example, is the relation of belonging to the same orbit). Under the very mild assumption that this relation $R$ is reflexive and transitive, $R$ gives $S$ the structure of a preorder (which in the group action case is an equivalence relation), and to understand all of $S$ it suffices to understand some subset $S_0 \subseteq S$ of elements which "cover" $S$ in the sense that implications from $S_0$ reach all of $S$.

Maybe the most famous example of this phenomenon is in computer science, where if $S$ is the set of problems in NP, then $S_0$ can be taken to be the set with a single element consisting of any NP-complete problem. Here the relation $R$ is polynomial-time reduction. But mathematicians also use reductions all the time, any time they end up saying something like "...so the problem reduces to understanding the special case where...." A typical mathematical example is using techniques like localization in commutative algebra to reduce a problem about arbitrary commutative rings to a particularly simple class of rings, maybe noetherian rings, local rings, or fields.