10
$\begingroup$

Let $\mathbf{M}_n$ be an $n \times n$ symmetric matrix $$ \mathbf{M}_n = \begin{cases} X_{j-i,i}\ &\text{if }i\leq j\leq r+i\\ 0\ &\text{if }r+i< j\leq n\end{cases} $$ for some fixed $r>0$, and the random variables $\{X_{i,j}\}$ are assumed real, positive, i.i.d., and have finite mean and variance.

As an example, for $r=1$ and $n=4$ we have,

$$\mathbf{M}_4 = \begin{pmatrix} X_{0,1} & X_{1,1} & 0 & 0\\ X_{1,1} & X_{0,2} & X_{1,2} & 0 \\ 0 & X_{1,2} & X_{0,3} & X_{1,3} \\ 0 & 0 & X_{1,3} & X_{0,4} \end{pmatrix}$$

I was wondering if something is known about the asymptotic of $\lambda_1(\mathbf{M}_n)$, i.e., the largest eigenvalue of $\mathbf{M}_n$, in the limit $n \to \infty$. In particular, is something is known about the deviation of $\lambda_1(\mathbf{M}_n)$ from its mean, i.e., $$ \Pr\left[|\lambda_1(\mathbf{M}_n)-\mathbb{E}\lambda_1(\mathbf{M}_n)|\geq t\right]\leq ? $$ I was wondering whether there is a general concentration bound, e.g., for non-identical matrices, which subsumes the above case.

$\endgroup$
7
  • $\begingroup$ google.com/url?sa=t&source=web&rct=j&url=http://… maybe this helps $\endgroup$
    – Mick
    Aug 8 '20 at 5:51
  • 2
    $\begingroup$ Obvious comment: $\max_i X_i + X_{i+1}$ is an upper bound for the spectral radius, as it is the maximum row sum. $\endgroup$ Aug 8 '20 at 12:28
  • 2
    $\begingroup$ one answer at math.stackexchange.com/a/1603016/87355 $\endgroup$ Aug 8 '20 at 14:25
  • 1
    $\begingroup$ @J.John : Well, what I wanted to use here is a simple remark that as the matrix is symmetric, its (spectral) norm exceeds the norm of any of its principal minors. So if the law is upper-bounded by $M$, for a large enough matrix there will be somewhere a large length $k$ subsequence $X_j\approx M, \, j=m,...,m+k$, and the norm of such a submatrix is $\approx 2M$. But this is not what you want to use for unbounded distributions... $\endgroup$ Aug 12 '20 at 19:52
  • 1
    $\begingroup$ @J.John: yes, there is. As the matrix is a symmetric one with positive elements, its maximal eigenvalue = its spectral radius = its $\ell_2$-norm, and the corresponding eigenvector has nonnegative elements. So take such a unit-length eigenvector $v$ for $L_k$, and you get $$\lambda_{\max}(M_k)\ge (v,M_k v) \ge (v,L_k v) = \lambda_{max}(L_k)$$ $\endgroup$ Aug 17 '20 at 16:42
2
$\begingroup$

I start with this simple remark: the tridiagonal matrix $$A_k=\begin{pmatrix}0 & 1 & & & \\ 1 & 0 & 1 & & \\ & 1 & 0 & \ddots & \\ & & \ddots & & 1 \\ & & & 1 & 0\end{pmatrix}$$, $A_k\in \mathbb{R}^{(k+1)\times (k+1)}$ have largest eigenvalue $\lambda_\max (A_k) =2\cos{\frac{\pi}{k+2}}$.

We will focus on the submatrices with large entries of $M_n$. When there are $k$ consecutive large entries :$ \forall i\leq k$ $X_{a+i}\geq C $ for some $a$, we will assume that $X_{a+i} = C$ for all $i$ and write $CA_k$. This is obiously not true but it is just to simplify the discussion. We then have $$ M_n = \begin{pmatrix}\ddots & \\ & C_1A_{k_1} \\ & & \ddots \\ & & & C_2 A_{k_2} \\ & & & & \ddots \\ & & & & & . \end{pmatrix} $$ where $\ddots$ have small entries (let say $\mathcal{O}(1)$) and $C_i\gg 1$. The largest eigenvalue will come from these submatrices $$\lambda_\max (M_n) \approx \max_j \lambda_{\max}(C_j A_{k_j})=\max_j 2 C_j\cos(\frac{\pi}{k_j+2})$$

For large $n$ the behaviour will depend on the tail of the random variable $X_1$.

We first consider the case of polynomial tail : $\mathbb{P}(X \geq K)\sim \frac{1}{K^\alpha}$.

For any $k$, $\lambda_{\max}(C A_{k})\geq K\Leftrightarrow C \geq \frac{K}{2\cos(\frac{\pi}{k+2})}$ and we estimate $$\mathbb{P}(\forall i\leq k, X_k \geq \frac{K}{2\cos(\frac{\pi}{k+2})}) = \Big(\frac{2\cos(\frac{\pi}{k+2})}{K} \Big)^k$$ For $K\rightarrow \infty$, one can see that the case $k=1$ have the much larger probability and we deduce that in this situation it is enougth to consider only $k=1$ submatrices. Conclusion for polynomial tail we have $$\lambda_\max (M_n) \approx \max_j X_j \sim n^{1/\alpha}$$ (Because there are $n$ iid $X_j$, we set $K=n^{1/\alpha}$ such that $\mathbb{P}(X_1 \geq K)=\frac{1}{n}$).

We now consider the case of exponential tail : $\mathbb{P}(X \geq K)\sim \exp(-\gamma K)$.

We estimate $$\mathbb{P}\Big(\forall i\leq k, X_k \geq \frac{K}{2\cos(\frac{\pi}{k+2})}\Big) = \exp\Big(-\frac{\gamma k K}{2 \cos(\frac{\pi}{k+2})} \Big)$$ Still here for $K\rightarrow \infty$, the case $k=1$ have the much larger probability. Conclusion for exponential tail we have $$\lambda_\max (M_n) \approx \max_j X_j \sim \frac{\log(n)}{\gamma}$$ (we set $K$ such that $\mathbb{P}(X_1 \geq K)=\frac{1}{n}$).

We continue with the case of sup-exponential tail : $\mathbb{P}(X \geq K)\sim \exp(-K^\gamma)$.

We have $$\mathbb{P}\Big(\forall i\leq k, X_k \geq \frac{K}{2\cos(\frac{\pi}{k+2})}\Big) = \exp\Big(-\frac{ k }{2^\gamma \cos(\frac{\pi}{k+2})^\gamma}K^\gamma \Big)$$ Here there is a $k^*$ that maximize $\frac{k}{\cos(\frac{\pi}{k+2})^\gamma}$ which have the much larger probability for $K\rightarrow \infty$. We also set $K$ such that this event is of order $1/n$ and then for sup-exponential tail we have $$\lambda_\max (M_n) \sim \frac{2\cos(\frac{\pi}{k^*+2})}{(k^*)^\frac{1}{\gamma}}\log(n)^{\frac{1}{\gamma}}$$

Finally in case of bounded $X$, for any $\epsilon>0$, and $k$, we can find $a$ such that $\forall i\leq k, X_{a+i}\geq \|X\|_\infty-\epsilon$ with probability that goes to $1$ as $n\rightarrow \infty$. Then $$2 \|X\|_\infty \geq \lambda_\max (M_n) \geq 2 (\|X\|_\infty-\epsilon) \cos(\frac{\pi}{k+2}) $$ and we get $\lambda_\max (M_n) \rightarrow 2 \|X\|_\infty$.

$\endgroup$
0

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.