A $p \times p$ real Toeplitz matrix has elements $A_{u v} = a_{u - v}$ and is fully defined by the elements of $a_{n}$ for $-p+1 \le n \le p-1$.

$A = \begin{bmatrix} a_{0} & a_{-1} & a_{-2} & \cdots & a_{-p+1} \\ a_{1} & a_{0} & a_{-1} & \cdots & a_{-p+2} \\ a_{2} & a_{1} & a_{0} & \cdots & a_{-p+3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{p-1} & a_{p-2} & a_{p-3} & \cdots & a_{0} \end{bmatrix}$

If this is a symmetric matrix then the signal has even symmetry $a_{n} = a_{-n}$. This post is going to look at two ways of generating symmetric Toeplitz matrices which are positive semi-definite.

### Auto-correlation of an infinite signal

One way to generate symmetric Toeplitz matrices which are positive semi-definite is to compute the auto-covariance of an infinite signal. An easy way to obtain an infinite signal is to use the periodic extension of a finite signal. The period $m$ should be at least $2p - 1$ to avoid periodic effects. If $m = p$ then the matrix will be circulant Toeplitz. The Fourier transform can be used to compute the auto-correlation.

### Sampled continuous function

It is possible to consider an infinite Toeplitz matrix with elements $a_{n}$ for $n \in \mathcal{Z}$. This matrix maps infinite sequences to infinite sequences such that $y = A x$ implies

$y_{u} = \sum_{v \in \mathcal{Z}} a_{u-v} z_{v} .$

The infinite sequence $a_{n}$ defines a $2 \pi$-periodic function in its discrete-time Fourier transform (DTFT)

$\hat{a}(\theta) = \sum_{n \in \mathcal{Z}} a_{n} e^{-i n \theta} .$

The values that this function takes in a period are the eigenvalues of the infinite Toeplitz matrix. Therefore, an infinite Toeplitz matrix will be positive semi-definite if and only if the DTFT of its elements is a non-negative function.

It can be shown that if a continuous function has a positive Fourier transform, then sampling the function will result in a sequence with a positive DTFT. The DTFT of a sampled continuous function $a_{n} = x(n)$ can be written as the continuous transform of the function multiplied by a “Dirac comb” or “impulse train”

$\hat{a}(\theta) = \sum_{n \in \mathcal{Z}} x(n) e^{-i n \theta} = \int_{t \in \mathcal{R}} x(t) \left[\sum_{n \in \mathcal{Z}} \delta(t-n)\right] e^{-i t \theta} dt .$

Using the transform of a Dirac comb and the fact that multiplication in time is convolution in frequency,

$\hat{a}(\theta) = \mathcal{F} \left\{ x(t) \sum_{n \in \mathcal{Z}} \delta(t-n) \right\}(\theta) = \sum_{n \in \mathcal{Z}} \hat{x}(\theta - 2 \pi n) .$

Therefore if the continuous transform of $x(t)$ is non-negative $\hat{x}(\theta) \ge 0$, then the sequence obtained by sampling that function $a_{n} = x(n)$ will have a non-negative DTFT $\hat{a}(\theta) \ge 0$. This gives us many ways to construct infinite symmetric Toeplitz matrices which are positive semi-definite. For example, the elements can be sampled from a Gaussian (transform is a Gaussian), triangle (transform is a squared sinc), sinc (transform is a rectangle), squared sinc (transform is a triangle), cosine, sech, Laplacian density function, etc.

Finally, we need a way to go from infinite matrices to finite matrices. This is easily achieved using the fact that any subset of the rows and columns of a positive semi-definite matrix is itself semi-definite. If $x^{T} A x$ for all $x$, then $y^{T} P^{T} A P y = (P y)^{T} A (P y) \ge 0$ for all $y$. Therefore we can simply take a finite section of the infinite matrix and be guaranteed that it is positive semi-definite.

This gives us two alternative methods by which to obtain symmetric positive semi-definite Toeplitz matrices.