3
$\begingroup$

Treating rotation in $\mathbb{R}^n$ as $x\to Ox$ for orthogonal $O^T O=O O^T=1$, we can easily get complete sets of independent rotation invariants for degree 1 and 2 homogeneous polynomials:

  1. Degree 1: for $p(x)=\sum_i P_i x_i$, rotation: $P_i\to \sum_a P_a O_{ai}$ has single invariant: $\sum_i P_i^2$: $$\sum_i \left(\sum_a P_a O_{ai}\right)^2 = \sum_{ia\alpha} P_a O_{ai} P_\alpha O_{\alpha i} = \sum_{a\alpha} P_a P_\alpha \delta_{a\alpha} = \sum_a P_a^2$$

  2. Degree 2: $p(x)=\sum_{ij} P_{ij} x_i x_j$ has $n$ independent rotation invariants: eigenspectrum of (symmetric) $P=P^T$, or equivalently $\{0,\ldots,n-1\}$ coefficients of characteristic polynomial $\det(P-\lambda I)$, or equivalently $\textrm{Tr}(P^m)$ for $m\in \{1,\ldots,n\}$. Let's check the last one:

$$\textrm{Tr}((O^T P O)^m)=\textrm{Tr}(O^T P^m O)=\sum_{iab} O_{ai}(P^m)_{ab}O_{bi}=\sum_{ab}(P^m)_{ab} \delta_{ab}=\textrm{Tr}(P^m).$$

For degree 3 such rotation would analogously mean:

$$P_{ijk}\to\sum_{abc} P_{abc} O_{ai} O_{bj} O_{ck}$$

How to construct rotation invariants for degree 3 and higher? How many independent invariants should we expect?

My motivation is testing graph isomorphism problem, which after looking at eigenspaces of adjacency matrix becomes question if two sets of points differ only by rotation, and theses sets can be described using homogeneous polynomials (stack) - efficient testing for degree 3 or 4 should be sufficient.


Update 1: In analogy to degree 1, here is one for degree 3: $\sum_{ijk} P_{ijk}^2$ (and the same for higher): $$\sum_{ijk}\left(\sum_{abc} P_{abc} O_{ai} O_{bj} O_{ck}\right)^2= \sum_{ijkabc\alpha\beta\gamma} P_{abc} O_{ai} O_{bj} O_{ck} P_{\alpha\beta\gamma} O_{\alpha i} O_{\beta j} O_{\gamma k}=\sum_{abc}P_{abc}^2$$


Update 2: In analogy to Tr$(P^2)=\sum_{ij} P_{ij} P_{ji}$ for degree 2, for degree 3 we can get invariant $\sum_{ijk} P_{ijk} P_{jki}$:

$$\sum_{ijk}\left(\sum_{abc} P_{abc} O_{ai} O_{bj} O_{ck}\right) \left(\sum_{\alpha\beta\gamma} P_{\beta\gamma\alpha} O_{\beta j} O_{\gamma k} O_{\alpha i}\right) =\sum_{abc} P_{abc} P_{bca} $$ As every $ijk$ summation leads to one Kronecker delta $\delta$. Analogously $\sum_{ijk} P_{ijk} P_{kij}$.


Update 3 (22.12.2017): We can analogously go with lager sets of variables, turning pairs of $O$ into Kronecker deltas: every variable should appear in exactly two terms.

For example $\sum_{abcdef} P_{abc} P_{ade} P_{bcf} P_{def} $ is rotation invariant this way.

We get nice combinatorics of indexes (like in free probability) - leading to final questions:

For degree 2 we would take Tr$(P^{m})$ for $m=1\ldots n$, the next one: Tr$(P^{n+1})$ would be dependent - how to generally choose the largest independent set of rotation invariants? Looking at degree 2, I suspect what is crucial is determining its size (kind of size of eigenbasis) - then "many"(?) sets of invariants of this size should be right ("determine eigenbasis").

Are they really all rotation invariants for homogeneous polynomials? (we know it is true for degree 1 and 2)

If all required invariants agree, can we effectively determine the rotation? (I suspect the set of possible rotations might be nasty (?) )


Update 4: Diagrammatic representation of some first rotation invariants for degree 1,2,3,4:

enter image description here

Degree of polynomial is also degree of vertex. Edge corresponds to summed index. Vertices and edges are unlabeled. Disconnected graphs gives invariants being products over its components.


Update 5: We can analogously get rotation invariants for general polynomials: $$p(x)=p+\sum_i p_i x_i +\sum_{ij} p_{ij} x_i x_j + \ldots $$ Beside the homogeneous terms like in the above diagram, there are also additional mixing terms corresponding to graphs with vertices of varying degree, starting with $\sum_{ab} p_a p_{ab} p_b$.

It is much better than what is offered by standard e.g. rotationally invariant spherical harmonics, which give only 1 rotation invariant per degree (angular momentum $l$), and don't allow to test mixing between them.

Here we probably get a complete set of rotation invariants - such that their agreement ensures that polynomials differ only by rotation.

How to choose such complete sets of invariants - completely defining polynomial of given degree modulo rotation?

For degree 2: $p(x)=x^T A x + b^Tx+ c$ describes e.g. paraboloid. Rotation invariants are: $c$, $\sum_i b_i^2$, Tr$(A^k)$ for $k=1\ldots n$. Adding $\sum_{ij} b_i (A^k)_{ij} b_j$ for $k=1...n-1$ invariants should completely define this paraboloid modulo rotation.


Update 6: For a complete set of invariants (determining polynomial modulo rotation), there is needed an automatic procedure to calculate a lot of them.

A simple way to do it is to build e.g. matrix like $M_{ab}=\sum_{cd} p_{acd} p_{cdb}$ and then construct Tr$(M^k)$ invariants for $k=1...n$. This was for "-<>-" graph with two external edges. Analogously we could construct "-<=|=|...|=>-" ladder-like graphs, constructed by expanding it step by step, and in each step getting $n$ invariants from closing such graph.

The question is if such construction can be systematized to get a complete set of invariants? For degree $d$ there should be ${n+d-1 \choose d}-n(n-1)/2$ of them, plus $n(n-1)/2$ mixed invariants describing relative rotation to the lower degree terms.


Update: I decided to write separate paper about these invariants, especially from perspective of machine learning applications (they are much stronger than standard approaches): https://arxiv.org/pdf/1801.01058

$\endgroup$
  • 1
    $\begingroup$ I believe the classical result is that, at least over characteristic $0$, there are no unexpected invariants: For $A =k[X_{11}, \dots, X_{nn}]$, the ring $A^{O(n)}$ is generated by the polynomial $X_{ij} X_{ji}$. The same holds for $A^{SO(n)}$ except that you also pick up $\det X$. $\endgroup$ – anomaly Dec 22 '17 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.