Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  JavaMan Jul 27 '11 at 18:18
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$. –  Arturo Magidin Jul 27 '11 at 18:18
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$? –  mixedmath Jul 27 '11 at 18:20
    
@DJC,@Arturo: Corrected, thanks. –  Jack Jul 27 '11 at 18:20
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. –  Michael Hardy Jul 27 '11 at 18:26
show 2 more comments

3 Answers

up vote 12 down vote accepted

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.

share|improve this answer
    
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. –  Jack Jul 27 '11 at 19:11
    
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. –  Jack Jul 27 '11 at 19:20
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? –  Arturo Magidin Jul 27 '11 at 19:22
    
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? –  Jack Jul 27 '11 at 19:28
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. –  Arturo Magidin Jul 27 '11 at 19:31
show 2 more comments

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$

share|improve this answer
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.