Any hint about solving this monster determinant?

Question

I'm asked to solve the following determinant: $$|A|= \begin{vmatrix} 1 &2 &3 &\cdots &{n-1} &n\\ 2 &3 &4 &\cdots &n &1\\ \vdots &\vdots &\vdots & &\vdots &\vdots\\ {n-1} &n &1 &\cdots &{n-3} &{n-2}\\ n &1 &2 &\cdots &{n-2} &{n-1} \end{vmatrix} $$ My attempt is to add all the other columns onto the first one, which gives $$|A|=\frac{n(n+1)}{2}|B|$$ where $|B|$ is, however, none the easier than $|A|$.
I think the result should be very special, since $A$ is a very special symmetric matrix itself. But I simply get stuck. Can you help me? thanks in advance.

---

EDIT
It just occurred to me that definition might work out well here. Am I on the right track?

I'm now into another question. If $(j_1,j_2,\cdots,j_n)$ is an $n-th$ permutation of ${1,2,\cdots,n}$ and the number of inversion pairs in there is $\tau$, then what's the number of inversion pairs in its inverse permutation $(j_n,j_{n-1},\cdots,j_2,j_1)$ ? This may shed a light on the problem.
Some friend of mine has given me a relatively simple solution, which I will add subsequently as an answer.

Answer 1

Notes

The approach in method 1 seems a little bit overkill for this problem.
I have added another approach (method 2) based on row/column operations.
I hope that will be more accessible.

---

Method 1 (inspired by Fourier transform on a circular lattice.)

Let $A$ be any $n \times n$ matrix whose entries has the form $$A_{ij} = a_{i+j},\quad 0 \le i, j < n$$ where $( a_k )$ is a periodic sequence of length $n$. Let $\phi_A(z)$ be the polynomial:

$$\phi_A(z) = \sum_{s=0}^{n-1} a_s z^s$$

Let $\displaystyle\;\omega = e^{\frac{2\pi i}{n}}\;$ be the $n^{th}$ root of unity. Let $\Omega$ and $\Delta$ be two $n \times n$ matrices defined by

$$\Omega_{ij} = \frac{1}{\sqrt{n}}\omega^{ij} \quad\text{ and }\quad \Delta_{ij} = \begin{cases} 1, & i + j \equiv 0, \pmod n\\ 0, & \text{ otherwise } \end{cases}$$

It is clear $$( \Omega^\dagger\Omega )_{ij} = \frac{1}{n}\sum_{k=0}^{n-1} \bar{\omega}^{ki}\omega^{kj} = \frac1n \sum_{k=0}^{n-1}\omega^{k(j-i)} = \delta_{ij} = (I_n)_{ij},\quad 0 \le i,j < n$$ where $\delta_{ij}$ is the Kronecker delta. This implies $\Omega^\dagger\Omega = I_n$ and $\Omega$ is an unitary matrix.

Notice $$ ( \Omega^\dagger A O )_{ij} = \frac1n \sum_{k=0}^{n-1}\sum_{l=0}^{n-1} \bar{\omega}^{ki} a_{k+l} \omega^{lj} = \phi_A(\omega^j) \left( \frac1n \sum_{k=0}^{n-1} \omega^{-k(i+j)}\right) = \phi_A(\omega^j) \Delta_{ij} $$ This leads to $$\det(A) = \det(\Delta) \prod_{j=0}^{n-1} \phi_A(\omega_j) = (-1)^{\frac{(n-1)(n-2)}{2}} \prod_{j=0}^{n-1} \phi_A(\omega_j)$$

For our case, $a_s = s+1$ for $0 \le s < n$ and

$$\phi_A(z) = 1 + 2z + 3z^2 + nz^{n-1} = \left(\frac{1-z^{n+1}}{1-z}\right)' = -(n+1)\frac{z^n}{1-z} + \frac{1-z^{n+1}}{(1-z)^2}$$

This implies

$$\phi_A(\omega^j) = \begin{cases} \displaystyle\;\frac{n(n+1)}{2}, & j = 0\\ \\ \displaystyle\;-\frac{n}{1-\omega^j}, & 1 \le j < n \end{cases}$$

As a result, $$\det(A) = (-1)^{\frac{(n-1)(n-2)}{2}} \left(\frac{n(n+1)}{2}\right)(-n)^{n-1}\prod_{j=1}^{n-1}\left(\frac{1}{1-\omega^j}\right)$$

Notice $$\prod_{j=1}^{n-1} (z-\omega^j) = \frac{z^n-1}{z-1} = 1 + z + \cdots + z^{n-1}$$ We get $$\det(A) = \frac12 (-1)^{\frac{n(n-1)}{2}} (n+1)n^{n-1}$$

Up to a sign, this is the same as the OEIS sequence A052182. The difference comes form the way one shift the rows. The one on OEIS are for matrices whose successive rows are shifted/rotated to right while the one for this problem is shifted/rotated to the left.

---

Method 2 (based on row/column operations)

For any $n > 2$, consider following three $n \times n$ matrices. $D_n, L_n$ are lower triangular while $R_n$ is upper triangle.

$$(D_n)_{ij} = \begin{cases} +1, & i = j\\ -1, & i = j+1\\ 0, & \text{otherwise} \end{cases} ,\quad (L_n)_{ij} = \begin{cases} 1, & i = j\\ 1, & i > 2 \land j = 2\\ 0, & \text{otherwise} \end{cases} \\ (R_n)_{ij} = \begin{cases} 1, & i = j\\ 1, & j = n\\ 0, & \text{otherwise} \end{cases} $$ For example, for $n = 5$, we have

$$D_5 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ -1 & 1 & 0 & 0 & 0\\ 0 & -1 & 1 & 0 & 0\\ 0 & 0 & -1 & 1 & 0\\ 0 & 0 & 0 & -1 & 1 \end{bmatrix} , \quad L_5 = \begin{bmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & -1 & 1 & 0 & 0\\ 0 & -1 & 0 & 1 & 0\\ 0 & -1 & 0 & 0 & 1 \end{bmatrix}\\ R_5 = \begin{bmatrix} 1 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$

It is clear the determinants of all these matrices are one.

1. If we multiply $A$ by $R_n$ from the left, the effect is summing all $n$ columns and place the results into last columns.

2. If we multiply $AR_n$ by $D_n$ from the right, the effect is

   • subtract the $(n-1)^{th}$ row form the $n^{th}$ row.
   • subtract the $(n-2)^{th}$ row from the $(n-1)^{th}$ row.
   • $\quad\quad\vdots$
   • subtract the $2^{nd}$ row from the $1^{st}$ row.

   The result is

   • the $1^{st}$ row remains untouhced.
   • aside from the first row, the $n^{th}$ column of every other row becomes $0$.
   • aside from the first row, most entries on every other row becomes $1$. In particular, all entries (except the last entry) in $2^{nd}$ row is $1$.

3. If we multiply $D_n A R_n$ by $L_n$ from the left, the effect is

   • subtract the $2^{nd}$ row from all rows below it.

   Since most entries there are $1$, the final effect is on $3^{rd}$ to last row, there is one any only one entries remain for each row.

The resulting matrix look like this:

$$L_n D_n A R_n = \begin{bmatrix} 1 & 2 & 3 & \cdots & n-2 & n-1 & \frac{n(n+1)}{2}\\ 1 & 1 & 1 & \cdots & 1 & 1 & 0\\ 0 & 0 & 0 & \cdots & 0 & -n & 0\\ 0 & 0 & 0 & \cdots & -n & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots\\ 0 & 0 & -n & \cdots & 0 & 0 & 0\\ 0 & -n & 0 & \cdots & 0 & 0 & 0 \end{bmatrix} $$ From this, we find $$\begin{align} \det(A) &= \det(L_n D_n A R_n)\\ &= \overbrace{ (-1)^{n-1} \frac{n(n+1)}{2} }^{\color{blue}{ \text{from expanding } 1^{st} \text{ row} }} \times \overbrace{ (-1)^{\frac{(n-2)(n-3)}{2}} }^{\color{blue}{ \text{from flipping } 2^{nd} \text{ to } (n-1)^{th} \text{row} }} \times (-n)^{n-2}\\ &= \frac12 (-1)^{\frac{n(n-1)}{2}} (n+1)n^{n-1} \end{align} $$

Answer 2

$A$ is symmetric and therefore has $n$ orthogonal real eigenvectors with eigenvalue $\lambda_1,\ldots, \lambda_n$ and we have $\det A=\lambda_1\cdot\ldots\cdot \lambda_n$. Guessing eigenvectors might help. Unfortunately this guessing (apart from the "all ones" vector) is only really simple in the complexification:

If $\zeta\in\mathbb C$ is an $n$th root of unity, let $v_\zeta:=(1,\zeta,\zeta^2,\ldots,\zeta^{n-1})^T$. Observe from the fact that multiplication by $\zeta$ rotates $v_\zeta$ componentwise that $$Av_\zeta=(1+2\zeta+\ldots+n\zeta^{n-1})\cdot v_{\zeta^{-1}}.$$ Hence $v_\zeta$ is an eigenvector of $A^2$ with eigenvalue $|1+2\zeta+\ldots+n\zeta^{n-1}|^2$. Since the $v_\zeta$ are linearly independant, we conclude that $$(\det A)^2= \prod_{\zeta^n=1}|1+2\zeta+\ldots+n\zeta^{n-1}|^2$$ hence $$\tag1\det A =\pm \prod_{\zeta^n=1} |1+2\zeta+\ldots+n\zeta^{n-1}|$$ Let's simplify: We have $$ \tag2(1+2\zeta+\ldots+n\zeta^{n-1})(1-\zeta)=1+\zeta+\ldots+\zeta^{n-1}-n$$ and $$ \tag3(1+\zeta+\ldots+\zeta^{n-1})(1-\zeta)=1-\zeta^n=0.$$ If $\zeta=1$ then clearly $1+2\zeta+\ldots+n\zeta^{n-1}=\frac{n(n-1)}{2}$. In all other cases, $(2)$ and $(3)$ imply $$(1+2\zeta+\ldots+n\zeta^{n-1})=\frac n{\zeta-1}.$$ Since the $\zeta-1$ with $\zeta^n=1$ and $\zeta\ne 1$ are precisely the roots of the polynomial $$\frac{(X+1)^n-1}{X}=X^{n-1}+\ldots + n$$ we conclude that $n=(-1)^{n-1}\prod_{\zeta^n=1,\zeta\ne 1}(\zeta-1)$. Therefore $(1)$ becomes $$|\det A|=\left|\frac{n(n+1)}{2}\cdot \frac{n^{n-1}}{\prod_{\zeta^n=1, \zeta\ne 1}(\zeta-1)}\right|=\frac{n^{n-1}(n+1)}{2}.$$

I am still fighting with the sign of $\det A$, though ...

Answer 3

Another way of looking at the $\det(A)$: by swapping pairs of rows $(1,n-1),(2,n-2)\dots$ this matrix is transformed into circulant matrix $C$ with the same $0$-th row $(1,\dots,n)$, which has a well known explicit formula for determinant, \begin{align} \det(C)&=\prod_{j=0}^{n-1}\sum_{k=0}^{n-1} (k+1)\exp\left(2\pi i\frac{jk}{n}\right). \end{align} Accounting to the number of swapped rows, \begin{align} \det(A)&=(-1)^{\lfloor (n+3)/2\rfloor}\det(C). \end{align} And as @Michael Biro has pointed out in the comment, A052182 gives \begin{align} \det(C)&=(-1)^{n-1}\frac{(n+1)n^{n-1}}{2}, \end{align} hence \begin{align} \det(A)&=(-1)^{\lfloor n/2\rfloor}\frac{(n+1)n^{n-1}}{2}. \end{align}

Answer 4

A friend of mine has given me a relatively easy solution as follows. ( Apologies that I'm on the mobile device so it's not convenient to code)

Well, I just uploaded the picture from my PC. It looks okay now :)