skew-circulant matrix

SWIFFT読んでたら出てきた. そんな名前だったのか.
以下, 多項式と行列表示の話. 某所の発表でこれを説明しなければならないのが面倒臭くてしょうがないので, ここに書いておく. 線形符号を知っている人なら知っていると思うので読み飛ばし推奨.

まずモニックなn次の整数係数多項式f(\alpha)を用意する. \mathbb{Z}[\alpha]/(f)は環.
x=(x_0,x_1,...,x_{n-1})^Tはn次整数ベクトル. これをx(\alpha)=x_0\alpha^0+x_1\alpha^1+\cdots+x_{n-1}=\alpha^{n-1}というn-1次以下の整数係数多項式と同一視する. これで\mathbb{Z}^n\mathbb{Z}[\alpha]/(f)も同一視できる. 二項演算子\otimes\mathbb{Z}[\alpha]/(f)上の積とする.
\mathrm{rot}_fという関数を用意する. これは\mathrm{rot}(x)=\alpha x(\alpha) \bmod{f}で定義される.
これを用いて, \mathrm{Rot}_fという関数も用意しよう. \mathrm{Rot}_f(x)=[x\,\mathrm{rot}(x)\,...\,\mathrm{rot}^{n-1}(x)]とn×n行列を出力する. f(\alpha)=\alpha^n-1の時, \mathrm{Rot}_f(x)がcirculant matrixと呼ばれる. f(\alpha)=\alpha^n+1の時が, skew-circulant matrix. それ以外はなんて呼ぶんだろう?
\mathrm{Rot}_fを使うと

  • x\otimes y = \mathrm{Rot}_f(x) y
  • \mathrm{Rot}_f(x)+\mathrm{Rot}_f(y) = \mathrm{Rot}_f(x + y)
  • \mathrm{Rot}_f(x) \mathrm{Rot}_f(y) = \mathrm{Rot}_f(x \otimes y)

が言えるので, 多項式の行列表現が出来て便利.
あと, 特殊なベクトルa^{(n)}=(1,a,a^2,...,a^{n-1})^T内積を取ると, x(a)=\langle x, a^{(n)} \rangleになるので, 多項式をaで評価することも出来る. よってフーリエ行列をFとしたときに, F x=[x(\omega^0)\,x(\omega^1)\,...\,x(\omega^{n-1})]となってフーリエ変換っぷりが良く分かると. フーリエ行列で\omega\mathbb{F}_qの原始根とするとReed-Solomon符号の生成行列になる.

という辺りを1分で喋れるわけもないのでどうしたもんだかな, と.