How to compute the determinant of this Toeplitz matrix?

Question

Given a positive integer $n$, express$$ f_n(x) = \left|\begin{array}{c c c c c} 1 & x & \cdots & x^{n - 1} & x^n\\ x & 1 & x & \cdots & x^{n - 1} \\ \vdots & x & \ddots & \ddots & \vdots\\ x^{n - 1} & \vdots & \ddots & 1 & x\\ x^n & x^{n - 1} & \cdots & x & 1 \end{array}\right| $$ as a polynomial of $x$.

I tried to find a recurrence relation of $\{f_n\}_{n \geqslant 1}$ using Laplace expansion, but there seems to be no patterns in the minors in the expansion. Is there a somewhat simple recurrence relation of $\{f_n\}_{n \geqslant 1}$ or these determinants can be computed with other methods?

Answer 1

@José Carlos Santos I cannot compete with your straightforward proof.

Nevertheless, I thought it could be interesting to provide a (longer...) proof by using a rather peculiar property of the given matrix : the fact that its inverse is the following tridiagonal $(n+1) \times (n+1)$ matrix :

$$\dfrac{1}{1-x^2}T_n \ \ \ \ \text{where} \ \ \ \ T_n:=\begin{pmatrix} 1& -x& 0 & \cdots& 0& 0\\ -x& x^2 + 1& -x & \ddots& 0& 0\\ 0& -x& x^2 + 1& \ddots& 0 &0\\ 0&0& -x& \ddots& -x &0\\ 0&0& \ddots& \ddots& x^2+1 &-x\\ 0&0&\cdots& 0& -x&1\end{pmatrix}$$

with exceptional entries $1$ in $(1,1)$ and $(n+1,n+1)$.

Let $S_n$ be the initial matrix ; it is indeed easy to verify that $S_n T_n=(1-x^2)I_{n+1}$.

Let us prove now that, whatever $n$, the determinant of $T_n$ has the constant expression:

$$\tag{1}\det(T_n)=(1-x^2).$$

Let us multiply the first line of $\det(T_n)$ by $x$, then add this new line to the second line (this operation doesn't modify $\det(T_n)$). Laplace expansion along the first column gives:

$$x\det(T_n)=x\det(T_{n-1}).$$

Knowing that $\det(T_1)=1-x^2$ by direct computation, we have reached our objective (1).

As a consequence,

$$\det(S_n)=\left(\dfrac{1}{(1-x^2)^{n+1}}\det(T_n)\right)^{-1}=(1-x^2)^n.$$

Remark : There is a nice interpretation of the initial matrix $S_n$ as the covariance matrix of an autoregressive process $V_{n+1}=xV_n+aX$ with $X \sim N(0,1)$ (see for the continuous case (https://www.le.ac.uk/users/dsgp1/COURSES/ELOMET/LECTURE5.PDF)). The inverse of a covariance matrix is almost as significant as the initial covariance matrix. See (https://stats.stackexchange.com/q/73463) for its different uses/interpretations.

Answer 2

The answer is: $f_n(x)=(1-x^2)^n$.

You can prove that this is true by induction. If you subtract from the first row the second row times $x$, all the entries of the first line after the first one become $0$ (and the first one is $1-x^2$). Therefore, $f_n(x)=(1-x^2)f_{n-1}(x)$. Since $f_1(x)=1-x^2$, you're done.

Answer 3

Subtract $x$ times row $2$ from row $1$, then $x$ times row $3$ from row $2$ etc. I get a lower triangular matrix with $n$ instances of $1-x^2$ on the diagonal and one $1$.

Answer 4

This is simply an illustration of José Carlos Santos' answer.

---

Subtracting $x$ times the second column from the first gives $$ \begin{align} f_n(x) &=\det\begin{bmatrix} 1&x&x^2&x^3&\cdots&x^n\\ x&1&x&x^2&\cdots&x^{n-1}\\ x^2&x&1&x&\cdots&x^{n-2}\\ x^3&x^2&x&1&\cdots&x^{n-3}\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ x^n&x^{n-1}&x^{n-2}&x^{n-3}&\cdots&1 \end{bmatrix}\\ &=\det\begin{bmatrix} \color{#C00}{1-x^2}&x&x^2&x^3&\cdots&x^n\\ 0&\color{#090}{1}&\color{#090}{x}&\color{#090}{x^2}&\color{#090}{\cdots}&\color{#090}{x^{n-1}}\\ 0&\color{#090}{x}&\color{#090}{1}&\color{#090}{x}&\color{#090}{\cdots}&\color{#090}{x^{n-2}}\\ 0&\color{#090}{x^2}&\color{#090}{x}&\color{#090}{1}&\color{#090}{\cdots}&\color{#090}{x^{n-3}}\\ \vdots&\color{#090}{\vdots}&\color{#090}{\vdots}&\color{#090}{\vdots}&\color{#090}{\ddots}&\color{#090}{\vdots}\\ 0&\color{#090}{x^{n-1}}&\color{#090}{x^{n-2}}&\color{#090}{x^{n-3}}&\color{#090}{\cdots}&\color{#090}{1} \end{bmatrix}\\[6pt] &=\color{#C00}{\left(1-x^2\right)}\color{#090}{f_{n-1}(x)} \end{align} $$ Since $f_0(x)=1$, we have that $$ f_n(x)=\left(1-x^2\right)^n $$

Answer 5

Let matrix-valued function $\mathrm M_1 : \mathbb R \to \mathbb R^{2 \times 2}$ be defined as follows

$$\mathrm M_1 (x) := \begin{bmatrix} 1 & x\\ x & 1\end{bmatrix}$$

and let matrix-valued function $\mathrm M_n : \mathbb R \to \mathbb R^{(n+1) \times (n+1)}$ be defined by

$$\mathrm M_n (x) := \begin{bmatrix} \mathrm M_{n-1} (x) & \mathrm v_{n} (x)\\ \mathrm v_{n}^\top (x) & 1\end{bmatrix}$$

where $\mathrm v_{n}^\top (x) := \begin{bmatrix} x^n & \cdots & x^2 & x\end{bmatrix}$. Let function $f_n : \mathbb R \to \mathbb R$ be defined by

$$f_n (x) := \det \mathrm M_n (x) = \det \begin{bmatrix} \mathrm M_{n-1} (x) & \mathrm v_{n} (x)\\ \mathrm v_{n}^\top (x) & 1\end{bmatrix} = \det \left( \mathrm M_{n-1} (x) - \mathrm v_{n} (x) \, \mathrm v_{n}^\top (x) \right)$$

Using the matrix determinant lemma,

$$f_n (x) = \underbrace{\det \left( \mathrm M_{n-1} (x) \right)}_{= f_{n-1} (x)} \cdot \left( 1 - \mathrm v_{n}^\top (x) \, \mathrm M_{n-1}^{-1} (x) \, \mathrm v_{n} (x) \right)$$

Let $\mathrm y (x) := \mathrm M_{n-1}^{-1} (x) \, \mathrm v_{n} (x)$ be the solution of the linear system $\mathrm M_{n-1} (x) \,\mathrm y (x) = \mathrm v_{n} (x)$. Since $\mathrm v_{n} (x)$ is equal to the $n$-th column of $\mathrm M_{n-1} (x)$ multiplied by $x$, the solution is $\mathrm y (x) = x \, \mathrm e_n$. Thus,

$$f_n (x) = f_{n-1} (x) \cdot \left( 1 - \mathrm v_{n}^\top (x) \, \mathrm y (x) \right) = f_{n-1} (x) \cdot \left( 1 - x^2 \right)$$

Since $f_1 (x) = 1 - x^2$, we obtain $\color{blue}{f_n (x) = (1-x^2)^n}$, as found by José Carlos Santos via other means.