直交多項式と超幾何関数(10)〜幕間：Krawtchouk多項式とKrawtchouk行列〜

これはKrawtchouk多項式の母関数の式から従う。実際、
\begin{align*} \sum_{i=0}^nK_{i, j}^{(n)}v^i =\sum_{i=0}^nk_i^{(n)}(j)(-2v)^i =\left\{1+\frac{1}{2}(-2v)\right\}^j\left\{1-\frac{1}{2}(-2v)\right\}^{n-j} =(1+v)^{n-j}(1-v)^j \end{align*}
となることから従う。（証明終わり）

行列$\left(K^{(n)}\right)^2$の$(i, j)$成分を計算すると
\begin{align*} \left(K^{(n)}\right)^2_{i, j} &=\sum_{l=0}^nK^{(n)}_{i, l}K^{(n)}_{l, j} \\ &=\sum_{l=0}^n(-2)^ik_i^{(n)}(l)(-2)^lk_l^{(n)}(j) \end{align*}
となる。ここで、Krawtchouk多項式$k_i^{(n)}(j)$に関する直交性の式を思い出すと(第8回目の記事内)
\begin{align*} \sum_{l=0}^nk_i^{(n)}(l)k_j^{(n)}(l)\binom{n}{l}\frac{1}{2^l}\frac{1}{2^{n-l}} =\delta_{ij}\binom{n}{j}\frac{1}{2^j}\frac{1}{2^j} \end{align*}
と書くことができていた。さらに、Krawtchouk多項式に関するduality(これも第8回目の記事内)を使うと
\begin{align*} k_j^{(n)}(l)=(-1)^{j+l}\binom{n}{j}\binom{n}{l}^{-1}\frac{1}{2^{j-l}}k_l^{(n)}(j) \end{align*}
と書き表される。このdualityを上の直交性の式に代入すると
\begin{align*} &\sum_{l=0}^nk_i^{(n)}(l)\left\{ (-1)^{j+l}\binom{n}{j}\binom{n}{l}^{-1}\frac{1}{2^{j-l}}k_l^{(n)}(j)\right\} \binom{n}{l}\frac{1}{2^l}\frac{1}{2^{n-l}} =\delta_{ij}\binom{n}{j}\frac{1}{2^j}\frac{1}{2^j} \\ &\quad\Leftrightarrow \sum_{l=0}^n(-2)^{j+l}k_i^{(n)}(l)k_l^{(n)}(j) =2^n\delta_{ij} \end{align*}
という式が得られる。以上よりKrawtchouk行列の平方の値は
\begin{align*} \left(K^{(n)}\right)^2_{i, j} &=\sum_{l=0}^n(-2)^ik_i^{(n)}(l)(-2)^lk_l^{(n)}(j) \\ &=(-2)^{i-j}\sum_{l=0}^n(-2)^{j+l}k_i^{(n)}(l)k_l^{(n)}(j) \\ &=(-2)^{i-j}2^n\delta_{ij} =2^n\delta_{ij} \end{align*}
のように計算でき、題意の式が従う。（証明終わり）

Walsh行列の帰納的な定義は一意的に定まるので、上の直接的な計算がそれを満たしていることを示せば良い。

まず初項$n=0$のとき、$i=j=0$に関して$p(i, j)=0$となる。
これはWalsh行列の成分$H_{0, 0}^{(0)}=1$であるという事実と合致する。

次に$n-1$の時の成立を仮定し、$H^{(n)}$の成分の値についても正しいことを示す。
$0\le i ,j\le 2^{n-1}-1$なる$i$と$j$を1つfixし、それに対して定理が正しいことを仮定する。
次数$n$の時、対応する$(i', j')$成分の値を計算すると

• $(i',\, j')=(i,\, j)$のとき: 明らかに$p(i',\, j')=p(i,\, j)$となり$(i,\, j)$成分の値に一致
• $(i',\, j')=(i+2^{n-1},\, j)$のとき: $2^{n-1}$の位も$i'$は1、$j'$は0となり$p(i,\, j)$の値は変わらない。$(i,\, j)$成分の値に一致
• $(i',\, j')=(i,\, j+2^{n-1})$のとき: 上に同じく$(i,\, j)$成分の値に一致
• $(i',\, j')=(i+2^{n-1},\, j+2^{n-1})$のとき: $2^{n-1}$の位が$i$,$j$ともに1であるので$p(i',\, j')=p(i,\, j)+1$の式が従う。ゆえに$(i,\, j)$成分の値の$-1$倍になる

ことを考えると、$H^{(n)}=H\otimes H^{(n-1)}$の式を満たしていることがわかる。(証明終わり)

まずWalsh行列の成分の値について復習する。添え字$i$及び$j$について
\begin{align*} i=\sum_{t=0}^Ri_t2^t,\quad j=\sum_{t=0}^Sj_t2^t \end{align*}
と2進展開がなされる時に、Hadamard行列の成分$H_{i, j}^{(n)}$は
\begin{align*} H_{i, j}^{(n)}=(-1)^{\#\{t \mid 0\le t\le \min\{R, S\}, \,\, i_t=j_t=1\}} \end{align*}
のように計算できていた。この事実をもとに上の定理の右辺の値を計算する。

さて$k\in w^{-1}(\{i\})$を1つとめる。具体的には$k=2^0+2^1+\cdots+2^{i-1}$とする。
別の言い方をすれば、$k=00\cdots011\cdots1_{(2)}$である。ただし$0$は$n-i$個、$1$は$i$個。
次に$l\in w^{-1}(\{j\})$を走らせて、$\#\{t \mid 0\le t\le n-1, \,\, i_t=j_t=1\}$の値を考察する。
しかしこれは大変なので、$i_t=j_t=1$の個数に関する和と見て式を書き直した方が楽である。

そこで変数$s:=\#\{t \mid 0\le t\le n-1, \,\, i_t=j_t=1\}$を固定する。($s$の変域は$0\le s\le \min\{i ,j\}$である)
この条件を満たす$l\in w^{-1}(\{j\})$の個数が何個あるのかを数えれば良い。
満たすべき条件は

• $n$桁の2進数、$1$の個数は$j$個
• 後ろから$i$個の中にある$1$の個数は$s$個

組み合わせ論の問題と化してしまった。
後ろから$i$個の中にある$1$の場所の選び方が$\binom{i}{s}$通り、前$n-i$個の中には$1$が$j-s$個あるので$\binom{n-i}{j-s}$通り。
この$s$ごとに$(-1)^s$が足されるのであった。
そして、$k$をfixしていたのは、対称性で全ての場合が同じ値になるので、その分の$\binom{n}{i}$倍が必要。

以上より
\begin{align*} (\text{右辺}) &=\sum_{s=0}^{\min\{i, j\}}(-1)^s\binom{n}{i}\binom{i}{s}\binom{n-i}{j-s} \quad \left(=S_{j, i}^{(n)}\right) \\ &=\sum_{s=0}^{\min\{i, j\}}(-1)^s\frac{n!}{i!(n-i)!}\frac{i!}{s!(i-s)!}\frac{(n-i)!}{(j-s)!(n-i-j+s)!} \\ &=\sum_{s=0}^{\min\{i, j\}}(-1)^s\frac{j!}{s!(j-s)!}\frac{n!}{j!(n-j)!}\frac{(n-j)!}{(i-s)!(n-i-j+s)!} \\ &=\sum_{s=0}^{\min\{i, j\}}(-1)^s\binom{n}{j}\binom{j}{s}\binom{n-j}{i-s} \\ &=\binom{n}{j}K_{i, j}^{(n)}=S_{i, j}^{(n)} \end{align*}
となり題意の式が従うことが示された。（証明終わり）

これは実際に$\alpha=\beta=\gamma=1$及び$\delta=-1$を代入することで、$(i,j)$成分の値が
\begin{align*} \left(\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}_N\right)_{i, j} =\sum_{v=\max\{0,\, i+j-N\}}^{\min\{i,\, j\}} \binom{j}{v}\binom{N-j}{i-v}(-1)^v \end{align*}
と書けていることから明らかに従う。
和の範囲が違って見えるのは二項係数が意味を持つ範囲を正確に書いただけであることに注意する。（証明終わり）

証明したくなーいのでやっぱり元論文で。なんかもっと簡明な証明方法はないんかいこれ。

実際、計算をしてみよう。
$H^{(1)}$は明らかに対角化可能であり、具体的な固有値・固有ベクトルは
\begin{align*} H^{(1)} =\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} =\begin{pmatrix} 1+\sqrt{2} & 1 \\ 1-\sqrt{2} & 1 \end{pmatrix}^{-1} \begin{pmatrix} \sqrt{2} & \\ & -\sqrt{2} \end{pmatrix} \begin{pmatrix} 1+\sqrt{2} & 1 \\ 1-\sqrt{2} & 1 \end{pmatrix} \end{align*}
のように書き表すことができる。従ってKrawtchouk行列に対しても
\begin{align*} K^{(N)} =\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}_N =\begin{pmatrix} 1+\sqrt{2} & 1 \\ 1-\sqrt{2} & 1 \end{pmatrix}_N^{-1} \begin{pmatrix} \sqrt{2} & \\ & -\sqrt{2} \end{pmatrix}_N \begin{pmatrix} 1+\sqrt{2} & 1 \\ 1-\sqrt{2} & 1 \end{pmatrix}_N \end{align*}
のように計算することができる。(これが上の定理のすごいところである)

まず真ん中の行列を計算する。これが対角行列になっているならば嬉しい。
$(i, j)$成分の値は
\begin{align*} \left(\begin{pmatrix} \sqrt{2} & 0 \\ 0 & -\sqrt{2} \end{pmatrix}_N\right)_{i, j} =\sqrt{2}^{N-i}(-\sqrt{2})^i\delta_{ij} \quad (\text{$i-v=j-v=0$ の時のみ意味を持つ}) \end{align*}
となり対角行列となることがわかる。
$i$番目の対角成分は$\sqrt{2}^{N-i}(-\sqrt{2})^i=(-1)^i2^{N/2}$となることから、例えば$N$が偶数の時は$+2^{N/2}$が$\frac{N}{2}+1$個、$-2^{N/2}$が$\frac{N}{2}$個であることが従う。$N$が奇数の時も同様である。（証明終わり）

証明も似た流れで行う。
まずはWalsh-likeの行列$A^{(n)}$の成分$A_{i,j}^{(n)}$について、$i$及び$j$の二進展開から計算できることを言う。
すなわち
$i=\sum_{k=0}^{n-1}i_k2^k$及び$j=\sum_{k=0}^{n-1}j_k2^k$(ただし$i_k, j_k$は0または1)としたときに、次の4つの数を計算する。
\begin{align*} a(i,j,n)&=\#\{k \mid 0\le k\le n-1, \,\, i_k=j_k=0\} \\ b(i,j,n)&=\#\{k \mid 0\le k\le n-1, \,\, i_k=1,\,\, j_k=0\} \\ c(i,j,n)&=\#\{k \mid 0\le k\le n-1, \,\, i_k=0,\,\, j_k=1\} \\ d(i,j,n)&=\#\{k \mid 0\le k\le n-1, \,\, i_k=j_k=1\} \end{align*}
もちろんこれら4つの数を加えると$n$と一致するはずである。
このとき、$A^{(n)}$の構成法から次が従う。
\begin{align*} A_{i, j}^{(n)}=\alpha^{a(i,j,n)}\beta^{b(i,j,n)}\gamma^{c(i,j,n)}\delta^{d(i,j,n)} \end{align*}
これの証明は全く同様なので省略する。(4つの場合分けそれぞれで$\alpha, \beta, \gamma, \delta$が掛かることを言えば良い)

さて次に2進モーメントの各点の逆像を変域で足し合わせるフェーズに取り掛かる。
今回は和の取り方の順番を変えようと思う。
具体的には、まず最初に$l\in w^{-1}(j)$を1つfixしておく。
ここの選び方は$\binom{n}{j}$通りであり、$l$は$00\cdots011\cdots1_{(2)}$の形にしておく。

次に$k\in w^{-1}(i)$を動かして、$A_{k, l}^{(n)}$の値を計算していく。
ここで変数を取り直して、$d(k,l,n)=v$とおき変数$v$についての足し算だと見ていく。
まず$k$における1の桁数は$i$桁なので、$b(k,l,n)+d(k,l,n)=i$である。ゆえに$b(k,l,n)=i-v$
同様に$l$における1の桁数は$j$桁なので、$c(k,l,n)+d(k,l,n)=j$である。ゆえに$c(k,l,n)=j-v$
最後に$a(k,l,n)$については、全体の和が$n$であることから
$a(k,l,n)=n-v-(i-v)-(j-v)=n-i-j+v$と計算することができる。
またこれらの個数を実現する$k$の選び方は、
$l$の後ろ$j$個の1の中で$v$個の1を選ぶ：$\binom{j}{v}$通り
$l$の前$n-j$個の0の中で$i-v$個の1を選ぶ：$\binom{n-j}{i-v}$通り
これらで決定することができる。

以上をまとめると
\begin{align*} J_{i,j}^{(n)}=\sum_v\binom{n}{j}\binom{j}{v}\binom{n-j}{i-v} \alpha^{n-i-j+v}\beta^{i-v}\gamma^{j-v}\delta^v \end{align*}
がわかり題意の式を示すことができた。（証明終わり）