# Upper bound for the eigenvalues of a matrix

$A_n$ is a real symmetric $n \times n$ matrix defined by

$$A_n = \begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{3} & \cdots & \frac{1}{n} \\ \frac{1}{2} & \frac{1}{2} & \frac{1}{3} & \cdots & \frac{1}{n} \\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & \cdots & \frac{1}{n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \frac{1}{n} & \frac{1}{n} & \frac{1}{n} & \cdots & \frac{1}{n} \\ \end{bmatrix}$$

Find an upper bound of the eigenvalues of $A_n$ as tight as possible.

Let $A_n = U+U^T-D,$ where $U$ is the upper triangular part of $A_n$ and $D$ is the diagonal of $A_n$.

Suppose $\lambda$ is the largest eigenvalue of $A_n = U^T U$.

For any $X \in \mathbb{R}^n$, $$X^T A_n X = X^T U^T U X = \left\Vert UX \right\Vert^2 \leq \lambda \left\Vert X \right\Vert^2 \implies \left\Vert UX \right\Vert \leq \sqrt{\lambda} \left\Vert X \right\Vert.$$ Since $U^T U$ is similar to $U U^T$, $\lambda$ is also the largest eigenvalue of $U U^T$.

Hence we also have $$\left\Vert U^T X \right\Vert \leq \sqrt{\lambda} \left\Vert X \right\Vert.$$ Similarly, $$\left\Vert D X \right\Vert \leq \left\Vert X \right\Vert.$$

Thus

$$\left\Vert A_n X \right\Vert = \left\Vert U X + U^T X - D X \right\Vert \leq \left\Vert U X \right\Vert + \left\Vert U^T X \right\Vert + \left\Vert D X \right\Vert \leq \left( 2 \sqrt{\lambda} + 1 \right) \left\Vert X \right\Vert.$$

Take $X$ to be the eigenvector of $A_n$ corresponding to $\lambda$, then

$$\left\Vert A_n X \right\Vert = \lambda \left\Vert X \right\Vert \leq \left( 2 \sqrt{\lambda} + 1 \right) \left\Vert X \right\Vert,$$

we have $\sqrt{\lambda} \leq 1+\sqrt{2} \implies \lambda \leq 3+2\sqrt{2}.$

Is there any tighter upper bound?

• FYI: For $n < 1.4 \times 10^7$, you'd be better off with the bound $\lambda \le \|A\|_F = \sqrt{\sum_{k = 1}^{n}\tfrac{2k-1}{k^2}} \le \sqrt{2\ln n+1}$. Of course, this is worse for large $n$. Also, this matrix is somewhat related to the Hilbert matrix $H_{i,j} = \frac{1}{i+j-1}$, whose largest eigenvalue is $\le \pi$ for any size $n$. Perhaps you can look up the proof of that fact and use similar techniques here. Aug 27, 2018 at 3:46

The matrix $$A_n$$ is semi-famous because its inverse is a tridiagonal matrix: $$A_n^{-1}=2B_n=2\begin{pmatrix} 1 & -1 & 0 & \cdots & 0 \\ -1 & 4 & -3 & 0 & \\ 0 & \ddots & \ddots & \ddots & 0 \\ 0 & 0 & -t_{n-2} & (n-1)^2 & -t_{n-1} \\ 0 & 0 & 0 & -t_{n-1} & n^2/2\end{pmatrix}$$ where $$t_n=n(n+1)/2$$ are the triangular numbers. It seems easier to find the smallest eigenvalue of $$B_n$$ than the largest eigenvalues of $$A_n$$. If $$v=(u_1(x),u_2(x),\ldots,u_n(x))$$ is an eigenvector of $$B_n$$ with eigenvalue $$x$$, then the components satisfy the recurrence relation $$u_{k+1}(x)=\frac{k^2-x}{t_k}u_k(x)-\frac{t_{k-1}}{t_k}u_{k-1}(x),\quad u_1(x)=1,u_2(x)=1-x$$ $$\left(\frac{n^2}{2}-x\right)u_n(x)=t_{n-1}u_{n-1}(x)\tag{1}$$ the last being the characteristic polynomial equation of $$B_n$$. To find the smallest root of this polynomial one might use more sophisticated techniques, but for brevity let's keep only the constant and $$x$$ term. The proofs are omitted but it is not hard to see that $$u_n(x)=1-2(H_n-1)x+\cdots$$ where $$H_n$$ are the harmonic numbers. Substituting these into $$(1)$$ and neglecting higher order terms gives $$x\approx \frac{n}{2 \left(n H_{n-1}+1\right)}$$, so the largest eigenvalue of $$A_n$$ is less than $$\lambda\le H_n$$ A comparison of the actual largest eigenvalue and $$H_n$$ is below: $$\begin{matrix}n&1&2&3&4&5&\ldots&20\\ \lambda_n&1&1.31&1.49&1.62&1.71&&2.22\\ H_n&1&1.5&1.83&2.08&2.28&&3.66\\ \end{matrix}$$