2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Why are you interested in this question? $\endgroup$
    – user526015
    Commented Mar 8, 2019 at 9:33
  • $\begingroup$ @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. $\endgroup$
    – LiKao
    Commented Mar 8, 2019 at 9:40
  • $\begingroup$ @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. $\endgroup$
    – LiKao
    Commented Mar 8, 2019 at 9:48
  • 2
    $\begingroup$ Yes, I realised that and deleted my comment ;) $\endgroup$
    – user526015
    Commented Mar 8, 2019 at 9:51

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – LiKao
    Commented Mar 8, 2019 at 11:27

You must log in to answer this question.

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