# Finding the eigenvalues of a matrix with very regular block structure

I have a matrix $$W$$ that can be described by the following block structure

$$W=\begin{pmatrix} 0_n & sC\\ sC^T & f(I_m-J_m) \end{pmatrix}$$

where

• $$J_m$$ is an $$m \times m$$ matrix only made up of ones

• $$0_n$$ is the $$n \times n$$ zero matrix

• $$I_m$$ is the $$m \times m$$ identity matrix

• $$C$$ is an $$n \times m$$ matrix whose entries are $$\pm 1$$

• $$f > 0$$ and $$s > 0$$ are real numbers.

So, this matrix has a highly regular structure. Most importantly, it is symmetric, so I know it must have $$n+m$$ real eigenvalues and eigenvectors. Are there any results, that could help me find the eigenvalues (and hopefully also the eigenvectors) of this kind of matrix?

If I directly try to compute the characteristic polynomial, this gets very messy, even though this matrix has this regular structure. The best I can do is simplify the expression

$$\det(W-\lambda I_{n+m})=\det\begin{pmatrix} -\lambda I_n & sC\\ sC^T & (f-\lambda)I_m-fJ_m) \end{pmatrix}$$

using the equivalence

$$\det\begin{pmatrix} A & B\\ C & D\end{pmatrix} = \det(A) \det(D-CA^{-1}B)$$

if $$A$$ is invertible, to write

$$\det(\lambda f(I_m-J_m)-\lambda^2I_m-s^2C^TC)=0$$

as an equation for the non-zero eigenvalues of $$W$$. But I fail to simplify this any further.

EDIT:

The reason I am interested in this, is to understand quadratic forms like $$x^T\; W\; D\;x$$, where $$D$$ is some positive diagonal matrix (or even $$0\leq d_i\leq 1$$. I am mostly interested in upper or lower bounds of these expressions.

• Why are you interested in this question?
– user526015
Mar 8, 2019 at 9:33
• @James This matrix defines the connection structure of a neural network model used in cognitive modeling. I am interested in two things, where the eigenvalues are needed: 1) providing upper and lower bounds on quadratic forms such as $x^T\;W\;D\;x$ where $D$ is a diagonal matrix with only positive entries. 2) Solving the linear ODE $\frac{d\;X}{d\;t}=W\;x+V$ for some vector $V$ with $v_i\geq 0$. The eigenvalues/eigenvectors are required for both. Mar 8, 2019 at 9:40
• @James Factoring $\lambda^2-s^2$ I get $(\lambda-s)(\lambda+s)$, so in the example I get eigenvalues $\pm s$ and not $\pm \sqrt{s}$, which are real. Since $W$ is symmetric and real, I can actually apply the spectral theorem "If A is Hermitian, there exists an orthonormal basis of V consisting of eigenvectors of A. Each eigenvalue is real." en.wikipedia.org/wiki/… So unless I really messed up something in the definition, all eigenvalues should be real. Mar 8, 2019 at 9:48
• Yes, I realised that and deleted my comment ;)
– user526015
Mar 8, 2019 at 9:51

This doesn't provide an answer but was way too long for a comment and contains an extended example that can give relevant insights in the problem so I decided to post it anyway.

Let us consider the simplest case of $$m=n=1$$. Out matrix then becomes $$\begin{pmatrix}0&sC\\ sC^T &0\end{pmatrix}.$$ Note that $$C=\pm 1$$ We may then calculate the characteristic polynomial to $$p(\lambda)=\lambda^2-s^2C^TC=\lambda^2-s^2$$ and the eigenvalues are $$\pm s$$.

Now the next more complicated case when $$m=n=2$$. The matrix becomes $$\begin{pmatrix}\begin{pmatrix}0&0\\ 0& 0\end{pmatrix} & sC \\ sC^T &f\begin{pmatrix}0 &-1\\ -1 &0\end{pmatrix}\end{pmatrix}.$$ Since $$m=n$$, we can use the formula $$\det\begin{pmatrix}A & B\\ C& D\end{pmatrix}=\det(AD-BC)$$ and we obtain $$p(\lambda)=\det\left(f\begin{pmatrix}-\lambda & 0\\ 0 & -\lambda\end{pmatrix}\begin{pmatrix}-\lambda & -1 \\ -1 &-\lambda\end{pmatrix}-s^2C^TC\right)\\ =\det\left(f\begin{pmatrix}\lambda ^2 & \lambda\\ \lambda & \lambda ^2\end{pmatrix}-s^2C^TC\right).$$ What can we have for $$C^TC$$? Let us write $$C=(c_{i,j})$$ with $$c_{i,j}=\pm 1$$. Then, $$p(\lambda)=\det\begin{pmatrix}f\lambda^2-s^2(c_{1,1}^2+c_{1,2}c_{2,1})& f\lambda-s^2(c_{1,1}c_{1,2}+c_{1,2}c_{2,2})\\ f\lambda-s^2(c_{2,1}c_{1,1}+c_{2,2}c_{1,2})& f\lambda^2-s^2(c_{2,1}c_{1,2}+c_{2,2}^2)\end{pmatrix}\\ =(f\lambda^2-s^2(c_{1,1}^2+c_{1,2}c_{2,1}))(f\lambda^2-s^2(c_{2,1}c_{1,2}+c_{2,2}^2))-(f\lambda-s^2(c_{1,1}c_{1,2}+c_{1,2}c_{2,2}))(f\lambda-s^2(c_{2,1}c_{1,1}+c_{2,2}c_{1,2}))\\=f^2\lambda^4-f\lambda^2s^2(c_{1,1}^2+2c_{1,2}c_{2,1}+c_{2,2}^2)+s^4(c_{1,1}^2c_{2,1}c_{2,2}+c_{1,1}^2c_{2,2}^2+c_{1,2}^2c_{2,1}^2+c_{1,2}c_{2,1}c_{2,2}^2)-(f^2\lambda^2-f\lambda s^2(c_{1,1}c_{1,2}+c_{1,2}c_{2,2}+c_{2,1}c_{1,1}+c_{2,2}c_{1,2})+s^4(c_{1,1}^2c_{1,2}c_{2,1}+c_{1,2}^2c_{1,1}c_{2,2}+c_{1,2}c_{2,1}c_{1,1}c_{2,2}+c_{1,2}^2c_{2,2}^2)).$$ Each $$c_{i,j}^2=1$$ so that we obtain $$p(\lambda)=f^2\lambda^4-2f\lambda^2s^2(1+c_{1,2}c_{2,1})+s^4(2+c_{2,1}c_{2,2}+c_{1,2}c_{2,1})-f^2\lambda^2+f\lambda s^2(c_{1,1}c_{1,2}+2c_{1,2}c_{2,2}+c_{2,1}c_{1,1})-s^4(1+c_{1,2}c_{2,1}+c_{1,1}c_{2,2}+c_{1,2}c_{2,1}c_{1,1}c_{2,2})\\ =f^2\lambda^4-f^2\lambda^2-2f\lambda^2s^2a+f\lambda s^2b+s^4c,$$ where $$a=1+c_{1,2}c_{2,1},\\ b=c_{1,1}c_{1,2}+2c_{1,2}c_{2,2}+c_{2,1}c_{1,1},\\ c=2+c_{2,1}c_{2,2}+c_{1,2}c_{2,1}-(1+c_{1,2}c_{2,1}+c_{1,1}c_{2,2}+c_{1,2}c_{2,1}c_{1,1}c_{2,2})=1+c_{2,1}c_{2,2}-c_{1,1}c_{2,2}-c_{1,2}c_{2,1}c_{1,1}c_{2,2}.$$ At this point, a case-by-case study on the possible values for the $$c_{i,j}$$'s is needed. Let me work out the cases when all of them are one.

Then, $$a=2, b=4, c=0$$ and $$p(\lambda)=f^2\lambda^4-f^2\lambda^2-4s^2f^2\lambda^2+4fs^2\lambda.$$ One eigenvalue is zero and after dividing out by the corresponding linear factor, we want to find the roots of $$q(\lambda)=f^2\lambda^3-(f^2-4s^2f^2)\lambda+4fs^2.$$ None of the roots is immediate so it is hard to go on from here.

In the case when all entries of $$C$$ are minus one, $$a=2, b=4, c=0$$, just as we had before.

If $$c_{1,1}=c_{2,2}=1$$, $$c_{1,2}=c_{2,1}=-1$$, $$a=2, b=-4, c=0$$ which again looks just like before.

You can analyse this situation further but my impression is that we can't say more than that $$\lambda=0$$ might always be an eigenvalue. If you can, write a little program that tests for you all possible cases for $$C$$.

• Yes, it is easy to prove that $\lambda=0$ is an eigenvalue in many cases. If $n>m$ then $rank(C)\leq m$ so the matrix $W$ is rank deficient and therefore $\lambda = 0$ is an eigenvalue. I am still looking for a proof that it is also rank deficient when $n_0\geq n\geq m$ for some $n_0$, because that would already tell me a lot about the existence of extrema of $x^T W x$. Mar 8, 2019 at 11:27