In some of my work (statistics), I need the eigenvalues of a very large matrix. As such I would like to reduce it to a simpler problem and it seems entirely possible to me as the matrix has a very clear pattern/design with many things repeated. I think I have found a way to calculate the eigenvalues on smaller matrices that works numerically but I cannot prove to myself why it is true. I rewrote the problem in general below.

Problem: Suppose we have two symmetric matrices $A$ and $B$, both $\in \mathbb{R}^{c\times c}$. Consider a block matrix, $M$, of size $K\geq2$ with $A-B/K$ on the diagonal and $-B/K$ elsewhere. That is, the matrix can be written as $\left(I_K\otimes A\right) - \left(1_K1_K' \otimes \frac{1}{K}B \right)$ where $1_K$ is a column vector of size $K$ with all elements equal to 1 and $\otimes$ is the kronecker product. For example, when $K = 2$,

$$ M = \begin{pmatrix}A - B/2 & -B/2 \\ -B/2 & A- B/2\end{pmatrix} $$

Through some logical guesses and some luck, I believe the eigen-values of $M$ are (in no particular order or care given to the eigen-vectors) given by the $c$ eigen-values of $A - B$, each repeated $K-1$ times, and the $c$ eigen-values of $A$. Combined, this is $c(K-1) + c = cK$ eigen-values.

In my work $c$ is generally small and $K$ becomes very large. I've tried to prove this but haven't been able to. But is seems to work in every numerical situation I try. I also haven't found similar enough questions anywhere else. But I do believe it is true. Maybe I am missing something simple with the block structure of the matrix. I notice that this does not work when $A$ and $B$ are not symmetric.

Below is some R code if you would like to look at it and see it works numerically.

K <- 20
c <- 4
A <- matrix(rnorm(c^2), c, c)
A <- crossprod(A)
B <- matrix(rnorm(c^2), c, c)
B <- crossprod(B)
M <- (diag(K) %x% A) - tcrossprod(matrix(1, K)) %x% B/K
true <- sort(eigen(M, symmetric = TRUE)$values)
one <- eigen(A, symmetric = TRUE)$values
two <- eigen(A - B, symmetric = TRUE)$values
test <- sort(c(rep(one, each = K - 1), two))
all.equal(true, test)

Note that $M (1_K \otimes u) = 1_K \otimes ((A - K B) u)$. Thus the $c$ eigenvalues of $A - K B$ (counted by multiplicity) are eigenvalues of $M$. On the other hand, for $2 \le j \le K$ if $w$ is the column vector with $w_1 = 1$, $w_j = -1$ and $w_i=0$ otherwise, $M (w \otimes u) = w \otimes (Au)$. Thus the $c$ eigenvalues of $A$ are eigenvalues of $M$ with multiplicity $(K-1)$ times their multiplicities in $A$. That makes a total multiplicity of $nK$, so it accounts for all the eigenvalues.

  • $\begingroup$ where is the fact that $A$ and $B$ are symmetric used? It doesn't work when $B$ is not symmetric. I run some examples and it works when $A$ is not symmetric, but in my actual case both are. $\endgroup$ – Anonymous Apr 11 at 22:00
  • $\begingroup$ Also, the first set are the eigenvalues of $A-B$, not $A-KB$ $\endgroup$ – Anonymous Apr 11 at 22:08
  • $\begingroup$ Actually ignore that second comment, I apologize. I stated the question a little incorrectly (and edited it now). I meant $B/K$ wherever I put $B$ in constructing $M$. In that case what you put is correct, just changed to be the $c$ eigenvalues of $A-B$. I'm still unsure though where symmetry comes in. $\endgroup$ – Anonymous Apr 11 at 22:51
  • $\begingroup$ Symmetry is not needed. $\endgroup$ – Robert Israel Apr 12 at 5:28
  • $\begingroup$ could you look at a similar question I posted here? $\endgroup$ – Anonymous May 7 at 20:22

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.