2
$\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$
  • 1
    $\begingroup$ Have you made any progress towards a solution yourself? Any insight that you have obtained would be useful. $\endgroup$ – Jonas Dahlbæk Aug 13 '14 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 '14 at 4:13
3
$\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$
  • $\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 '14 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 '14 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 '14 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 '14 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 '14 at 4:06
0
$\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$

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.