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?

  • $\begingroup$ I think the proof sounds fine. $\endgroup$ – user148177 Jul 24 '15 at 9:52
  • $\begingroup$ 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. $\endgroup$ – bgins Jul 24 '15 at 9:53
  • $\begingroup$ bgins, do you know of a more elementary proof? I personally prefer an elementary proof for an elementary statement. :) $\endgroup$ – Mark Lao Jul 24 '15 at 10:14
  • 1
    $\begingroup$ 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.) $\endgroup$ – joriki Jul 24 '15 at 10:34
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.