Now with this, it is time to consider the notion of block diagonal matrices.
Definition A.12.1Let A and B be two n×n matrices. Then A is similar to B, written as A ∼ Bwhen there exists an invertible matrix S such that A = S^{−1}BS.
Theorem A.12.2Let A be an n × n matrix. Letting λ_{1},λ_{2},
⋅⋅⋅
,λ_{r}be the distinct eigenvalues of A,arranged in some order, there exist square matrices P_{1},
⋅⋅⋅
,P_{r}such that A is similar to the block diagonalmatrix
( )
| P.1 ⋅⋅⋅ 0. |
P = |( .. ... .. |)
0 ⋅⋅⋅ Pr
in which P_{k}has the single eigenvalue λ_{k}. Denoting by r_{k}the size of P_{k}it follows that r_{k}equals thedimension of the generalized eigenspace for λ_{k}which is V_{λi} =
ri m∏ ri
ker(A − λiI) , for minimal polynomial p (λ ) = (λ − λi)
i=1
where the B_{i} are the matrices described in the statement of the theorem. Then S^{−1} must be of the
form
( )T
S−1 = C1 ⋅⋅⋅ Cr
where C_{i}B_{i} = I_{ri×ri}. Also, if i≠j, then C_{i}AB_{j} = 0 the last claim holding because A : V_{λj}
↦→
V_{λj} so the
columns of AB_{j} are linear combinations of the columns of B_{j} and each of these columns is orthogonal to
the rows of C_{i} since C_{i}B_{j} = 0 if i≠j. Therefore,
and C_{rk}AB_{rk}≡ P_{r} is an r_{k}× r_{k} matrix.
What about the eigenvalues of P_{k}? The only eigenvalue of A restricted to V_{λk} is λ_{k} because if Ax = μx
for some x ∈ V_{λk} and μ≠λ_{k}, then
(A − λ I)rk x = (A − μI +(μ − λ )I)rk x
k k
( )
r∑k rk rk−j j rk
= j (μ − λk) (A − μI) x = (μ− λk) x ⁄= 0
j=0
contrary to the assumption that x ∈ V_{λk}. Now if μ is an eigenvalue for P_{k},P_{k}z = μz,z≠0,
then
( ) ( ) ( )
| 0 | | 0 | | 0 |
AS ( z ) = S ( Pkz ) = μS( z )
0 0 0
From the definition of S, the vector on the right in the above equation is nonzero, in V_{λk} and so from what
was just observed, μ = λ_{k}. ■
Appendix B The Hausdorff Maximal Theorem
The purpose of this appendix is to prove the equivalence between the axiom of choice, the Hausdorff
maximal theorem, and the well-ordering principle. The Hausdorff maximal theorem and the well-ordering
principle are very useful but a little hard to believe; so, it may be surprising that they are equivalent to the
axiom of choice. First it is shown that the axiom of choice implies the Hausdorff maximal theorem, a
remarkable theorem about partially ordered sets.
A nonempty set is partially ordered if there exists a partial order, ≺, satisfying
x ≺ x
and
if x ≺ y and y ≺ z then x ≺ z.
An example of a partially ordered set is the set of all subsets of a given set and ≺≡⊆. Note that two
elements in a partially ordered sets may not be related. In other words, just because x, y
are in the partially ordered set, it does not follow that either x ≺ y or y ≺ x. A subset of a
partially ordered set, C, is called a chain if x, y ∈C implies that either x ≺ y or y ≺ x. If
either x ≺ y or y ≺ x then x and y are described as being comparable. A chain is also called
a totally ordered set. C is a maximal chain if whenever
^C
is a chain containing C, it follows
the two chains are equal. In other words C is a maximal chain if there is no strictly larger
chain.
Lemma B.0.1Let ℱ be a nonempty partially ordered set with partial order ≺. Then assuming theaxiom of choice, there exists a maximal chain in ℱ.
Proof: Let X be the set of all chains from ℱ. For C∈X, let
S C = {x ∈ ℱ such that C∪ {x } is a chain strictly larger than C}.
If S_{C} = ∅ for any C, then C is maximal. Thus, assume S_{C}≠∅ for all C∈X. Let f(C) ∈ S_{C}. (This is where the
axiom of choice is being used.) Let
g(C) = C ∪ {f(C )}.
Thus g(C) ⊋ C and g(C) ∖C ={f(C)} = {a single element of ℱ}. A subset T of X is called a tower
if
∅ ∈ T,
C ∈ T impliesg(C) ∈ T,
and if S⊆T is totally ordered with respect to set inclusion, then
∪S ∈ T .
Here S is a chain with respect to set inclusion whose elements are chains.
The idea is this:
Find the smallest tower T_{0}
Show that If a chain C_{0} of T_{0} is comparable to every chain in T_{0} so that it either contains of
is contained in every set of T_{0}, then whenever D ⊋ C_{0}, you must have g
(C0)
⊆D. Thus you
can’t have things growing out in another direction.
Show that if T_{1} is the set of all chains of T_{0} which are comparable to every chain in T_{0}, then
T_{1} is a tower. Thus, since T_{0} is the smallest tower, you have T_{1} = T_{0} and T_{0} is a chain.
Consider ∪T_{0}∈T_{0}. You would need g
(∪T0)
∈T_{0} but this does not happen because g
(∪T0)
is a strictly longer chain than T_{0} having something in it which is not in T_{0}. This contradiction
shows that there must be a maximal chain, one which cannot be enlarged further.
Step 1: Note that X is a tower. Let T_{0} be the intersection of all towers. Thus, T_{0} is a tower, the
smallest tower.
Step 2: Let C_{0} be a set of T_{0} which is comparable to every set of T_{0}. Such sets exist, ∅ being an
example. Let
ℬ ≡ {D ∈ T0 : D ⊋ C0 and f (C0)∈∕D }.
The picture represents sets of ℬ. As illustrated in the picture, D is a set of ℬ when D is larger than C_{0} but
fails to be comparable to g
(C0)
. Thus there would be more than one chain ascending from C_{0} if ℬ≠∅, rather
like a tree growing upward in more than one direction from a fork in the trunk. It will be shown this can’t
take place for any such C_{0} by showing ℬ = ∅.
PICT
This will be accomplished by showing
^T0
≡T_{0}∖ℬ is a tower. Since T_{0} is the smallest tower, this will
require that
^T
0
= T_{0} and so ℬ = ∅.
Claim:
T^
0
is a tower and so ℬ = ∅.
Proof of the claim:It is clear that ∅∈
^T
0
because for ∅ to be contained in ℬ it would be required to
properly contain C_{0} which is not possible. Suppose D∈
T^
0
. The plan is to verify g
(D )
∈
T^
0
.
Since g
(D )
∈T_{0} and C_{0} is comparable to every set in T_{0}, it follows that either g
(D)
⊆C_{0} or
C_{0}⊇ g
(D)
.
Case 1: g
(D )
⊆C_{0}. Then by definition, g
(D )
∕∈
ℬ because to be in ℬ the set must properly contain C_{0}.
Thus g
(D )
∈T_{0}∖ℬ.
Case 2: g
(D )
⊋ C_{0}. There are two subcases, D⊆C_{0} and D ⊋ C_{0}. In the second case, D satisfies the first
criterion for being in ℬ but it isn’t in ℬ and so f
(C0)
∈D⊆}
(D)
. Thus g
(D)
is not in ℬ so it is in T_{0}∖ℬ.
Now consider the first case that D⊆C_{0} and yet
g (D ) ≡ {f (D )}∪ D ⊋ C0 ⊇ D
something is in
{f (D )}
∪D which is not in C_{0} but D⊆C_{0} and so that thing is f
(D )
. Thus
everything in C_{0} is in
{f (D )}
∪D but f
(D )
is nothing in C_{0}. Hence D⊇C_{0}⊇D so D = C_{0}. This
means
f (C0) ∈ g(D) ≡ {f (D)} ∪D ≡ {f (C0)}∪ D
and so g
(D )
∈∕
ℬ.
Now suppose S is a totally ordered subset of
^
T0
with respect to set inclusion. Then if every element of S
is contained in C_{0}, so is ∪S and so ∪S∈
^
T0
since this union can’t be in ℬ. If, on the other hand, some chain
from S, C, contains C_{0} properly, then since C
∕∈
ℬ, f
(C0)
∈C⊆∪S showing that ∪S
∕∈
ℬ also. This has
proved
^
T0
is a tower and since T_{0} is the smallest tower, it follows
^
T0
= T_{0}. This has shown roughly that no
splitting into more than one ascending chain can occur at any C_{0} which is comparable to every set of T_{0}.
Next it is shown that every element of T_{0} has the property that it is comparable to all other
elements of T_{0}. This is done by showing that these elements which possess this property form a
tower.
Step 3:Define T_{1} to be the set of all elements of T_{0} which are comparable to every element of T_{0}.
(Recall the elements of T_{0} are chains from the original partial order.)
Claim: T_{1} is a tower.
Proof of the claim: It is clear that ∅∈T_{1} because ∅ is a subset of every set. Suppose
C_{0}∈T_{1}. It is necessary to verify that g
(C0)
∈T_{1}. Let D∈T_{0} (Thus D⊆C_{0} or else D ⊋ C_{0}.)and
consider g
(C0)
≡C_{0}∪
{f (C0)}
. If D⊆C_{0}, then D⊆ g
(C0)
so g
(C0)
is comparable to D. If
D ⊋ C_{0}, then D⊇ g
(C0)
by what was just shown
(ℬ = ∅)
. Hence g
(C0)
is comparable to D.
Since D was arbitrary, it follows g
(C0)
is comparable to every set of T_{0}. Now suppose S is a
chain of elements of T_{1} and let D be an element of T_{0}. If every element in the chain, S is
contained in D, then ∪S is also contained in D. On the other hand, if some set, C, from S
contains D properly, then ∪S also contains D. Thus ∪S∈T_{1} since it is comparable to every
D∈T_{0}.
This shows T_{1} is a tower and proves therefore, that T_{0} = T_{1}. Thus every set of T_{0} compares with every
other set of T_{0} showing T_{0} is a chain in addition to being a tower.
Step 4: Now ∪T_{0},g
(∪ T0)
∈T_{0}. Hence, because g
(∪ T0)
is an element of T_{0}, and T_{0} is a chain of these,
it follows g
(∪ T0)
⊆∪T_{0}. Thus
∪T0 ⊇ g(∪T0) ⊋ ∪T0,
a contradiction. Hence there must exist a maximal chain after all. ■
If X is a nonempty set,≤ is an order on X if
x ≤ x,
and if x, y ∈ X, then
either x ≤ y or y ≤ x
and
if x ≤ y and y ≤ z then x ≤ z.
≤ is a well order and say that
(X,≤ )
is a well-ordered set if every nonempty subset of X has a smallest
element. More precisely, if S≠∅ and S ⊆ X then there exists an x ∈ S such that x ≤ y for all y ∈ S. A
familiar example of a well-ordered set is the natural numbers.
Lemma B.0.2The Hausdorff maximal principle implies every nonempty set can be well-ordered.
Proof: Let X be a nonempty set and let a ∈ X. Then {a} is a well-ordered subset of X.
Let
ℱ = {S ⊆ X : there exists a well order for S}.
Thus ℱ≠∅. For S_{1}, S_{2}∈ℱ, define S_{1}≺ S_{2} if S_{1}⊆ S_{2} and there exists a well order for S_{2}, ≤_{2}such
that
(S2,≤2) is well-ordered
and if
y ∈ S2 ∖ S1 then x ≤2 y for all x ∈ S1,
and if ≤_{1}is the well order of S_{1} then the two orders are consistent on S_{1}. Then observe that ≺ is a
partial order on ℱ. By the Hausdorff maximal principle, let C be a maximal chain in ℱ and
let
X∞ ≡ ∪ C.
Define an order, ≤, on X_{∞} as follows. If x, y are elements of X_{∞}, pick S ∈C such that x, y are both in
S. Then if ≤_{S} is the order on S, let x ≤ y if and only if x ≤_{S}y. This definition is well defined because of
the definition of the order, ≺. Now let U be any nonempty subset of X_{∞}. Then S ∩ U≠∅ for some S ∈C.
Because of the definition of ≤, if y ∈ S_{2}∖S_{1}, S_{i}∈C, then x ≤ y for all x ∈ S_{1}. Thus, if y ∈ X_{∞}∖S then
x ≤ y for all x ∈ S and so the smallest element of S ∩U exists and is the smallest element in U. Therefore
X_{∞ } is well-ordered. Now suppose there exists z ∈ X ∖ X_{∞}. Define the following order, ≤_{1}, on
X_{∞}∪{z}.
x ≤1 y if and only if x ≤ y whenever x,y ∈ X ∞
x ≤1 z whenever x ∈ X ∞.
Then let
^C = {S ∈ C or X ∞ ∪ {z}}.
Then
^C
is a strictly larger chain than C contradicting maximality of C. Thus X ∖X_{∞} = ∅ and this shows X
is well-ordered by ≤. This proves the lemma.
With these two lemmas the main result follows.
Theorem B.0.3The following are equivalent.
The axiom of choice
The Hausdorff maximal principle
The well- ordering principle.
Proof:It only remains to prove that the well-ordering principle implies the axiom of choice. Let I be a
nonempty set and let X_{i} be a nonempty set for each i ∈ I. Let X = ∪{X_{i} : i ∈ I} and well order X. Let
f