What are the properties needed for a matrix $A$ to have $\mbox{Spec}(A)= \mbox{Spec}(A \cdot P)$, where
\begin{equation} P = \begin{pmatrix} 0 & \cdots & 0 & 1 \\ \vdots & \cdot^{\cdot^{\cdot}} & 1 & 0 \\ 0 & \cdot^{\cdot^{\cdot}} & \cdot^{\cdot^{\cdot}} & \vdots \\ 1 & 0 & \cdots & 0 \end{pmatrix} \end{equation}
is the matrix that, in the product $A \cdot P$, swaps all the columns of $A$?
$\mbox{Spec}(A)$ denotes the spectrum of $A$.
I've found a class of matrices (a subset of symmetric matrices of size $2^k\times 2^k$ with $k$ even) that satisfy this condition, but i was not able to figure out what are the key properties needed for $A$ to make this happen.
An example of matrix I've found is:
\begin{equation} A = \begin{pmatrix} 0 &0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &1 &1 &0\\ 0 &0 &0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &1 &0 &0 &1\\ 0 &0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &1 &0 &0 &1\\ 0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &0 &1 &1 &0\\ 0 &0 &0 &1 &0 &0 &0 &0 &0 &1 &1 &0 &0 &0 &0 &1\\ 0 &0 &1 &0 &0 &0 &0 &0 &1 &0 &0 &1 &0 &0 &1 &0\\ 0 &1 &0 &0 &0 &0 &0 &0 &1 &0 &0 &1 &0 &1 &0 &0\\ 1 &0 &0 &0 &0 &0 &0 &0 &0 &1 &1 &0 &1 &0 &0 &0\\ 0 &0 &0 &1 &0 &1 &1 &0 &0 &0 &0 &0 &0 &0 &0 &1\\ 0 &0 &1 &0 &1 &0 &0 &1 &0 &0 &0 &0 &0 &0 &1 &0\\ 0 &1 &0 &0 &1 &0 &0 &1 &0 &0 &0 &0 &0 &1 &0 &0\\ 1 &0 &0 &0 &0 &1 &1 &0 &0 &0 &0 &0 &1 &0 &0 &0\\ 0 &1 &1 &0 &0 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &0\\ 1 &0 &0 &1 &0 &0 &1 &0 &0 &0 &1 &0 &0 &0 &0 &0\\ 1 &0 &0 &1 &0 &1 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0\\ 0 &1 &1 &0 &1 &0 &0 &0 &1 &0 &0 &0 &0 &0 &0 &0\\ \end{pmatrix} \end{equation}
Considering the natural $n$-dimensional representation of the symmetric group $S_n$, namely $$ \sigma \in S_n\mapsto T_\sigma \in M_n(\mathbb C), $$ where $T_\sigma $ is the operator defined on the canonical basis by $T_\sigma (e_i)=e_{\sigma (i)}$, observe that the given matrix $P$ coincides with $T_\sigma $, where $\sigma $ is the permutation $$ \sigma =(n, n-1, \ldots , 2, 1). \tag{1} $$
In what follows we will restrict our discussion to values of $n$ for which $\sigma $ is an even permutation, noting that this happens if and only if $n$ is of the form $4k$ or $4k+1$.
In 1899 G. A. Miller [1] proved that, for $n\geq 5$, any element $\sigma $ of the alternating group $A_n$ is a commutator, that is, $$ \sigma =\tau ^{-1}\rho ^{-1}\tau \rho , \tag{2} $$ for some $\tau $ and $\rho $ in $A_n$.
We will therefore assume that $n\geq 5$ (in addition to the above assumption), so this includes the case $n=2^k$ with $k$ even of interest to the OP, at least for $k≥4$, and hence also the case of the big $16×16$ matrix mentioned in the statement of the question.
Employing Miller's Theorem, let $\tau $ and $\rho $ be as in (2) w.r.t. the permutation $\sigma $ described in (1), and put $$ A=T_\tau , \quad \text{and}\quad U=T_\rho . $$ From (2) we therefore deduce that $P=A^{-1}U^{-1}AU$, which implies that $$ U^{-1}AU =AP. \tag{3} $$ We then see that $A$ and $AP$ are similar matrices, so they have the same spectrum!
To get further examples, let $B$ be any matrix commuting with $U$, and observe that (3) implies that $$ BAP= BU^{-1}AU = U^{-1}BAU, $$ whence the same reasoning applies giving $$ \text{Spec}(BA)=\text{Spec}(BAP). $$
I haven't checked but I suspect that the $16\times 16$ example described in the question is of the above form. Moreover the OP claims to have found a whole class of matrices satisfying this condition so it would be interesting to check what is the relationship between their examples and the ones we give here!
[1] Miller, G. A., On the commutators of a given group., American M. S. Bull. (2) 6, 105-109 (1899). ZBL30.0136.03.