Bound on eigenvalues of block matrix made up of negative semi-definite blocks

I have a block matrix, $$M= L-I$$, where $$L$$ takes the form, $$L= \begin{bmatrix} 0 & L_2& \ldots & L_M \\ L_1 &0 &\ldots & L_M \\ \vdots & \vdots & \ddots & \vdots \\ L_1 & L_2& \ldots& 0 \end{bmatrix}$$ and $$I$$ is an appropriately sized identity matrix. The $$L_m$$ are all negative semi-definite with one eigenvalue $$\lambda_1 = -\frac{1}{2}$$ and another eigenvalue $$-\frac{1}{2}< \lambda_2 <0$$ (Edit: the exact value depends on the matrix, so this one might be different for each block). Some of the $$L_m$$ may not be full rank and thus have some additional eigenvalues $$\lambda_3 =0$$ reducing the multiplicity of $$\lambda_2$$.

I can see numerically that the largest positive eigenvalue of $$L$$ is $$\frac{1}{2}$$ and thus the largest eigenvalue of $$M$$ in nonabsolute terms is $$-\frac{1}{2}$$.

Is there a way to prove this numerical result based on the known eigenvalues of the $$L_m$$ and the structure of $$L$$?

Thank you!

Edit: $$\lambda_i$$ for $$i =1,2,3$$ are the only eigenvalues for the $$L_i$$. $$\lambda_3=0$$ may not be an eigenvalue of all $$L_i$$, but those $$L_i$$ that have $$\lambda_3$$ as an eigenvalue are not invertible as some of the rows and corresponding columns are all zero.

• Are the $L_k$ symmetrical or not ? Commented Apr 25, 2023 at 13:03
• Yes, they are symmetric. Commented Apr 25, 2023 at 13:12
• Are $\lambda_1$ and $\lambda_2$ respectively the smallest and the second smallest eigenvalues? Can some $\lambda_i$ less than $\lambda_1$ or lie between $\lambda_1$ and $\lambda_2$? Commented Apr 26, 2023 at 9:58

It isn't clear whether the $$L_i$$s have the same size and whether their eigenvalues are arranged in ascending order or not. I suppose that they have identical sizes, $$-\frac{1}{2}I\preceq L_i\preceq0$$ and $$\lambda_\min(L_i)=-\frac12$$ for each $$i$$.

Suppose each $$L_i$$ is $$N\times N$$. Let $$P=\operatorname{diag}(\sqrt{-2L_1},\sqrt{-2L_2},\ldots,\sqrt{-2L_M})$$ and let $$e\in\mathbb C^M$$ be the vector of ones. Then $$L=\left[(ee^T-I_M)\otimes I_N\right](-\frac{P^2}{2})$$. Therefore $$\lambda_j(L) =\frac12\lambda_j(\left[(I_M-ee^T)\otimes I_N\right]P^2) =\frac12\lambda_j(P\left[(I_M-ee^T)\otimes I_N\right]P).$$ Now, suppose that each $$L_i$$ is negative definite. Then $$P$$ is invertible and $$\|P\|_2=1$$. Since $$P\left[(I_M-ee^T)\otimes I_N\right]P$$ is congruent to $$P\left[(I_M-ee^T)\otimes I_N\right]P$$, precisely $$(M-1)N$$ of its eigenvalues are positive and the rest are negative. That is, if we arrange the eigenvalues of $$L$$ in ascending order, we have $$\lambda_1(L)\le\cdots\le\lambda_N(L)<0<\lambda_{N+1}(L)\le\cdots\le\lambda_{MN}(L)$$ and $$\lambda_{MN}(L)=\lambda_\max(L)=\frac12\lambda_\max(P\left[(I_M-ee^T)\otimes I_N\right]P).$$ Let $$x$$ be a unit eigenvector corresponding to the maximum eigenvalue of $$P\left[(I_M-ee^T)\otimes I_N\right]P$$. Then \begin{aligned} 0&<\frac12\lambda_\max(P\left[(I_M-ee^T)\otimes I_N\right]P)\\ &=\frac12x^TP\left[(I_M-ee^T)\otimes I_N\right]Px\\ &=\frac12\|Px\|_2^2\left(\frac{Px}{\|Px\|_2}\right)^T\left[(I_M-ee^T)\otimes I_N\right]\left(\frac{Px}{\|Px\|_2}\right)\\ &\le\frac12\left(\frac{Px}{\|Px\|_2}\right)^T\left[(I_M-ee^T)\otimes I_N\right]\left(\frac{Px}{\|Px\|_2}\right)\\ &\le\frac12\max_{\|y\|_2=1}y^T\left[(I_M-ee^T)\otimes I_N\right]y\\ &=\frac12\lambda_\max\left[(I_M-ee^T)\otimes I_N\right]\\ &=\frac12. \end{aligned} It follows that $$0<\lambda_\max(L)\le\frac12$$ when the $$L_i$$s are negative definite. Since the eigenvalues of a matrix is a continuous function of matrix entries and every negative semidefinite matrix is the limit of a sequence of negative definite matrices, by a continuity argument, when the $$L_i$$s are negative semidefinite, we obtain $$0\le\lambda_\max(L)\le\frac12$$ and $$\lambda_1(L)\le\cdots\le\lambda_N(L)\le0\le\lambda_{N+1}(L)\le\cdots\le\lambda_{MN}(L)\le\frac12.$$

• [+1] We have common points of departure, but I hadn't in particular neither thought to use Sylvester's law of inertia for the signs of the eigenvaluee, nor to the min-max characterization of eigenvalues through Rayleigh quotients. Commented Apr 26, 2023 at 12:56
• This is extremely elegant and helpful. Apologies for not having been precise enough (see edit). $P$ is not invertible and the congruency does not hold, but if I followed your proof correctly that should not be too much of an issue as then there might simply be some other eigenvalues $\lambda_j<\lambda_{max} \leq 1/2$ all of which may be positive or negative but less than 1/2? If so I will happily mark this as correct! Thanks again! Commented Apr 28, 2023 at 17:41
• @bast3456 Please see my new edit. I have also corrected a minor mistake in my previous edit. Commented Apr 29, 2023 at 3:18
• @user1551 that is great - thanks a bunch! Just for my understanding: if I was only interested in showing that the largest eigenvalue is less than 1/2 (regardless if positive or not), would your initial proof (without the congruency argument) been sufficient? Or did I miss something, why the congruency argument would be necessary also for that? Commented Apr 30, 2023 at 10:12
• @bast3456 The use of matrix congruence is not necessary, but then I need to justify that $L$ or $P\left[(I_M-ee^T)\otimes I_N\right]P$ has at least one nonnegative eigenvalue in some other ways. E.g. since $L$ is traceless and similar to a symmetric matrix, it has a real spectrum and its maximum eigenvalue is nonnegative. Commented May 1, 2023 at 8:26

(Too long for a comment)

Let blocks $$L_k$$ have dimension $$n \times n$$.

The issue can be reduced to the study of $$L$$, because the spectrum of $$L-I$$ (where $$I=I_{Mn}$$) is obtained by shifting the spectrum of $$L$$.

$$L$$ can be written under the form of a product :

$$L=\underbrace{\begin{pmatrix}0& I & I &\cdots &I&I\\ I&0&I &\cdots&I& I\\ \cdots &&& \cdots \\ I&I&I &\cdots& 0&I\\ I&I&I& \cdots & I & 0\end{pmatrix}}_A\underbrace{\begin{pmatrix}L_1& 0 & 0 &\cdots &0&0\\ 0&L_2&0 &\cdots&0& 0\\ \cdots &&& \cdots \\ 0&0&0 &\cdots& L_{M-1}&0\\ 0&0&0& \cdots & 0 & L_M\end{pmatrix}}_B\tag{1}$$

(where $$I=I_n$$), with $$B$$ (symmetrical) negative semi-definite.

Besides, on can write $$A=I \otimes C$$ (Kronecker product) where :

$$C:=\begin{pmatrix}0& 1 & 1 &\cdots &1&1\\ 1&0&1 &\cdots&1& 1\\ \cdots &&& \cdots \\ 1&1&1 &\cdots& 0&1\\ 1&1&1& \cdots & 1 & 0\end{pmatrix}=\mathbf{11^T}-I_{M}$$

[$$\mathbf{1}$$ is the $$M \times 1$$ column vector with all $$1$$ entries.]

• $$C$$ has a known spectrum : $$\underbrace{-1,-1, \cdots -1}_{n-1 \ \text{times}},(n-1)$$.

As a consequence, the spectrum of $$A=I \otimes C$$ is the same (product of their resp. eigenvalues), with a multiplicity of each eigenvalue multiplied by $$n$$...

• Besides, the spectrum of $$L$$ is the union of the spectra of all the $$L_k$$.

I post these thoughts knowing that they are far from solving the question.

Edit : Some more "thoughts" :

• If each $$L_k$$ is diagonalizable, one can write $$B=D\Lambda D^T$$ for a certain block-diagonal matrix $$D$$.

• Product (1) : $$L=AB$$ can advantageously be transformed into $$L=(-A)(-B)$$ representing that I will write $$L=A_1B_1$$ where $$B_1$$ is positive semi-definite.

• Using the concept of square root for a positive semi-definite matrix (see here), $$L=A_1B_1=A_1\sqrt{B_1}\sqrt{B_1}$$ has the same spectrum as

$$C=\sqrt{B_1}A_1\sqrt{B_1}=\sqrt{B_1}^TA_1\sqrt{B_1}\tag{2}$$

(due to property spectrum($$MN$$)=spectrum($$NM$$)), matrix $$C$$ given by (2) being equivalent (recall : $$A \$$ vs. $$\ Q^{-1}AP$$) but not similar (recall : $$A \$$ vs. $$\ P^{-1}AP$$) to matrix $$A_1$$ which would have help towards a conclusion.