Prove that if P and Q are permutation matrices with $(P-I)(Q−I) = 0$ then they represent disjoint permutations.

Question

Before even starting let me make clear this question is not duplicate of this which asks for proving just the inverse statement.

Prove that if $P$ and $Q$ are permutation matrices with $(P-I)(Q−I)=0$ then, they represent disjoint permutations

MY TRY :- Let P and Q be the matrices corresponding to the respective permutations $p$ and $q$ in cycle notation. Let $p$ and $q$ do not represent disjoint permutations. For e.g. $p = (123)$ and $q=(345)$ We have that $$ P = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} \text{ and } Q = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}.$$ Now $PQ$ being a permutation will not have two $1$'s in same row. But $P+Q-I$ have two $1$'s and one $-1$ in the "third" row, and $PQ\neq P+Q-I$ which is equivalent $(P-I)(Q-I)\neq 0$ so we reach a contradiction visually. But isn't there some clear method to prove it theoritically?

I am new to group theory. Please ask for clarifications in case of any discrepancies.

Answer 1

Hint: Let $\pi$ denote the permutation corresponding to $P$, and let $e_1,e_2,\dots,e_n$ denote the standard basis of $\Bbb F^n$. Suppose that $\pi = \sigma_1\cdots \sigma_k$ is a decomposition into disjoint cycles (including all "cycles with length $1$"). Let $S_k = \{a_1,\dots,a_\ell\}$, where $\sigma_k = (a_1 \cdots a_\ell)$.

Note that $\ker(P - I)$ is spanned by the vectors $v_k = \sum_{j \in S_k} e_j$. In particular, if $S_k = e_p$, then $e_p \in \ker (P-I)$. Because $P$ is orthogonal, we have $\operatorname{im}(P - I) = \ker(P - I)^\perp$.

Answer 2

"$P$ and $Q$ are disjoint" means that for every $i$, $$ Pe_i \ne e_i \implies Qe_i = e_i\\ Qe_i \ne e_i \implies Pe_i = e_i $$ but $$ Qe_i = e_j \ne e_i \implies 0 = (P-I)(Q-I)e_i=(P-I)(e_j-e_i) \\ \implies P(e_j-e_i) = e_j-e_i\implies Pe_i = e_i $$ and $$ Pe_i = e_j \ne e_i \implies 0 = (P-I)(Q-I)Q^Te_i=(P-I)(e_i -Q^Te_i) \\ \implies P(e_i-Q^Te_i) = e_j - PQ^Te_i = e_i-Q^Te_i\implies e_i = Q^Te_i\\ \implies Qe_i = e_i $$

Answer 3

The assumption that $PQ = P + Q - I$ is [a priori] stronger than we need. We may instead simply work with the assumption that the diagonal of $P+Q-I$ only has entries in $\{0,1\}$.

If we let $1 \leq k \leq n$ be arbitrary and write $A_{kk}$ for the $k$th diagonal entry of $A$, then $$\begin{align*}(P+Q)_{kk}-1 = (P&+Q-I)_{kk} \in \{0,1\} \\ &\iff (P+Q)_{kk} \in \{1,2\} \\ &\iff P_{kk} = 1 \text{ or } Q_{kk} = 1\end{align*}$$ where the justification for the last $\implies$ is due to $P_{kk}, Q_{kk} \in \{0,1\}.$

Now we're basically finished. That the permutation matrices $P$ and $Q$ represent disjoint permutations is equivalent to the statement that, for any $1\leq k\leq n,$ $$P_{kk} = 0 \implies Q_{kk} = 1 \\\text{ and } \\Q_{kk} = 0 \implies P_{kk} = 1,$$ which is logically equivalent, since $P_{kk}, Q_{kk} \in \{0,1\}$, to $$P_{kk} = 1 \text{ or } Q_{kk} = 1$$

---

A final note: If $P,Q$ are permutation matrices and the diagonal of $P+Q-I$ has entries in $\{0,1\}$, then we can show $PQ = QP = P+Q-I,$ so this is not actually a strengthening/weakening of the theorem.