469

sides to obtain vk1, the eigenvector upon which the chain Bk is based, is a linear combination

of {B1, · · · ,Bk−1} contrary to the construction. Since {B1, · · · ,Bk} is linearly independent,the process terminates. This proves the claim.

Claim 3: Suppose Nw = 0. (w is an eigenvector) Then there exist scalars, ci such that

w =s

∑i=1

civi1.

Recall that vi1 is the eigenvector in the ith chain on which this chain is based.

Proof of Claim 3: From the construction, w ∈ span(B1, · · · ,Bs) since otherwise, itcould serve as a base for another chain. Therefore, w =∑

si=1 ∑

rik=1 ck

i vik. Now apply N

to both sides. 0 =∑si=1 ∑

rik=2 ck

i vik−1 and so by Claim 2, ck

i = 0 if k ≥ 2. It follows thatw =∑

si=1 c1

i vi1 and this proves the claim.

If Nw = 0, then w ∈ span(B1, · · · ,Bs) . In fact, it was a particular linear combina-tion involving the bases of the chains. What if Nkw = 0? Does it still follow that w ∈span(B1, · · · ,Bs)?

Claim 4: If Nkw = 0, then w ∈ span(B1, · · · ,Bs) .Proof of Claim 4: Suppose this true that if Nk−1w,k ≥ 2, it follows that

w ∈ span(B1, · · · ,Bs) .

Then suppose Nkw = 0. If Nk−1w = 0, then by induction, w ∈ span(B1, · · · ,Bs). The othercase is that Nk−1w ̸= 0. Then you have the chain Nk−1w, · · · ,w where Nk−1w is an eigen-vector. The chain has length no longer than the lengths of any of the Bi by construction.Then by Claim 3,

Nk−1w =s

∑i=1

civi1 =

s

∑i=1

ciNk−1vik

And so, Nk−1(w−∑

si=1 civi

k

)= 0 which implies by induction that

w−s

∑i=1

civik ∈ span(B1, · · · ,Bs) .

This proves Claim 4.Since every w satisfies Nnw = 0 this shows that span(B1, · · · ,Bs) = Fn. By Claim 2,

{B1, · · · ,Bs} is independent. Therefore, this is a basis for Fn.Now consider the block matrix S =

(B1 · · · Bs

)where

Bk =(

vk1 · · · vk

rk

).

Thus

S−1 =

C1...

Cs

From the construction, Nvk

j ∈ span(Bk) , and so CiNvkj = 0. It follows that CiBi = Iri×ri and

CiNB j = 0 if i ̸= j. Let

Ck =

uT

1...

uTrk

 .