参考文献
- Toeplitz matrix - Wikipedia. https://en.wikipedia.org/wiki/Toeplitz_matrix（参照日 2022年4月9日）.
- Circulant matrix - Wikipedia. https://en.wikipedia.org/wiki/Circulant_matrix（参照日 2022年4月9日）.
- R. M. Gray, Toeplitz and Circulant Matrices: A Review. https://ee.stanford.edu/~gray/toeplitz.pdf（参照日 2022年4月9日）.
- Matrix-vector multiplication using the FFT. https://math.mit.edu/icg/resources/teaching/18.085-spring2015/toeplitz.pdf（参照日 2022年4月9日）.
- 雑記： numpy.fft の話 - クッキーの日記. https://cookie-box.hatenablog.com/entry/2020/01/29/212400（参照日 2022年4月9日）.
行列であって各成分が必ず左斜め上の成分と同じであるような行列をテプリッツ行列というらしい [1][2][4]。正方行列でなくてもいいらしい [1] が以降は正方行列しか扱わない。ちなみに国旗がこのような模様である国があったような気がしたが調べてみるとあまりこのような模様の国旗はなかったので勘違いだったらしい。
$$
T = \begin{pmatrix}
t_0 & t_{-1} & \cdots & t_{-(n-2)} & t_{-(n-1)} \\
t_1 & t_0 & \cdots & t_{-(n-3)} & t_{-(n-2)} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
t_{n-2} & t_{n-3} & \cdots & t_0 & t_{-1} \\
t_{n-1} & t_{n-2} & \cdots & t_1 & t_0 \\
\end{pmatrix}
$$
ここで、左上 $n \times n$ ブロックが $T$ であるような以下の $2n \times 2n$ テプリッツ行列を考える。T = \begin{pmatrix}
t_0 & t_{-1} & \cdots & t_{-(n-2)} & t_{-(n-1)} \\
t_1 & t_0 & \cdots & t_{-(n-3)} & t_{-(n-2)} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
t_{n-2} & t_{n-3} & \cdots & t_0 & t_{-1} \\
t_{n-1} & t_{n-2} & \cdots & t_1 & t_0 \\
\end{pmatrix}
$$
$$
\begin{pmatrix}
t_0 & t_{-1} & \cdots & t_{-(n-2)} & t_{-(n-1)} & 0 & t_{n-1} & \cdots & t_2 & t_1 \\
t_1 & t_0 & \cdots & t_{-(n-3)} & t_{-(n-2)} & t_{-(n-1)} & 0 & \cdots & t_3 & t_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
t_{n-2} & t_{n-3} & \cdots & t_0 & t_{-1} & t_{-2} & t_{-3} & \cdots & 0 & t_{n-1} \\
t_{n-1} & t_{n-2} & \cdots & t_1 & t_0 & t_{-1} & t_{-2} & \cdots & t_{-(n-1)} & 0 \\
0 & t_{n-1} & \cdots & t_{2} & t_{1} & t_0 & t_{-1} & \cdots & t_{-(n-2)} & t_{-(n-1)} \\
t_{-(n-1)} & 0 & \cdots & t_{3} & t_{2} & t_1 & t_0 & \cdots & t_{-(n-3)} & t_{-(n-2)} \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
t_{-2} & t_{-3} & \cdots & 0 & t_{n-1} & t_{n-2} & t_{n-3} & \cdots & t_0 & t_{-1} \\
t_{-1} & t_{-2} & \cdots & t_{-(n-1)} & 0 & t_{n-1} & t_{n-2} & \cdots & t_1 & t_0 \\
\end{pmatrix}
$$
\begin{pmatrix}
t_0 & t_{-1} & \cdots & t_{-(n-2)} & t_{-(n-1)} & 0 & t_{n-1} & \cdots & t_2 & t_1 \\
t_1 & t_0 & \cdots & t_{-(n-3)} & t_{-(n-2)} & t_{-(n-1)} & 0 & \cdots & t_3 & t_2 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
t_{n-2} & t_{n-3} & \cdots & t_0 & t_{-1} & t_{-2} & t_{-3} & \cdots & 0 & t_{n-1} \\
t_{n-1} & t_{n-2} & \cdots & t_1 & t_0 & t_{-1} & t_{-2} & \cdots & t_{-(n-1)} & 0 \\
0 & t_{n-1} & \cdots & t_{2} & t_{1} & t_0 & t_{-1} & \cdots & t_{-(n-2)} & t_{-(n-1)} \\
t_{-(n-1)} & 0 & \cdots & t_{3} & t_{2} & t_1 & t_0 & \cdots & t_{-(n-3)} & t_{-(n-2)} \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
t_{-2} & t_{-3} & \cdots & 0 & t_{n-1} & t_{n-2} & t_{n-3} & \cdots & t_0 & t_{-1} \\
t_{-1} & t_{-2} & \cdots & t_{-(n-1)} & 0 & t_{n-1} & t_{n-2} & \cdots & t_1 & t_0 \\
\end{pmatrix}
$$
