Efficient way to find eigenvalues of the matrix

Question

I have a matrix $A = (a_{ij})$, $A\in M_n(\mathbb{R})$, where $a_{ij} = i + j\pmod{n}$. I want to find it's eigenvalues, but it's really hard to count it's determinant (to find triangular matrix). Is there an easier way? I noticed that the sum of elements is equal in each line, but I'm not sure can it help or not.

Answer 1

I will leave my answer below just in case anyone finds it useful, but I misread the question and missed that the entries are $i+j \boldsymbol{\bmod n}$, what I say below applies to the matrix $(i+j)_{n\times n}$.

---

This matrix will have $0$ as an eigenvalue with multiplicity $n-2$, since its rank is always $2$.

The remaining two eigenvalues $\lambda$ and $\mu$ satisfy $$\lambda+\mu=\operatorname{tr}(A)=2 + \cdots + 2n=n(n+1),$$ and the product $\lambda\mu$ is the coefficient of $x^{n-2}$ in the characteristic polynomial (by, say, Viète's formulæ), which you can show to be $\frac{n^2}{12}(n^2-1)$.

From this, you can solve simultaneously to get that the eigenvalues are $$\frac{n(n+1)}{2}\pm\sqrt{\frac{n^2(n+1)(n+2)}{6}},$$ each with multiplicity $1$, and $0$ with multiplicity $n-2$.

Answer 2

Here's an answer for $\ n\ $ from $2$ to $10$. While some patterns are evident, they seem difficult to generalise.

In general, $$ A_n=\pmatrix{2&3&4&\cdots&0&1\\ 3&4&5&\cdots&1&2\\ \vdots&\vdots&\vdots&&\vdots&\vdots\\ 0&1&2&\cdots&n-2&n-1\\ 1&2&3&\cdots&n-1&0}\ . $$ As the OP mentioned, each row of this matrix sums to the same value, namely $\ {n\choose 2}\ $, so this is an eigenvalue corresponding to the eigenvector $\ \pmatrix{1\\1\\ \vdots\\1}\ $.

For $\ n=2,3,\dots,10\ $, we have \begin{align} \det\left(xI_2-A_2\right)&=x^2-1\\ &=(x-1)(x+1)\\ \det\left(xI_3-A_3\right)&=x^3-3x^2-3x+9\\ &=(x-3)(x^2-3)\\ \det\left(xI_4-A_4\right)&=x^4-4x^3-20x^2+32x+96\\ &=(x-6)(x^3+2x^2-2^3x-2^4)\\ &=(x-6)(x^2-8)(x+2)\\ \det\left(xI_5-A_5\right)&=x^5-10x^4-25x^3+250x^2+125x-1250\\ &=(x-10)(x^4-5^2x^2+5^3)\\ \det\left(xI_6-A_6\right)&=x^6-12x^5-93x^4+576x^3+2592x^2\\ &\hspace{2em}-5184x-19440\\ &=(x-15)(x+3)(x^2-36)(x^2-12)\\\ \det\left(xI_7-A_7\right)&=x^7-21x^6-98x^5+2058x^4+2401x^3\\ &\hspace{2em}-50421x^2-16807x+352947\\ &=(x-21)(x^6-2\cdot7^2x^4+7^4x^2-7^5)\\ \det\left(xI_8-A_8\right)&=x^8-24x^7-272x^6+3840x^5+24064x^4\\ &\hspace{2em}-147456x^3-753664x^2+1572864x+7340032\\ &=(x-28)(x^2-32)(x+4)(x^4-2^7x^2+2^{11})\\ \det\left(xI_9-A_9\right)&=x^9-36x^8-270x^7+9720x^6+19683x^5-708588x^4\\ &\hspace{2em}-531441x^3+19131876x^2+4783969x-17218688\\ &=(x-36)(x^2-27)(x^6-3\cdot9^2x^4+2\cdot9^4x^2-3\cdot9^5)\\ \det\left(xI_{10}-A_{10}\right)&=x^{10}-40x^9-625x^8+16000x^7+132000x^6-1680000x^5\\ &\hspace{2em}-1105\cdot10^4x^4+64\cdot10^6x^3+38\cdot10^7x^2-8\cdot10^8x\\ &\hspace{2em}-45\cdot10^8\\ &=(x-45)(x+5)(x^4-10^2x^2+2\cdot10^3)(x^4-3\cdot10^3x+10^4)\ . \end{align}

Thus, the eigenvalues are, \begin{align} \text{of } A_2:&-1,1\ ,\\ \text{of } A_3:&\pm\sqrt{3}, 3\ ,\\ \text{of } A_4:&\pm\sqrt{8},-2,6\ ,\\ \text{of } A_5:&\pm\sqrt{\frac{25-5\sqrt{5}}{2}},\pm\sqrt{\frac{25+5\sqrt{5}}{2}},10\ ,\\ \text{of } A_6:&-3,\pm2\sqrt{3},\pm6,15\, \\ \text{of } A_7:&\pm\sqrt{\omega_1}, \pm\sqrt{\omega_2},\pm\sqrt{\omega_3},21\ ,\\ \text{of } A_8:&-4,\pm4\sqrt{2},\pm4\sqrt{4-2\sqrt{2}},\pm4\sqrt{4+2\sqrt{2}}, 28\ ,\\ \text{of } A_9:&\pm3\sqrt{3},\pm\sqrt{\xi_1}, \pm\sqrt{\xi_2},\pm\sqrt{\xi_3}, 36\ ,\\ \text{of } A_{10}:&-5,\pm\sqrt{50-10\sqrt{5}},\pm\sqrt{50+10\sqrt{5}}, \pm10\sqrt{\frac{3-\sqrt{5}}{2}},\pm10\sqrt{\frac{3+\sqrt{5}}{2}}, 45\ , \end{align} where $\ \omega_1, \omega_2, \omega_3\ $ are the roots of the cubic $\ x^3-2\cdot7^2x^2+7^4x-7^5\ $, and $\ \xi_1,\xi_2,\xi_3\ $ the roots of the cubic $\ x^3-3\cdot9^2x^2+2\cdot9^4x-3\cdot9^5\ $ (all of which are positive real numbers).

The main feature of these results that stand out for me is that all the characteristic polynomials split over $\ \mathbb{Z}\ $ into factors of the form $\ x+a, x^2+b, x^4+ cx^2+d,\ $ or $\ x^6+ex^4+fx^2+g\ $.