6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ maybe you can get the characteristic polynomial explicitly $\endgroup$ Commented Jun 18 at 16:59

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ This looks like a nice heuristics. However, how do you justify the sentence containing (1)? In particular, to what space is $\phi$ assumed to belong? What exactly do you mean by "in the limit"? $\endgroup$ Commented Jun 19 at 0:07
  • $\begingroup$ @IosifPinelis It's all rigorous. For each $n$, the largest eigenvalue is given by the maximization problem $\max_{||x||_2 = 1} x^T A_n x$. If you look at the maximization problem as $n \to \infty$, you get a maximization problem over $[0,1]$, where you want to maximize $\int_{[0,1]^2} (1-|x-y|)\phi(x)\phi(y) dx dy$ over all $\phi \in L^2([0,1])$. The same argument showing that, in the finite-dimensional case, the maximizer is attained by an eigenvector applies to the infinite-dimensional case here (in $L^2([0,1])$). So, to answer your last question, you can assume $\phi \in L^2([0,1])$. $\endgroup$ Commented Jun 19 at 0:15
  • $\begingroup$ I still think that details of the limit transition are needed here. They may be rather straightforward, but likely rather tedious. $\endgroup$ Commented Jun 19 at 0:51
  • $\begingroup$ Details on the sufficient regularity of $\phi$ are also needed, I think. In particular, how do you exclude $\lambda=0$? $\endgroup$ Commented Jun 19 at 0:54
  • $\begingroup$ @IosifPinelis About your last comment, did you see the edit at the end? Also, $\lambda = 0$ implies $\phi \equiv 0$, no? $\endgroup$ Commented Jun 19 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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