Toeplitz, circulant, and finite-index conventions for structured solvers

All vector and matrix indices below start at $0$. A rectangular Toeplitz matrix $T\in {\mathbb{C}}^{m\times n}$, where $m,n\ge 1$, is specified by lags $t_r\in \mathbb{C}$ for $-(n-1)\le r\le m-1$ and has entries $T_{ij}:=t_{i-j}(0\le i<m,0\le j<n)\mathrm{.}$ For a square matrix $T\in {\mathbb{C}}^{n\times n}$, Hermitian Toeplitz means $t_{-r}=\overline{t_r}$ for $0\le r<n$. It is positive definite when $x^{\ast }Tx>0$ for every nonzero $x\in {\mathbb{C}}^n$, where $x^{\ast }:={\bar{x}}^T$ and the product is the matrix product of Rectangular matrix multiplication and the identity matrix $I_n$, including zero-sized shapes.

For $N\ge 1$, a vector $c=(c_0,\dots ,c_{N-1}{)}^T\in {\mathbb{C}}^N$ generates the circulant matrix $C(c{)}_{ij}:=c_{(i-j)<mrow><mi\; mathvariant="normal">m</mi><mi\; mathvariant="normal">o</mi><mi\; mathvariant="normal">d</mi></mrow>N}(0\le i,j<N)\mathrm{.}$ For $n\ge 1$ and $0\le j<n$, let $e_j\in {\mathbb{C}}^n$ be the coordinate vector with $(e_j{)}_i=1$ when $i=j$ and $0$ otherwise. For $a\in {\mathbb{C}}^n$, $J_{n}a$ is the reversed vector, $(J_{n}a{)}_i=a_{n-1-i}$; $J_0$ is the unique map on the empty vector. The lower-triangular Toeplitz matrix of $a$ is $L(a)\in {\mathbb{C}}^{n\times n}$ with $L(a{)}_{ij}=a_{i-j}$ when $i\ge j$, and $0$ otherwise. The canonical unitary DFT is the map ${\mathcal{F}}_N$ of The unitary discrete Fourier transform on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$; the unnormalised DFT used for operation counts is $D_N:=\sqrt{N}{\mathcal{F}}_N$.

These conventions specify matrix orientation, conjugation, normalization, and boundary indexing; in particular, circulant eigenvalues below use the negative-sign canonical DFT.