1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user7530 Jul 25 '19 at 20:49
  • $\begingroup$ Where is this problem from? $\endgroup$ – Viktor Glombik Jul 25 '19 at 22:00
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How did you come up with the idea to use that specific test vector? $\endgroup$ – Viktor Glombik Jul 25 '19 at 21:53
  • $\begingroup$ @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! $\endgroup$ – J.G Jul 25 '19 at 21:58
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.