6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i don't know if it helps, but $n(n+1)/2$ is an eigenvalue and the eigenvector is $(1,1,\cdots, 1).$ $\endgroup$ – abel Apr 18 '15 at 13:51
  • 2
    $\begingroup$ "I think eigenvalues won't have a role to play in the value of the determinant" --- you might want to reflect on this a moment. $\endgroup$ – WillO Apr 18 '15 at 13:56
  • $\begingroup$ Up to a sign, I get $n^{n-2} (n^2 + n)/2$ $\endgroup$ – WillO Apr 18 '15 at 13:59
  • 4
    $\begingroup$ oeis.org/A052182 $\endgroup$ – Michael Biro Apr 18 '15 at 14:01
  • 1
    $\begingroup$ See theorem 17 on page 23 of this article. $\endgroup$ – Count Iblis Apr 18 '15 at 21:24
1
$\begingroup$

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} $$

$\endgroup$
2
$\begingroup$

$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 ...

$\endgroup$
  • $\begingroup$ Thanks! But I have trouble following this part: $$Av_\zeta=(1+2\zeta+\ldots+n\zeta^{n-1})\cdot v_{\zeta^{-1}}.$$ I understand why multiplication by ζ rotates vζ componentwise, but cannot figure out how you get that equation from this fact? $\endgroup$ – Vim Apr 18 '15 at 15:16
  • $\begingroup$ The sign appears to be $(-1)^{\lfloor n/2\rfloor}$. $\endgroup$ – g.kov Apr 18 '15 at 15:38
2
$\begingroup$

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}

$\endgroup$
2
$\begingroup$

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)
enter image description here

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

$\endgroup$
  • $\begingroup$ By the way it is the same as @achille hui 's method2, but may be easier to follow. $\endgroup$ – Vim Apr 19 '15 at 14:59
  • $\begingroup$ +1 it is now readable and does clearly show all those steps that is hard to typeset. $\endgroup$ – achille hui Apr 20 '15 at 1:42
  • $\begingroup$ This is slick ! $\endgroup$ – Gabriel Romon Nov 20 '16 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.