置換行列

1 ならば 2：$P_\sigma$ の第 $j$ 列は $e_{\sigma(j)}$ なので、$1$ は第 $\sigma(j)$ 行に 1 つだけある。第 $i$ 行の $1$ は $\sigma(j)=i$ となる列 $j$、すなわち $j=\sigma^{-1}(i)$ の 1 か所だけにある。
2 ならば 1：第 $j$ 列の $1$ がある行の番号を $\sigma(j)$ とおく。$\sigma(j)=\sigma(j')$ なら第 $\sigma(j)$ 行の第 $j$ 列と第 $j'$ 列に $1$ があり、各行の $1$ は 1 つなので $j=j'$ である。よって $\sigma\colon\{1,\dots,n\}\to\{1,\dots,n\}$ は単射であり、有限集合の間の単射なので全単射、すなわち $\sigma\in S_n$ である。$A$ の第 $j$ 列は $e_{\sigma(j)}$ なので $A=P_\sigma$ である。
最後に、$P_\sigma=P_\tau$ なら各 $j$ で $e_{\sigma(j)}=e_{\tau(j)}$ であり、$K$ では $1\ne0$ なので標準基底の元は互いに異なり、$\sigma(j)=\tau(j)$ である。$\square$

1：$P_\sigma x=\sum_jx_jP_\sigma e_j=\sum_jx_je_{\sigma(j)}=\sum_ix_{\sigma^{-1}(i)}e_i$（$i=\sigma(j)$ とおき直した）。
2：前半は 1 を $A$ の各列に当てればよい。後半は $AP_\sigma$ の第 $j$ 列が $AP_\sigma e_j=Ae_{\sigma(j)}$、すなわち $A$ の第 $\sigma(j)$ 列であることによる。
3：$P_\sigma^{-1}e_{\sigma(j)}=e_j$ なので
$$ Be_{\sigma(j)}=P_\sigma Ae_j=P_\sigma\sum_ia_{ij}e_i=\sum_ia_{ij}e_{\sigma(i)} $$
であり、$B$ の第 $\sigma(j)$ 列の第 $\sigma(i)$ 成分は $a_{ij}$ である。$\square$

1：各 $j$ について $P_\sigma P_\tau e_j=P_\sigma e_{\tau(j)}=e_{\sigma(\tau(j))}=P_{\sigma\tau}e_j$ であり、$P_{\mathrm{id}}e_j=e_j$ である。よって $P_\sigma P_{\sigma^{-1}}=P_{\sigma^{-1}}P_\sigma=I_n$ となり $P_\sigma$ は正則で、$\sigma\mapsto P_\sigma$ は群準同型である。単射であることは prop-pmat-characterization の最後の主張による。像は準同型の像なので部分群である。
2：前半は 1 から従う。後半は成分で、$(P_\sigma^{\top})_{ij}=(P_\sigma)_{ji}$ が $1$ になるのは $j=\sigma(i)$、すなわち $i=\sigma^{-1}(j)$ のときであり、これは $(P_{\sigma^{-1}})_{ij}$ が $1$ になる条件と同じである。
3：Leibniz の公式（行列式 の記事の定義「Leibnizの公式による定義」）で
$$ \det P_\sigma=\sum_{\tau\in S_n}\operatorname{sgn}(\tau)\prod_{i=1}^{n}(P_\sigma)_{i\,\tau(i)} $$
である。$(P_\sigma)_{i\,\tau(i)}=1$ となるのは $i=\sigma(\tau(i))$ のときだけなので、積が $0$ でないのはすべての $i$ で $\sigma\tau(i)=i$、すなわち $\tau=\sigma^{-1}$ のときだけである。その項は $\operatorname{sgn}(\sigma^{-1})=\operatorname{sgn}\sigma$ に等しい。$\square$

段 1（番号の付け替え）．$\sigma$ の巡回置換を $(a_{k,1}\,a_{k,2}\,\cdots\,a_{k,\ell_k})$（$k=1,\dots,r$）とし、$a_{1,1},\dots,a_{1,\ell_1},a_{2,1},\dots$ をこの順に $1,2,\dots,n$ へ写す置換を $\rho$ とする。$\sigma':=\rho\sigma\rho^{-1}$ は、連続した番号のブロック $\{1,\dots,\ell_1\}$、$\{\ell_1+1,\dots,\ell_1+\ell_2\}$、… の上でそれぞれ番号を 1 つずつ進める巡回置換の積である。thm-pmat-homomorphism より $P_{\sigma'}=P_\rho P_\sigma P_\rho^{-1}$ は $P_\sigma$ と相似なので、固有多項式は等しい（固有多項式）。
段 2（ブロック対角化）．$\sigma'$ は各ブロックをそれ自身に写すので、$P_{\sigma'}e_j=e_{\sigma'(j)}$ も同じブロックの基本ベクトルであり、$P_{\sigma'}$ はブロック対角行列 $\operatorname{diag}(C_{\ell_1},\dots,C_{\ell_r})$ になる。ここで $C_\ell$ は $\ell$ 次の巡回置換 $(1\,2\,\cdots\,\ell)$ の置換行列である。区分対角行列の行列式は対角ブロックの行列式の積なので（行列式 の記事の命題「三角行列と区分三角行列の行列式」）、$\det(tI_n-P_{\sigma'})=\prod_k\det(tI_{\ell_k}-C_{\ell_k})$ である。
段 3（$C_\ell$ の固有多項式）．$C:=C_\ell$ は $Ce_j=e_{j+1}$（$j<\ell$）、$Ce_\ell=e_1$ を満たすので、$C^me_1=e_{m+1}$（$0\le m\le\ell-1$）、$C^\ell=I_\ell$ である。$I,C,\dots,C^{\ell-1}$ は線形独立である（$\sum_mc_mC^m=O$ を $e_1$ に当てると $\sum_mc_me_{m+1}=0$ となり、すべての $c_m$ が $0$）。よって $C$ の最小多項式 $\mu$ の次数は $\ell$ 以上であり、$C^\ell-I=O$ から $\mu$ は $t^\ell-1$ を割り切るので $\mu=t^\ell-1$ である。Cayley–Hamiltonの定理により $\mu$ は固有多項式を割り切り、どちらも次数 $\ell$ のモニック多項式なので、$\det(tI_\ell-C)=t^\ell-1$ である。
段 4（複素数の場合）．$t^{\ell}-1=\prod_{m=0}^{\ell-1}(t-\zeta^m)$（$\zeta=e^{2\pi i/\ell}$）から固有値の主張を得る。$P_\sigma$ は実の直交行列なので ${}^{t}P_\sigma P_\sigma=P_\sigma{}^{t}P_\sigma=I$ を満たす正規行列であり、正規行列はユニタリ行列で対角化できる（スペクトル定理）。$\square$

$A$ の第 $j$ 列を $c_j$ とし、$c_j$ の $0$ でない成分の行番号の集合（台）を $S_j$ とする。${}^{t}AA=I$ より、$j\ne k$ のとき $\sum_ia_{ij}a_{ik}=0$ であり、各項は $0$ 以上なので、すべての $i$ で $a_{ij}a_{ik}=0$ である。よって $S_j\cap S_k=\emptyset$ である。また $\sum_ia_{ij}^2=1$ なので $S_j\ne\emptyset$ である。$\{1,\dots,n\}$ の互いに交わらない空でない $n$ 個の部分集合 $S_1,\dots,S_n$ は、どれもちょうど 1 個の元からなる（元の個数の合計が $n$ 以下で、各々 $1$ 以上だから）。$S_j=\{\sigma(j)\}$ とおくと $\sigma$ は単射、したがって全単射である。$c_j$ の $0$ でない成分は $a_{\sigma(j)j}$ だけで、$a_{\sigma(j)j}^2=1$、$a_{\sigma(j)j}\ge0$ なので $a_{\sigma(j)j}=1$ である。よって $A=P_\sigma$ である。$\square$