# How to prove eigenvalues of specific block matrix are as proposed

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)  ## 1 Answer 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. • 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. – Anonymous Apr 11 at 22:00 • Also, the first set are the eigenvalues of$A-B$, not$A-KB$– Anonymous Apr 11 at 22:08 • 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. – Anonymous Apr 11 at 22:51
• Symmetry is not needed. – Robert Israel Apr 12 at 5:28
• could you look at a similar question I posted here? – Anonymous May 7 at 20:22