Skip to main content
MathOverflow

Return to Answer

simplified
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Here's a direct proof, arguing by induction on $n$, and then on the common order $k\ge 1$ of the that if permutation matrices $A,B$, that if $A,B$(of size $n\ge 0$) have the same characteristic polynomial (or equivalently are linearly equivalent, since these are diagonalizable) then they are conjugate as permutations, i. For $k=1$ we have $A=B=I_n$e. Assume $k\ge 2$, have the same cycle decomposition.

If $A,B$ have some cycle of common size, then we can "remove" it (which divides the characteristic polynomial by the same factor while reducing the matrix size). So we can suppose there are no cycles of common size. Let $p$ be a prime divisor of $k$. Thenlength in $A^p$$A$ and $B^p$ are linearly conjugate$B$. In this case, and hence by inductionwe have the same cycle decomposition. Each cycle of order $pq$ (for some $q\ge 1$) for $A^p$ orto prove that $B^p$ comes from$n=0$.

Consider a cycle of ordermaximal length $p^2q$$m$ occurring in botheither $A$ andor $B$. Hence there is none. Thus, $k$ is a square-free number, say $k=p_1\dots p_\ell$ (we suppose by contradiction $k\ge 2$, that is,in $\ell\ge 1$)$A$. The existence of a $k$-cycle means that the root of unityThen $\exp(2i\pi/k)$$\xi=\exp(2i\pi/m)$ is a root of the characteristic polynomial which is a property shared byof $A$, and $B$; hence $A$ and $B$ have no $k$-cycle. Consider a cycle of maximal length $r$ occurring in $A$ or $B$, say in $A$; we can suppose that $p$ does not divide $r$. ThenBut since $A^p$$B$ has the same cycleonly cycles of length $r$. But it is permutation conjugate to $B^r$, which has no such large cycle$<m$, sinceits characteristic polynomial does not vanish at $B$ has none. We$\xi$, and we get a contradiction.

Here's a direct proof, arguing by induction on $n$, and then on the common order $k\ge 1$ of the permutation matrices $A,B$, that if $A,B$ have the same characteristic polynomial (or equivalently are linearly equivalent, since these are diagonalizable). For $k=1$ we have $A=B=I_n$. Assume $k\ge 2$.

If $A,B$ have some cycle of common size, then we can "remove" it (which divides the characteristic polynomial by the same factor). So we can suppose there are no cycles of common size. Let $p$ be a prime divisor of $k$. Then $A^p$ and $B^p$ are linearly conjugate, and hence by induction have the same cycle decomposition. Each cycle of order $pq$ (for some $q\ge 1$) for $A^p$ or $B^p$ comes from a cycle of order $p^2q$ in both $A$ and $B$. Hence there is none. Thus, $k$ is a square-free number, say $k=p_1\dots p_\ell$ (we suppose by contradiction $k\ge 2$, that is, $\ell\ge 1$). The existence of a $k$-cycle means that the root of unity $\exp(2i\pi/k)$ is a root of the characteristic polynomial which is a property shared by $A$ and $B$; hence $A$ and $B$ have no $k$-cycle. Consider a cycle of maximal length $r$ occurring in $A$ or $B$, say in $A$; we can suppose that $p$ does not divide $r$. Then $A^p$ has the same cycle of length $r$. But it is permutation conjugate to $B^r$, which has no such large cycle, since $B$ has none. We get a contradiction.

Here's a direct proof that if permutation matrices $A,B$ (of size $n\ge 0$) have the same characteristic polynomial (or equivalently are linearly equivalent, since these are diagonalizable) then they are conjugate as permutations, i.e., have the same cycle decomposition.

If $A,B$ have some cycle of common size, then we can "remove" it (which divides the characteristic polynomial by the same factor while reducing the matrix size). So we can suppose there are no cycles of common length in $A$ and $B$. In this case, we have to prove that $n=0$.

Consider a cycle of maximal length $m$ occurring in either $A$ or $B$, say in $A$. Then $\xi=\exp(2i\pi/m)$ is a root of the characteristic polynomial of $A$, and hence of $B$. But since $B$ has only cycles of length $<m$, its characteristic polynomial does not vanish at $\xi$, and we get a contradiction.

Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Here's a direct proof, arguing by induction on $n$, and then on the common order $k\ge 1$ of the permutation matrices $A,B$, that if $A,B$ have the same characteristic polynomial (or equivalently are linearly equivalent, since these are diagonalizable). For $k=1$ we have $A=B=I_n$. Assume $k\ge 2$.

If $A,B$ have some cycle of common size, then we can "remove" it (which divides the characteristic polynomial by the same factor). So we can suppose there are no cycles of common size. Let $p$ be a prime divisor of $k$. Then $A^p$ and $B^p$ are linearly conjugate, and hence by induction have the same cycle decomposition. Each cycle of order $pq$ (for some $q\ge 1$) for $A^p$ or $B^p$ comes from a cycle of order $p^2q$ in both $A$ and $B$. Hence there is none. Thus, $k$ is a square-free number, say $k=p_1\dots p_\ell$ (we suppose by contradiction $k\ge 2$, that is, $\ell\ge 1$). The existence of a $k$-cycle means that the root of unity $\exp(2i\pi/k)$ is a root of the characteristic polynomial which is a property shared by $A$ and $B$; hence $A$ and $B$ have no $k$-cycle. Consider a cycle of maximal length $r$ occurring in $A$ or $B$, say in $A$; we can suppose that $p$ does not divide $r$. Then $A^p$ has the same cycle of length $r$. But it is permutation conjugate to $B^r$, which has no such large cycle, since $B$ has none. We get a contradiction.