Let $\{P_1, \cdots, P_n\}$ be $n$ permutation matrices with size $n \times n$.
I'd like to build a $n^2 \times n^2$ matrix $P$ such that $P^\top P=P P^\top$ is a multiple of the identity, and structured as follows: $$ P = \begin{pmatrix}P_1\,|&\cdots&|\,P_n\\\hline\\ &R&\\&&\end{pmatrix}, $$ where the sign matrix $R \in \{\pm 1\}^{(n^2 - n)\times n^2}$ completes the first $n$ rows of $P$.
My questions are:
- Is it easy to build $R$? What are common possibilities?
- Can $R$ be also made by $n \times n$ blocks, each one being a permutation matrix multiplied by a $\pm 1$?
- Can we relate these blocks to the $P_i$'s of the first block-row?
(Update) Here is a solution I found for $n = 4$, that could help to understand my question.
If $\{P_1, \cdots, P_4\}$ are some permutation matrices of size $2 \times 2$ (or of any square size bigger, actually), then the following matrix is unitary: $$ P = \begin{pmatrix} \ P_1&\ P_2&\ P_3&\ P_4\\ \ P_2&-P_1&-P_4&\ P_3\\ \ P_4&-P_3&\ P_2&-P_1\\ -P_3&-P_4&P_1&P_2 \end{pmatrix} $$ Above, the second row is achieved by locally flipping the blocks of the first row, with some sign change rule; the 3rd row is obtained from the 2nd by flipping pair of blocks (and some sign change rule); and the 4th is obtained from the first by again locally flipping block of the 3rd.
My feeling is that the construction above should generalize to any $n$ that is a power of 2. Is there some "butterfly" like method behind? Or, having a look the signs, would it be possible to obtain $P$ from some matrix product of the $\{P_i\}$'s and an Hadamard matrix (but how integrate the flipping of blocks inside)? Many thanks.
Any starting point would be very much appreciated.
Thank you, Laurent