# Permutation and signature matrices “almost commute”

Let $\mathcal{P}$ be the set of all permutation matrices of order $n$ and $\mathcal{S}$ the set of all signature matrices of order $n$. Furthermore, let $$\mathcal{P}\mathcal{S} = \{PS \mid P\in\mathcal{P}, S\in\mathcal{S}\}$$ and $$\mathcal{S}\mathcal{P} = \{SP \mid S\in\mathcal{S}, P\in\mathcal{P}\}$$ Show that $\mathcal{P}\mathcal{S} = \mathcal{S}\mathcal{P}.$

The following is what I have done so far.

The statement to be proven becomes more obvious if we consider the following restatement. Restatement: For every $P\in\mathcal{P}$ and for every $S\in\mathcal{S}$, there exists an $S'\in\mathcal{S}$ such that $PS=S'P$.

Intuitive proof: If we think of a signature matrix $S$ as a matrix that changes the signs of the row/s (column/s) of a given matrix $A$ if it is multiplied on the left (right) of $A$, and knowing that a signature matrix multiplied on either side of $A$ does $\textbf{not}$ change the arrangement of the entries of $A$ but only its signs, what we want to prove becomes almost "obvious".

As an example, if $P=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$ and $S=\begin{bmatrix} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$, then $PS=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & -1 & 0 \end{bmatrix}$ because $S$ negated the second column of $P$.

To make $PS=S'P$, the $S'$ we are looking for should therefore negate the third row of $P$. So $S'=\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & -1 \end{bmatrix}$.

It's not difficult to imagine that this holds for every $P\in\mathcal{P}$ and for every $S\in\mathcal{S}$.

Question: How does one write this intuitive proof rigorously?

• I think the proof sounds fine. – user148177 Jul 24 '15 at 9:52
• Perhaps it might be helpful to note that each $P\in\mathcal{P}$ induces an automorphism $S\to PSP^{-1}=S'$ of $\mathcal{S}$, a rotational change of basis, which preserves the trace. This is reminiscent of a theorem of Witt. – bgins Jul 24 '15 at 9:53
• bgins, do you know of a more elementary proof? I personally prefer an elementary proof for an elementary statement. :) – Mark Lao Jul 24 '15 at 10:14
• Note that your restatement isn't a purely logical restatement of the claim; you already need some knowledge of permutation and signature matrices to see the equivalence. A purely logical restatement would need to have $P'\in\mathcal{P}$ on the right-hand side. (In other words, by proving the restated version you're actually proving more than the claim.) – joriki Jul 24 '15 at 10:34
• Mark Lao, I tried to complete & supply context (en.wikipedia.org/wiki/Matrix_similarity) for your highly geometric and group theoretic line of reasoning, which is a beautiful way to prove, as joriki notes, the stronger statement that similarity transformation or change of basis by a permutation matrix $P$ is an endomorphism (en.wikipedia.org/wiki/…) of $\mathcal{S}$, whereas we only need to show that flipping "random" signs of rows, or columns, of any $P$ both lead to the same set of "sign-enhanced" permutation matrices. – bgins Jul 24 '15 at 17:49

You could just use the definition of matrix multiplication, and do it all mechanically. Recall that, by definition, $$(AB)_{ij} = \sum_{k=1}^n (A)_{ik}(B)_{kj},$$ where $A$ has $n$ columns and $B$ has $n$ rows. An $n \times n$ matrix $P$ is a permutation matrix if there exists some permutation $\sigma \in S_n$ such that $$(P)_{ij} = (I)_{\sigma(i)j},$$ where $I$ is, as usual the identity matrix. Finally, an $n \times n$ matrix $S$ is a signature matrix if $$(S)_{ij} = s(i)(I)_{ij} = s(j)(I)_{ij},$$ where $s(i) = \pm 1$ for all $i$. Using these definitions, we can begin formalising the argument.
Suppose $P$ is a permutation matrix, corresponding to $\sigma \in S_n$ as above, and $S$ is a signature matrix corresponding to function $s$ as above. All our matrices are $n \times n$. Note first that $$(P^{-1})_{ij} = (P)_{\sigma^{-1}(i)j} = (P)_{i\sigma(j)},$$ simply by multiplying $PP^{-1}$ and $P^{-1}P$. Then, \begin{align} (PSP^{-1})_{ij} &= \sum_{k=1}^n \sum_{l=1}^n (P)_{ik}(S)_{kl}(P^{-1})_{lj} \\ &= \sum_{k=1}^n \sum_{l=1}^n (I)_{\sigma(i)k}s(k)(I)_{kl}(I)_{l\sigma(j)} \\ &= \sum_{k=1}^n (I)_{\sigma(i)k}s(k) \sum_{l=1}^n (I)_{kl}(I)_{l\sigma(j)} \\ &= \sum_{k=1}^n (I)_{\sigma(i)k}s(k) (I)_{k\sigma(j)}. \end{align} Note the above sum is $0$ when $\sigma(i) \neq \sigma(j) \iff i \neq j$. When $i = j$, the only term in the above sum that is non-zero is where $k = \sigma(i) = \sigma(j)$. Therefore, $$(PSP^{-1})_{ij} = s(\sigma(i)) (I)_{ij},$$ which is another signature matrix $S'$. Therefore we may write $PS = S'P$. By a similar argument, you can use the above calculation to go the other direction.