# Thread: Permutation matrix properties proof

1. ## Permutation matrix properties proof

The problem asks to establish the following properties of $\displaystyle n \times n$ permutation matrices, for all $\displaystyle \sigma, \tau \in \mathcal{S}_n$.

1. $\displaystyle P_\sigma = I$ iff $\displaystyle \sigma(k) = k$ for all $\displaystyle k$, where $\displaystyle I$ denotes the $\displaystyle n \times n$ identity matrix.

2. $\displaystyle P_\sigma P_\tau = P_{\sigma \circ \tau}$.

3. $\displaystyle (P_\sigma)^{-1} = P_{\sigma^{-1}}$.

4. $\displaystyle P_\sigma$ is an orthogonal matrix, that is, $\displaystyle (P_\sigma)^{-1} = (P_\sigma)^T$.

Can someone pls check if my attempts below are correct proofs? Does the first one below qualify as a proof?

1. If $\displaystyle \sigma(k) = k$ for all $\displaystyle k$ then $\displaystyle P_\sigma A$ does not swap any rows of $\displaystyle A$ and therefore $\displaystyle P_\sigma A = A = I A$ which implies $\displaystyle P_\sigma = I$. If $\displaystyle P_\sigma = I$ then $\displaystyle P_\sigma A = I A = A$ meaning $\displaystyle \sigma(k) = k$ for all $\displaystyle k$.

2. $\displaystyle P_\sigma P_\tau A$ swaps $\displaystyle k$th row of $\displaystyle A$ with $\displaystyle \tau(k)$th row which is then swapped with $\displaystyle \sigma(\tau(k))$th row. So $\displaystyle k$th row is swapped with $\displaystyle (\sigma \circ \tau)(k)$th row which is what $\displaystyle P_{\sigma \circ \tau} A$ does. Therefore $\displaystyle P_\sigma P_\tau = P_{\sigma \circ \tau}$.

3. Property 2 says that $\displaystyle P_{\sigma}P_{\sigma^{-1}} = P_{\sigma \circ \sigma^{-1}}$. Because $\displaystyle (\sigma \circ \sigma^{-1})(k) = k$ for all $\displaystyle k$, property 1 says $\displaystyle P_{\sigma \circ \sigma^{-1}} = I$. Hence $\displaystyle P_{\sigma}P_{\sigma^{-1}} = I = P_{\sigma}(P_{\sigma})^{-1}$ and $\displaystyle (P_\sigma)^{-1} = P_{\sigma^{-1}}$.

4. If $\displaystyle [P_{\sigma}]_{ij} = 1$, then the $\displaystyle j$th row of $\displaystyle A$ will be the $\displaystyle i$th row of $\displaystyle P_{\sigma} A$. The inverse $\displaystyle P_{\sigma}^{-1}$ must copy the $\displaystyle i$th row back to the $\displaystyle j$th row and therefore $\displaystyle [P_{\sigma}^{-1}]_{ji} = [P_{\sigma}]_{ij}$. Let all other entries of $\displaystyle (P_{\sigma})^{-1}$ be zero, since all other $\displaystyle P_{\sigma}$ entries are also zero, we have $\displaystyle [P_{\sigma}^{-1}]_{ij} = [P_{\sigma}]_{ji} = [P_{\sigma}^T]_{ij}$.

2. permutation matrices do more than "swap rows". a more apt description would be "shuffle rows", or "permute rows".

so a better proof of (1) says the k-th row of PσA = the k-th row of A, hence PσA = A, for all A (important!), because only then can you conclude Pσ = I (because the multiplicative identity I of nxn matrices is unique).

(2) same problem. Pτ takes the k-th row of A to the τ(k)-th row of PτA, and then Pσ takes that to the σ○τ(k)-th row of PσPτA. the rows aren't "swapped" we can't say that the τ(k)-th row of A is taken by Pτ to the k-th row of A.

(3) looks fine.

(4) this is not true. only the other entries in the j-th row and the i-th column of Pσ^-1 will be 0. you need to argue row-by-row, or column-by-column, since Pσ has a 1 in EACH row and EACH column. that is, the j-th column of Pσ is ei, the i-th basis vector. so the transpose has the i-th basis vector in the j-th row.

clearly, when you multply Pσ by its transpose, the only non-zero entries of the product will be on the diagonal, when i = j, because the i,j-th entry of Pσ(Pσ^T) is <ej,ei>, which is what i think you meant. since the ej form an orthonormal basis, this will be the identity matrix I, so the inverse of Pσ is its transpose.

all of this assumes that the columns of Pσ are σ(ei) for each i. if the rows of Pσ are σ(ei), then PσPτ = Pτσ instead of (2), but all the other properties hold. sometimes permutation matrices are defined this way, because sometimes algebraists use τσ to mean do τ first, then σ (so they write (x)τσ).

the point is, that σ-->Pσ defines an monomorphism of Sn into GLn(F). the orthogonality of the Pσ is a nice bonus, geometrically it means all versions of F^n have the same geometric properties, the labelling of the basis vectors doesn't matter that much (well, almost. odd permutations of Sn reverse orientation).

3. Thanks for such a detailed explaination. This has been one more useful lesson about proofs.

,

,

,

,

,

# property of pwrmutation matrix

Click on a term to search for related topics.