10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Use Gershgorin circles. $\endgroup$ – Davide Giraudo Aug 2 '12 at 10:48
9
$\begingroup$

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[$.

$\endgroup$
7
$\begingroup$

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.$$

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – J. M. is a poor mathematician Aug 2 '12 at 11:55
  • 1
    $\begingroup$ @J.M. Thanks for the paper. $\endgroup$ – Davide Giraudo Aug 2 '12 at 12:13
  • $\begingroup$ Thank you Davide, as always - much appreciated. $\endgroup$ – Conan Wong Aug 7 '12 at 4:48
  • $\begingroup$ @J.M. It's been a few years since you commented, but do you have any references handy on the relationship between Chebyshev polynomials and tridiagonal Toeplitz matrices? $\endgroup$ – Ben Bray Dec 12 '16 at 17:24

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.