Denote the set of $n\times n$ [permutation matrices](http://mathworld.wolfram.com/PermutationMatrix.html) by $\mathfrak{S}\_n$. The ordinary transpose preserves this group.


Given $P\in\mathfrak{S}\_n$, construct the $n\times n$ matrix ${}^tP$ according to the rules:


(1) leave the 4 rims unchanged (1st row, 1st column, last row, last column);


(2) [transpose](https://en.wikipedia.org/wiki/Transpose) its $(n-2)\times(n-2)$-submatrix found by removing the 4 rims.


**Example.** 
$$A=\begin{pmatrix} 1&0&0&0\\0&0&0&1\\0&1&0&0\\0&0&1&0
\end{pmatrix} \rightarrow
{}^tA=\begin{pmatrix} 1&0&0&0\\0&0&1&1\\0&0&0&0\\0&0&1&0
\end{pmatrix}.$$
**Example.** 
$$B=\begin{pmatrix} 1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0
\end{pmatrix} \rightarrow
{}^tB=\begin{pmatrix} 1&0&0&0\\0&0&0&1\\0&0&1&0\\0&1&0&0
\end{pmatrix}.$$ 
Notice that ${}^tB$ is a permutation while ${}^tA$ is not!



> 
> **Question.** What is $a\_n:=\#\{^{t}P\in\mathfrak{S}\_n:\,\,P\in\mathfrak{S}\_n\}$, for $\geq3$? Easy: $a\_3=6$.
> 
> 
> 


**Remark.** This was a modest case (see answer below). We could easily generalize the problem in many ways.



> 
> **Question 2.** Split $P=\begin{pmatrix}A&B\\C&D\end{pmatrix}\in\mathfrak{S}\_{2n}$ into four $n\times n$ matrices, and define the operation ${}^{tt}P=\begin{pmatrix}{}^tA&{}^tB\\ {}^tC&{}^tD\end{pmatrix}.$ How many [involutions](http://mathworld.wolfram.com/PermutationInvolution.html) are there in $\mathfrak{S}\_{2n}$ such that $^{tt}P$ is a permutation?
> 
> 
> 



transposing "unrimmed" permutations
The answer is $a\_n=8(n-2)!$ for $n\ge 4$.
Subdivide into cases depending on the values at corners and count. (6 cases give 1, 1 case gives 2 times $(n-2)!$)


