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.

Problem:

Let A be a square matrix with all diagonal entries equal to 2, all entries directly above or below the main diagonal equal to 1, and all other entries equal to 0. Show that every eigenvalue of A is a real number strictly between 0 and 4.

Attempt at solution:

  • Since A is real and symmetric, we already know that its eigenvalues are real numbers.

  • Since the entries in the diagonal of A are all positive (all 2), A is positive definite iff the determinants of all the upper left-hand corners of A are positive. I think this can be proven via induction (showing that each time the dimension goes up, the determinant goes up too)

  • Since A is symmetric and positive definite, eigenvalues are positive, i.e. greater than 0.

But I can't get the upper bound of 4. Any help would be appreciated. Thank you.

share|improve this question
3  
Use Gershgorin circles. –  Davide Giraudo Aug 2 '12 at 10:48

2 Answers 2

up vote 7 down vote accepted

The characteristic polynomial of $A-2I$ is the $n\times n$ determinant $D_n(X)$ of the matrix with entries $-1$ directly above or below the main diagonal, entries $X$ on the main diagonal, and entries $0$ everywhere else, hence $$ D_{n+2}(X)=XD_{n+1}(X)-D_n(X), $$ for every $n\geqslant0$ with $D_1(X)=X$ and the convention $D_0(X)=1$. This recursion is obviously related to Chebyshev polynomials and one can prove:

For every $u$ in $(0,\pi)$ and $n\geqslant0$, $D_{n}(2\cos(u))=\dfrac{\sin((n+1)u)}{\sin(u)}$.

Assume that this holds for $n$ and $n-1$ for some $n\geqslant1$, then $$ D_{n+1}(2\cos(u))\sin(u)=2\cos(u)\sin(nu)-\sin((n-1)u)=\sin((n+1)u). $$ Since $D_1(2\cos(u))=2\cos(u)=\sin(2u)/\sin(u)$ and $D_0(2\cos(u))=1=\sin(u)/\sin(u)$, this proves the claim. Hence $x=2\cos(k\pi/(n+1))$ solves $D_n(x)=0$ for every $1\leqslant k\leqslant n$. These $n$ different values are the eigenvalues of $A-2I$.

Since the eigenvalues of $A-2I$ are all in the interval $[-2\cos(\pi/(n+1)),+2\cos(\pi/(n+1))]$, the eigenvalues of $A$ are all in the interval $]0,4[$.

share|improve this answer

Gershgorin circle theorem help us to conclude that the eigenvalues of $A$ are in the interval $(0,4)$.

Actually, we can compute them. First, we notice that $A$ is similar to the matrix which has $2$ on the diagonal, $-1$ directly above and below it, and the other entries are $0$ (multiply on the left and on the right by $\operatorname{diag}((-1)^j,1\leq j\leq n)$. If $x=(x_1,\dots,x_n)$ is a eigenvector for the eigenvalue $\lambda$, we should have $$-x_{j-1}+(2-\lambda)x_j-x_{j+1}=0, 2\leq j\leq n-1.$$ We can assume that $\lambda$ has the form $2(1-\cos \theta)$. Then we should have $$-x_{j-1}+2\cos \theta \cdot x_j-x_{j+1}=0.$$ We want the initial condition to be $x_0=0$ and $x_1\neq 0$. Such a recurrence relation can be solved by $a \alpha^k+b\beta^k$, where $\alpha$ and $\beta$ are the roots of $X^2-2\cos \theta X+1$. These one are $e^{i\theta}$ and $e^{-i\theta}$, and we have $a=-b$, hence we can take $x_j=\sin(j\theta)$. The last equation should be $$2\cos\theta \sin(n\theta)-\sin((n-1)\theta)=0,$$ hence $$2\cos\theta\sin(n\theta)-\sin(n\theta)\cos\theta)+\cos(n\theta)\sin\theta=0,$$ which gives $$\cos\theta\sin(n\theta)+\cos(n\theta)\sin\theta=0,$$ so $\sin((n+1)\theta)=0$. Hence the eigenvalues of $A$ have the form $$\lambda_k:=2\left(1-\cos\left(\frac{k\pi}{n+1}\right)\right)=4\sin^2\left(\frac{k\pi}{2(n+1)}\right),1\leq k\leq n.$$

share|improve this answer
2  
Or, $\lambda_k=4\sin^2\frac{k\pi}{2(n+1)}$. See this paper for more results on tridiagonal Toeplitz matrices (which are intimately related to the Chebyshev polynomials). –  J. M. Aug 2 '12 at 11:55
1  
@J.M. Thanks for the paper. –  Davide Giraudo Aug 2 '12 at 12:13
    
Thank you Davide, as always - much appreciated. –  Conan Wong Aug 7 '12 at 4:48

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.