5

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?

Leox
  • 8,120

2 Answers2

2

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.

Ben Grossmann
  • 225,327
Sempliner
  • 2,414
  • Either your notation is confusing or your answer is wrong. $A$ will not generally fix all $n$ of the basis vectors. – Ben Grossmann Aug 21 '15 at 13:51
  • Yes, obviously. I'd forgotten n was already taken. – Sempliner Aug 21 '15 at 15:02
  • Please explane how do you get the term ${\rm Tr}(A)^2?$ It does not implies from yours explanation. – Leox Aug 21 '15 at 18:00
  • 1
    Yes it does: if you have n apples and you want to figure out how many pairs of n apples you can get selecting with replacement when order matters you get n^2. Our fixed points are the n apples. The trace counts the number of fixed points. To get the fixed points in sym we take these fixed vectors, add the fixed vectors of A^2, this will count each e_ie_i twice because it is a fixed vector of A and of A^2, and we will count the same vector e_ie_j twice because n^2 is only the correct number of apples if order matters. So we divide by 2 to get rid of these redundancies. Then subtract the number – Sempliner Aug 21 '15 at 18:52
  • of e_ie_i where e_i is fixed by A because these cannot occur. – Sempliner Aug 21 '15 at 18:52
2

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.

Ben Grossmann
  • 225,327
  • Thank you. Please explane the expression for $q.$ – Leox Aug 21 '15 at 14:51
  • It suffices to note that $\tr(A^2)$ is the number of fixed points when you apply the permutation twice in a row. Can you figure it out from there? – Ben Grossmann Aug 21 '15 at 14:52
  • Each fixed point of $A$ is also a fixed point of $A^2$. Moreover, there will be two fixed points of $A^2$ for every $2$-cycle (transposition) in $A$. – Ben Grossmann Aug 21 '15 at 15:05
  • Yes, I see now. So, if the permutation that correspondes to the operator $A$ has the cycle decompositon $$ 1^{\alpha_1} 2^{\alpha_2} \cdots m^{\alpha_m}, \alpha_1+2\alpha_2+\cdots+m \alpha_m=m,$$ then $$ {\rm Tr}(A^i)=\sum_{d|i} d \alpha_d.$$ Am I right? – Leox Aug 21 '15 at 17:56
  • That is some crazy notation you brought out. But yes, that's totally correct. – Ben Grossmann Aug 21 '15 at 18:06