4
$\begingroup$

I have a block matrix of size $2N \times 2N$ of the form $$B = \begin{bmatrix} A_N & C_N \\ C_N & A_N \end{bmatrix}$$ where $A_N$ and $C_N$ are both $N \times N$ matrices. Specifically, $$A_N = \begin{bmatrix} 0 & \cdots & 1 \\ \vdots & \ddots & \vdots \\ 1 & \cdots & 0 \end{bmatrix} \qquad C_N = \begin{bmatrix} 1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 1 \end{bmatrix} $$ That is, $A_N$ has zeroes on the diagonal, and all other entries $1$; $C_N$ has zeroes along the minor diagonal, and all other entries are $1$.

I would like to find the eigenvalues of the matrix $B$.

$\endgroup$
2
  • 1
    $\begingroup$ Have you made any progress towards a solution yourself? Any insight that you have obtained would be useful. $\endgroup$ Aug 13, 2014 at 10:15
  • $\begingroup$ I known the eigenvalues, but i don't how to prove by theoretical. Also by row reduction we got second row of B is N x 2N zero matrix and that matrix have eigenvalues 1/2th of eigenvalues of B. $\endgroup$
    – Naveen
    Aug 14, 2014 at 4:13

2 Answers 2

4
$\begingroup$

I will answer your question just for the cases $N = 2$ and $N = 3$:

Let

$$ B_2 = \left( \begin{array}{cccc} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{array} \right), \quad B_3 = \left( \begin{array}{cccccc} 0 & 1 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \end{array} \right), $$

then, $\text{Spec}{(B_2)} = {(-2,2,0,0)} \, $ and $\text{Spec}{(B_3)} = (-2,-2,0,0,0,4). $

With the help of numerics, I've been able to show (at least for sufficiently large values of $N$) that the characteristic polynomial is given by:

$$\color{blue}{p(\lambda) =\det{(B_N - \lambda I_{2N})} = (\lambda - 2N +2)(\lambda+2)^{N-1} \lambda^N }$$

which tells you that the only eigenvalues of this kind of matrices are $-2,0,2N-2 \ $ with the corresponding multiplicities given by $p(\lambda)$.

Here is an animation showing the spectrum of the matrices $B_N$ for $N \in (2,30)$:

enter image description here


Here's the same approach in the case we have the $B_N$ matrices defined as:

$$B_N = \begin{bmatrix} C_N & A_N \\ A_N & C_N \end{bmatrix},$$

then:

$$\color{blue}{p(\lambda) =\det{(B_N - \lambda I_{2N})} = \left\{ \begin{array}{ll} \left(\lambda - 2N + 2\right) (\lambda-2)^{N/2}(\lambda+2)^{(N-2)/2} \lambda^{N} & N \text{ even} \\ \left(\lambda - 2N + 2\right) (\lambda-2)^{(N-1)/2}(\lambda+2)^{(N-1)/2} \lambda^{N} & N \text{ odd} \end{array}\right.}$$

which tells you that the only eigenvalues of this kind of matrices are $-2,0,2,2N-2 \ $ with the corresponding multiplicities given by $p(\lambda)$.

Here is another animation showing the spectrum of the matrices $B_N$ for $N \in (2,30)$:

enter image description here

pretty cool!

Hope somebody can shed some light on these results.

Cheers!

$\endgroup$
6
  • $\begingroup$ Are you sure? Maybe the error is in front of my eyes but I don't manage to spot it. $\endgroup$
    – Dmoreno
    Aug 13, 2014 at 11:17
  • $\begingroup$ Oh, I see it now. I totally misread the question. Then, it's completely wrong what I have posted and I will edit it as soon as possible. $\endgroup$
    – Dmoreno
    Aug 13, 2014 at 11:22
  • $\begingroup$ Edited! It's funny to see how the $\lambda = 2N-2$ eigenvalue stays unchanged when the definition of $B_N$ changes and how the $\lambda = 2$ eigenvalue rises up (or vanishes) in the second case. $\endgroup$
    – Dmoreno
    Aug 13, 2014 at 13:04
  • $\begingroup$ Thank you, your ans correct. I known the eigenvalues, but i don't how to prove by theoretical. I have another problem, i got B_N by deleting first row and column of the form [ 0 1 1 .... 1] and [0 1 1 ... 1]^t. So any idea to get eigenvalues of that matrix. I known deleting one row(k^th) and column(k^th), eigenvalues of second one lise between eigenvalues of first one by Cauchy interlacing theorem $\endgroup$
    – Naveen
    Aug 13, 2014 at 21:26
  • $\begingroup$ Also in you ans small mistake in B_4 matrix, first row is [0 1 1 1 1 0] and last row is [0 1 1 1 1 0]. So B_N unchanged for any N. $\endgroup$
    – Naveen
    Aug 14, 2014 at 4:06
1
$\begingroup$

A bit late, but still:

The $2N\times 2N$ matrix $B$ is the adjacency matrix of a $2N-2$-regular bipartite graph. Each row sums to the same value: $2N-2$. It thus follows that $2N-2$ is an eigenvalue with eigenvector $[1,\ldots,1]^{\top}$.

Since $B$ is symmetric, it possesses an orthogonal set of eigenvectors. Since we found one eigenvector ($[1,\ldots,1]^{\top}$), the remaining eigenvectors must be orthogonal to it, i.e., they must have entries summing to zero. One way is to take the $2N$-length vector with $N$ ones and $N$ minus ones as the eigenvector, and this gives the eigenvalue $2$. Finally, we can see that since there are repeated rows and columns in $B$, zero is an eigenvalue.

$\endgroup$

You must log in to answer this question.

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