2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Are the $L_k$ symmetrical or not ? $\endgroup$
    – Jean Marie
    Commented Apr 25, 2023 at 13:03
  • $\begingroup$ Yes, they are symmetric. $\endgroup$
    – bast3456
    Commented Apr 25, 2023 at 13:12
  • $\begingroup$ 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$? $\endgroup$
    – user1551
    Commented Apr 26, 2023 at 9:58

2 Answers 2

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ [+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. $\endgroup$
    – Jean Marie
    Commented Apr 26, 2023 at 12:56
  • $\begingroup$ 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! $\endgroup$
    – bast3456
    Commented Apr 28, 2023 at 17:41
  • $\begingroup$ @bast3456 Please see my new edit. I have also corrected a minor mistake in my previous edit. $\endgroup$
    – user1551
    Commented Apr 29, 2023 at 3:18
  • $\begingroup$ @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? $\endgroup$
    – bast3456
    Commented Apr 30, 2023 at 10:12
  • 1
    $\begingroup$ @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. $\endgroup$
    – user1551
    Commented May 1, 2023 at 8:26
1
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .