14
$\begingroup$

The question is related to the eigenvalue problem. Using MAPLE, I calculated the following determinants:

$\begin{align} \begin{vmatrix} -\lambda & 1 \\ 1 & -\lambda \\ \end{vmatrix}&=\lambda^2-1\\ \begin{vmatrix} -\lambda & 1 & 0 \\ 1& -\lambda & 1 \\ 0& 1 & -\lambda \\ \end{vmatrix}&=-\lambda^3+2\lambda\\ \begin{vmatrix} -\lambda & 1 &0 &1 \\ 1& -\lambda & 1 &0 \\ 0& 1& -\lambda & 1 \\ 1& 0& 1& -\lambda \\ \end{vmatrix}&=\lambda^4-4\lambda^2\\ \begin{vmatrix} -\lambda &1 &0 &1 &0 \\ 1& -\lambda &1 &0 &1 \\ 0& 1& -\lambda &1 &0 \\ 1& 0& 1& -\lambda &1 \\ 0& 1& 0& 1& -\lambda \\ \end{vmatrix}&=-\lambda^5+6\lambda^3\\ \begin{vmatrix} -\lambda &1 &0 &1 &0 &1 \\ 1& -\lambda &1 &0 &1 &0 \\ 0& 1& -\lambda &1 &0 &1 \\ 1& 0& 1& -\lambda &1 &0 \\ 0& 1& 0& 1& -\lambda &1 \\ 1& 0& 1& 0&1 & -\lambda \\ \end{vmatrix}&=-9\lambda^4+\lambda^6\\ \end{align} $ But I have no idea how to calculate the determinants quickly by hand. Here is my question:

What is the determinant in the $n$ by $n$ case?

  • 0
    Based on my comment above about about separating even and odd positions in the matrix, I posted [this question](http://math.stackexchange.com/questions/54133/eigenvalues-of-certain-block-matrices), which actually fully answers the present question as well.2011-07-28

3 Answers 3

14

You are computing the characteristic polynomial of the matrix whose rows/columns alternate $0$ and $1$s, with first row beginning with $0$, second row beginning with $1$, then $0$, then $1$, etc.

The matrix is symmetric, hence diagonalizable; in particular, the dimension of the nullspace equals the multiplicity of $0$ as a root of the characteristic polynomial. Since the matrix is $n\times n$ and has rank $2$, the multiplicity of $\lambda=0$ as a root of the characteristic polynomial is $n-2$. Thus, the polynomial is a multiple of $(-1)^n\lambda^{n-2}$. Hence it is of the form $(-1)^n\lambda^{n-2}p(\lambda)$, where $p(\lambda)$ is a monic polynomial of degree $2$.

The only remaining question is what are the two other eigenvalues.

Looking at your pattern, you have the following values for $p(\lambda)$: $\begin{align*} n&=2 &\qquad p(\lambda)&= \lambda^2-1\\ n&=3 &\qquad p(\lambda)&= \lambda^2-2\\ n&=4 &\qquad p(\lambda)&= \lambda^2-4\\ n&=5 &\qquad p(\lambda)&= \lambda^2-6\\ n&=6 &\qquad p(\lambda)&= \lambda^2-9 \end{align*}$

For even $n$, $n=2k$, it seems reasonable to conjecture that $p(\lambda)=\lambda^2-k^2$. A simple way to verify this is to show that the matrix has eigenvectors associated to $k$ and to $-k$. For example, when $k=2$, the matrix is $\left(\begin{array}{cccc} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 \end{array}\right).$ It is easy to verify that $(1,-1,1,-1)^t$ is an eigenvector associated to $-2$, and that $(1,1,1,1)^t$ is an eigenvector associated to $2$. Similar vectors will work for all even $n$.

For odd $n$, it seems a bit tricker, but the same basic idea works. Try to find appropriate eigenvectors and eigenvalues, which is very easy to do. Suggestion. Due to the symmetry, it seems like a good idea to look for an eigenvector $(a_1,a_2,\ldots,a_n)^t$ with $a_1=a_3=a_5=\cdots=a_n$ and $a_2=a_4=\cdots=a_{n-1}$. By scaling, we may assume that $a_1=1$, and $a_2=r$ for some $r$. If $n=2k+1$, then applying the matrix to such a vector will give you that the odd entries of the image have value $kr$, and the even entries have value $k+1$. If you want this to be an eigenvector associated to some $\lambda\neq 0$, then you want $\lambda = kr$, and $\lambda r = k+1$; take it from there.

Moral. While we usually think of the characteristic polynomial as "the easy way" to find the eigenvalues, it's important to remember that the relationship goes both ways: every eigenvalue you can find gives you a linear factor of the characteristic polynomial too. It's often useful to "play one against the other". Here, the determination of "most" of the roots follows by staring at the matrix, and because the matrix is highly structured it turns out to be easier to find the eigenvalues directly than trying to compute the characteristic polynomial and then factoring.

  • 0
    @Mariano: Which requires more sign changes usually (computing $\det(\lambda I - A)$); but in any case, if you notice the work done by the original poster, it is clear he was using $\det(A-\lambda I)$ rather than $\det(\lambda I - A)$, so the leading factor of his version of the characteristic polynomial has leading coefficient $(-1)^n$.2011-08-11
5

Let us denote the matrix in $n$-dimensions by $\Lambda_n$ and the two non vanishing eigenvalues by $a$ and $b$. We have

$a+b = tr(\Lambda_n) = 0$

$a^2+b^2 = tr(\Lambda_n^2) = 2\lceil \frac{n}{2}\rceil\lfloor\frac{n}{2}\rfloor$

which implies that:

$a ^2= b^2 =-ab = \lceil \frac{n}{2}\rceil \lfloor\frac{n}{2}\rfloor$

Thus the two nonvanishing eigenvalues contributtion to the characteristic polynomial:

$\lambda^2-\lceil \frac{n}{2}\rceil \lfloor\frac{n}{2}\rfloor$

2

Based on the given results, you should be able to guess what the eigenvalues are. Can you write down an explicit set of eigenvectors for those eigenvalues? Does your construction generalize?