Let $A$ be an $n\times n$ matrix. Say it satisfies $A^\intercal = P_1 A P_2$, where $P_1$ and $P_2$ are permutation matrices.
Question: Is there a permutation matrix $P$ such that $A^\intercal = P A P$?
By taking transpose, it is easy to see that $A^\intercal = P_1 A P_2 \iff A^\intercal = P_2 A P_1$.
As an example, say $P_1$ is the matrix associated with the cyclic permutation $1\rightarrow 2 \rightarrow \cdots \rightarrow n \rightarrow 1$ and $P_2=I$, then the above condition implies that $A$ commutes with $P_1$, which means $A$ is a circulant matrix, i.e., $A$ is of the form
$$
A=\begin{pmatrix}
a_1 & a_2 & a_3 & \cdots & a_n\\
a_n & a_1 & a_2 & \cdots & a_{n-1}\\
a_{n-1} & a_n & a_1 & \cdots & a_{n-2}\\
\vdots & \vdots & \vdots & \ddots & \vdots\\
a_2 & a_3 & a_4 & \cdots & a_1
\end{pmatrix}~.
$$
It is easy to see that reversing the columns of $A$ gives a symmetric matrix. In other words, $A^\intercal = P A P$, where $P$ is given by $P_{ij} = \delta_{i+j,n+1}$. More generally, whenever $P_1$ is the matrix associated with a cyclic permutation and $P_2=I$, there is a $P$ such that $A^\intercal = PAP$.
Any hints on how to proceed for the general problem are greatly appreciated.
Update: Defining $B = AP_2$, $Q = P_2^\intercal P_1$, and $R = P_2^\intercal P$, we can reformulate the above question as follows.
Question (v2): Given an $n\times n$ matrix $B$ such that $B^\intercal = Q B = BQ$ for some permutation matrix $Q$, is there a permutation matrix $R$ such that $B^\intercal = RBR$?
As explained in the example above, the answer is yes if $Q$ is the matrix associated with a cyclic permutation.
Best Answer
The matrix $$ A = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$ is a counterexample. Indeed, it satisfies $A^\intercal = P_1 A P_2$ for $P_2 = I$ and $$ P_1 = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}~, $$ but it can be verified by hand (or numerically as I did) that there is no permutation matrix $P$ such that $A^\intercal = P A P$.