Given an invertible matrix $A$, when is it possible to find a matrix $S$ such that $$A = SPS^{-1},$$ where $P$ is a permutation matrix? When this is possible, is there a practical method (say, similar to diagonalization) of finding $S$?
A relaxation of the above would be to find a $T$ such that $$A = TPDT^{-1},$$ where $D$ is diagonal. This is of course always possible when $A$ is diagonalizable (with $P$ equal to the identity matrix), but it seems highly likely that the above would work for a broader class of matrices, or offer several possible solutions.
Lastly, for a set of matrices $A,B,\ldots$ that can not necessarily be simultaneously diagonalized, would it be possible to find a single $T$ that transforms them all like $$A = TP_AD_AT^{-1},\quad B = TP_BD_BT^{-1},\ldots$$ for some set of permutation matrices $P_A,P_B,\ldots$ and diagonal matrices $D_A,D_B,\ldots$?
I have not been able to find any relevant source, or make any progress other than the trivial fact that $$\mathrm{tr}(A) = \mathrm{tr}(P_AD_A), \quad\mathrm{tr}(B) = \mathrm{tr}(P_BD_B),\ldots$$ Any advice would be highly appreciated!
$A\in M_ n(\mathbb{C})$ is similar to a permutation iff
$A$ is diagonalizable over $\mathbb{C}$ and there are positive integers $p_1,\cdots,p_k$ st $p_1+\cdots+ p_k=n$ and its characteristic polynomial is in the form $(x^{p_1}-1)\cdots (x^{p_k}-1)$.
Now if $A$ has the above property, then it is similar to $diag(A_1,\cdots,A_k)$ where $A_i$ is the matrix associated to the cycle $(1,\cdots,p_i)$.