I want to evaluate a trace which is complicated: $$ \mathrm{Tr}(SA_iSA_j) $$ The $n \times n$-matrices $S,A_i$ are all symmetric for all $0 \leq j \leq \log2(n)$. I used numerics and spotted a pattern in the data, from which I obtained a function $f(n,i,j)$ which I believe is correct.
Now I need to prove that I have found the right expression. What would prove $f(n,i,j) = \mathrm{Tr}(SA_iSA_j)$ apart from a brute force calculation?
EDIT: I added the definition of the matrices for completeness: Suppose $I_{2^j}$ denote the identity matrix of dimension $2^j \times 2^j$ and $\vec {1}_n$ a vector of ones with length $n$. Then $$A_j = 2^{-(2i+1)}\begin{bmatrix} 0&I_{2^j}&0&0& \cdots &0\\ I_{2^j}&0&I_{2^j}&0&&0\\ 0&I_{2^j}&0&I_{2^j}&&0\\ 0&0&I_{2^j}&\ddots\\ \vdots&&&&&I_{2^j}\\ 0&0&0&&I_{2^j}&0\\ \end{bmatrix} \qquad \qquad S = \frac{1}{n}(nI_n - \vec{1}_n\vec{1}_n^T)$$ Also the expression which we want to prove is correct is $$f(n,i,j) = \frac{n^2}{2} \frac{n - 2^{\max{i,j}}}{2^{3 \max{i,j}}} + \left(\frac{n}{2^{\max{i,j}}} - 1\right) \left(\frac{n}{2^{\min{i,j}}} - 1\right) - 2 n\frac{n - 2^{\max{i,j}} - 2^{(\min{i,j)}-1}}{2^{j + i}}$$