PTOW10 solution - Pedersen.nb

Tridiagonal Treat
Let A be a real symmetric n´n tridiagonal matrix with nonzero subdiagonal and superdiagonal entries.
Prove that (1) rank A ³ n - 1 and (2) A has n distinct eigenvalues.
Proof.
a1
b1
0
Let A = 0
0
»
0
b1
a2
b2
0
0
»
0
0
b2
a3
b3
0
0
0
b3
a4
¸
… 0
0
0
0
¸
¸
bn-2
0
…
…
0
0
»
0
0
, where we know that bi ¹ 0.
bn-2
an-1 bn-1
bn-1 an
We know that A v = 0 has at least the trivial solution. I will show that if it has two nontrivial solutions,
then they are multiples of each other. Let v and w be two nontrivial solutions. Then we have:
a1
b1
0
0
0
»
0
b1
a2
b2
0
0
»
0
0
b2
a3
b3
0
0
0
b3
a4
¸
0
0
0
¸
¸
bn-2
… 0
0
…
…
0
0
»
0
0
bn-2
an-1 bn-1
bn-1 an
v1
v2
v3
v4 = 0, and similarly for w.
»
vn-1
vn
That gives us the following n equations for vi :
a1 v1 + b1 v2 = 0,
bi vi + ai+1 vi+1 + bi vi+2 = 0, for i = 1, 2, ..., n - 2, and
bn-1 vn-1 + an vn = 0.
And a simliar set of n equations for wi
The first equation determines that: v2 =
-a1 v1
,
b1
which is defined since b1 ¹ 0.
SImilarly, the next n - 2 equations determine that: vi+2 =
-bi vi -ai+1 vi+1
,
bi
for i=1,2,...,n-2.
These n - 1 equations completely determine the vector v given its first component v1 . It can also be
seen in these equations that if v1 = 0, then v = 0. (and similarly for wL Therefore we know that v1 ¹ 0
w
and w1 ¹ 0. Let c = 1 , so that w1 = c v1 . It can easily be seen that the first n - 1 equations for wi then
v1
determine that wi = c vi for i = 2, 3, ..., n. Therefore w = c v, so that if there are any nontrivial solutions,
they are multiples of each other.
This proves that the dimension of the null space is at most 1. Since the null space is the orthogonal
complement of the row space, that means that the row space has a dimension of at least n - 1, hence
(1) rank A ³ n - 1.
2
PTOW10 solution - Pedersen.nb
Now let Λ be any eigenvalue of A, which is equivalent to the existence of a nontrivial solution to
HA - ΛIL v = 0. Since the matrix A is real symmetric, we know that its eigenvalues are real, hence (A-ΛI)
is also a real symmetric n´n tridiagonal matrix with nonzero subdiagonal and superdiagonal entries,
and therefore we know that the null space of (A-ΛI) is at most 1 dimensional. Since Λ is an eigenvalue,
the null space must be at least 1 dimensional, therefore it is 1 dimensional. This means that the
eigenspace for Λ is 1 dimensional, or in other words, that the geometric multiplicity of Λ is 1. However, it
does not imply that the algebraic multiplicity is 1. A matrix can have eigenvalues which have an algebraic multiplicity greater than their geometric multiplicity. Such matrices are called defective, and do not
have a set of n linearly independent eigenvectors. That is equivalent to the matrices not being diagonalizable. However, every normal matrix is diagonalizable, and a real symmetric matrix is a special case
of a normal matrix, therefore A is not defective. Hence, the algebraic multiplicity of Λ must be equal to
the geometric multiplicity of Λ, implying that every eigenvalue of A has an algebraic multiplicity of 1,
hence (2) A has n distinct eigenvalues.

Download Report