W

£

¢

W

and let and be the lower and upper triangular parts of , respectively. Then

£ ¤ ¢

§¥

¦ ²

If is an eigenvalue of , then so is .

¢

¦©¨ The eigenvalues of the matrix T

¬X y w

¢ £ ¤

¥

¬

de¬ned for are independent of .

`

Y

£ R

6 A

£

The ¬rst property is shown by simply observing that if is an eigenvector

R

²

T T

associated with , then is an eigenvector of associated with the eigenvalue . ¢

X X

“

¬

Consider the second property. For any , the matrix is similar to , i.e., ¢ ¢ ¢

with de¬ned by

W “ @¤

¤¢ ¤

¬

¤

y

This proves the desired result

T

A de¬nition which generalizes this important property is consistently ordered matrices. X

Varga [213] calls a consistently ordered matrix one for which the eigenvalues of are ¢

independent of . Another de¬nition given by Young [232] considers a speci¬c class of

matrices which generalize this property. We will use this de¬nition here. Unlike Property

A, the consistent ordering property depends on the initial ordering of the unknowns.

¥ ¤h

©' $ 2¨) 2 vB9

9A

§ ) )§

¦

A matrix is said to be consistently ordered if the vertices of its adja-

£¦

cency graph can be partitioned in sets , , , with the property that any two ¦

¦

¡

W X

adjacent vertices and in the graph belong to two consecutive partitions and , with

E ¦ ¦

H

H

vw

²¬ w

¬

, if , and , if . wW E

E

¤W W ¤W

y y

It is easy to show that consistently ordered matrices satisfy property A: the ¬rst color is

R¦ R¦

made up of all the partitions with odd and the second with the partitions with even E

.

E

µ£ „ ¢

|5¥ j qz A C¡y 5

„ 5| | 5£§|

¢ ¡

t¡C

9C @¡

¨§ £ "!

¥

¤B©7 ©¦§¥¢£

£A 9 ¨ ¤

Block tridiagonal matrices of the form

£

#

W £ £W # £

„

¬ ..

W R

.

£

#

.. ..

R R

‚ . .

X W “ # X

W “ X X X

R#

whose diagonal blocks are diagonal matrices are called -matrices. Clearly, such ma-

trices are consistently ordered. Note that matrices of the form (4.42) are a particular case

¢

¬

with . ˜

¡

Consider now a general, consistently ordered matrix. By de¬nition, there is permuta-

W¤

¡

tion of which is the union of disjoint subsets

(Q(˜ (

©

§ ¡

y

± r¯¯ i ¯®

£ £ £ W ¢¡

¡ ¡ ¡ ¬ X

¤H ¡

¥ ¥

vR c ¬ ¬

u ¡

with the property that if and belongs to , then belongs to ¡Y

( E E

H W

§

¡

depending on whether or . This permutation can be used to permute E

E

¥ ¡

symmetrically. If is the permutation matrix associated with the permutation , then

clearly

§§ ¦¬ ¤ §

¥¥