Solve $n$th order determinant

Question

Solve $n$th order determinant: $$ \begin{pmatrix} 1 & 2 & 3 & \cdots & n-2 & n-1 &n\\ 2 & 3 & 4 & \cdots & n-1& n& 1\\ 3 & 4 & 5 & \cdots & n &1 &2\\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots&\vdots\\ n-2 &n-1&n &\cdots &n-5 &n-4 &n-3\\ n-1 &n&1 &\cdots &n-4 &n-3 &n-2\\ n &1&2 &\cdots &n-3 &n-2 &n-1\\ \end{pmatrix} $$

I tried adding $2$nd to $n$th row to the $1$st row, then the first row is: $$ \begin{pmatrix} \frac{n(n+1)}{2} &\frac{n(n+1)}{2} \cdots \frac{n(n+1)}{2}\\ \end{pmatrix} $$ then I took out $\frac{n(n+1)}{2}$ from the first row to get $$ \begin{pmatrix} 1 & 1 & \cdots& 1\\ \end{pmatrix} $$ and then tried to work with that but I don't think this is the correct approach because anything I tried doesn't look nice.

Answer 1

This is a circulant matrix, where one can show the following formula for its determinant:

Determinant of circulant matrix

For

$$ A=\begin{pmatrix} a_1 & a_2 & a_3 & \cdots & a_n\\ a_2 & a_3 & a_4 & \cdots & a_1\\ a_3 & a_4 & a_5 & \cdots & a_2\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ a_n & a_1 & a_2 & \cdots & a_{n-1}\\ \end{pmatrix} $$ we have $$ \det (A) = (-1)^{\left\lfloor\frac{n}{2}\right\rfloor}\prod_{j=0}^{n-1}\left(a_n + \sum_{k=1}^{n-1} a_k\omega_j^k\right), $$ where $\omega_j=e^{\frac{2\pi i j}{n}}$. In our case it is $$ (-1)^{n - 1}n^{n - 2}(n^2 + n)/2, $$ see OEIS, and

Interesting determinant problem

Answer 2

With the help of WA, we get this sequence $$ 1, -3, -18, 160, 1875, -27216, -470596, \dots $$ oeis/A052182 tells us that the determinant is $(-1)^{n-1}n^{n-2}\dfrac{(n^2 + n)}{2}$, except for the sign.

Answer 3

Let us denote by $A$ the matrix corresponding to the determinant we have to compute.

Our objective is to show that :

$$\tag{*}\det(A)=(-1)^{n-1}n^{n-2}\dfrac{n(n + 1)}{2}$$

As $C:=A^T$ is circulant, we can use the following result : (https://en.wikipedia.org/wiki/Circulant_matrix), (http://www.math.columbia.edu/~ums/pdf/cir-not5.pdf):

A $n \times n$ circulant matrix $C$ is diagonalizable under the form

$$C=F_n^{−1}DF_n$$

where $F_n$ is the $n$-th order matrix of DFT (Discrete Fourier Transform) with general term $\omega^{k\ell}$ where $\omega:=e^{-\tfrac{2 i \pi}{n}}.$

Moreover if we denote by $\lambda_k$ the entries $D_{kk}$ of diagonal matrix $D$, with $V=(\lambda_1, \lambda_2, ... \lambda_n)^T$, $V$ is the DFT of the first column $(1,2,...n)^T$ of $C$ , i.e,

$$\begin{pmatrix}\lambda_1\\ \lambda_2\\ \vdots \\ \vdots \\ \lambda_n\end{pmatrix}=\underbrace{\begin{pmatrix}\omega^{0 \times 0}&&\cdots&&\omega^{(n-1)0}\\ &&&& \\ &&\omega^{k \ell}&&\\ &&&&\\ \omega^{0(n-1)}&&\cdots&&\omega^{(n-1)(n-1)}\end{pmatrix}}_{\text{DFT matrix} \ \ F_n}\begin{pmatrix}1\\2\\ \vdots \\ \vdots \\ n\end{pmatrix}$$

Thus:

$$\tag{1}\det(C)=\det(D)=\prod_{k=1}^n \lambda_k=\prod_{k=0}^{n-1} p(\omega^k),$$

where polynomial $p$ is defined by

$$p(x):=1+2x+3x^2+4x^3+...+nx^{n-1}=q'(x)$$

$$\text{with} \ \ q(x):=1+x+x^2+\cdots+x^n=\dfrac{1-x^{n+1}}{1-x}$$

As an immediate consequence :

$$\tag{2}\text{if} \ x \neq 1, \ p(x)=q(x)'=\dfrac{nx^{n+1}-(n+1)x^n+1}{(1-x)^2}.$$

In (1), let us treat separately the case $k=0$:

$$p(\omega^0)=p(1)=1+2+3+\cdots+n=\dfrac{n(n+1)}{2}$$

Concerning the general case, using (2):

$$\tag{3}\text{for} \ k=1,2,... (n-1): \ \ p(\omega^k)= \dfrac{n(\omega^k-1)}{(\omega^k-1)^2}=n\dfrac{1}{\omega^k-1}$$

(because any $n$th root of unity at power $n$ is equal to $1$.)

As a consequence

$$\prod_{k=1}^{n-1} p(\omega^k)=n^{n-1}\prod_{k=1}^{n-1}\dfrac{1}{\omega^k-1}$$

In view of objective (*), it remains to prove that

$$\tag{4}\prod_{k=1}^{n-1}(\omega^k-1)=(-1)^{n-1}n.$$

This will be done by considering $r$ defined by

$$\tag{5}r(x):=1-x^n=(1-x)s(x) \ \text{with} \ \ s(x):=1+x+x^2+\cdots +x^{n-1}$$

But the roots of $s$ are the $\omega^k$ for $k=1\cdots (n-1)$ ; thus, the factorized form of $s$ is:

$$\tag{6}s(x)=\prod_{k=1}^{n-1}(x-\omega^k)$$

Setting $x=1$ in (6) and (5) resp. gives (4).

Remark: This proof is different from the direct proofs using lines and columns manipulations. Its interest lies in the facts that

• it is based on mathematics (circulant matrices, Fourier Transform, $n$th roots of unity) that are beyond "tricks of the trade".

• it explains in particular why we have factors $\dfrac{n(n+1)}{2}$ and $n^{n-2}$ in the result.