4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – JimmyK4542
    Aug 27, 2018 at 3:46

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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.