How can I check whether there exists a common basis with respect to which two matrices 𝐴 and 𝐵 are permutation matrices?
More explicitly, let $A$ and $B$ be two unitary matrices whose eigenvalues form complete sets of roots of unity (meaning there is a unitary transformation to a permutation matrix for each). How can I check whether their exists a single unitary $U$ such that $$ P_A = U A U^\dagger, \quad P_B = U B U^\dagger, $$ such that $P_A$ and $P_B$ are permutation matrices?
Here's a possible method:
We might as well assume that $A$ is already a permutation matrix -- just conjugate $A$ and $B$ by the same unitary matrix $C$ and relabel.
Now if we are looking to conjugate $B$ to a permutation matrix AND retain $A$ as a permutation matrix, then we'll need to conjugate by something that centralizes $A$ -- so our conjugating matrix, call it $X$, must lie in $C_G(A)$, where $G=U(n)$.
(Note: you might wonder about the possibility that $A$ could be conjugated to a different permutation matrix instead, therefore allowing a larger choice for $X$; however this question assures us that if we were to do this, we could then conjugate by a permutation matrix to return $A$ to its original form, without affecting whether or not $B$ is a permutation matrix.)
$C_G(A)$ is easy enough to calculate -- especially if $A$ is made up of cycles of different lengths. Now let $\mathcal{B}$ be the natural basis. We use the reformulation of @YCor to consider what happens when we apply $X$ to $\mathcal{B}$. So, for instance, if $$A=\begin{pmatrix} & 1 & \\ & & 1 \\ 1 & & \end{pmatrix}$$ then the elements of $C_G(A)$ are unitary matrices of the form $$ X=\begin{pmatrix} a & b & c \\ c & a & b \\ b & c & a \end{pmatrix}.$$ If we apply the matrix $X$ to the natural basis, then we obtain a basis of the form $$\left\{\begin{pmatrix}a \\ c \\ b \end{pmatrix}, \begin{pmatrix} b \\ a \\ c\end{pmatrix}, \begin{pmatrix} c \\ b \\ a \end{pmatrix}\right\}$$ where $a,b,c$ are restricted to ensure the basis is orthonormal.
These are all of the orthonormal bases for which $A$ is the permutation matrix written above. Now $B$ will be a permutation matrix with respect to one of these bases, say $\mathcal{B}_1$, if and only if, for all $v\in \mathcal{B}_1$, $Bv\in\mathcal{B}_1$. One simply has to test whether any of the listed bases have this property.
Remarks:
So, algorithmically, it might be most efficient to use the observations in the comments about products of $A$ and $B$: take a few products of $A$ and $B$ of some bounded length -- if any of these can't be conjugated to permutation matrices, then, obviously, you stop. If they ALL can be conjugated to a permutation matrix, then choose whichever product resulted in a permutation matrix with fewest repeated cycles.
Added later: In fact, we can make that final step (where we study the action of the matrix $B$ on a bunch of bases) much more efficient if we check the isomorphism type of the group $\langle A, B\rangle$; this must be isomorphic to a subgroup of $S_n$, in which $A$ must correspond to the given permutation matrix (so, for instance, if $A$ was the matrix in the example above, then its image in $S_n$ would be the 3-cycle $(1,2,3)$). This allows us to explicitly list the possible permutations corresponding to $B$. For each of these possibilities, one has an explicit action on the basis $\mathcal{B}_1$.
So, for instance, in the example above, if $B$ were to correspond to the element $(1,2)$, then its action on the basis $\mathcal{B}_1$ would need to swap the first two basis elements. Checking this specific property is much more straightforward than checking if $B$ preserves any of the possible bases obtained using the centralizer of $A$.
One partial answer, for which you don't need the knowledge that the spectra are complete sets of roots of unity.
First step : verify that the group $G$ generated by $A$ and $B$ is finite (it should be contained a permutation group of $n$ elements). For this, explore the free group in two letters $a$ and $b$ (together with $a^{-1}$ and $b^{-1}$). Consider the disk $D_k$ of words $w$ of length $\le k$, and let $N_k$ be the number of distinct elements $w(A,B)$ for $w\in D_k$. If $N_k$ comes to exceed $n!$, the basis does not exist. If not, you have reached a $k$ so that $N_{k+1}=N_k$ ; the group is finite and you still have a chance, provided this $N=N_k$ is $\le n!$.
Next step : In the latter case, you must verify that the trace of $w(A,B)$ is a non-negative integer, for every $w\in D_k$.
I suspect that the converse is true, and that it is a result about linear representations of finite groups. Does anyone have a clue ?
