Matrix functions reducing eigenspectrum degeneracy?

118 Views Asked by At

Standard matrix functions fulfill $spec(f(A))=f(spec(A))$ relation for eigenspectrum, maintaining degeneracy if $f$ is injection. For simplicity we can focus on real symmetric matrices.

However, recently working on graph isomorphism problem (stack), I got construction of matrix functions which, surprisingly, sometimes are able to reduce degeneracy, like splitting eigenspace into two smaller ones, for example:

$$t(A)_{ab}:=\sum_{ij} A_{ai} A_{aj} A_{ij} A_{ib} A_{jb} $$

It comes from "$\triangleleft\hspace{-0.4mm}\triangleright$"- shape graph with $a, b$ on left and right, $i,j$ on top and bottom. It is very strange matrix function, degree 3 vertices of this graph make that eigendecomposition $A=\sum_k \lambda_k v_k v_k^T$ leads to kind of scalar products of three vectors: $(u,v,w)=\sum_i u_i v_i w_i$, I completely don't have experience with (?)

Examples of its reduction of eigenspectrum degeneracy come from adjacency matrices for strongly regular graphs (toughest cases for graph isomorphism problem, distinguished thanks to this function) - here are two 16x16 such $\{0,1\}$ coefficients symmetric matrices $A$ and $B$:

1111111000000000    1111111000000000
1111000111000000    1111000111000000
1111000000111000    1110100100110000
1111000000000111    1101010010001100
1000111100100100    1010101000101010
1000111010010010    1001011000010101
1000111001001001    1000111001000011
0100100111100100    0110000101010110
0100010111010010    0101000011101001
0100001111001001    0100001111000011
0010100100111100    0010100010111001
0010010010111010    0010010100110101
0010001001111001    0001100010101110
0001100100100111    0001010100011110
0001010010010111    0000101101001110
0001001001001111    0000011011110001

Eigenspectrum of both is the same: {7, 3, 3, 3, 3, 3, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1}

Eigenspectrum of $t(A)$ is {145, 57, 57, 57, 57, 57, 57, 1, 1, 1, 1, 1, 1, 1, 1, 1}

Eigenspectrum of $t(B)$ is {145, 49, 49, 49, 49, 49, 49, 9, 9, 9, 9, 9, 9, 1, 1, 1}

So the former has the same eigenspectrum degeneracy, but the later got 9=6+3 split of eigenspace in some strange symmetry breaking (I completely don't understand) PDF of Mathematica file for this calculation.

Is there a literature for matrix functions reducing eigenspectrum degeneracy?

For scalar product of three vectors?

Any intuitions what $A\to t(A)$ function is doing?