3
$\begingroup$

$$ A := \begin{pmatrix} 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 & \frac{1}{n}\\ \frac{1}{n} & \frac{1}{n} & \frac{1}{n} & \frac{1}{n} & \frac{1}{n} \end{pmatrix}$$

How to prove that all the eigenvalues of $A$ are less than $3 + 2 \sqrt{2}$?

This question is similar to this one.

I have tried the Cholesky decomposition $A = L^{T} L$, where

$$L^{T} = \left(\begin{array}{ccccc} 1 & 0 & 0 & \cdots & 0\\ \frac{1}{2} & \frac{1}{2} & 0 & \cdots & 0\\ \frac{1}{3} & \frac{1}{3} & \frac{1}{3} & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ \frac{1}{n} & \frac{1}{n} & \frac{1}{n} & \frac{1}{n} & \frac{1}{n} \end{array}\right)$$

then

$$(L^{T})^{-1}=\left(\begin{array}{ccccc} 1 & & & \cdots\\ -1 & 2 & & \cdots\\ & -2 & 3 & \cdots\\ \vdots & \vdots & \vdots & \ddots\\ & & & -(n-1) & n \end{array}\right)$$

$$A^{-1}=L^{-1}(L^{T})^{-1}$$

How to prove the eigenvalues of $A^{-1}$

$$\lambda_{i}\geq\frac{1}{3+2\sqrt{2}}$$

Further, I find that $A$ is the covariance matrix of Brownian motion at time $1, 1/2, 1/3, \ldots, 1/n$

Improve this question
$\endgroup$
1
  • $\begingroup$ It's positive definite, so all the eigenvalues are positive. $\endgroup$ Commented Jul 24, 2020 at 10:31

2 Answers 2

Reset to default
2
$\begingroup$

In this answer I show that the largest eigenvalue is bounded by $5< 3 + 2\sqrt{2}$. I will first use the interpretation of this matrix as the covariance matrix of the Brownian motion at times $(\frac{1}{n},\dots, 1)$ (I reversed the order so that the sequence of times is increasing, which is more natural for me).

We have $A_{ij} = \mathbb{E} (B_{t_{i}} B_{t_j})$. The largest eigenvalue will be the supremum over the unit ball of the expression $\langle x, A x\rangle$, which is equal to $\sum_{i,j} A_{ij} x_{i} x_{j}$. This is equal to $\mathbb{E} (\sum_{i=1}^{n} x_{i} B_{t_{i}})^2$. In order to exploit the independence of increments of the Brownian motion, we rewrite the sum $\sum_{i=1}^{n} x_i B_{t_{i}}$ as $\sum_{i=1}^{n} y_{i} (B_{t_{i}} - B_{t_{i-1}})$, where $y_{i}:= \sum_{k=i}^{n} x_{k}$ and $t_0:=0$. Thus we have

$ \mathbb{E} (\sum_{i=1}^{n} x_{i} B_{t_{i}})^2 = \sum_{i=1}^{n} y_{i}^2 (t_{i}-t_{i-1}). $

The case $i=1$ is somewhat special and its contribution is $\frac{y_1^2}{n} \leqslant \sum_{k=1}^{n} x_{k}^2 = 1$. For the other ones we have $t_{i} - t_{i-1} = \frac{1}{(n-i+1)(n-i+2)}\leqslant \frac{1}{(n-i+1)^2}$. At this point, to get a nicer expression, I will reverse the order again by defining $z_{i}:= y_{n-i+1}$. So we want to estimate the expression

$ \sum_{i=1}^{n} \left(\frac{z_i}{i}\right)^2. $

We can now use use Hardy's inequality to bound it by $4 \sum_{i=1}^{n} x_{i}^2 =4$. So in total we get 5 as an upper bound, if I haven't made any mistakes.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Brilliant. Thank you very much. But why $y_1$ is special? Can't we get 4 as upper bound? $\endgroup$ Commented Jul 23, 2020 at 14:42
  • 1
    $\begingroup$ The $i=1$ case is special because $t_1 - t_0 = \frac{1}{n}$, which is not quadratic like the other differences. $\endgroup$ Commented Jul 23, 2020 at 15:06
  • $\begingroup$ Thank you so much. I have spent much time trying to prove it through linear algebra, but failed. We get L through Cholesky decomposition, and (Lx)'(Lx) is hard to deal with. $\endgroup$ Commented Jul 24, 2020 at 10:36
0
$\begingroup$

Inspired by @Mateusz Wasilewski I find another method.

\begin{eqnarray*} \langle x,Ax\rangle & = & \langle Lx,Lx\rangle\\ & = & \sum_{i=1}^{n}u_{i}^{2} \end{eqnarray*}

where $u_{i}=\sum_{j=i}^{n}\frac{1}{j}x_{j}$.

\begin{eqnarray*} \sum_{i=1}^{n}u_{i}^{2} & = & \sum_{i=1}^{n}(\sum_{k=i}^{n}b_{k})^{2}\quad(\text{where} \ b_{k}=\frac{1}{k}x_{k})\\ & = & \sum_{i=1}^{n}(\sum_{k=i}^{n}b_{k}^{2}+2\sum_{k>j\geq i}b_{k}b_{j})\\ & = & \sum_{k=1}^{n}\sum_{i=1}^{k}b_{k}^{2}+2\sum_{j=1}^{n-1}\sum_{k=j+1}^{n}\sum_{i=1}^{j}b_{k}b_{j}\\ & = & \sum_{k=1}^{n}\frac{x_{k}^{2}}{k}+2\sum_{j=1}^{n-1}\sum_{k=j+1}^{n}b_{k}x_{j}\\ & = & \sum_{k=1}^{n}\frac{x_{k}^{2}}{k}+2\sum_{k=2}^{n}\sum_{j=1}^{k-1}b_{k}x_{j}\\ & = & \sum_{k=1}^{n}\frac{x_{k}^{2}}{k}+2\sum_{k=2}^{n}b_{k}z_{k-1}\\ & = & x_1^2 +\sum_{k=2}^{n}\frac{(z_{k}-z_{k-1})^{2}}{k}+2\sum_{k=2}^{n}\frac{(z_{k}-z_{k-1})}{k}z_{k-1}\\ & = & x_{1}^{2}+\sum_{k=2}^{n}\frac{z_{k}^{2}-z_{k-1}^{2}}{k}\\ & = & \sum_{k=1}^{n}\frac{z_{k}^{2}}{k}-\sum_{k=1}^{n-1}\frac{z_{k}^{2}}{k+1}\\ & = & \sum_{k=1}^{n-1}z_{k}^{2}(\frac{1}{k}-\frac{1}{k+1})+\frac{z_{n}^{2}}{n} \end{eqnarray*}

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.