テプリッツ行列
テプリッツ行列（テプリッツぎょうれつ、英: Toeplitz Matrix）は、左から右の各下降対角線に沿って要素が一定であるような行列である。対角一定行列（たいかくいっていぎょうれつ、英: Diagonal-Constant Matrix）とも。名前の由来は数学者 Otto Toeplitz。テプリッツ行列は次のような行列である。
- [math] \begin{bmatrix} a & b & c & d & e \\ f & a & b & c & d \\ g & f & a & b & c \\ h & g & f & a & b \\ j & h & g & f & a \end{bmatrix} [/math]
任意の n×n 行列 A が次のような形式であれば、それをテプリッツ行列と呼ぶ。
- [math] A = \begin{bmatrix} a_{0} & a_{-1} & a_{-2} & \ldots & \ldots &a_{-n+1} \\ a_{1} & a_0 & a_{-1} & \ddots & & \vdots \\ a_{2} & a_{1} & \ddots & \ddots & \ddots& \vdots \\ \vdots & \ddots & \ddots & \ddots & a_{-1} & a_{-2}\\ \vdots & & \ddots & a_{1} & a_{0}& a_{-1} \\ a_{n-1} & \ldots & \ldots & a_{2} & a_{1} & a_{0} \end{bmatrix} [/math]
i 行目、j 列目の A の要素を Ai,j と記述するとき、以下が成り立つ。
- [math]A_{i,j} = A_{i-1,j-1}[/math]
特性
行列を使った方程式の一般形
- [math]Ax=b[/math]
は、n元線型方程式系を表す。この A がテプリッツ行列であった場合、その系はやや特殊となる（自由度が n2 ではなく 2n − 1 になる）。したがって、テプリッツ系は通常より解きやすいと期待される。
これは次の変形で調べることができる。
- [math]AU_n-U_mA[/math]
これは階数が2で、[math]U_k[/math] は down-shift operator である。特に単純な計算で次のように示すことができる。
- [math] AU_n-U_mA= \begin{bmatrix} a_{-1} & \cdots & a_{-n+1} & 0 \\ \vdots & & & -a_{-n+1} \\ \vdots & & & \vdots \\ 0 & \cdots & & -a_{n-n-1} \end{bmatrix} [/math]
ここで、行列の空の場所はゼロに置換されている。
特性
2つのテプリッツ行列の加算は O(n) の時間でなされ、テプリッツ行列とベクトルの乗算は O(n log n)、2つのテプリッツ行列の乗算は O([math]n^2[/math]) の時間でなされる。
テプリッツ系 [math]Ax=b[/math] は、レビンソン＝ダービン・アルゴリズムで Θ([math]n^2[/math]) の時間で解ける。このアルゴリズムのバリエーションは James Bunch 的意味で弱安定性を有する（すなわち、良条件の線型系で数値的安定性を示す）。
有限次元空間に圧縮された三角関数多項式による乗算演算子はテプリッツ行列で表すことができるので、テプリッツ行列はフーリエ級数とも密接に関連する。
テプリッツ行列が [math]a_i=a_{i+n}[/math] という属性も持つ場合、それを巡回行列と呼ぶ。
テプリッツ行列は persymmetric である。対称テプリッツ行列は centrosymmetric であり、かつ bisymmetric である。
畳み込みは行列の積で表すことができ、その際の入力の1つはテプリッツ行列に変換される。例えば、[math]h[/math] と [math]x[/math] の畳み込みは次のようになる。
[math] \begin{matrix} y & = & h \ast x \\ & = & \begin{bmatrix} h_1 & 0 & \ldots & 0 & 0 \\ h_2 & h_1 & \ldots & \vdots & \vdots \\ h_3 & h_2 & \ldots & 0 & 0 \\ \vdots & h_3 & \ldots & h_1 & 0 \\ h_{m-1} & \vdots & \ldots & h_2 & h_1 \\ h_m & h_{m-1} & \vdots & \vdots & h_2 \\ 0 & h_m & \ldots & h_{m-2} & \vdots \\ 0 & 0 & \ldots & h_{m-1} & h_{m-2} \\ \vdots & \vdots & \vdots & h_m & h_{m-1} \\ 0 & 0 & 0 & \ldots & h_m \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \\ \end{bmatrix} \\ y^T & = & \begin{bmatrix} h_1 & h_2 & h_3 & \ldots & h_{m-1} & h_m \\ \end{bmatrix} \begin{bmatrix} x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & 0& \ldots & 0 \\ 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & \ldots & 0 \\ 0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots & \vdots & \ldots & 0 \\ 0 & \ldots & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} & \vdots \\ 0 & \ldots & 0 & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} \\ \end{bmatrix} \end{matrix} [/math]
この手法は、自己相関、相互相関、移動平均などの計算にも拡張できる。