2
$\begingroup$

Rotation (change of basis) is a natural matrix transformation (let's focus on real $\mathbb{R}^{n\times n}$ here): $$r_O(A)=O^TAO\qquad \textrm{for some orthogonal}\qquad O^TO=OO^T=1$$

There are well known 1-matrix operations which are rotation invariant - trace of powers and characteristic polynomial: $$\textrm{Tr}(A^k)=\textrm{Tr}(r_O(A)^k)\qquad \qquad \det(A-\lambda I)=\det(r_O(A)-\lambda I)$$ generating two families of symmetric polynomials of eigenvalues.

I have just realized that there is natural 2-matrix rotation invariant Frobenius inner product ("scalar product for matrices"): $$\langle A, B\rangle_F:=\textrm{Tr}(AB^T)=\sum_{ij} A_{ij} B_{ij}\qquad \textrm{inducing}\qquad \|A\|_F^2=\sum_{ij}A_{ij}^2=\textrm{Tr}(AA^T)$$ Frobenius norm. Its rotation-invariance is easy to check: $\langle r_O(A),r_O(B)\rangle_F=\langle A, B\rangle_F.$

What other rotation-invariant operations on matrices are known?

I am mostly interested in real symmetric matrices - my motivation is that graph isomorphism problem can be transformed into testing if $\mathcal{A}=\{a_1 A_1+\ldots+a_m A_m\}$ and $\mathcal{B}=\{b_1 B_1+\ldots+b_m B_m\}$ linear spaces of symmetric matrices differ only by rotation (stack) - the question is how to test it effectively?


Update 1: Analogously to Frobenius inner product, $\det(AB^T-\lambda I)$ is also rotation-invariant, hence the entire eigenspectrum of $AB^T$ is rotation-invariant. Analogously for larger number of matrices: $\det(ABC-\lambda I)=\det(r_O(A)r_O(B)r_O(C)-\lambda I)$. Are there also essentially different constructions?

Update 2: Regarding testing if two linear spaces ($\mathcal{A}$ and $\mathcal{B}$) of symmetric matrices differ only by rotation, I think I have a way. Using $\textrm{Tr}(A)$ is dangerous as it is often 0 (e.g. for testing graph isomorphism). $1=\textrm{Tr}(A^2)=\sum_{ij} a_i a_j \textrm{Tr}(A_i A_j)$ defines elipsoid in $\mathcal{A}$, which has to correspond to analogous ellipsoid in $\mathcal{B}$ - we can use it to rescale to sphere. Then $\textrm{Tr}(A^3)$ should allow to uniquely define $m-1$ points on such sphere: first as the one maximizing $\textrm{Tr}(A^3)$ (unique?), second as maximizing it in orthogonal direction, and so on - then it would be sufficient to test if these points agree for $\mathcal{A}$ and $\mathcal{B}$.

Update 2.1: Unfortunately $\sum_i x_i^3$ has exponential number of maxima on unit sphere, so maximizing $\textrm{Tr}(A^3)$ won't work. A different than $\textrm{Tr}(A^2)$ quadratic, also inexpensive to calculate, is $\det(A-\lambda I)[\lambda^{n-2}]=\pm \sum_{i<j} \lambda_i \lambda_j$, giving some hope here. Other are generalized characteristic polynomials.

Update 3: $\det(A-\lambda I)[\lambda^{n-2}]=\pm \sum_{i<j} \lambda_i \lambda_j$ has turned out identical as $\textrm{Tr}(A^2)$. However, $\textrm{Tr}(A^3)$ as homogeneous polynomial, can be effectively describe with rotation invariants.

$\endgroup$
  • 2
    $\begingroup$ Bhatia's Matrix Analysis has an interesting result on unitarily invariant norms: in particular, every such norm can be described as a function applied to the singular values of the matrix $\endgroup$ – Omnomnomnom Dec 15 '17 at 14:34
  • 1
    $\begingroup$ You may also look at math.stackexchange.com/questions/1782042/… $\endgroup$ – Widawensen Dec 15 '17 at 16:14
1
$\begingroup$

A systematic way to build rotational invariants of one or more matrices (or other tensors) would be given by scalar Penrose tensor diagrams built from the basic building blocks that are the given matrices, the metric tensor, the braiding, the unit matrix, and the Levi-Civita-Tensor, and built using the operations of horizontal composition, vertical composition, addition, multiplication by arbitrary scalar functions applied to simpler rotational invariants, and functional abstraction over scalar parameters.

All diagrams built this way will automatically describe something that transforms as a scalar under rotations, because they are built using only the input matrices and rotation invariant concepts.

I'm not entirely sure if that exhausts all possibilities (see here for a possibly relevant question), but it should give you a lot of different ones. Also it does not answer the question of which and how many different independent single invariants you need for a complete invariant. Given that you linked the problem to graph isomorphism, I suppose that won't be easy to find out.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.