If permutation matrices are conjugate in $\operatorname{GL}(n,\mathbb{F})$ are the corresponding permutations conjugate in the symmetric group? There is a standard embedding of the symmetric group $S_n$ into $\operatorname{GL}(n,\mathbb{F})$ (for any field $\mathbb{F}$) that sends each permutation in $S_n$ to the corresponding permutation matrix.  As this is a group homomorphism, certainly, conjugate permutations map to conjugate matrices.  What about the converse?  Suppose that $A$ and $B$ are similar permutation matrices in $\operatorname{GL}(n,\mathbb{F})$ coming from permutations $\alpha$ and $\beta$ in $S_n$.  Does it follow that $\alpha$ and $\beta$ are already conjugate in $S_n$?  (I thought that I had a proof, but I noticed that the argument seems to fail in positive characteristic.)
I think the following argument works independently of the field. The dimension of the fixed point subspaces of $A$ and $B$ are equal to the total number of cycles (including cycles of length $1$) of $\alpha$ and $\beta$ so, if $A$ and $B$ are similar matrices, then $\alpha$ and $\beta$ must have the same total numbers of cycles.

The same applies to $\alpha^p$ and $\beta^p$ for any prime $p$, and the number of their cycles are equal to $a_1+a_2p$ and $b_1 + b_2p$, where $a_1$ and $a_2$ are the numbers of cycles of $\alpha$ of length not divisible by $p$ and divisible by $p$ respectively, and similarly for $b_1,b_2$ with $\beta$. So $a_1+a_2p=b_1+b_2p$, and since we already know that $a_1+a_2=b_1+b_2$, we get $a_1=b_1$, $a_2=b_2$. In other words, for any prime $p$, $\alpha$ and $\beta$ have the same numbers of cycles of lengths divisible by $p$.

Now, by an inductive argument on the number of prime factors of $k$, we can show that for any integer $k&gt;0$, $\alpha$ and $\beta$ have the same numbers of cycles of lengths divisible by $k$, and that implies that $\alpha$ and $\beta$ have the same cycle types, so are conjugate in $S_n$.

For example for $k=12$ let $a_i$ be the number of cycles of $\alpha$ of length $j$, where $\gcd(j,12)=i$, for $i=1,2,3,4,6,12$. By induction, we know $a_1+a_2+a_3+a_4+a_6+a_{12}$, $a_2+a_4+a_6+a_{12}$, $a_3+a_6+a_{12}$, $a_4+a_{12}$ and $a_6+a_{12}$. The total number of cycles of $\alpha^{12}$ is $a_1+2a_2+3a_3+4a_4+6a_6+12a_{12}$ so that number, together with the already known sums, is enough to determine $a_{12}$ and hence to prove that $a_{12}=b_{12}$.
Yes, they both permute the standard basis and have the same cycle structure. 

It's easier to see if you view them as linear transformations: Each cycle corresponds to a stable subspace of the total space and the cycle decomposition corresponds to the stable decomposition.