置換行列についての覚書

1. $\sigma,\tau \in \mathfrak{S}_{n}$とする．このとき
   \begin{align} p_{\sigma \circ \tau} \epsilon_{j} &= \epsilon_{(\sigma\circ\tau)(j)} \\ &= \epsilon_{\sigma(\tau(j))} \\ &= p_{\sigma}\epsilon_{\tau(j)} \\ &= p_{\sigma}p_{\tau} \epsilon_{j} \end{align}
   より$p_{\sigma\circ\tau} = p_{\sigma} \circ p_{\tau}$となるので，（行列の積の定義（cf. mat例13）より）
   $$ P(\sigma\circ\tau) = P_{\sigma\circ\tau} \textcolor{orange}{=} P_{\sigma}P_{\tau} = P(\sigma)P(\tau)$$
   が成り立つ．
2. $\sigma\in\mathfrak{S}_{n}$とし，$P_{\sigma} = I_{n}$とする．このとき，$p_{\sigma} = \id_{\mathbb{C}^{n}}$より，任意の$j \in \{1,\ldots,n\}$に対して
   $$ \epsilon_{\sigma(j)} = p_{\sigma}\epsilon_{j} = \epsilon_{j}\quad \leadsto\quad \sigma(j) = j$$
   が成り立つので，$\sigma = \id$を得る．

$\sigma \in \mathfrak{S}_{n}$とする．このとき
$$ P_{\sigma}^{\transpose}(i,j) = P_{\sigma}(j,i) = \delta_{j,\sigma(i)} = \delta_{i,\sigma^{-1}(j)} = P_{\sigma^{-1}}(i,j)$$
より，
$$ P_{\sigma}^{\transpose} = P_{\sigma^{-1}} = P(\sigma^{-1}) = P(\sigma)^{-1} = P_{\sigma}^{-1}$$
が成り立つ．

Step 1.

正整数$\ell \in \mathbb{N}_{>0}$に対して$\ell$次置換行列$C_{\ell} \in \mathrm{Perm}(\ell)$を
$$ C_{\ell} \coloneqq P((12\cdots \ell)) = \begin{bmatrix} 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix}$$
で定めると，
\begin{align} \det(t I_{\ell}-C_{\ell}) &= \det\begin{bmatrix} t & 0 & \cdots & 0 & -1 \\ -1 & t & \cdots & 0 & 0 \\ 0 & -1 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & -1 & t \end{bmatrix} \\ &= t \cdot \det\begin{bmatrix} t & \cdots & 0 & 0 \\ -1 & \cdots & 0 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ 0 & \cdots & -1 & t \end{bmatrix} + (-1)^{1+\ell}(-1)\cdot \det\begin{bmatrix} -1 & t & \cdots & 0 \\ 0 & -1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & -1 \end{bmatrix} \\ &= t \cdot t^{\ell-1} + (-1)^{1+\ell}(-1) \cdot (-1)^{\ell-1} \\ &= t^{\ell} -1 \end{align}
が成り立つ．

Step 2.

置換$\sigma \in \mathfrak{S}_{n}$の“広義”巡回置換分解を
$$ \sigma = \sigma_{\ell_{1}} \cdots \sigma_{\ell_{m}}$$
とする：
$$ \sigma_{\ell_{j}} \coloneqq (i_{1,j} \cdots i_{\ell_{j},j}),\ 1 \leq j \leq m,\ 1 \leq \ell_{j} \leq n.$$
このとき，$\mathbb{C}^{n}$の基底$(\epsilon_{i_{1,1}},\ldots,\epsilon_{i_{\ell_{1},1}},\ldots,\epsilon_{i_{1,m}},\ldots,\epsilon_{i_{\ell_{m},m}})$に関する$p_{\sigma}$の表現行列は
$$ C_{\ell_{1}} \oplus\cdots\oplus C_{\ell_{m}}$$
となる．したがって
\begin{align} f_{\sigma}(t) &= \det(t I_{n} - (C_{\ell_{1}} \oplus\cdots\oplus C_{\ell_{m}})) \\ &= \det((t I_{\ell_{1}} - C_{\ell_{1}}) \oplus\cdots\oplus (t I_{\ell_{m}} - C_{\ell_{m}})) \\ &= \prod_{j=1}^{m} \det(t I_{\ell_{j}} - C_{\ell_{j}}) \\ &= \prod_{j=1}^{m} (t^{\ell_{j}} - 1) \\ &= \prod_{\ell=1}^{n} (t^{\ell}-1)^{\#\{j \in \{1,\ldots,m\} \,:\, \ell_{j}=\ell\}} \\ &= \prod_{\ell=1}^{n} (t^{\ell}-1)^{N_{\ell}} \end{align}
が成り立つ．

Step 1.

$\ell$次置換行列$C_{\ell} \in \mathrm{Perm}(\ell)$の最小多項式$\mu_{\ell} \coloneqq \mu_{(12 \cdots \ell)}$は
$$ \mu_{\ell}(t) = t^{\ell}-1 = \prod_{k \mid \ell} \Phi_{k}(t)$$
で与えられる．実際，

1. $C_{\ell}^{\ell} = I_{\ell}$より$\mu_{\ell}(t) \mid t^{\ell}-1$を得る．
2. $\deg \mu_{\ell} \leq \ell-1$として
   $$ \mu_{\ell}(t) = a_{\ell-1}t^{\ell-1} + \cdots + a_{1}t + a_{0}$$
   とおくと，
   \begin{align} 0 &= \mu_{\ell}(C_{\ell})\epsilon_{1} \\ &= (a_{\ell-1}C_{\ell}^{\ell-1} + \cdots + a_{1}C_{\ell} + a_{0}I_{\ell})\epsilon_{1} \\ &= a_{\ell-1}\epsilon_{\ell} + \cdots + a_{1}\epsilon_{2} + a_{0}\epsilon_{1} \end{align}
   より
   $$ a_{\ell-1} = \cdots = a_{1} = a_{0} = 0$$
   が得られるが，これは不合理である．

Step 2.

$\mathbb{C}^{n}$の適当な基底に関する$p_{\sigma}$の表現行列は
$$ I_{\ell_{0}} \oplus C_{\ell_{1}} \oplus\cdots\oplus C_{\ell_{m}}$$
となる（のだった）．よって
\begin{align} \mu_{\sigma} &= \mathrm{LCM}\{\mu_{1},\mu_{\ell_{1}},\ldots,\mu_{\ell_{m}}\} \\ &= \mathrm{LCM}\left\{\Phi_{1},\prod_{k_{1} \mid \ell_{1}} \Phi_{k_{1}}, \ldots, \prod_{k_{m} \mid \ell_{m}} \Phi_{k_{m}}\right\} \\ &= \prod\{\Phi_{k} : \exists\,j \in \{1,\ldots,m\},\ k \mid \ell_{j}\}\\ \end{align}
が成り立つ．

可逆行列$Z \in \mathrm{GL}(n,\mathbb{C})$を
$$ Z(j,k) \coloneqq \zeta_{n}^{(n-j+1)k}\quad \leadsto\quad \hat{Z}(k) = \begin{bmatrix} \zeta_{n}^{nk} \\ \zeta_{n}^{(n-1)k} \\ \vdots \\ \zeta_{n}^{2k} \\ \zeta_{n}^{k} \end{bmatrix} = v_{n}^{k}$$
で定める．このとき
\begin{align} \Gamma_{a}(C_{n})\hat{Z}(k) &= (a_{0}I_{n} + a_{1}C_{n} +\cdots+ a_{n-1}C_{n}^{n-1})v_{n}^{k} \\ &= a_{0}v_{n}^{k} + a_{1}\zeta_{n}^{k}v_{n}^{k} +\cdots+ a_{n-1}(\zeta_{n}^{k})^{n-1}v_{n}^{k} \\ &= (a_{0}+a_{1}\zeta_{n}^{k} +\cdots+ a_{n-1}(\zeta_{n}^{k})^{n-1})v_{n}^{k} \\ &= \Gamma_{a}(\zeta_{n}^{k})v_{n}^{k}\\ &= \Gamma_{a}(\zeta_{n}^{k}) \hat{Z}(k) \end{align}
より
$$ \Gamma_{a}(C_{n})Z = Z \begin{bmatrix} \,\Gamma_{a}(\zeta_{n}) & & & \\ & \ddots && \\ && \Gamma_{a}(\zeta_{n}^{n-1}) & \\ &&& \Gamma_{a}(\zeta_{n}^{n}) \end{bmatrix}$$
となるので，
$$ \det \Gamma_{a}(C_{n}) = \Gamma_{a}(1)\Gamma_{a}(\zeta_{n}) \cdots \Gamma_{a}(\zeta_{n}^{n-1})$$
が成り立つ．

まづ
$$ \mathrm{Conv}(\mathrm{Perm}(n)) \coloneqq \left\{X \in \mathrm{Mat}(n,n;\mathbb{R}) : \exists\,(a_{\sigma})_{\sigma} \in [0,1]^{\mathfrak{S}_{n}},\ \sum_{\sigma\in\mathfrak{S}_{n}} a_{\sigma} = 1,\ X = \sum_{\sigma\in\mathfrak{S}_{n}} a_{\sigma}P_{\sigma}\right\}$$
とおき，写像$h \colon \mathrm{Mat}(n,n;\mathbb{R}) \to \mathbb{R}$を
$$ h(A) \coloneqq \max_{\sigma\in\mathfrak{S}_{n}}\,\langle A \mid P_{\sigma} \rangle = \sup\,\{\langle A \mid X \rangle : X\in\mathrm{Conv}(\mathrm{Perm}(n))\}$$
で定める（これを$\mathrm{Conv}(\mathrm{Perm}(n))$の支持函数（support function）という）．このとき
$$ \mathrm{Conv}(\mathrm{Perm}(n)) = \{S \in \mathrm{Mat}(n,n;\mathbb{R}) : \forall A \in \mathrm{Mat}(n,n;\mathbb{R}),\ \langle A \mid S \rangle \leq h(A)\}$$
が成り立つことを示せばよい．

1. $S \in \mathrm{Conv}(\mathrm{Perm}(n))$とすると，$$ S = \sum_{\sigma\in\mathfrak{S}_{n}} a_{\sigma}P_{\sigma},\ a_{\sigma}\in[0,1],\ \sum_{\sigma\in\mathfrak{S}_{n}} a_{\sigma} = 1$$
   と書けるので，任意の$A \in \mathrm{Mat}(n,n;\mathbb{R})$に対して
   $$ \langle A \mid S \rangle = \sum_{\sigma\in\mathfrak{S}_{n}} a_{\sigma} \langle A \mid P_{\sigma} \rangle \leq \sum_{\sigma\in\mathfrak{S}_{n}} a_{\sigma} h(A) = h(A)$$
   が成り立つ．
2. $S \notin \mathrm{Conv}(\mathrm{Perm}(n))$とする．いま$\mathrm{Conv}(\mathrm{Perm}(n))$は$\mathbb{R}^{n!}$から$\mathrm{Mat}(n,n;\mathbb{R})$への連続写像
   $$ (a_{\sigma})_{\sigma} \mapsto \sum_{\sigma\in\mathfrak{S}_{n}} a_{\sigma}P_{\sigma}$$
   による$(n!-1)$単体の像なのでコンパクトであり，したがって$X_{0} \in \mathrm{Conv}(\mathrm{Perm}(n))$であって
   $$ \|S-X_{0}\| = \dist{S}{\mathrm{Conv}(\mathrm{Perm}(n))} > 0$$
   を満たすものが存在する．そこで$A_{0} \coloneqq S-X_{0}\ (\neq O_{n})$とおくと，
   $$ \langle A_{0} \mid S \rangle - \langle A_{0} \mid X_{0} \rangle = \langle A_{0} \mid S-X_{0} \rangle = \|S-X_{0}\|^{2} > 0\quad\leadsto\quad \langle A_{0} \mid S \rangle > \langle A_{0} \mid X_{0} \rangle$$
   が成り立つ．あとは任意の$\sigma\in\mathfrak{S}_{n}$に対して
   $$ \langle A_{0} \mid X_{0} \rangle \geq \langle A_{0} \mid P_{\sigma} \rangle$$
   が成り立つことを示せばよい．ところで$\sigma\in\mathfrak{S}_{n}$とすると，任意の$r \in\;]0,1]$に対して，$(1-r)X_{0}+rP_{\sigma} \in \mathrm{Conv}(\mathrm{Perm}(n))$より，
   \begin{align} \|A_{0}\|^{2} &= \|S-X_{0}\|^{2} \\ &\textcolor{orange}{\leq} \|S-((1-r)X_{0}+rP_{\sigma}) \|^{2} \\ &= \|A_{0} - r(P_{\sigma}-X_{0})\|^{2} \\ &= \|A_{0}\|^{2} - 2r\langle A_{0} \mid P_{\sigma}-X_{0} \rangle + r^{2} \|P_{\sigma}-X_{0}\|^{2} \end{align}
   が成り立つので，
   $$ \langle A_{0} \mid P_{\sigma} \rangle - \langle A_{0} \mid X_{0} \rangle \leq \frac{r}{2}\|P_{\sigma}-X_{0}\|^{2} \to 0 \quad (r \to 0)$$
   を得る．

Step 1.

任意の$S \in \mathrm{DS}(n)\smallsetminus\{I_{n}\}$に対して，$\sigma_{S}\in\mathfrak{S}_{n}\smallsetminus\{\id\}$であって
$$ 0 \notin \{S(i,\sigma_{S}(i)) : 1 \leq i \leq n,\ i \neq \sigma_{S}(i)\}$$
なるものが存在することを示す．

1. $n = 1$のときは自明に成り立つ．
2. $S \in \mathrm{DS}(n+1)\smallsetminus\{I_{n+1}\}$とし，
   $$ \forall \sigma\in\mathfrak{S}_{n+1}\smallsetminus\{\id\},\ 0 \in \{S(i,\sigma(i)) : 1 \leq i \leq n+1,\ i \neq \sigma(i)\}$$
   が成り立ったと仮定する．このとき，$S$の固有多項式$f_{S}$は
   $$ f_{S}(t) = (t-S(1,1))\cdots(t-S(n+1,n+1)) + \sum_{\sigma\in\mathfrak{S}_{n+1}\smallsetminus\{\id\}} \sgn(\sigma) \cdot (t\delta_{1,\sigma(1)}-S(1,\sigma(1)))\cdots(t\delta_{n+1,\sigma(n+1)}-S(n+1,\sigma(n+1)))$$
   で与えられるが，各$\sigma\in\mathfrak{S}_{n+1}\smallsetminus\{\id\}$に対して，$i_{\sigma} \in \{1,\ldots,n+1\}$であって
   $$ i_{\sigma} \neq \sigma(i_{\sigma}),\ S(i_{\sigma},\sigma(i_{\sigma})) = 0\quad\leadsto\quad t\delta_{i_{\sigma},\sigma(i_{\sigma})}-S(i_{\sigma},\sigma(i_{\sigma})) = 0$$
   なるものが存在するので，上式第$2$項は$0$となり，
   $$ f_{S}(t) = (t-S(1,1))\cdots(t-S(n+1,n+1))$$
   が成り立つ．ところで，二重確率行列$S$は固有値$1$を持つので，$i_{0} \in \{1,\ldots,n+1\}$であって$S(i_{0},i_{0}) = 1$なるものが存在し，したがって
   $$ S = \begin{bmatrix} &&& 0 &&& \\ &&& \vdots &&& \\ &&& 0 &&& \\ 0 & \cdots & 0 & 1 & 0 & \cdots & 0 \\ &&& 0 &&& \\ &&& \vdots &&& \\ &&& 0 &&& \\ \end{bmatrix}$$
   となる．よって$S$の第$i_{0}$行と第$i_{0}$列を取り除いてできる$n$次正方行列を$S_{0}$とおくと，$S_{0} \in \mathrm{DS}(n)\smallsetminus\{I_{n}\}$であるから，数学的帰納法の仮定より$\sigma_{0} \in \mathfrak{S}_{n+1}\smallsetminus\{\id\}$であって
   $$ \sigma_{0}(i_{0}) = i_{0},\ 0 \notin \{S(i,\sigma_{0}(i)) : 1 \leq i \leq n+1,\ i \neq i_{0},\ i \neq \sigma_{0}(i)\},$$
   すなわち
   $$ 0 \notin \{S(i,\sigma_{0}(i)) : 1 \leq i \leq n+1,\ i \neq \sigma_{0}(i)\}$$
   を満たすものが存在するが，これは不合理である．

Step 2.

$S \in \mathrm{DS}(n)$とする．このとき任意の$A \in \mathrm{Mat}(n,n;\mathbb{R})$に対して
$$ \sum_{i,j=1}^{n} A(i,j)S(i,j) \leq \max_{\sigma\in\mathfrak{S}_{n}} \sum_{i=1}^{n} A(i,\sigma(i))$$
が成り立つことを示せばよい（cf. conv-hull）．

1. そこで$A \in \mathrm{Mat}(n,n;\mathbb{R})$とし$\tau\in\mathfrak{S}_{n}$であって
   $$ \max_{\sigma\in\mathfrak{S}_{n}} \sum_{i=1}^{n} A(i,\sigma(i)) = \sum_{i=1}^{n} A(i,\tau(i)) = \tr(AP_{\tau})$$
   なるものを取る．いま$SP_{\tau} \in \mathrm{DS}(n)$であり，perm-orthoより
   $$ \langle A \mid S \rangle = \tr(AS^{\transpose}) = \tr((AP_{\tau})(P_{\tau}^{\transpose}S^{\transpose})) = \tr((AP_{\tau})(SP_{\tau})^{\transpose}) = \langle AP_{\tau} \mid SP_{\tau} \rangle$$
   であるから，$\tau = \id$としてよい：
   $$ \forall \sigma\in\mathfrak{S}_{n},\ \tr(AP_{\sigma}) \leq \tr A.$$
2. さて，$r \in \mathbb{R}_{>0}$とし
   $$ A_{r} \coloneqq A + rI_{n} \in \mathrm{Mat}(n,n;\mathbb{R})$$
   とおく．このとき，任意の$\sigma\in\mathfrak{S}_{n}\smallsetminus\{\id\}$に対して
   \begin{align} \tr A_{r} - \tr (A_{r}P_{\sigma}) &= (\tr A -\tr(AP_{\sigma})) + rn - r \tr P_{\sigma} \\ &\geq rn-r(n-1) \\ &= r \end{align}
   が成り立つ．
3. つぎに，$r \in \mathbb{R}_{>0}$とし，$T_{0} \in \mathrm{DS}(n)$であって
   $$ \sup_{T\in\mathrm{DS}(n)} \langle A_{r} \mid T \rangle = \langle A_{r} \mid T_{0} \rangle$$
   を満たすものを考える（注意：$\mathrm{DS}(n) \subset \mathrm{Mat}(n,n;\mathbb{R})$は有界閉集合なので，このような$T_{0}$は存在する）．もし$T_{0} \neq I_{n}$であるとすると，前段より$\tau_{0} \in \mathfrak{S}_{n}\smallsetminus\{\id\}$であって
   $$ 0 \notin \{T_{0}(i,\tau_{0}(i)) : 1 \leq i \leq n,\ i \neq \tau_{0}(i)\}$$
   を満たすものが存在する．そこで
   $$ r' \coloneqq \min\{T_{0}(i,\tau_{0}(i)) : 1 \leq i \leq n,\ i \neq \tau_{0}(i)\} \in \mathbb{R}_{>0}$$
   とおいて$T_{r'} \in \mathrm{Mat}(n,n;\mathbb{R})$を
   $$ T_{r'} \coloneqq T_{0} + r'I_{n} - r'P_{\tau_{0}^{-1}}$$
   で定めると，
   $$ T_{r'}(i,j) = T_{0}(i,j) + r'\delta_{i,j} -r'\delta_{\tau_{0}(i),j} = \begin{cases} T_{0}(i,i) + r' & \tau_{0}(i) \neq i = j \\ T_{0}(i,\tau_{0}(i)) - r' & i \neq \tau_{0}(i) = j \\ T_{0}(i,j) & \text{otherwise} \end{cases}$$
   より$T_{r'}(i,j) \geq 0$であって，
   $$ T_{r'}\epsilon = T_{0}\epsilon + r'I_{n}\epsilon - r'P_{\tau_{0}^{-1}}\epsilon = \epsilon + r'\epsilon -r'\epsilon = \epsilon = T_{r'}^{\transpose}\epsilon$$
   が成り立つので，$T_{r'} \in \mathrm{DS}(n)$である．ところがこのとき
   \begin{align} \langle A_{r} \mid T_{r'} \rangle - \langle A_{r} \mid T_{0} \rangle &= \langle A_{r} \mid T_{r'}-T_{0} \rangle \\ &= \langle A_{r} \mid r'I_{n} -r'P_{\tau_{0}^{-1}} \rangle \\ &= r'(\langle A_{r} \mid I_{n} \rangle - \langle A_{r} \mid P_{\tau_{0}}^{\transpose} \rangle) \\ &= r' \left(\tr A_{r} - \tr(AP_{\tau_{0}})\right) \\ &\geq r' r \\ &>0 \end{align}
   となって$T_{0}$の取り方に反する．
4. よって任意の$r \in \mathbb{R}_{>0}$に対して
   $$ \langle A \mid S \rangle \leq \langle A_{r} \mid S \rangle \leq \langle A_{r} \mid T_{0} \rangle = \langle A_{r} \mid I_{n} \rangle = \tr A_{r} = \tr A + rn$$
   が成り立つ．
5. 以上より
   $$ \sum_{i,j=1}^{n} A(i,j)S(i,j) = \langle A \mid S \rangle \leq \tr A = \max_{\sigma\in\mathfrak{S}_{n}} \sum_{i=1}^{n} A(i,\sigma(i))$$
   を得る．