Trace of hadamard product of adjacency matrices based on eigenvalues

Question

Let $A$ be the adjacency matrix of the simple graph $G_n$. Is there any formula for $\text{trace}(A^3 \circ A^2)$ based on eigenvalues of $A$?

Answer 1

There is no such formula, because the trace in question is not invariant among cospectral graphs.

It is easy to generate a random pair of adjacency matrices $A,B$ of two cospectral simple graphs such that $\operatorname{trace}(A^3\circ A^2)\ne\operatorname{trace}(B^3\circ B^2)$. The matrices I obtained, however, are too big to be written down. The smallest ones I found were $39\times39$. Yet you may try the following Matlab code. The details of part of the algorithm are justified in Godsil and McKay, Constructing cospectral graphs, Aequationes Mathematicae 25:257-268, 1982 (downloadable from here at the time of writing).

%F is the adjacency matrix of the Frucht graph
n=12;
F=[...
      0 1 0 0 0 0 1 0 0 0 1 0;...
      1 0 1 0 0 0 0 1 0 0 0 0;...
      0 1 0 1 0 0 0 0 1 0 0 0;...
      0 0 1 0 1 0 0 0 1 0 0 0;...
      0 0 0 1 0 1 0 0 0 1 0 0;...
      0 0 0 0 1 0 1 0 0 1 0 0;...
      1 0 0 0 0 1 0 0 0 0 1 0;...
      0 1 0 0 0 0 0 0 0 0 1 1;...
      0 0 1 1 0 0 0 0 0 0 0 1;...
      0 0 0 0 1 1 0 0 0 0 0 1;...
      1 0 0 0 0 0 1 1 0 0 0 0;...
      0 0 0 0 0 0 0 1 1 1 0 0];

x=[ones(n/2,1); zeros(n/2,1)];
y=[zeros(n/2,1); ones(n/2,1)];

%H and K are cospectral; see sec. 2.3 of Godsil and McKay
H=[F x;x' 0];
K=[F y;y' 0];
I=eye(n+1);

m=3;
for k=1:10000
   P=triu(floor(2*rand(m,m)),1); P=P+P';  % make P symmetric
   Q=triu(floor(2*rand(m,m)),1); Q=Q+Q';  % make Q symmetric

   %A and B are cospectral; see sec. 3.6 of Godsil and McKay
   A=kron(P,I)+kron(Q,H);
   B=kron(P,I)+kron(Q,K);

   t1=trace((A^2).*(A^3)); t2=trace((B^2).*(B^3));
   if t1~=t2
      A, B
      u=sort(eig(A)); v=sort(eig(B));
      [u, v, u-v]  % u-v should be the zero vector
      [t1 t2]
      break;
   end
end