4
$\begingroup$

Consider this problem:

Let $\pi$ be a permutation of integers $\{1,2,...,n\}$. If $x = (x_1, x_2, ...,x_n)$ is a vector in $\mathbb{C}^n$, write $Ax = (x_{\pi(1)},x_{\pi(2)},...,x_{\pi(n)})$. Find the spectrum of A.


My thoughts:

1) Since $A$ is a permutation of $x$, one of these permutations must be the identity permutation, for which the eigenvalue should be $1$.

2) The only other eigenvalue should be $0$?? Since there shouldn't exist another $\lambda$ for which $Ax = \lambda x$ since the direction of $x$ isn't preserve in all other permutations?

Are my thoughts correct? What is the spectrum of $A$? And what would $A$ look like?

$\endgroup$
6
$\begingroup$

$0$ is never an eigenvalue because the matrix is invertible (because by switching columns and rows you eventually get the identity matrix, so that the dterminant of the matrix is $\pm 1$).

The permutation $\pi$ can be written as a product of disjoint cycles, $\pi=\gamma_1\gamma_2\ldots \gamma_r$, where each $\gamma_k$ is a cycle. Denote by $\Gamma_k$ the support of $\gamma_k$ and $g_k=|\Gamma_k|$. Let $\Delta=\lbrace 1,2,\ldots, n \rbrace \setminus \bigcup_k \Gamma_k$, and consider the subspaces $E_k={\mathsf{span}}(e_i|i\in \Gamma_k)$, $F={\mathsf{span}}(e_i|i\in \Delta)$. Then all those subspaces are invariant by $A$, and the total space is the direct sum of them.

On $F$, $A$ acts as the identity (with eigenvalue $1$). On $E_k$, $A$ acts a linear operator with characteristic polynomial $X^{g_k}-1$, its eigenvalues are the $g_k$-th roots of unity.

$\endgroup$
  • $\begingroup$ I guess you meant to write $\Gamma_k$ instead of $S_k$ and $F$ instead of $\Delta$? $\endgroup$ – levap Nov 5 '17 at 9:19
  • $\begingroup$ @levap Corrected, thanks. $\endgroup$ – Ewan Delanoy Nov 5 '17 at 9:36
  • $\begingroup$ I'm sorry my understanding of permutation is limited, but what is $\Gamma_k$ the "support"? $\endgroup$ – B.Li Nov 5 '17 at 22:08
  • 1
    $\begingroup$ @B.Li The support of $\gamma$ is the set of all values not fixed by $\gamma$ : $\lbrace i | \gamma(i)\neq i\rbrace$ $\endgroup$ – Ewan Delanoy Nov 5 '17 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.