Determinant of a Toeplitz matrix

Question

How can I calculate the determinant of the following Toeplitz matrix?

\begin{bmatrix} 1&2&3&4&5&6&7&8&9&10\\ 2&1&2&3&4&5&6&7&8&9 \\ 3&2&1&2&3&4&5&6&7&8 \\ 4&3&2&1&2&3&4&5&6&7 \\ 5&4&3&2&1&2&3&4&5&6 \\ 6&5&4&3&2&1&2&3&4&5 \\ 7&6&5&4&3&2&1&2&3&4 \\ 8&7&6&5&4&3&2&1&2&3 \\ 9&8&7&6&5&4&3&2&1&2 \\ 10&9&8&7&6&5&4&3&2&1 \\ \end{bmatrix}

Answer 1

We define the following $n \times n$ (symmetric) Toeplitz matrix

$${\rm A}_n := \begin{bmatrix} 1 & 2 & 3 & \dots & n-1 & n \\ 2 & 1 & 2 & \dots & n-2 & n-1 \\ 3 & 2 & 1 & \dots & n-3 & n-2 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ n-1 & n-2 & n-3 & \dots & 1 & 2 \\ n & n-1 & n-2 & \dots & 2 & 1 \\ \end{bmatrix}$$

Hence,

$${\rm A}_{n+1} = \begin{bmatrix} {\rm A}_n & {\rm c}_n\\ {\rm c}_n^\top & 1\end{bmatrix}$$

where ${\rm c}_n = {\rm A}_n {\rm e}_n + {\Bbb 1}_n$. Computing the determinant,

$$\det \left( {\rm A}_{n+1} \right) = \det \begin{bmatrix} {\rm A}_n & {\rm c}_n\\ {\rm c}_n^\top & 1\end{bmatrix} = \left( 1 - {\rm c}_n^\top {\rm A}_n^{-1} {\rm c}_n \right) \det \left( {\rm A}_n \right)$$

where

$$\begin{aligned} {\rm c}_n^\top {\rm A}_n^{-1} {\rm c}_n &= \left( {\rm A}_n {\rm e}_n + {\Bbb 1}_n \right)^\top {\rm A}_n^{-1} \left( {\rm A}_n {\rm e}_n + {\Bbb 1}_n \right)\\ &= \underbrace{{\rm e}_n^\top {\rm A}_n {\rm e}_n}_{= 1} + \underbrace{{\rm e}_n^\top {\Bbb 1}_n}_{= 1} + \underbrace{{\Bbb 1}_n^\top {\rm e}_n}_{= 1} + \underbrace{{\Bbb 1}_n^\top {\rm A}_n^{-1} {\Bbb 1}_n}_{= \frac{2}{n+1}} = 3 + \frac{2}{n+1}\end{aligned}$$

and, thus,

$$\boxed{ \quad \det \left( {\rm A}_{n+1} \right) = -2 \left( \frac{n+2}{n+1} \right) \det \left( {\rm A}_n \right) \quad }$$

and, since $\det \left( {\rm A}_1 \right) = 1$, after some work, we eventually conclude that

$$\color{blue}{\boxed{ \quad \det \left( {\rm A}_n \right) = (-1)^{n-1} \left( n + 1 \right) 2 ^{n-2} \quad }}$$

which is related to integer sequence A001792, as pointed out by Somos.

---

Addendum

How to show the following?

$${\Bbb 1}_n^\top {\rm A}_n^{-1} {\Bbb 1}_n = \frac{2}{n+1}$$

Note that the $n$-th column of matrix ${\rm A}_n$ is the reversal of its first column. Hence,

$${\rm A}_n \left( {\rm e}_1 + {\rm e}_n \right) = (n+1) {\Bbb 1}_n$$

Left-multiplying both sides by ${\Bbb 1}_n^\top {\rm A}_n^{-1}$,

$$\underbrace{{\Bbb 1}_n^\top {\rm A}_n^{-1} {\rm A}_n \left( {\rm e}_1 + {\rm e}_n \right)}_{= {\Bbb 1}_n^\top \left( {\rm e}_1 + {\rm e}_n \right) = 2} = (n+1) {\Bbb 1}_n^\top {\rm A}_n^{-1} {\Bbb 1}_n$$

and, thus,

$${\Bbb 1}_n^\top {\rm A}_n^{-1} {\Bbb 1}_n = \frac{2}{n+1}$$

---

SymPy code

>>> from sympy import *
>>> [ Matrix(n, n, lambda i,j: 1 + abs(i-j)).det() for n in range(1,11) ]
[1, -3, 8, -20, 48, -112, 256, -576, 1280, -2816]

Answer 2

some patterns.... there is a bit of cancellation in the fractions, before that the diagonal matrix, term at position $jj$ ( for $j \geq 2$) is $$ -2 \left( \frac{j+1}{j} \right) $$ which leads to some telescoping in the determinant of the diagonal matrix, and this is the same (integer) as the original matrix. The relationship $Q^T D Q = H$ for symmetric $H$ and $\det Q = 1$ is called congruence.

$$\left( \begin{array}{rr} 1 & 0 \\ 2 & 1 \\ \end{array} \right) \left( \begin{array}{rr} 1 & 0 \\ 0 & - 3 \\ \end{array} \right) \left( \begin{array}{rr} 1 & 2 \\ 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rr} 1 & 2 \\ 2 & 1 \\ \end{array} \right) $$

$$\left( \begin{array}{rrr} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & \frac{ 4 }{ 3 } & 1 \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & - 3 & 0 \\ 0 & 0 & - \frac{ 8 }{ 3 } \\ \end{array} \right) \left( \begin{array}{rrr} 1 & 2 & 3 \\ 0 & 1 & \frac{ 4 }{ 3 } \\ 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrr} 1 & 2 & 3 \\ 2 & 1 & 2 \\ 3 & 2 & 1 \\ \end{array} \right) $$

$$\left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 3 & \frac{ 4 }{ 3 } & 1 & 0 \\ 4 & \frac{ 5 }{ 3 } & \frac{ 5 }{ 4 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & - 3 & 0 & 0 \\ 0 & 0 & - \frac{ 8 }{ 3 } & 0 \\ 0 & 0 & 0 & - \frac{ 5 }{ 2 } \\ \end{array} \right) \left( \begin{array}{rrrr} 1 & 2 & 3 & 4 \\ 0 & 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 3 } \\ 0 & 0 & 1 & \frac{ 5 }{ 4 } \\ 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrr} 1 & 2 & 3 & 4 \\ 2 & 1 & 2 & 3 \\ 3 & 2 & 1 & 2 \\ 4 & 3 & 2 & 1 \\ \end{array} \right) $$

$$\left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 \\ 3 & \frac{ 4 }{ 3 } & 1 & 0 & 0 \\ 4 & \frac{ 5 }{ 3 } & \frac{ 5 }{ 4 } & 1 & 0 \\ 5 & 2 & \frac{ 3 }{ 2 } & \frac{ 6 }{ 5 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 0 \\ 0 & - 3 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 8 }{ 3 } & 0 & 0 \\ 0 & 0 & 0 & - \frac{ 5 }{ 2 } & 0 \\ 0 & 0 & 0 & 0 & - \frac{ 12 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrrrr} 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 3 } & 2 \\ 0 & 0 & 1 & \frac{ 5 }{ 4 } & \frac{ 3 }{ 2 } \\ 0 & 0 & 0 & 1 & \frac{ 6 }{ 5 } \\ 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrr} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 2 & 3 \\ 4 & 3 & 2 & 1 & 2 \\ 5 & 4 & 3 & 2 & 1 \\ \end{array} \right) $$

$$\left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 \\ 3 & \frac{ 4 }{ 3 } & 1 & 0 & 0 & 0 \\ 4 & \frac{ 5 }{ 3 } & \frac{ 5 }{ 4 } & 1 & 0 & 0 \\ 5 & 2 & \frac{ 3 }{ 2 } & \frac{ 6 }{ 5 } & 1 & 0 \\ 6 & \frac{ 7 }{ 3 } & \frac{ 7 }{ 4 } & \frac{ 7 }{ 5 } & \frac{ 7 }{ 6 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & - 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 8 }{ 3 } & 0 & 0 & 0 \\ 0 & 0 & 0 & - \frac{ 5 }{ 2 } & 0 & 0 \\ 0 & 0 & 0 & 0 & - \frac{ 12 }{ 5 } & 0 \\ 0 & 0 & 0 & 0 & 0 & - \frac{ 7 }{ 3 } \\ \end{array} \right) \left( \begin{array}{rrrrrr} 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 3 } & 2 & \frac{ 7 }{ 3 } \\ 0 & 0 & 1 & \frac{ 5 }{ 4 } & \frac{ 3 }{ 2 } & \frac{ 7 }{ 4 } \\ 0 & 0 & 0 & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } \\ 0 & 0 & 0 & 0 & 1 & \frac{ 7 }{ 6 } \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrr} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 & 2 & 3 \\ 5 & 4 & 3 & 2 & 1 & 2 \\ 6 & 5 & 4 & 3 & 2 & 1 \\ \end{array} \right) $$

$$ \tiny \left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & \frac{ 4 }{ 3 } & 1 & 0 & 0 & 0 & 0 \\ 4 & \frac{ 5 }{ 3 } & \frac{ 5 }{ 4 } & 1 & 0 & 0 & 0 \\ 5 & 2 & \frac{ 3 }{ 2 } & \frac{ 6 }{ 5 } & 1 & 0 & 0 \\ 6 & \frac{ 7 }{ 3 } & \frac{ 7 }{ 4 } & \frac{ 7 }{ 5 } & \frac{ 7 }{ 6 } & 1 & 0 \\ 7 & \frac{ 8 }{ 3 } & 2 & \frac{ 8 }{ 5 } & \frac{ 4 }{ 3 } & \frac{ 8 }{ 7 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & - 3 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 8 }{ 3 } & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - \frac{ 5 }{ 2 } & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & - \frac{ 12 }{ 5 } & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & - \frac{ 7 }{ 3 } & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & - \frac{ 16 }{ 7 } \\ \end{array} \right) \left( \begin{array}{rrrrrrr} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 3 } & 2 & \frac{ 7 }{ 3 } & \frac{ 8 }{ 3 } \\ 0 & 0 & 1 & \frac{ 5 }{ 4 } & \frac{ 3 }{ 2 } & \frac{ 7 }{ 4 } & 2 \\ 0 & 0 & 0 & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } \\ 0 & 0 & 0 & 0 & 1 & \frac{ 7 }{ 6 } & \frac{ 4 }{ 3 } \\ 0 & 0 & 0 & 0 & 0 & 1 & \frac{ 8 }{ 7 } \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrrr} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 1 & 2 & 3 & 4 & 5 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 \\ 5 & 4 & 3 & 2 & 1 & 2 & 3 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 \\ 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \end{array} \right) $$

jump to 10 ................................

$$ Q^T D Q = H $$ $$\left( \begin{array}{rrrrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & \frac{ 4 }{ 3 } & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & \frac{ 5 }{ 3 } & \frac{ 5 }{ 4 } & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 5 & 2 & \frac{ 3 }{ 2 } & \frac{ 6 }{ 5 } & 1 & 0 & 0 & 0 & 0 & 0 \\ 6 & \frac{ 7 }{ 3 } & \frac{ 7 }{ 4 } & \frac{ 7 }{ 5 } & \frac{ 7 }{ 6 } & 1 & 0 & 0 & 0 & 0 \\ 7 & \frac{ 8 }{ 3 } & 2 & \frac{ 8 }{ 5 } & \frac{ 4 }{ 3 } & \frac{ 8 }{ 7 } & 1 & 0 & 0 & 0 \\ 8 & 3 & \frac{ 9 }{ 4 } & \frac{ 9 }{ 5 } & \frac{ 3 }{ 2 } & \frac{ 9 }{ 7 } & \frac{ 9 }{ 8 } & 1 & 0 & 0 \\ 9 & \frac{ 10 }{ 3 } & \frac{ 5 }{ 2 } & 2 & \frac{ 5 }{ 3 } & \frac{ 10 }{ 7 } & \frac{ 5 }{ 4 } & \frac{ 10 }{ 9 } & 1 & 0 \\ 10 & \frac{ 11 }{ 3 } & \frac{ 11 }{ 4 } & \frac{ 11 }{ 5 } & \frac{ 11 }{ 6 } & \frac{ 11 }{ 7 } & \frac{ 11 }{ 8 } & \frac{ 11 }{ 9 } & \frac{ 11 }{ 10 } & 1 \\ \end{array} \right) \left( \begin{array}{rrrrrrrrrr} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & - 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & - \frac{ 8 }{ 3 } & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & - \frac{ 5 }{ 2 } & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & - \frac{ 12 }{ 5 } & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & - \frac{ 7 }{ 3 } & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & - \frac{ 16 }{ 7 } & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & - \frac{ 9 }{ 4 } & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - \frac{ 20 }{ 9 } & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & - \frac{ 11 }{ 5 } \\ \end{array} \right) \left( \begin{array}{rrrrrrrrrr} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & 1 & \frac{ 4 }{ 3 } & \frac{ 5 }{ 3 } & 2 & \frac{ 7 }{ 3 } & \frac{ 8 }{ 3 } & 3 & \frac{ 10 }{ 3 } & \frac{ 11 }{ 3 } \\ 0 & 0 & 1 & \frac{ 5 }{ 4 } & \frac{ 3 }{ 2 } & \frac{ 7 }{ 4 } & 2 & \frac{ 9 }{ 4 } & \frac{ 5 }{ 2 } & \frac{ 11 }{ 4 } \\ 0 & 0 & 0 & 1 & \frac{ 6 }{ 5 } & \frac{ 7 }{ 5 } & \frac{ 8 }{ 5 } & \frac{ 9 }{ 5 } & 2 & \frac{ 11 }{ 5 } \\ 0 & 0 & 0 & 0 & 1 & \frac{ 7 }{ 6 } & \frac{ 4 }{ 3 } & \frac{ 3 }{ 2 } & \frac{ 5 }{ 3 } & \frac{ 11 }{ 6 } \\ 0 & 0 & 0 & 0 & 0 & 1 & \frac{ 8 }{ 7 } & \frac{ 9 }{ 7 } & \frac{ 10 }{ 7 } & \frac{ 11 }{ 7 } \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & \frac{ 9 }{ 8 } & \frac{ 5 }{ 4 } & \frac{ 11 }{ 8 } \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \frac{ 10 }{ 9 } & \frac{ 11 }{ 9 } \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \frac{ 11 }{ 10 } \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{array} \right) = \left( \begin{array}{rrrrrrrrrr} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 2 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 2 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 3 & 2 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 5 & 4 & 3 & 2 & 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 5 & 4 & 3 & 2 & 1 & 2 & 3 & 4 & 5 \\ 7 & 6 & 5 & 4 & 3 & 2 & 1 & 2 & 3 & 4 \\ 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 2 & 3 \\ 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 2 \\ 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \end{array} \right) $$