Upper bound on the largest eigenvalue of a block matrix

Question

I would like to derive an upper bound on the largest eigenvalue of the following matrix in terms of the dimension of $X$ which is 5 and the dimension of the sub-matrix of zeros which is 2. \begin{equation} X= \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ \end{pmatrix} \end{equation} In general, say we have an $n \times n$ matrix of ones. Define a matrix $X$ by subtracting an $m \times m$ matrix of ones with $m<n$ from the last $m$ columns and rows of the original matrix. Is there an upper bound on the largest eigenvalue of $X$ in terms of $m$ and $n$?

Answer 1

You can exactly find the nonzero eigenvalues in terms of $n$ and $m$. Note that there are two of them as this is a rank two matrix. We will use test vectors of the form $(ax,ax,\ldots,ax,x,\ldots,x)$, where there are $n-m$ copies of $ax$, $m$ copies of $x$, and where $x$ will be a nonzero indeterminate. The eigenvalue equations give \begin{gather} (n-m)ax+mx=\lambda ax\\ (n-m)ax=\lambda x. \end{gather} The second equation says we need $a=\lambda/(n-m)$. If we do this, the first equation solves to the following quadratic \begin{equation} \lambda +m=\lambda^2/(n-m)\iff \lambda^2-(n-m)\lambda-m(n-m). \end{equation} The quadratic formula yields \begin{equation} \lambda=\frac{(n-m)\pm\sqrt{(n-m)^2+4m(n-m)}}{2}. \end{equation} You can verify that this holds for your specific instance, yielding $\lambda_1=\frac{3+\sqrt{33}}{2}$.

Answer 2

Let $\ A\ $ and $\ B\ $ be the $\ (n-m)\times (n-m)\ $ and $\ m\times m\ $ matrices of ones, respectively. If $\ z\ $ is an eigenvector of $\ \pmatrix{A & B\\ B^\top& 0}\ $, with $\ x=\pmatrix{z_1\\z_2\\ \vdots\\z_{n-m}}\ $ and $\ y=\pmatrix{z_{n-m+1}\\z_{n-m+2}\\ \vdots\\z_n} \ $, corresponding to eigenvalue $\ \lambda\ $, then

$$ \pmatrix{A & B\\ B^\top& 0}\pmatrix{x\\y}=\lambda\pmatrix{x\\y}\ . $$ Now if $\ S_x=\sum_\limits{i=1}^{n-m}x_i\ $ and $\ S_y=\sum_\limits{i=1}^m y_i\ $, then it follows from the above matrix equation that $$ \begin{array}{rcr} \left(n-m-\lambda\right)S_x &+&\left(n-m\right) S_y &=& 0 &\mbox{and}\\ mS_x &-&\lambda S_y &=& 0 \end{array} $$ These equations have non-zero solutions for $\ S_x\ $ and $\ S_y\ $ if and only if $\ -\lambda\left(n-m-\lambda\right)-m\left(n-m\right)=0\ $, which has solutions $$ \lambda = \frac{n-m\pm\sqrt{\left(n-m\right)^2 +4m\left(n-m\right)}}{2}\ . $$ On the other hand, if $\ S_x=S_y=0\ $, then since $\ z\ne 0\ $, it follows from the above matrix equation that $\ \lambda = 0\ $. Thus, $\ \lambda = 0\ $ and $\displaystyle\lambda=\frac{n-m\pm\sqrt{\left(n-m\right)^2 +4m\left(n-m\right)}}{2}\ $ are the only eigenvalues.