# Upper bound on the largest eigenvalue of a block matrix

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

• Well, there is an obvious bound $n-m \leq \lambda_1 \leq n,$ but I wouldn't be surprised if $\lambda_1$ has a closed-form formula for this special matrix. – user7530 Jul 25 '19 at 20:49
• Where is this problem from? – Viktor Glombik Jul 25 '19 at 22:00

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}$$.
• @ViktorGlombik I think trying vectors where the first $n-m$ coordinates are the same and the last $m$ coordinates are the same is natural, and being completely honest I used a calculator online to see the pattern! – J.G Jul 25 '19 at 21:58
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.