Maximal eigenvalue of a real symmetric Toeplitz matrix

Question

The $n×n$ matrix $A_n$ is defined by the elements $a_{ij}=n−|i−j|$. \begin{bmatrix} n & n-1 & n-2 & \cdots & 1\\ n-1 & n & n-1 & \cdots & 2\\ n-2 & n-1 & n & \cdots & 3\\ \vdots & \vdots & \vdots & & \vdots \\ 1 & 2 & 3 & \cdots & n \end{bmatrix}

The maximal eigenvalue of this Toeplitz matrix seems to be proportional to $n^2$.
Could someone please show me how to write the exact expression of the following limit value?

$$\lim_{n \to \infty} \frac{\rho(A)}{n^2}$$

Here is my attempt:

Gerschgorin theorem

$$\rho(A) \le n+\sum_{i=\left \lceil \frac{n}{2} \right \rceil }^n i$$

$$\rho(A) \le n+\frac{3n^{2}}{4}$$

Cauchy-Schwartz inequality

$$\langle A\vec{1} ,\vec{1} \rangle \le \Vert A\vec{1} \Vert_2 \cdot \Vert \vec{1} \Vert_2$$

Spectral norm

$$\|A\|_2 = \sup_{\vec{x} \neq \vec{0}} \frac{\|A\vec{x}\|_2}{\|\vec{x}\|_2}$$

$$\frac{\|A\vec{1}\|_2}{\|\vec{1}\|_2} \leq \|A\|_2$$

$$\|A\vec{1}\|_2 \leq \|A\|_2\cdot \|\vec{1}\|_2 $$

Real Symmetric

$$ \rho(A)=\Vert A \Vert_2$$

$$\langle A\vec{1} ,\vec{1} \rangle \le \Vert A\vec{1} \Vert_2 \cdot \Vert \vec{1} \Vert_2 \le \|A\|_2\cdot \|\vec{1}\|_2 \cdot \Vert \vec{1} \Vert_2 \le \rho(A) \cdot \sqrt{n} \cdot \sqrt{n} = n \rho(A)$$

$$\rho(A) \ge \frac{\langle A\vec{1} ,\vec{1} \rangle}{n} =\frac{n^2+\sum_{i=1}^{n-1} 2i^2}{n} =\frac{\frac{n}{3} + \frac{2n^3}{3}}{n}=\frac{2n^2}{3}+\frac{1}{3}$$

$$\frac{2}{3} \le \frac{\rho(A)}{n^2} \le \frac{3}{4} $$

The result obtained by computer calculation for $n=10000$ is approximately $0.6755169463223237.$

I have also attempted to use the inverse matrix to calculate the reciprocals of the eigenvalues. $$\begin{bmatrix} \frac{1}{2}+\frac{1}{2n+2} & -\frac{1}{2} & & & & \frac{1}{2n+2}\\ -\frac{1}{2} & 1 & -\frac{1}{2} & && \\ & -\frac{1}{2} & 1 & -\frac{1}{2} & &\\ & & -\frac{1}{2} & 1& -\frac{1}{2}&\\ & & & -\frac{1}{2} &1 &-\frac{1}{2}\\ \frac{1}{2n+2} & & & & -\frac{1}{2}& \frac{1}{2}+\frac{1}{2n+2} \end{bmatrix}$$ This inverse matrix appears to asymptotically approach this, $a=1,$ $b=-\frac{1}{2}$

Tridiagonal Matrix $\lambda_k = a + 2b \cos \left( \frac{k\pi}{n} \right), \quad k = 1, 2, 3, \ldots, n.$

$$\begin{bmatrix} a+b & b & & & & \\ b & a & b & && \\ & b & a & b& &\\ & & b & a& b&\\ & & & b &a &b\\ & & & & b& a+b \end{bmatrix}$$

However, this is only helpful for finding the limit of the largest eigenvalue of the inverse matrix, which is also the reciprocal of the smallest eigenvalue of the original matrix. Solving for the smallest eigenvalue of the inverse matrix will be significantly affected by the four corners, $1/(2n+2).$

Answer 1

The characteristic polynomial of OPs inverse $A_n^{-1}$ can be derived exactly to be (see, e.g., here) \begin{align} p_n(\lambda) &= \det(A_n^{-1}-\lambda I_n)=\frac{2^{1-n}}{1+n} + {}\\ \tag{1}\label{eq:1} &+\operatorname{Tr}\left[ \left(\begin{smallmatrix} \frac{1+n/2}{1+n} - \lambda & -\frac 1 4 \\ 1 & 0 \end{smallmatrix}\right) \left(\begin{smallmatrix} 1 - \lambda & -\frac 1 4 \\ 1 & 0 \end{smallmatrix}\right)^{n-2} \left(\begin{smallmatrix} \frac{1+n/2}{1+n} - \lambda & -\frac 1 {4(1+n)^2} \\ 1 & 0 \end{smallmatrix}\right) \right]. \end{align} Using the substitution $\cos\varphi = 1-\lambda$ this simplifies to \begin{align}\tag{2a}\label{eq:2a} p_n(\varphi) &= \frac{2^{1-n}}{1+n} \left[ 1 + \cos(n \varphi) - n \sin(n \varphi) \tan\left(\tfrac\varphi 2\right) \right] \\ \tag{2b}\label{eq:2b} &=\frac{2^{2-n}}{1+n} \, \cos^2\left(\tfrac{n\varphi} 2\right) \left[ 1 - n \tan\left(\tfrac{n\varphi} 2\right)\tan\left(\tfrac{\varphi} 2\right) \right] . \end{align} We observe that half of the eigenvalues of $A_n^{-1}$ (and $A_n$) are trivial ($\varphi_k = 2\pi k/n$ with odd $k$ fulfilling $0<k<n$), while the other half are roots of the last term in \eqref{eq:2b}. The minimal eigenvalue $\lambda_\mathrm{min}(n)$ of $A_n^{-1}$ belongs to the latter set.

To get the asymptotic smallest eigenvalue $\lambda_\mathrm{min}(n) \sim \Lambda_\mathrm{min} n^{-2}$, we expand \begin{align}\tag{3}\label{eq:3} \varphi=\arccos(1-\lambda) = \sqrt{2\lambda}+O(\lambda^{3/2}). \end{align} Inserting this into the relevant factor of \eqref{eq:2b} and expanding around $n=\infty$, we get \begin{align}\tag{4}\label{eq:4} p_\infty(\Lambda) = 1 - \sqrt{\frac \Lambda 2} \tan\left(\sqrt{\frac \Lambda 2}\right). \end{align} The numerical solution of $P_\infty(\Lambda_\mathrm{min})=0$ is $\Lambda_\mathrm{min}=1.4803477\ldots$, and we get the result $\Lambda_\mathrm{min}^{-1}=0.6755169\ldots\,.$

Note that one can also get the large-$n$ corrections with this method.

Answer 2

The limit $\lim_{n \to \infty} \frac{\rho(A)}{n^2}$ is equal to $2/y^2$, where $y$ is the smallest positive real solution to $$2\cos y + 2 = y\sin y.$$

Indeed, in the limit, an eigenvector $\phi : [0,1] \to \mathbb{C}$ has eigenvalue $\lambda$ if $$\int_0^1 \Bigl(1-|x-y|\Bigr)\phi(y)dy = \lambda \phi(x) \tag{1}$$ for each $x \in [0,1]$.

By $(1)$, $\phi$ is regular enough so that we can write $\phi(x) = \sum_{n=0}^\infty a_n x^n$ as a power series, thereby obtaining, from $(1)$, the equations $$\lambda a_0 = \sum_{n=0}^\infty \frac{1}{(n+1)(n+2)}a_n,$$ $$\lambda a_1 = \sum_{n=0}^\infty \frac{1}{n+1}a_n,$$ $$\lambda a_n = -\frac{2}{(n-1)n} a_{n-2},$$ the last being for $n \ge 2$. One derives from the last equation that $a_{2k} = \frac{(-2\lambda^{-1})^k}{(2k)!}a_0$ and $a_{2k+1} = \frac{(-2\lambda^{-1})^k}{(2k+1)!}a_1$ for $k \ge 0$. Substituting these values into the first two equations gives $$\lambda a_0 = \lambda \sin^2(\frac{1}{\sqrt{2\lambda}}) a_0 + \frac{2-\sqrt{2\lambda}\sin(\sqrt{\frac{2}{\lambda}})}{4}\lambda a_1$$ $$\lambda a_1 = \sqrt{\frac{\lambda}{2}}\sin(\sqrt{\frac{2}{\lambda}})a_0 + \lambda\sin^2(\frac{1}{\sqrt{2\lambda}}) a_1.$$ Simplifying and then dividing the equations gives $$\frac{\cos^2(\frac{1}{\sqrt{2\lambda}})}{\sqrt{\frac{\lambda}{2}}\sin(\sqrt{\frac{2}{\lambda}})} = \frac{2-\sqrt{2\lambda}\sin(\sqrt{\frac{2}{\lambda}})}{4\lambda \cos^2(\frac{1}{\sqrt{2\lambda}})}.$$

Now just let $y = \sqrt{2/\lambda}$ and observe $4\cos^4 (y/2) = (\sin y)(y-\sin y)$ is equivalent to $2\cos y + 2 = y\sin y$.

[Edit: I now just realized $(1)$ implies $\lambda \phi''(x) = -2\phi(x)$, yielding $\phi(x) = C_1\sin\Bigl(\sqrt{\frac{2}{\lambda}}x\Bigr)+C_2\cos\Bigl(\sqrt{\frac{2}{\lambda}}x\Bigr)$.]