Math 221 (02) • Final Exam, with Solution Guide
Part I gave matrices E and M as follows, calling for: (1) E^{T}
and E^{–1} ; (2) E·M and E^{T}·M ;
and (4) M·E^{T} and M·E ; and
(3, 5, 6) related discussion:
1 0 0 0 0 a_{1} b_{1} c_{1} d_{1} e_{1} 1 0 0 0 0 1 0 0 0 0
0 1 0 0 3 a_{2} b_{2} c_{2} d_{2} e_{2} 0 1 0 0 0 0 1 0 0 3
E = 0 0 1 0 0 , M = a_{3} b_{3} c_{3} d_{3} e_{3} . Ans.: 1. E^{T} = 0 0 1 0 0 , E^{1} = 0 0 1 0 0 .
0 0 0 1 0 a_{4} b_{4} c_{4} d_{4} e_{4} 0 0 0 1 0 0 0 0 1 0
0 0 0 0 1 a_{5} b_{5} c_{5} d_{5} e_{5} 0 3 0 0 1 0 0 0 0 1
2. & 3. E·M is exactly the matrix obtained from M by adding, to row 2,
three times row 5 (and leaving all rows other than row 2 unchanged); E^{T}·M
is exactly the matrix obtained from M by adding, to row 5, three times row 2
(and leaving all rows other than row 5 unchanged).
4. & 5. M·E^{T} is exactly the matrix obtained from M by adding, to column 2,
thrice column 5 (leaving all columns other than column 2 unchanged); M·E is exactly
the matrix obtained from M by adding, to column 5, thrice column 2 (leaving all columns
other than column 5 unchanged).
6. Each of E·M^{T} and M·E^{T} is simply the transpose of the other:
E·M^{T} = (M·E^{T})^{T} , M·E^{T} =
(E·M^{T})^{T} .
Part II, 1.
Given matrices A and B , with B being k × r
and A being r × n , here’s why the k × n product matrix
M =_{def} B·A has rank(M) < r :
Remember that the rank of A is, among other things, the dimension of the row space of A ,
which, without a doubt, cannot exceed r , the number of rows A has to begin with:
rank(A) < r . All the rows of the product B·A are, of course,
linear combinations of the rows of A , and consequently the row space of B·A
must be a subspace of the row space of A , and therefore be of dimension no greater.
Summing up, then, to finish this argument:
rank(M) = rank(B·A) = dim(rowspace(B·A)) <
dim(rowspace(A)) < r .
2. Given a k × n matrix M with rank(M) < r and fully reduced
rowequivalent form R = frref(M) , let E be the invertible k × k matrix
(product of elementary matrices corresponding to the individual steps in the rowreduction process)
multiplication by which converts M to R : E·M = R .
Multiplying each side of this equation on the left by the inverse E^{–1} of E ,
we obtain a factorization M = E^{–1}·E·M =
E^{–1}·R of M .
Here E^{–1} is an invertible k × k matrix, while the fully rowreduced
matrix R , of same rank as M , has all rows below the first r rows populated
entirely with zeros. It follows that the entries after the r^{th} entry in each
row of E^{–1} play no role whatsoever in computing the entries of the matrix
product E^{–1}·R — indeed, if we remove from
E^{–1} all the columns after the r^{th} , and likewise
remove from R all the (fullyzero) rows after the r^{th} ,
we obtain matrices, call them B and A , say, that are in fact k × r and r × n ,
and, more importantly, still have the same product (namely, M ) as have E^{–1}
and R , which is to say (concluding this proof):
B·A = E^{–1}·R
= E^{–1}·E·M = M .
3. Why, now, should it be the case that rank(M) the least of the integers r for which
there are factorizations (M) = B·A for matrices A and B as envisioned
in question 1? Because the results of questions 1 and 2, taken together, assure that those are the same
integers as those that rank(M) itself is < to, and it is as plain as the fact that
George Washington’s white horse is white that the least integer that rank(M) itself
is < to must be rank(M) .
Part III, 1. All the hydrogens (H), at the points (1, 1, 1) ,
(–1, 1, –1) , (1, –1, –1) , and (–1, –1, 1) have distance from
the carbon (C) at the origin (0, 0, 0) given by the (positive choice of) square root
of the quantity (±1)^{2} + (±1)^{2} + (±1)^{2} = 3 .
So, indeed, the hydrogens are all equidistant from the carbon,
with common distance given by √3 .
2. As to the distances of the various hydrogens from each other, notice to begin with that the distance
of any of the last three (each with two negative coordinates) from the first one, at (1, 1, 1) , is
the (positive) square root of ((–1) – 1)^{2} + ((–1) – 1)^{2} = 8 ,
i.e., is √8 . And three very similar calculations
show that the distance between any two of the last three hydrogens is likewise
√8 (details left to the reader).
3. For the angles at the (C) of any two of the (C)(H) rays, we offer two approaches.
First approach: recall that the cosine of the angle θ between nonzero vectors
(0 u)
and
(0 v)
is given in all generality by the formula
cos(θ) =  u •
v ——— · u·v

Where u and v are the coordinate vectors of any two (H)es, we easily calculate (in each of the
six cases) that u·v = 3 ,
while u • v = –1 , so that
cos(θ) = (–1)/3 .
Second approach:
H The distances from the single carbon to the various hydrogens all being
· the same, namely √3, and the distances between any two hydrogens also
√3 / all being the same, namely √8 = 2√2, we may subdivide any HCH triangle,
/  all of which are both isosceles and congruent one to another (see figure
C• √8 at left), into two (mutually congruent) subtriangles, by erecting a
\  perpendicular to the HH side from the C vertex, thereby not only bisecting
√3 \ both the angle at vertex C, and the HH side, but also in fact creating two
· (1, √2, √3) right triangles*, each of which has, for the cosine of the
H angle ∠HCM at vertex C, just cos(∠HCM) = 1/√3 (see second figure, below).
H Now the angle ∠HCH we are after is just twice ∠HCM, so we may apply
· the standard double angle formula for cosines,
√3 /√2
/  cos(∠HCH) = cos(2×∠HCM) = cos²(∠HCM)  sin²(∠HCM) =
C•+ M
\  = 2cos²(∠HCM)  1 = 2×(1/√3)²  1 = (2/3)  1 = 1/3 ,
√3 \√2
· which again solves our problem, just as before, but without dot products.
H

H
· 4. As for the angles ∠HHH, notice that every threehydrogen triangle (see
/ \ figure at left) is equilateral, since each hydrogenhydrogen distance is √8 .
√8/ \√8 But equilateral triangles are also equiangular, so at each hydrogen we must have
/ \ angle ∠HHH = π/3 (think: 60 degrees), and cos(∠HHH) = cos(π/3) = 1/2 .
H· — — — ·H
√8 
* (How many other “standard” right triangles do you know of, or can you
think of, besides the (1, √2, √3)? — The (1, 1, √2)? the (3, 4, 5)?
the (5, 12, 13)? the (1, √3, √4)? the (1, √4, √5)? the (1, √5, √6)? ... ?)
Part IV: We record the five matrices (3 by 3, 4 by 4, 5 by 5, 6 by 6,
and general n by n , with n > 7) named in this part:
A = 
 1 1 0 
 0 1 1 
 1 0 1  
, B = 
 1 1 0 0 
 0 1 1 0 
 0 0 1 1 
 1 0 0 1  
, C = 
 1 1 0 0 0 
 0 1 1 0 0 
 0 0 1 1 0 
 0 0 0 1 1 
 1 0 0 0 1  
, D = 
 1 1 0 0 0 0 
 0 1 1 0 0 0 
 0 0 1 1 0 0 
 0 0 0 1 1 0 
 0 0 0 0 1 1 
 1 0 0 0 0 1  
, and M = 
 1 1 0 0 0 . . . 0 0 
 0 1 1 0 0 . . . 0 0 
 0 0 1 1 0 . . . 0 0 
 0 0 0 1 1 . . . 0 0 
 :
: : 
 :
: : 
 0 0 0 0 . . . 1 1 0 
 0 0 0 0 . . . 0 1 1 
 1 0 0 0 . . . 0 0 1  
. 
1. It is easy to calculate det(A) = 2 (there are only two nonzero products involved, and they
each come out to +1), so A is invertible.
As for B : row 4, if we add row 2 to it, becomes [ 1 1 1 1 ] ; and row 3,
if we add row 1 to it, becomes [ 1 1 1 1 ] also; so subtracting this modified row 3 from the
already modified row 4 gives a row of zeros, and thus elementary row operations rowreduce
B to a rowequivalent form with a row of zeros, whence B is not invertible.
(Another approach is to compute det(B) , using the approach of expanding by minors
along, say, the bottom row: the minor for the entry 1 in the SW corner is a
lower triangular 3 by 3 matrix, with all ones on the main diagonal, and hence of determinant 1,
while the minor for the entry 1 in the SE corner is an
upper triangular 3 by 3 matrix, again with all ones on the main diagonal, and hence of determinant 1 as well.
But the signs linked with those two corner entries are –1 and +1, respectively, and so
det(B) = (–1)·1·1 + (+1)·1·1 = 0,
and B is not invertible.)
C , however, like A , is invertible again: if we compute det(C) by
the expansion method applied to B , we find that det(C) = 2 because
the minor for the entry 1 in the SW corner is a
lower triangular 4 by 4 matrix, with all ones on the main diagonal, and hence of determinant 1,
while the minor for the entry 1 in the SE corner is an
upper triangular 4 by 4 matrix, again with all ones on the main diagonal, and hence of determinant 1 as well,
while the signs linked with those two corner entries are now both +1, so that
det(C) = 1 + 1 = 2.
Just as was the case for B , the matrix D is not invertible. The reasons, too,
are much the same: we can, for example, add rows 2 and 4 to row 6 to obtain a row full of ones; but
we can add rows 5 and 3 to row 1 to obtain another row full of ones; subtracting the new row 1 from
the new row 6 delivers a row full of zeros, which shows that the frref of D has
a row full of zeros, guaranteeing that D is not invertible. Alternatively, we can compute
det(D) by expanding along the bottom row: just as before, the minors of the two entries 1 are
lower or uppertriangular matrices with all ones along their diagonals, hence of determinant 1, but the
signs linked with the positions of those entries 1 are –1 and +1, respectively, so that (just as
before) det(D) = (–1) + (+1) = 0, which again guarantees
that D is not invertible.
2. Inverses for A and for C may be found either by explicitly rowreducing each of them to the corresponding identity matrix, and seeing what the sequence of row operations actually used does
to the identity matrix itself, or by using the
(1/det(X))·Adj(X) approach; by either
method,
A^{–1} = 
 +½ –½ +½ 
 +½ +½ –½ 
 –½ +½ +½  
, C^{ –1} = 
 +½ –½ +½ –½ +½ 
 +½ +½ –½ +½ –½ 
 –½ +½ +½ –½ +½ 
 +½ –½ +½ +½ –½ 
 –½ +½ –½ +½ +½ 

. 
3. Convenient (if not fully reduced) rowechelon forms of B and D are
B' = 
 1 1 0 0 
 0 1 1 0 
 0 0 1 1 
 0 0 0 0  
and D' = 
 1 1 0 0 0 0 
 0 1 1 0 0 0 
 0 0 1 1 0 0 
 0 0 0 1 1 0 
 0 0 0 0 1 1 
 0 0 0 0 0 0  
, 
respectively, so the nullspaces of these matrices have dimension 1, and it suffices to give but a single
nonzero vector, in either case, to exhibit a basis. So, for example, as basis for the nullspace of
B we may take the column vector transpose of
[ –1 +1 –1 +1 ] ,
and as basis for the nullspace of D we may take the
column vector transpose of
[ –1 +1 –1 +1 –1 +1 ] .
4. In general, the n by n matrices M will be invertible when n is odd,
and not invertible, but of nullity 1, when n is even. Here’s why.
When n is even, if we add to the bottom row all the evennumbered rows above it, we completely
fill the bottom row with ones (think of the adjacent pair of ones in each row as a little brick, or
domino — we’re just bricklaying a little wall of ones between the existing ones in the
bottom row). Similarly, if we add to the top row all the oddnumbered rows below it, we completely
fill the top row with ones.
We now subtract the (new) top row from the (new) bottom row, obtaining
(as newest bottom row) a row full of zeros, and then proceed to subtract from the top row all the
oddnumbered rows below it, thereby restoring the top row to its original condition. The end result
of the row operations just described is a convenient (if not fully reduced) rowechelon form of
M , whose first n – 1 rows are exactly the rows of M ,
while the bottom row is allzero. The nullity of M is thus 1, and a handy basis
for the nullspace of M is the nlength column whose entries alternate strictly between +1 and
–1.
When n is odd, on the other hand, calculating det(M) the same way we did for
A or C — that is, expanding by minors along the bottom row,
whose two nonzero entries 1 both live in positions linked to the sign +1 and have minors that are
either lower or uppertriangular matrices having (only ones on their main diagonal, and hence)
determinant 1 — shows us once again that det(M) = 1 + 1 = 2.
And as for M^{ –1} in these cases, we will have
M^{ –1} = 
 +½ –½ +½ –½ +½
. . . –½ +½ 
 +½ +½ –½ +½ –½
. . . +½ –½ 
 –½ +½ +½ –½ +½
. . . –½ +½ 
 +½ –½ +½ +½ –½
. . . +½ –½ 
 :
:
: 
 :
:
: 
 –½ +½ –½ +½
. . . +½ –½ +½ 
 +½ –½ +½ –½
. . . +½ +½ –½ 
 –½ +½ –½ +½
. . . –½ +½ +½  
, 
where the entries on the main diagonal, and each entry immediately below those,
are all +½ , and the remaining entries all alternate, checkerboard fashion,
between +½ and –½ .
Part V: The diagrammatic inequality <_{(1)} expresses the geometric observation
that the LH figure, with its four triangles and central parallelogram, has area no greater
than that of the RH figure, presumably on the grounds that the four triangles are
exactly the same in the two figures, while the central rectangle within the RH figure must have
area at least as great as the area of the central parallelogram within the LH figure
(as the sides in both cases are exactly the same, but the altitude on the RHS is > the
altitude on the LHS).
Inequality <_{(2)} recapitulates inequality <_{(1)}
algebraically, taking for its
LHS the algebraic expression (a + y)(b + x) for the
area of the entire rectangular LH figure, and for its RHS the sum
of the algebraic expressions for the areas of the four little triangles and
the central rectangle making up the RH figure.
Inequality <_{(5)} is what results if, after carrying out the multiplication
indicated in the RHS of inequality <_{(2)} , one then subtracts
from either side the quantity ab + xy ; inequality
<_{(4)} is the familiar triangle inequality for ordinary real numbers;
and the ∴_{(3)} symbol (“∴” in HTML) is probably doing double duty,
pointing both to the fact that inequality <_{(5)} follows from
inequality <_{(2)} , and to the conclusion to be drawn from the conjunction of
inequalities <_{(4)} and <_{(5)} , that ax + by ,
which, after all, is just  u • v  , is <
√a² + b² ·
√x² + y² , which,
in turn, is just  u · v  , i.e., that
 u • v 
<
 u · v  .
Part VI. Q. 1: F_{1} through F_{10} are:
1, 1, 2, 3, 5, 8, 13, 21, 34, and 55, respectively.
F_{–10} through F_{–1} are:
–55, 34, –21, 13, –8, 5, –3, 2, –1, and 1, respectively.
Q. 2: The “fundamental recursion formula” (*) F_{n+1} =
F_{n–1} + F_{n} is posited initially only for
n > 1 where F_{n–1} and F_{n}
are already known.
For n = 0 , of course, F_{n+1} = F_{1} = 1 ,
F_{n} = F_{0} = 0 , and
F_{n–1} = F_{–1} = +F_{1} = 1 ,
so (*) continues to hold (saying just: 1 = 1 + 0).
For n < 0 , say n = – k with k > 0 , what needs to be checked is
whether F_{n+1} = F_{n–1} + F_{n}
remains true, given, after all, that F_{n} is defined for negative n via the equation
F_{n} = (–1)^{k+1}F_{k}
(k = – n > 0) .
When n = – k with k > 0 , of course, n + 1 = – k + 1
= – (k – 1) and n – 1 = – k – 1 = – (k + 1) .
So it's a matter of checking, for k > 0 , whether
(–1)^{(k–1)+1}F_{k–1} =
(–1)^{k+1}F_{k} +
(–1)^{(k+1)+1}F_{k+1} .
Now, when k is even (and > 0), this means checking whether F_{k–1}
= – F_{k} + F_{k+1} ; but just
adding F_{k} to both sides gives confirmation in the form of a known instance of (*).
And when k is odd (and > 2), it means checking instead whether
– F_{k–1} = F_{k} –
F_{k+1} ;
this time, we add F_{k–1}
+
F_{k+1} to both sides and again
obtain confirmation in the form of a known instance of (*). The only case not yet treated, namely that of
k = 1 , is now too easy to waste HTML bytes on (don’t believe me? — try it!).
Q. 3: In a nutshell, F_{1}² + . . . + F_{n}² =
F_{n}·(F_{n–1} + F_{n}) =
F_{n}·F_{n+1} .
Q. 4: Where M =   0 1   1 1   ,
we have: M   1   0   = 1^{st} column of M =
  0   1   ; M   0   1   = 2^{nd}
column of M =   1   1   ; and M 
 x   y   =   0x + 1y  
1x + 1y   =   y   x + y   . 
Q. 5: When n > 1 , M 
   F_{n–1} F_{n} 
   =    
F_{n} F_{n–1} + F_{n} 
   =    
F_{n} F_{n+1}     ,
using the frf (*) and the third part of Q. 4.

Q. 6: The only Fibonacci number the NW entry 0 in M can be is F_{0} .
With totally undirected thinking, the remaining entries 1 in M might be any of
F_{1} , F_{2} , or F_{–1} .
But, coupled with the results of Qq. 4 & 5, the suggestions to think of
  1   0   as     F_{–1}
F_{0}     and of   0   1   as 
   F_{0} F_{1}     lead
to the insights: 
1^{st} column of M = M   1   0  
= M     F_{–1}
F_{0}    
=     F_{0} F_{1}     , and

2^{nd} column of M = M   0   1  
= M     F_{0}
F_{1}    
=     F_{1} F_{2}     ,

on the basis of which we are led to write: M =     F_{0}
F_{1} F_{1} F_{2}     .

Q. 7 (i): We wish to confirm that M^{ n} =     F_{n–1} F_{n}
F_{n} F_{n+1}
    at least for n = 0, 1, 2 . First, for n = 0 , we have

   F_{n–1} F_{n}
F_{n} F_{n+1}
    =     F_{–1} F_{0} F_{0} F_{1}     =     1 0 0 1     = I_{2×2} = M^{ 0} ; for n = 1 , just see the last line of Q. 6, above; and for n = 2 , notice

   F_{n–1} F_{n}
F_{n} F_{n+1}
    =     F_{1} F_{2} F_{2} F_{3}     =     1 1 1 2     , while M^{ 2} =     0 1 1 1     ·     0 1 1 1     =     1 1 1 2     , too.

(ii) Assuming that n > 0 is an integer for which the formula
M^{ n} =     F_{n–1} F_{n}
F_{n} F_{n+1}
    happens to be valid, we have, as desired,

M^{ n+1} = M·M^{ n} =     0 1 1 1     ·     F_{n–1} F_{n}
F_{n} F_{n+1}
    =     F_{n} F_{n}_{+1}
F_{n}_{–1}+F_{n} F_{n}+F_{n}_{+1}
    =     F_{n} F_{n}_{+1}
F_{n}_{+1} F_{n}_{+2}
    .

N.B.: In Q. 13 we will see that the expression given here for M^{ n} is in fact valid for all integers n , and not just for n > 0 .
Q. 8, (i): det(M) = 0·1 – 1·1 = 0 – 1 = –1 ;
(ii): det(M^{ n}) = (det(M))^{n}
= (–1)^{n} ; (iii): (using 7(i)) det(M^{ n}) =
F_{n–1}·F_{n+1} –
(F_{n})^{2} ; and
(iv): combining (ii) and (iii), we have
F_{n–1}·F_{n+1} –
(F_{n})^{2} = (–1)^{n} ; if we rebalance this by adding
(F_{n})^{2} to both sides, we obtain
F_{n–1}·F_{n+1} =
(F_{n})^{2} + (–1)^{n} , as desired.
Q. 9, (i): First, divide both sides of the equation
F_{n–1}·F_{n+1} =
(F_{n})^{2} + (–1)^{n}
by (F_{n})^{2} to obtain 
F_{n–1} F_{n+1} ——
—— F_{n} F_{n}  = 1
+  (–1)^{n} ——— (F_{n})^{2} 
; 
now, multiply both sides of this result by 
F_{n} —— F_{n–1} 
to obtain the desired  F_{n+1} ——
F_{n}  = ( 1 + 
(–1)^{n} ——— (F_{n})^{2} 
)  F_{n} —— F_{n–1}
 . 
(ii): Divide both sides of the equation
F_{n–1}·F_{n+1} –
(F_{n})^{2} = (–1)^{n}
(with which 8(iv) begins) by F_{n}F_{n–1} ,
and you have the desired equation
F_{n+1} ——
F_{n}  –  F_{n} ——
F_{n–1}  = 
(–1)^{n} ——— F_{n}
F_{n–1}  .

(Alternatively, expand (multiply out) the RHS of the final result of 9(i), simplify, and then
rebalance, to come to the same conclusion.)
Q. 10: The number F_{n+k+1} is the SE entry
(in position (2,2)) in the matrix power M^{ n+k} .
But as M^{ n+k} =
M^{ n}·M^{ k}
and the SE entry in
M^{ n}·M^{ k}
is obtained by "zipping" together row 2 of M^{ n} with column 2 of
M^{ k} , that entry is just
F_{n} F_{k} + F_{n+1} F_{k+1} ;
thus:
F_{n+k+1} =
F_{n} F_{k} + F_{n+1} F_{k+1} .
Q. 11: Using either direct matrix multiplication or 7(i) (with n = 2), one finds:
M·M = M ² =   1 1   1 2   . 
But
I_{2×2} + M =   1 0   0 1   + 
 0 1   1 1   =   1 1   1 2   , also.
So M ² = I_{2×2} + M , QED.

(BTW: What do you get if you multiply on both sides by M^{ n–1} ,
for n > 1 ? — A.: M^{ n+1} =
M^{ n–1} + M^{ n} ,
an analogue to the frf (*).) 
Q. 12: Rebalancing M ² = I_{2×2} + M , we obtain
M ² – M = I_{2×2} . But
M ² – M can be factored, two different ways:
M·(M – I_{2×2}) =
M ² – M =
(M – I_{2×2})·M , whence also:
M·(M – I_{2×2}) =
I_{2×2} =
(M – I_{2×2})·M ,
and this shows M has
(M – I_{2×2})
as twosided inverse. (An alternate approach: by 8(i), M is invertible.
Writing M^{ }¹ for its inverse, multiply both sides of
M ² – M = I_{2×2} (on the left, say) by
M^{ }¹ . Simplifying, out pops
M – I_{2×2} = M^{ }¹ .)
Q. 13: Let n < 0 — say, n = – k with k =  n  > 0 . To see that
the formula of 7(i) remains valid for such n , when M^{ n} is
defined (as in the problem) as (M^{ }¹)^{ k} ,
it suffices to check that both (a) the RHS of 7(i) and (b) the matrix M^{ n}
= (M^{ }¹)^{ k} serve as inverse for
the matrix M^{ k} . First check (a):
M^{ k}· 
   F_{n–1} F_{n}
F_{n} F_{n+1}    
= 
   F_{k–1} F_{k}
F_{k} F_{k+1}    
·    
(–1)^{k+2}F_{k+1}
(–1)^{k+1}F_{k}
(–1)^{k+1}F_{k}
(–1)^{k}F_{k–1}    
=    
(–1)^{k+2}(F_{k–1}F_{k+1} –
(F_{k})²)
(–1)^{k+1}(F_{k–1}F_{k} –
F_{k}F_{k–1})
(–1)^{k+2}(F_{k}F_{k+1} –
F_{k+1}F_{k})
(–1)^{k+1}((F_{k})² –
F_{k+1}F_{k–1})    
= 
= 
   (–1)^{k+2}(–1)^{k}
(–1)^{k+1}·0 (–1)^{k+2}·0
(–1)^{k+1}(–(–1)^{k})     = 
 +1 0   0 +1   = I_{2×2} .

The other check (b) is easier, because, with M being invertible, so is each positive power
M^{ k} of M , and
(M^{ k})^{}¹ =
(M^{ }¹)^{ k} .
Q. 14: Recall that the quadratic formula identifies as roots of the polynomial
ax² + bx + c the quantities λ^{+} =
(^{1}/_{2a})(– b +
√ b² – 4ac ) , and
guarantees validity of the factorization formula ax² + bx + c =
(x – λ^{+ })(x – λ^{– }) .
For the polynomial p(x) = x² – x – 1 of the problem, we have
a = 1 , b = –1 , and c = –1 , so that
λ^{+} = ½ (1 + √ 5 ) and
λ^{–} = ½ (1 – √ 5 ) .
Alternatively, just multiply out the product
(x – λ^{+ })(x – λ^{– }) =
(x – ½
(1 + √ 5 ))(x –
½ (1 – √ 5 )) , and
notice that the result simplifies, using the relations (do check these, please!)
λ^{+ } + λ^{– } = 1 and
λ^{+ }·λ^{– } = –1 , to exactly the desired
polynomial p(x) = x² – x – 1 of the problem.
Q. 15: M – x·I_{2×2} = 
 0 1   1 1   –   x 0   0 x   = 
 –x 1   1 1–x  , whence
det(M – x·I_{2×2}) =
x² – x – 1 ; the eigenvalues of M are the roots of this
polynomial, found in Q. 14.

Q. 16, (i): Yes, M ·    
1 λ^{+ }    
=     λ^{+ } 1+λ^{+ } 
   and λ^{+ }·    
1 λ^{+ }     = 
   λ^{+ } (λ^{+ })^{2} 
  
are equal, because (λ^{+ })^{2} = 1+λ^{+ } (this follows from
(λ^{+ })^{2} – (1+λ^{+ }) = p(λ^{+ }) = 0 ).

(ii): Again: yes, M ·    
1 λ^{– }    
=     λ^{– } 1+λ^{– } 
   and λ^{– }·    
1 λ^{– }     = 
   λ^{– } (λ^{– })^{2} 
   are equal (argue as as for (i) — just replace each
“ λ^{+ } ” by a “ λ^{– } ” ). 
[Remarks: The upshot here, to be used in Qq. 1822, is that    
1 λ^{+ }    
is an eigenvector for M corresponding to the eigenvalue λ^{+ } , while 
  
1 λ^{– }     is an eigenvector for
M corresponding to the eigenvalue λ^{– } .]

Q. 17: (λ^{+ })^{2} = 1+λ^{+ } has already been checked, in 16(i) above;
(λ^{– })^{2} = 1+λ^{– } is checked the same way.
And both (λ^{+ })^{–1} = –λ^{– } and
(λ^{– })^{–1} = –λ^{+ } follow from the
observation λ^{+ }·λ^{– } = –1 made near the
end of the discussion of Q. 14 above.
Q. 18: The 2×2 matrices S and Λ are defined as
S =     1 1
λ^{– } λ^{+ }    
and Λ =     λ^{– } 0
0 λ^{+ }    
. And the discussion of Q. 16 
provides columnbycolumn confirmation that
M·S ( = 
   λ^{– } λ^{+ }
1+λ^{– } 1+λ^{+ } 
   ) = S·Λ ( = 
   λ^{– } λ^{+ }
(λ^{– })^{2} (λ^{+ })^{2} 
  
) . 
Q. 19: We have det(S) = λ^{+ } – λ^{– } =
½ (1 + √ 5 ) –
½ (1 – √ 5 ) =
½ √ 5 +
½ √ 5 =
√ 5 ; and det(Λ) =
λ^{+ }·λ^{– } = –1 , as in Q. 17 above.
Q. 20: Multiplying both sides of the equation (cf. Q. 18)
M·S = S·Λ
on the right by S^{ –1} , delivers M =
M·S·S^{ –1} =
S·Λ·S^{ –1} .
Raising both sides to a positive integer power n > 0 , one obtains
M^{ n} =
(S·Λ·S^{ –1})^{n}
= (S·Λ·S^{
–1})·(S·Λ·S^{
–1})· . . . ·(S·Λ·S^{
–1})·(S·Λ·S^{
–1}) = (S·Λ·S^{
–1})·(S·Λ·S^{
–1})· . . .
·(S·Λ^{2}·S^{
–1}) = . . . = (S·Λ·S^{
–1})·(S·Λ^{n–1}·S^{
–1}) = S·Λ^{n}·S^{
–1} .
Thus M^{ n} =
S·Λ^{n}·S^{
–1} for all integers n > 0 . For n = 0 , this equation remains valid because
M^{ 0} = I_{2×2} , and (as Λ^{0}
= I_{2×2} as well, by the same convention)
S·Λ^{0}·S^{ –1} =
S·S^{ –1} = I_{2×2} , too. Finally,
as each of the matrices M , S , and Λ is invertible (why?),
we must have M^{ –1} =
(S·Λ·S^{ –1})^{–1} =
S·Λ^{–1}·S^{ –1} ,
and raising both sides of this to the n^{th} power, for
n = – n < 0 , gives
M^{ n} = (M^{ –1})^{n}
= (S·Λ^{–1}·S^{ –1})^{n}
= S·(Λ^{–1})^{n}·S^{ –1}
= S·Λ^{n}·S^{ –1} ,
which thus finishes settling the matter for all integers n .
Q. 21: Three preliminary remarks will help.
First, for notational convenience, we will
write [0 1]^{T} in place of the column
  0   1   .

The other two:
(α) whatever the 2 × m matrix A , the matrix product
[0 1]·A just gives the second (= bottom) row of A ; and
(β) whatever the k × 2 matrix B , the matrix product
B·[0 1]^{T} just gives the second (= right hand) column of B .
(i) Applying remark (α) above to A = M^{ n} , and
taking into account the formula of 7(i), we have [0 1]·M^{ n}
= [F_{n} F_{n+1}] ; then, by applying (β) to
B = [F_{n} F_{n+1}] (or by just multiplying out),
we have [F_{n}
F_{n+1}]·[0 1]^{T} = F_{n+1} .
Thus [0 1]·M^{ n}·[0 1]^{T}
= F_{n+1} .
(ii) With S as above, and relying on remark (α),
we have [0 1]·S = the bottom row of S =
[λ^{– } λ^{+ }] .
(iii) Relying on remark (β) above,
S^{ –1}·[0 1]^{T} is
the second column of S^{ –1} . These entries are
easily computed, via the cofactors / signed minors approach, as being:
on top, ^{–1}/_{√5} ,
and below, ^{+1}/_{√5} , or
[ ^{–1}/_{√5}
^{+1}/_{√5} ]^{T} ,
all told.
Q. 22: Combining the results of Qq. 20 and 21, expanding Λ^{n} ,
multiplying out (twice), and simplifying, we obtain:
F_{n+1} =
[0 1]·M^{ n}·[0 1]^{T} =
[0 1]·S·Λ^{n}·S^{
–1}·[0 1]^{T} =
[λ^{– } λ^{+ } ] · 
  
(λ^{– })^{n} 0
0 (λ^{+ })^{n}    
·     
^{–1}/_{√5}
^{+1}/_{√5}     
= 
= [(λ^{– })^{n+1}
(λ^{+ })^{n+1}] ·     
^{–1} /_{√5}
^{+1} /_{√5}     
=
– (λ^{– })^{n+1}/√5 +
(λ^{+ })^{n+1}/√5 =
((λ^{+ })^{n+1} –
(λ^{– })^{n+1}) /√5 .

Q. 23: We establish the “closedform” formula F_{n} =
((λ^{+ })^{n} –
(λ^{– })^{n}) /√5
for the Fibonacci numbers
“out of the blue” for n > 0 by (i) checking the first few cases
(with n = 0, 1, & 2), and then (ii) checking the counterpart of
the frf (*) as a working principle for general n > 0 .
(i_{0}) (n = 0): F_{0} = 0 ;
but (λ^{+ })^{0} = 1 and (λ^{– })^{0} = 1 ,
so the difference in parentheses on the RHS is zero, hence the entire RHS
= 0 as well.
(i_{1}) (n = 1): F_{1} = 1 ;
but (λ^{+ })^{1} = λ^{+ } , and
(λ^{– })^{1} = λ^{– } ; and, by Q. 19,
λ^{+ } – λ^{– } =
√5 ; so the RHS
= 1 as well.
(i_{2}) (n = 2): F_{2} = 1 ; but (recall Q. 17)
(λ^{+ })^{2} = 1 + λ^{+ } , and
(λ^{– })^{2} = 1 + λ^{– } ; so, just as before,
(λ^{+ })^{2} – (λ^{– })^{2} =
(1 + λ^{+ }) – (1 + λ^{– }) =
λ^{+ } – λ^{– } =
√5 , and the RHS again
= 1 as well.
(ii) Suppose we have an integer n > 0 for which we happen already to know that
F_{n–1} =
((λ^{+ })^{n–1} –
(λ^{– })^{n–1}) /√5
and
F_{n} =
((λ^{+ })^{n} –
(λ^{– })^{n}) /√5
are valid.
We shall show that, as a consequence of these assumptions, the formula
F_{n+1} =
((λ^{+ })^{n+1} –
(λ^{– })^{n+1}) /√5
is valid too.
To do so, we note first that the LHS F_{n+1}
of the equation we seek to establish is the sum F_{n+1} =
F_{n–1} + F_{n} of the LHS’s
of the equations we are assuming valid; so it will suffice to establish that the RHS’s
stand in a similar relation to each other.
And for this it’s clearly enough to show that
((λ^{+ })^{n+1} –
(λ^{– })^{n+1})
=
((λ^{+ })^{n–1} –
(λ^{– })^{n–1})
+
((λ^{+ })^{n} –
(λ^{– })^{n}) .
But, fortunately, we do know
(λ^{+ })^{2} = 1 + λ^{+ } ,
and
(λ^{– })^{2} = 1 + λ^{– } .
Multiplying both sides of the first of these equations by
(λ^{+ })^{n–1} , and both sides of the second by
(λ^{– })^{n–1} , we obtain
(λ^{+ })^{n+1} =
(λ^{+ })^{n–1} +
(λ^{+ })^{n} and
(λ^{– })^{n+1} =
(λ^{– })^{n–1} +
(λ^{– })^{n} ;
then subtracting, we find that, indeed,
((λ^{+ })^{n+1}
–
(λ^{– })^{n+1})
= ((λ^{+ })^{n–1} +
(λ^{+ })^{n})
–
((λ^{– })^{n–1} +
(λ^{– })^{n})
=
((λ^{+ })^{n–1} –
(λ^{– })^{n–1})
+
((λ^{+ })^{n} –
(λ^{– })^{n}) ,
as desired. QED.
PS: A supplementary challenge (but an easy one) for the reader: prove
that this closedform formula for F_{n} remains valid
also for n < 0 .
Tentatively completed 11 June 2006 . . . Everything best
viewed at screen widths of 1,000 pixels or greater . . . Courier portions of Part III —
best viewed (sigh!) in MSIE 6 (Netscape 7 and Opera render with ugly misalignments).   Back to the Math 221 Home Page 