Question. How can we formalize these intuitions about predicates on matrices?
Let $P$ denote a predicate on matrices, so that $P(A)$ is true for some choices of matrix $A$ and false for all others. Then as I understand it, $P$ is preserved under equivalence of matrices iff $P$ is induced by a "natural" predicate on linear transforms between vector spaces.
Now let $Q$ denote a predicate on square matrices. Then as I understand it:
- $Q$ is preserved under similarity of matrices iff $Q$ is induced by a "natural" predicate on endolinear transforms.
- $Q$ is preserved under congruence of matrices iff $Q$ is induced by a "natural" predicate on bilinear forms.
I'm not 100% sure these statements are actually correct, especially that last one.
Anyway, these are imprecise statements, owing mainly to the undefined use of the word "natural". How can we formalize them? There is a suggestion here that "natural" in this context is correctly formalized by the concept of a "natural transformation," but the details aren't clear to me.
Let $S$ be a set and $P \colon M_n(\mathbb{F}) \rightarrow S$ a function which is invariant under similarity - that is, $P(A^{-1} \cdot B \cdot A) = P(B)$ for all $B \in M_n(\mathbb{F})$ and $A \in GL_n(\mathbb{F})$. You can take $S = \mathbb{F}$ and $P = \det$ or $P = \mathrm{trace}$ or you can take $S = \{0,1\}$ and think of $P$ as a predicate.
Using $P$, you can define a family of functions $P_V \colon \mathrm{Hom}(V,V) \rightarrow S$, one for each vector space $V$ over $\mathbb{F}$ of dimension $n$, by
$$ P_V(T) = P([T]^{B_V}_{B_V}) \tag{1} $$
where $[T]^{B_V}_{B_V} \in M_n(\mathbb{F})$ is the matrix representing $T$ with respect to the basis $B_V$ (used for both the domain and range) and $B_V$ is some arbitrary basis.
Now, for $P_V$ to be well-defined, we need to check that this definition is independent of the basis we have chosen for $V$ and this follows immediately from the similarity invariance of $P$. This "checking" is done "pointwise", for each $V$ separately. However, if we look at the family $\{ P_V \}_{V}$, we see that this family (of predicates, or invariants) satisfies an additional property - $P_V$ and $P_W$ are not independent but satisfy some relations.
To state them, let me introduce some notation. Given a bijective linear map $\phi \colon V \rightarrow W$, let me denote by $\phi_{*} \colon \mathrm{Hom}(V,V)\rightarrow (W,W)$ the linear map defined by $$ \phi_{*}(T) = \phi \circ T \circ \phi^{-1}. $$ This map is a linear isomorphism. Then, for any pair of vector spaces $V$ and $W$ and any invertible linear map $\phi \colon V \rightarrow V$ we have the following commutative diagram:
$$\require{AMScd} \begin{CD} \mathrm{Hom}(V,V) @>{P_V}>> S\\ @VV\phi_{*}V @VV\mathrm{id}V \\ \mathrm{Hom}(W,W) @>{P_W}>> S \end{CD}$$
That is, $$P_W(\phi_{*}(T)) = P_W(\phi \circ T \circ \phi^{-1}) = P_V(T)$$ for all $T \in \mathrm{Hom}(V,V)$ and all $\phi \colon V \rightarrow W$. This is the naturality property of the collection of functions $\{P_V\}_{V}$. In fact, since $\phi_{*}$ is an isomorphism and any two vector spaces of dimension $n$ are isomorphic, we see that this commutativity implies that $\phi_{V}$ is determined uniquely by its behaviour on a specific vector space $V$.
Given a linear map $T \colon \mathbb{F}^n \rightarrow \mathbb{F}^n$ there is a unique matrix $A \in M_n(\mathbb{F})$ such that $T(x) = Ax$ and so we obtain a ("natural", without any choices) isomorphism from $M_n(\mathbb{F})$ to $\mathrm{Hom}(\mathbb{F}^n,\mathbb{F}^n)$. Using this identification, we see that $P_{\mathbb{F}^n} = P$ and we have extended $P$ from being defined on $\mathrm{Hom}(\mathbb{F}^n,\mathbb{F}^n)$ (which is "naturally" identified with $M_n(\mathbb{F})$) to be defined on all $\mathrm{Hom}(V,V)$, but in a very specific way which keeps the diagram above commutative.
How can we construct a family $P_V$ of functions that are not natural in the sense above? Well, take two different similarity-invariant functions on $M_n(\mathbb{F})$ (say $\det$ and $\mathrm{trace}$) and "define" $P_V$ by
$$ P_V = \begin{cases} P_1([T]_{B_V}^{B_V}) & \mbox{if } V = \mathbb{F}^n \\ P_2([T]_{B_V}^{B_V}) & \mbox{if } V \neq \mathbb{F}^n \end{cases} $$
Then $P_V$ will still be a well-defined family of predicates (this uses the similarity invariant of $P_i$) but it won't satisfy the naturality property.
The same discussion applies for bilinear forms and I leave it as an exercise to choose the neccesary categories, functors and modifications in order to make the discussion match the definition of natural transformation in category theory. Using the definition above, your statements become precise theorems (or rather "observations").