テプリッツ行列

テプリッツ行列（テプリッツぎょうれつ、英: Toeplitz Matrix）は、左から右の各下降対角線に沿って要素が一定であるような行列である。対角一定行列（たいかくいっていぎょうれつ、英: Diagonal-Constant Matrix）とも。名前の由来は数学者オットー・テプリッツ（英語版）。テプリッツ行列は次のような行列である。

{\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}}

任意の n×n 行列 A が次のような形式であれば、それをテプリッツ行列と呼ぶ。

{\boldsymbol {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}}

i 行目、j 列目の A の要素を A_i,j と記述するとき、以下が成り立つ。

A_{i,j}=A_{i-1,j-1}

特性

行列を使った方程式の一般形

{\boldsymbol {A}}{\boldsymbol {x}}={\boldsymbol {b}}

は、n元線型方程式系を表す。この A がテプリッツ行列であった場合、その系はやや特殊となる（自由度が n² ではなく 2n − 1 になる）。したがって、テプリッツ系は通常より解きやすいと期待される。

これは次の変形で調べることができる。

{\boldsymbol {A}}{\boldsymbol {U}}_{n}-{\boldsymbol {U}}_{m}{\boldsymbol {A}}

これは階数が2で、 ${\boldsymbol {U}}_{k}$ は down-shift operator である。特に単純な計算で次のように示すことができる。

{\boldsymbol {A}}{\boldsymbol {U}}_{n}-{\boldsymbol {U}}_{m}{\boldsymbol {A}}={\begin{bmatrix}a_{-1}&\cdots &a_{-n+1}&0\\\vdots &\ddots &&-a_{-n+1}\\\vdots &&\ddots &\vdots \\0&\cdots &\cdots &-a_{n-n-1}\end{bmatrix}}

ここで、行列の空の場所はゼロに置換されている。

特性

2つのテプリッツ行列の加算は O(n) の時間でなされ、テプリッツ行列とベクトルの乗算は O(n log n)、2つのテプリッツ行列の乗算は O( $n^{2}$ ) の時間でなされる。

テプリッツ系 ${\boldsymbol {A}}{\boldsymbol {x}}={\boldsymbol {b}}$ は、レビンソン＝ダービン・アルゴリズム（英語版）で Θ( $n^{2}$ ) の時間で解ける。このアルゴリズムのバリエーションは James Bunch 的意味で弱安定性を有する（すなわち、良条件の線型系で数値的安定性を示す）。