# Efficiently computing symmetric Toeplitz matrix such that $Tx=y$

Let $$x,y \in \mathbb{R}^N$$ be known vectors. I am looking for an efficient means to compute the $$N$$ coefficients of the following symmetric Toeplitz matrix

$$T = \begin{bmatrix} c_0 & c_1 & \ldots & c_{N-1} \\ c_1 & c_0 & \ldots & c_{N-2} \\ \vdots & \vdots & \ddots & \vdots \\ c_{N-1} & c_{N-2} & \ldots & c_0 \end{bmatrix}$$

which satisfies

$$Tx=y$$

Tests in Mathematica seem to indicate that all $$c_i$$ can be uniquely determined from $$x$$ and $$y$$, but I cannot find a generic algorithm to do this.

Are you sure this is always possible with a symmetric Toeplitz matrix? Take for example $$x = [1, 1, 0, \ldots, 0]^T$$. Then the first two elements of $$T \cdot x$$ are given by $$c_0 + c_1$$ and $$c_1 + c_0$$. Therefore, if $$y_0 \neq y_1$$, there is no solution.
$$T = {\rm toep}\{c\} = \begin{bmatrix} c_0 & 0 & 0 & \ldots & 0 \\ c_1 & c_0 & 0 & \ldots & 0 \\ c_2 & c_1 & c_0 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_{N-1} & c_{N-2} & c_{N-3}& \ldots & c_0 \end{bmatrix},$$ we have $${\rm toep}\{c\} \cdot x = {\rm toep}\{x\} \cdot c$$ due to the commutativity of the (truncated) convolution. To see this, just write out the product: $$y_0 = c_0 x_0$$, $$y_1 = c_0 x_1 + c_1 x_0$$, $$y_2 = c_0 x_2 + c_1 x_1 + c_2 x_0$$ and so on, you can clearly see how $$c$$ and $$x$$ are interchangeable. Then, it is easy to find $$c$$ via $$c = {\rm toep}\{x\}^{-1} \cdot y$$. Note that since the Toeplitz matrix is diagonal, this can be done efficiently. We have $$c_0 = \frac{y_0}{x_0}$$, $$c_1 = \frac{y_1 - c_0 x_1}{x_0}$$, etc.
If you must do it with symmetrix Toeplitz matrices (which will not always work), write out your products and isolate the c's. You'll notice that $$T = c_0 I + \sum_{n=1}^{N-1} c_n (D_n + D_n^T)$$, where $$D_n$$ is a matrix with ones on its $$n$$-th diagonal (note that $$D_n = D_1^n$$ for $$n\geq 1$$). Therefore, $$T x = c_0 x + \sum_{n=1}^{N-1} c_n (D_n + D_n^T)x$$, which we can write as $$T x = X \cdot c$$, where $$X=\begin{bmatrix} x & (D_1 + D_1^T)x & \ldots & (D_{N-1} + D_{N-1}^T)x\end{bmatrix}.$$ This allows to solve for $$c$$ via $$c = X^{-1} y$$, provided that $$X$$ is invertible (it is not for my example given in the beginning of this post).
You are looking for a $c$ such that $y = c \ast x,$ where $\ast$ denotes (cyclic) convolution. Take Fourier transforms (DFT, in this case) of both sides, to get $\widehat{y} = \widehat{c} \widehat{x},$ where the multiplication is pointwise.It follows that you can compute $c$ given $x, y$ as long as the compatibility condition that $\widehat{y}_i$ is zero if $\widehat{x}_i$ is.
• I didn't think to diagonalize $T$. Doesn't this only work, though, if $T$ is circulant, not symmetric Toeplitz? – Steven Roberts Apr 2 '18 at 3:12