Find trace of linear operator Let $A$ be a linear operator which acts on the vector space $V=\langle x_1,x_2, \ldots,x_n\rangle$  by permutation of the basis vectors. Suppose we know its eigenvalues ( some roots of unity  ): $\lambda_1, \lambda_2, \ldots, \lambda_n.$
Now consider the vector space $V^{(2)} \subset {\rm Sym}^2 V$ generated by elements $x_i x_j, i<j,$ $\dim V^{(2)}=\binom{n}{2}.$ Let us expand the operator $A$ on $V^{(2)}$    by linearity and by $A(x_i x_j)=A(x_i)A(x_j)$. Denote the extension by $A^{(2)}$. It is clear that  $A^{(2)}$ permutes the basis vectors of   $V^{(2)}$ so $A^{(2)}$   is an endomorphism of $V^{(2)}$.
Question. What is the trace  of the $A^{(2)}?$ 
By  method of trial and error I have found a formula for the trace
$$
{\rm Tr}(A^{(2)})=\sum_{i=1}^n\lambda_i^2+\sum_{i<j}\lambda_i \lambda_j-\sum_{i=1}^n \lambda_i
$$
but I can't prove it. Any ideas?
 A: If $A$ acts on this basis than the trace is simply going to be the size $N$ of the set of basis vectors that it fixes (i.e. the number of $i$ such that $A(x_i) = x_i$) and as such we have that $Tr(A) = \sum_{i = 1}^n \lambda_i = N$. Then the number of basis vectors fixed by $A^{(2)}$ is simply $\frac{\text{Tr}(A^2) + \text{Tr}(A)^2}{2} - N$ which is precisely your formula. This is because $A^{(2)}$ fixes a vector when $A$ transposes two vectors, which corresponds to a fixed vector of $A^2$, or when $A$ fixes two vectors.
A: Note that the trace of any permutation is its number of fixed points (that is, the number of $1$-cycles).  As in my previous answer, let $x_{ij}$ denote $x_ix_j = x_{ji}$.
In order to have $A^{(2)}(x_{ij}) = x_{ij}$, we must have
$$
(Ax_i)(Ax_j) = x_{ij}
\DeclareMathOperator{\tr}{Tr}
$$
There are precisely two ways in which this can occur:


*

*$x_i$ and $x_j$ are fixed points of $A$, which is to say that $Ax_i = x_i$ and $Ax_j = x_j$.

*$A$ transposes $x_i$ and $x_j$, which is to say that $A x_i = x_j$ and $Ax_j = x_i$.


So: if $A$ has $p$ fixed points, then $\binom p2$ fixed points of $A^{(2)}$ will result.  If $A$ has $q$ transpositions, then $q$ fixed points of $A^{(2)}$ will result.  That is, $\tr(A^{(2)}) = \binom p2 + q$.
However, we note that $p = \tr(A)$, and $q = \frac12(\tr(A^2) - \tr(A))$.  So, we now have
$$
\tr(A^{(2)}) = \frac{\tr(A)(\tr(A) - 1)}{2} + \frac 12[\tr(A^2) - \tr(A)] =\\
\frac 12\tr(A^2) + \frac12 {\tr(A)^2} - \tr(A)
$$
In terms of the eigenvalues of $A$, this gives us
$$
\tr(A^{(2)}) = 
\frac 12 \sum_{i=1}^n \lambda_i^2 + \frac 12 \left(\sum_{i=1}^n \lambda_i\right)^2
- \sum_{i=1}^n \lambda_i =\\
\sum_{i=1}^n\lambda_i^2+\sum_{i<j}\lambda_i \lambda_j-\sum_{i=1}^n \lambda_i
$$
precisely as desired.
