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?

  • 1
    The determinant of the $3 \times 3$ matrix is actually $-x^3 + 2x$. This should help establish a pattern, at least for the leading term of the polynomial.2011-07-27
  • 1
    There's something wrong in the computation of the second determinant: the determinant should be a polynomial of degree $3$ in $\lambda$ with leading coefficient $-1$, not $-3$.2011-07-27
  • 1
    Doing a quick look, is your 3 by 3 case correct? It seems that the leading coefficient should always be either 1 or negative 1 so perhaps you just meant $ - \lambda ^3 + 2 \lambda$?2011-07-27
  • 0
    @DJC,@Arturo: Corrected, thanks.2011-07-27
  • 1
    What if we permute the indices of the rows and columns, so that instead of listing them in the order 1, 2, 3, 4, 5, 6, we write them in the order 1, 3, 5, 2, 4, 6, i.e. first odd, then even? We get: $$ \begin{bmatrix} -\lambda & 0 & 0 & 1 & 1 & 1 \\ 0 & -\lambda & 0 & 1 & 1 & 1 \\ 0 & 0 & -\lambda & 1 & 1 & 1 \\ 1 & 1 & 1 & -\lambda & 0 & 0 \\ 1 & 1 & 1 & 0 & -\lambda & 0 \\ 1 & 1 & 1 & 0 & 0 & -\lambda \end{bmatrix} $$ The eigenvalues of the $3\times 3$ matrix of 1s are: 3, 0, 0.2011-07-27
  • 1
    FWIW: Toeplitz matrices such as yours often have "nice" properties. You might want to search for stuff on "banded Toeplitz matrices"...2011-07-28
  • 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

13

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
    Hmm, we often find the eigenvalues first and then the eigenvectors. It's interesting to see that in this case we do somewhat the opposite.2011-07-27
  • 0
    I don't quite follow you in the second paragraph that why the factor is $(-1)^n\lambda ^{n-2}$ instead of $\lambda^{n-2}$. After all, the $n-2$ multiple root $0$ gives the factor $C\lambda^{n-2}$ where $C$ is a nonzero constant.2011-07-27
  • 1
    @Jack: The leading coefficient of the characteristic polynomial of an $n\times n$ matrix is $(-1)^n$. By pulling out the $(-1)^n$ into the factor that "we already know", I am left with a *monic* quadratic polynomial still to be determined. If you only factor out $\lambda^{n-2}$, then the remaining factor will be a quadratic polynomial with leading coeffcient $(-1)^{n}$, and why bother with that leading coefficient, if we can put it into the "known part" immediately?2011-07-27
  • 0
    Fair enough. So you first factor out the known part $(-1)^n\lambda^{n-2}$ which is from the spectrum theorem as I understand, then you use the possible eigenvectors to find the quadratic part, i.e., the two nonzero eigenvalues. Correct?2011-07-27
  • 1
    @Jack: Essentially, yes. I factor out $(-1)^n\lambda^{n-2}$, then look for a pattern in what's left. For even $n$, the pattern is obvious, so we try it: find eigenvectors with eigenvalues $k$ and $-k$, that gives the roots of the quadratic (note that in the even case, all rows add up to $k$, so $(1,\ldots,1)^t$ *must* be an eigenvector). For odd $n$ the pattern may not be so obvious, so we play a bit with possible eigenvectors (trying simplified vectors first because they are easier); turns out that one can quickly figure out what two other eigenvalues/eigenvectors are, which finishes it.2011-07-27
  • 0
    @Arturo: half the the world (the one which is right! :) ) defines the characteristic polynomial so that it is monic!2011-08-11
  • 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?