If permutation matrices are conjugate in $\operatorname{GL}(n,\mathbb{F})$ are the corresponding permutations conjugate in the symmetric group?

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>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}$.

Note: I've edited this proof to replace the induction step with an appeal to the Möbius inversion formula.

Note: I've added a shorter proof in the case of characteristic zero.

This is true in any characteristic. $A$ and $B$ are similar if and only if they define isomorphic $F[X]$-module structures on $F^n$ via $Xv = Av$ and $Xv = Bv$, respectively.

If the cycles of $\alpha$ have lengths $n_1, \dots, n_s$, then the canonical $F[X]$-module structure is isomorphic to $M = \oplus_i F[X]/(X^{n_i} - 1)$.

I will assume first that the characteristic is $p > 0$. Write $n_i = r_i p^{k_i}$ with $r_i$ prime to $p$. Then $M = \oplus_i F[X]/(X^{r_i} - 1)^{p^{k_i}}$. We want to check that the numbers $r_i$ and $k_i$ are well-determined by $M$ up to permutation. Let $h_k(r)$ denote the number of times the factor $(X^r - 1)^{p^k}$ appears in the sum for $M$.

For any number $r$ prime to $p$, write $\phi_r$ for the $r$th cyclotomic polynomial. The polynomials $\phi_r$ are pairwise relatively prime, and $X^r - 1 = \prod_{d|r} \phi_d$. We have $M = \oplus_r M_r$ where $M_r$ is the submodule of $M$ annihilated by some power of $\phi_r$, and $M_r = \bigoplus_{i \text{ such that } r|r_i} F[X]/(\phi_r^{p^{k_i}})$. For a fixed $r$, the powers appearing in this decomposition are well determined by $M_r$ (and hence $M$), by the uniqueness part of the structure theorem for finitely generated modules over a PID.

If we let $f_k(r)$ be the number of times that $\phi_r^{p^k}$ appears in the decomposition of $M_r$, then $f_k(r)$ is well determined by $M$ and we have $f_k(r) = \sum_{q \text{ such that } r|q} h_k(q)$. To finish the proof, it will be enough to show that the function $f_k = f$ uniquely determines the function $h_k= h$.

If we let $N$ be a common multiple of all numbers $q$ for which $h(q) \ne 0$ (or equivalently, for which $f(q) \ne 0$), and we write $f'(t) = f(N/t)$ and $h'(t) = h(N/t)$, then we have $f'(u) = \sum_{t, \, t|u} h'(t)$. It follows from the Möbius inversion formula that $h'$ is determined by $f'$, hence $h$ by $f$.

If the characteristic is zero, argue the same way, but replacing all powers $p^{k_i}$ with $1$.

Note that the argument using the characteristic polynomial fails in positive characteristic $p$, since for example $X^2 - 1 = (X-1)^2$ when $p = 2$.

ALTERNATIVE PROOF IN CHARACTERISTIC ZERO:

Let $h(c)$ denote the number of cycles of length $c$ in a decomposition of $\alpha$. Note that $\operatorname{tr} A$ is the number of fixed points of the permutation $\alpha$. Thus if we let $f(n) = \operatorname{tr} A^n$, then $f(n)$ is also the number of fixed points of the permutation $\alpha^n$, namely $$f(n) = \sum_{c|n} ch(c).$$ It follows from the Möbius inversion formula that the function $h(c)$ is entirely determined by $f(n)$, hence by $A$.

This is true in characteristic $0$. If $A$ is a permutation matrix corresponding to the permutation $\sigma \in S_n$, then the characteristic polynomial of $A$ is $f(T) = \prod_{k=1}^\infty(1-T^k)^{a_k}$, where $a_k$ is the number of cycles of length $k$ in $\sigma$. (Remark that this is actually a finite product.) I claim that you can recover the cycle type of $\sigma$ from $f(T)$, i.e. that you can recover the sequence $\{a_k\}$. Remark that

$$\log f(T) = -\sum_{k=1}^\infty \sum_{m=1}^\infty\frac{T^{km}}{m}a_k = - \sum_{l=1}^\infty\frac{T^{l}}{l}b_l$$

where $b_l = \sum_{d \mid l} d a_d$. By induction (or by Möbius inversion), we can recover the sequence $\{a_k\}$ from the sequence $\{b_l\}$, and hence from $f(T)$. Therefore the cycle type of $\sigma$ is completely determined by its characteristic polynomial, and two elements of $S_n$ are conjugate iff they have the same cycle type.