When can an eigenvector be chosen uniquely which is invariant to permutation?

Question

Suppose $A\in\Re^{n\times n}_{sym}$ is a symmetric matrix with eigenvalues $\lambda_1,\dotsc,\lambda_n$ in decreasing order. What I seek is a way to choose an eigenvector that is invariant to permutations of $A$. Essentially, let $\phi:\Re^{n\times n}\mapsto\Re^{n}$ be a function that returns an eigenvector corresponding to the $i$th largest eigenvalue of the matrix. Let $P$ be a permutation matrix. Then I want $\phi$ to have the property that $\phi(PAP^T)=P\phi(A)$ for some large class of $A\in \Re^{n\times n}_{sym}$ and all permutation matrices $P$.

For example, if $\lambda_i$ has multiplicity one then there are only two choices for the eigenvectors with norm 1. If we further impose that the sum of the components of the eigenvector is non-zero then we can have $\phi$ choose the unit norm eigenvector which has positive sum and this will be invariant to permutations.

This example can be extended to allow for eigenvectors who sum to zero by considering a sequence of functions $f_1,f_2,\dotsc$ from $\Re^{n}$ to $\Re$ that are symmetric in the components of the input and such that for all $i\in \mathbb{N}$ and $x\in\Re^{n}$, we have $f_i(-x)=-f_i(x)$. Now, as long as there is one function $f_i$ which is non-zero for a unit norm eigenvector, we can choose the eigenvector so that the first non-zero function is positive. (Note: for some other reasons I would like the $f_i$ to be smooth or Lipschitz for example though for now I'm happy to have anything that works :) .)

This allows for large classes of matrices to have a unique permutation invariant eigenvector choice. As a counter example, suppose that $A$ has an $i$th eigenvector of $[1,\dotsc,1, -1,\dotsc,-1]^T$ where there are $n/2$ ones and $n/2$ negatives ones. Then any function which is symmetric and odd (as above) will return 0 for this vector so a unique choice is not possible by the above method.

What is the largest such class of matrices for which the $i$th eigenvector can be chosen in this way? What is the corresponding procedure? Is there any procedure that works when the eigenvalue has multiplicity greater than one?

Answer 1

You can always do it if there is any eigenvector not summing to 0, and some other times too. First define $Aut(A)$ to be the group of permutation matrices $R$ such that $RAR^T=A$. If $A\boldsymbol{x}=\lambda\boldsymbol{x}$, then $AR\boldsymbol{x}=RAR^TR\boldsymbol{x}=\lambda R\boldsymbol{x}$ so $R\boldsymbol{x}$ is also an eigenvector. Extending this idea, the sum $$ \boldsymbol{y} = \sum_{R\in Aut(A)} R\boldsymbol{x}$$ is also an eigenvector (unless it is $\boldsymbol{0}$, which is the only time this proof fails). Furthermore, $R\boldsymbol{y}=\boldsymbol{y}$ for all $R\in Aut(A)$.

Now define, for all permutation matrices $P$, $\phi(PAP^T) = P\boldsymbol{y}$. It satisfies your condition provided it is well-defined, i.e. if $\phi(PAP^T)=\phi(QAQ^T)$ for any two permutation matrices $P,Q$ such that $PAP^T=QAQ^T$. But $PAP^T=QAQ^T$ is the same as $Q^TP\in Aut(A)$, which implies $P\boldsymbol{y}=Q\boldsymbol{y}$, so we are done.

If $Aut(A)$ acts transitively, only a constant eigenvector can satisfy your requirement, so at most one eigenvalue will work. This happens.

Answer 2

The obvious choice for functions is the odd elementary symmetric polynomials. If these are all $0$ on a vector, that vector has the minus=permutation property. (Because the polynomial whose roots are the coefficients is a polynomial in $x^2$)

This will get you all matrices with different eigenvalues, satisfying the minus=permutation property.

However note that, though polynomials are smooth, this will of course be very sensitive to minor changes.

If you have multiplicity, then the unit-norm vectors form a circle and a sphere. Throw out all the pairs of vectors that are the same up to permutation. If you have anything left, no two vectors will have the same elementary symmetric polynomials. So just maximize with respect to some lexicographic order on the elementary symmetric polynomials.

I do not believe there is any way to characterize the situation where this works.

In full generality, you can choose if no permutation of the matrix is actually the exact same matrix. Edit: And, as Brendan McKay points out, some other times too.