# Largest eigenvalue of finite band random matrices

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.

– Mick
Aug 8 '20 at 5:51
• Obvious comment: $\max_i X_i + X_{i+1}$ is an upper bound for the spectral radius, as it is the maximum row sum. Aug 8 '20 at 12:28
• one answer at math.stackexchange.com/a/1603016/87355 Aug 8 '20 at 14:25
• @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... Aug 12 '20 at 19:52
• @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)$$ Aug 17 '20 at 16:42

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