Let $S$ be a finite set of real numbers, and let $T$ be the set of all $n\times n$ matrices having entries in $S$.

Question

Let $S$ be a finite set of real numbers, and let $T$ be the set of all $n\times n$ matrices having entries in $S$. Prove that $$\sum\limits_{A\in T}\mbox{trace}(A^2)=\sum\limits_{A\in T}(\mbox{trace}(A))^2$$

Here I tried to proceed with the eigenvalue but since $A$ is real matrix eigenvalues many not be real. In that case, how we can prove the result

Answer 1

Unfortunately, even though eigenvalue analysis is usually the correct approach when dealing with questions like this, it is not the right approach here.

Instead, I think the best approach is to just expand the definition of trace. Following Grossman's suggestion, we have $$\sum_{A} \text{trace}(A^2) = \sum_A \sum_{i = 1}^n (A^2)_{ii} = \sum_A \sum_{i = 1}^n \sum_{j = 1}^n A_{ij}A_{ji} = \sum_{i = 1}^n \sum_{j = 1}^n \sum_A A_{ij}A_{ji}.$$ The inner sum is now decoupled, which means for each specific $(i,j)$, it only involves a few entries of $A$. This makes it very easy to analyze. Specifically, when $i \neq j$, $A_{ij}$ and $A_{ji}$ are "independently" selected from $S$, so $$\sum_A A_{ij}A_{ji} = |S|^{n^2 - 2} \cdot s(S)^2$$ where $s(S)$ is the sum of elements in $S$. Similarly, when $i = j$, we have $$\sum_A A_{ij}A_{ji} = |S|^{n^2 - 1} s(S^2)$$ where $s(S^2)$ is the sum of squares of elements in $S$. Thus $$\sum_{i = 1}^n \sum_{j = 1}^n \sum_A A_{ij}A_{ji} = n(n - 1) \cdot |S|^{n^2 - 2} \cdot s(S)^2 + n \cdot |S|^{n^2 - 1} s(S^2).$$ One can compute the right hand side in the same way. $$\sum_{A} \text{trace}(A) = \sum_{i = 1}^n \sum_{j = 1}^n \sum_A A_{ii}A_{jj},$$ and you can check that it is also equal to $n(n - 1) \cdot |S|^{n^2 - 2} \cdot s(S)^2 + n \cdot |S|^{n^2 - 1} s(S^2)$, using the same method.

Answer 2

\begin{align} \sum\limits_{A\in T}\mbox{trace}(A^2)&=\sum\limits_{A\in T}\sum_{i=1}^n[A^2]_{ii}=\sum\limits_{A\in T}\sum_{i=1}^n\sum_{j=1}^nA_{ij}A_{ji}\\ &=\sum_{i=1}^n\sum_{j=1}^n\left[\sum\limits_{A\in T}A_{ji}A_{ij}\right]= \sum_{i=1}^n\sum_{j=1}^n\left[\sum_{a\in S,b\in S}\sum_{\substack{A\in T\\A_{ij}=a, A_{ji}=b}}ab\right]\\ &=\sum_{i=1}^n\sum_{j=1}^n\left[\sum_{a\in S,b\in S}|\{A\in T: A_{ij}=a, A_{ji}=b\}|ab\right]\\ &=\sum_{i=1}^n\sum_{j=1}^n\left[\sum_{a\in S,b\in S}|\{A\in T: A_{ii}=a, A_{jj}=b\}|ab\right]\\ &=\sum_{i=1}^n\sum_{j=1}^n\left[\sum_{a\in S,b\in S}\sum_{\substack{A\in T\\A_{ii}=a, A_{jj}=b}}ab\right] =\sum_{i=1}^n\sum_{j=1}^n\left[\sum\limits_{A\in T}A_{ii}A_{jj}\right]\\ &=\sum\limits_{A\in T}\left[\sum_{i=1}^nA_{ii}\right]\left[\sum_{j=1}^nA_{jj}\right]=\sum\limits_{A\in T}\left[\sum_{i=1}^nA_{ii}\right]^2=\sum\limits_{A\in T}(\mbox{trace}(A))^2. \end{align}