Positive Definiteness of Finite Toeplitz Covariance Matrices

From a Spectrum to a Finite Covariance Matrix

For ordered measurements, a Toeplitz covariance matrix records the same covariance at every pair of positions with the same lag. The central question here is when this structured matrix is a valid, nonsingular covariance matrix. A spectral density gives a direct answer: its values weight the frequency components of every finite linear combination of measurements.

Use the normalization in which the covariance at lag $h$ is the Fourier coefficient $\gamma_h=\int_{-\pi}^{\pi} e^{ih\lambda}f(\lambda)\,d\lambda$. For a real stationary process, the spectral density $f$ is real and even, and the covariances satisfy $\gamma_{-h}=\gamma_h$.

Definition: Let $f$ be an integrable, real, even, nonnegative function on $[-\pi,\pi]$, and define $\gamma_h=\int_{-\pi}^{\pi} e^{ih\lambda}f(\lambda)\,d\lambda$ for every integer $h$. The $n\times n$ finite Toeplitz matrix generated by these covariances is $T_n=(\gamma_{j-k})_{j,k=0}^{n-1}$. It is positive definite if $x^\mathsf{T}T_nx>0$ for every nonzero real vector $x\in\mathbb R^n$.

The factor $1/(2\pi)$ is included in some definitions of spectral density instead. Under that alternative convention, the Fourier-coefficient formula and the bounds below acquire corresponding factors of $2\pi$. The convention above fixes those constants throughout this tutorial.

The Quadratic Form as a Spectral Integral

For a vector $x=(x_0,\ldots,x_{n-1})^\mathsf{T}$, form the finite trigonometric polynomial $P_x(\lambda)=\sum_{j=0}^{n-1}x_j e^{ij\lambda}$. Expanding its squared magnitude gives $|P_x(\lambda)|^2=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}x_jx_k e^{i(j-k)\lambda}$. The terms in this expansion are exactly the Fourier factors used to define the entries of $T_n$.

Theorem: Under the definition above, for every $x\in\mathbb R^n$, $$ x^\mathsf{T}T_nx=\int_{-\pi}^{\pi}f(\lambda)\left|\sum_{j=0}^{n-1}x_je^{ij\lambda}\right|^2\,d\lambda. $$ If $f(\lambda)>0$ almost everywhere, then $T_n$ is positive definite for every finite $n$.

Proof. Since the sums are finite and $f$ is integrable, we can expand and integrate term by term:

\begin{aligned} \int_{-\pi}^{\pi}f(\lambda)|P_x(\lambda)|^2\,d\lambda &=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}x_jx_k \int_{-\pi}^{\pi}e^{i(j-k)\lambda}f(\lambda)\,d\lambda\\ &=\sum_{j=0}^{n-1}\sum_{k=0}^{n-1}x_jx_k\gamma_{j-k} =x^\mathsf{T}T_nx. \end{aligned}

For positive definiteness, take any nonzero $x$. Then $P_x$ is a nonzero polynomial in $e^{i\lambda}$: its coefficients are not all zero. A nonzero polynomial has only finitely many roots, so $P_x(\lambda)$ can vanish at only finitely many points of $[-\pi,\pi]$. Thus $|P_x(\lambda)|^2>0$ almost everywhere. Together with $f(\lambda)>0$ almost everywhere, this makes the integrand positive almost everywhere. It is integrable because $|P_x(\lambda)|\leq\sum_j|x_j|$ and $f$ is integrable. A nonnegative integrable function that is positive almost everywhere on an interval of positive length has a strictly positive integral. Hence $x^\mathsf{T}T_nx>0$ for every nonzero $x$, as required. $\square$

The proof is finite-dimensional: it needs no limiting argument. Its key fact is that a nonzero finite polynomial cannot vanish at almost every frequency. Strict positivity of the density therefore rules out any nonzero vector with zero variance.

Worked Examples

Worked Example: An AR(1) Covariance Matrix

Suppose the spectral density is $f(\lambda)=\dfrac{\sigma^2}{2\pi}\dfrac{1-\rho^2}{1-2\rho\cos\lambda+\rho^2}$, where $\sigma^2>0$ and $|\rho|<1$. Show that the $3\times3$ Toeplitz matrix is positive definite, and calculate its quadratic form for $x=(1,-2,1)^\mathsf{T}$ when $\rho=1/2$.

The geometric-series identity $\dfrac{1-\rho^2}{1-2\rho\cos\lambda+\rho^2}=\sum_{h\in\mathbb Z}\rho^{|h|}e^{-ih\lambda}$ gives the Fourier coefficients $\gamma_h=\sigma^2\rho^{|h|}$. The series is absolutely convergent because $|\rho|<1$. Also, the denominator in $f$ is $|1-\rho e^{i\lambda}|^2$, which is strictly positive for every $\lambda$ when $|\rho|<1$. The theorem therefore gives positive definiteness.

The matrix is $T_3=\sigma^2\begin{pmatrix}1&\rho&\rho^2\\\rho&1&\rho\\\rho^2&\rho&1\end{pmatrix}$. For the stated vector, the diagonal terms contribute $1+4+1=6$ before multiplication by $\sigma^2$. The three off-diagonal pairs contribute $-4\rho$, $2\rho^2$, and $-4\rho$, respectively. Hence $x^\mathsf{T}T_3x=\sigma^2(6-8\rho+2\rho^2)$. At $\rho=1/2$, this is $\sigma^2(6-4+1/2)=5\sigma^2/2>0$.

Worked Example: A Moving-Average Spectrum

Consider $f(\lambda)=|1+\tfrac12 e^{-i\lambda}|^2/(2\pi)$. Find the $3\times3$ Toeplitz matrix and its quadratic form at $x=(1,-1,2)^\mathsf{T}$.

Expanding the squared magnitude gives $f(\lambda)=(1+\tfrac14+\cos\lambda)/(2\pi)$. Since the integral of $e^{ih\lambda}/(2\pi)$ over $[-\pi,\pi]$ is $1$ for $h=0$ and $0$ for nonzero integer $h$, the coefficients are $\gamma_0=5/4$, $\gamma_1=\gamma_{-1}=1/2$, and $\gamma_h=0$ for $|h|>1$. Therefore $T_3=\begin{pmatrix}5/4&1/2&0\\1/2&5/4&1/2\\0&1/2&5/4\end{pmatrix}$.

The diagonal contribution to the quadratic form is $(5/4)(1^2+(-1)^2+2^2)= (5/4)6=15/2$. The adjacent pairs contribute $2(1)(-1)(1/2)=-1$ and $2(-1)(2)(1/2)=-2$; the remaining pair contributes zero. Thus $x^\mathsf{T}T_3x=15/2-1-2=9/2$.

The density is bounded below: $|1+\tfrac12e^{-i\lambda}|\geq 1-\tfrac12=1/2$, so $f(\lambda)\geq 1/(8\pi)>0$. The positive value just calculated is consistent with the theorem, and the bound also gives a quantitative guarantee for every nonzero vector.

Worked Example: A Cosine Spectrum and an Eigenvalue Bound

Let $f(\lambda)=(2+\cos\lambda)/(2\pi)$. Construct $T_3$, evaluate its quadratic form at $x=(1,1,1)^\mathsf{T}$, and give a lower bound that applies to every vector.

The constant term contributes $\gamma_0=2$. Because $\cos\lambda=(e^{i\lambda}+e^{-i\lambda})/2$, the coefficients at lags $1$ and $-1$ are both $1/2$; all other nonzero-lag coefficients vanish. Thus $T_3=\begin{pmatrix}2&1/2&0\\1/2&2&1/2\\0&1/2&2\end{pmatrix}$. For $x=(1,1,1)^\mathsf{T}$, the diagonal terms sum to $6$, and the two adjacent pairs contribute $1$ each. The quadratic form is $8$.

For any $\lambda$, $f(\lambda)\geq 1/(2\pi)$. The integral representation and the orthogonality of the functions $e^{ij\lambda}$ give $\int_{-\pi}^{\pi}|P_x(\lambda)|^2\,d\lambda=2\pi\sum_{j=0}^{n-1}x_j^2$. Therefore $x^\mathsf{T}T_nx\geq\sum_jx_j^2$. For the chosen vector this bound is $3$, and the exact value $8$ satisfies it.

Positive Definiteness and Eigenvalue Bounds

Positive definiteness says that each nonzero vector has positive quadratic form. A stronger statement gives one positive lower bound that works for all vectors. This distinction matters numerically: a matrix can be positive definite but have a very small minimum eigenvalue.

Corollary: If the spectral density satisfies $m\leq f(\lambda)\leq M$ almost everywhere for constants $0<m\leq M<\infty$, then, for every $x\in\mathbb R^n$, $$ 2\pi m\|x\|_2^2\leq x^\mathsf{T}T_nx\leq 2\pi M\|x\|_2^2. $$ Consequently, every eigenvalue of $T_n$ lies between $2\pi m$ and $2\pi M$.

Derivation. Multiply the inequalities $m\leq f(\lambda)\leq M$ by the nonnegative quantity $|P_x(\lambda)|^2$, and integrate. By the quadratic-form identity, the middle integral is $x^\mathsf{T}T_nx$. Orthogonality gives $\int_{-\pi}^{\pi}|P_x(\lambda)|^2\,d\lambda=2\pi\|x\|_2^2$, yielding both bounds. For a real symmetric matrix, its smallest and largest eigenvalues are the minimum and maximum of $x^\mathsf{T}T_nx$ over unit vectors. Applying the bounds to those vectors proves the eigenvalue claim. $\square$

The strict-positivity theorem needs $f>0$ almost everywhere, but does not require a uniform lower bound $m>0$. Thus positive definiteness alone does not supply an eigenvalue bound independent of the vector or matrix size.

Why the Condition Matters—and a Common Mistake

Covariance matrices enter likelihood calculations, generalized least squares, and numerical algorithms that solve linear systems. Positive definiteness ensures that the variance of every nonzero linear combination is positive; for a finite covariance matrix, it also ensures invertibility and permits a Cholesky factorization. A spectral condition is especially useful for Toeplitz structure because it verifies these properties for every finite section at once.

Common mistake: It is tempting to argue that $f(\lambda)>0$ at every frequency automatically gives a fixed positive lower eigenvalue bound. The quadratic-form proof does give strict positivity for each nonzero vector, but a fixed bound of the form $f(\lambda)\geq m>0$ is a separate hypothesis. A density can approach zero on frequencies without being zero on a set of positive measure. In that case the theorem still gives positive definiteness, while the corollary may not apply.

A second error is to confuse a positive semidefinite matrix with a positive definite one. Nonnegativity of $f$ makes every quadratic form nonnegative by the integral identity. To conclude strict positivity using the theorem, one also needs $f>0$ almost everywhere. This condition is sufficient; it is not a claim that every positive definite Toeplitz matrix must come from a density strictly positive almost everywhere.

Key takeaway: The finite Toeplitz quadratic form is the integral of the spectral density times the squared magnitude of a finite trigonometric polynomial. Almost-everywhere positivity of the density makes that integral strictly positive for every nonzero vector; a uniform eigenvalue bound requires the stronger condition that the density be bounded away from zero.

Check Your Understanding

Use the quadratic-form representation to answer these questions.

For a nonzero vector $x$, why can $P_x(\lambda)$ vanish at only finitely many frequencies?
Which assumptions on $f$ and its Fourier coefficients define the real symmetric matrix $T_n$ used here?
If $f\geq 0$ almost everywhere but is not positive almost everywhere, what conclusion about $x^\mathsf{T}T_nx$ follows directly from the integral identity?
What additional condition on $f$ yields the lower eigenvalue bound in the corollary?
Under this tutorial’s normalization, what is $\int_{-\pi}^{\pi}|P_x(\lambda)|^2\,d\lambda$ in terms of $\|x\|_2^2$?