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?
Best Answer
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.