LINEAR ALGEBRA PROBLEM BOOK Paul R. Halmos THE DOLCIANI MATHEMATICAL EXPOSITIONS Publishedby THEMATHEMATICAL ASSOCIATIONOFAMERICA CommitteeonPublications JAMESW. DANIEL,Chairman DolcianiMathematicalExpositionsEditorialBoard BRUCEP.PALKA, Editor CHRISTINEW. AYOUB IRLC. BIVENS BRUCEA. REZNICK The DolcianiMathematicalExpositions NUMBERSIXTEEN LINEAR ALGEBRA PROBLEM BOOK PAUL R. HALMOS PublishedandDistributedby THEMATHEMATICAL ASSOCIATIONOFAMERICA (cid:13)c1995by TheMathematicalAssociationofAmerica(Incorporated) LibraryofCongressCatalogCardNumber94-79588 PrintISBN978-0-88385-322-1 ElectronicISBN978-1-61444-212-7 PrintedintheUnitedStatesofAmerica Currentprinting(lastdigit): 10987654 The DOLCIANI MATHEMATICAL EXPOSITIONS series of the Mathematical Association of America was established through a generous gift to the Association from Mary P. Dolciani, Professor of MathematicsatHunter College of the City Uni- versity of New York. Inmakingthe gift, Professor Dolciani, herself anexceptionally talented and successful expositor of mathematics, had the purpose of furthering the ideal of excellencein mathematicalexposition. TheAssociation,foritspart,wasdelightedtoacceptthegraciousgestureinitiating the revolving fund for this series from one who has served the Association with distinction, both asamember of the Committee on Publicationsandasamember of the Board of Governors. It was with genuine pleasure that the Board chose to name the seriesin herhonor. Thebooksintheseriesareselectedfortheirlucidexpositorystyleandstimulating mathematical content. Typically, they contain an ample supply of exercises, many with accompanyingsolutions. Theyare intendedto besufficiently elementaryfor the undergraduateandeventhemathematicallyinclinedhigh-schoolstudenttounderstand andenjoy,butalsotobeinteresting andsometimeschallengingtothemoreadvanced mathematician. 1. MathematicalGems,RossHonsberger 2. MathematicalGemsII, RossHonsberger 3. MathematicalMorsels,RossHonsberger 4. MathematicalPlums, RossHonsberger (ed.) 5. GreatMomentsinMathematics(Before1650),HowardEves 6. MaximaandMinima withoutCalculus,IvanNiven 7. GreatMomentsinMathematics(After1650),Howard Eves 8. MapColoring,Polyhedra,andtheFour-ColorProblem,DavidBarnette 9. MathematicalGemsIII, RossHonsberger 10. MoreMathematicalMorsels,RossHonsberger 11. OldandNewUnsolvedProblemsinPlaneGeometryandNumberTheory,Victor Klee andStanWagon 12. ProblemsforMathematicians,YoungandOld, PaulR. Halmos 13. ExcursionsinCalculus:AnInterplayoftheContinuousandtheDiscrete,Robert M.Young 14. The WohascumCounty Problem Book, George T. Gilbert, Mark I. Krusemeyer, LorenC. Larson 15. Lion Hunting and Other Mathematical Pursuits: A Collection of Mathematics, Verse, and Stories by Ralph P. Boas, Jr., Gerald L. Alexanderson and Dale H. Mugler (eds.) 16. LinearAlgebraProblemBook,PaulR. Halmos 17. FromErdo}stoKiev:Problemsof OlympiadCaliber,RossHonsberger 18. WhichWayDidtheBicycleGo?...andOtherIntriguingMathematicalMysteries, JosephD.E. Konhauser,DanVelleman,andStanWagon 19. InPo(cid:19)lya’sFootsteps:MiscellaneousProblemsandEssays,RossHonsberger 20. Diophantusand Diophantine Equations, I. G. Bashmakova(Updated by Joseph Silvermanandtranslated byAbe Shenitzer) 21. LogicasAlgebra,PaulHalmosandStevenGivant 22. Euler:TheMasterof UsAll, William Dunham 23. TheBeginningsandEvolutionofAlgebra,I.G.BashmakovaandG.S.Smirnova (Translated byAbeShenitzer) 24. MathematicalChestnutsfrom AroundtheWorld,RossHonsberger 25. Counting on Frameworks:Mathematics to Aid the Design of Rigid Structures, JackE. Graver 26. MathematicalDiamonds,RossHonsberger 27. Proofs that Really Count: The Art of Combinatorial Proof, Arthur T. Benjamin andJennifer J.Quinn 28. MathematicalDelights, RossHonsberger 29. Conics,Keith Kendig 30. Hesiod’sAnvil:fallingandspinningthroughheavenandearth,AndrewJ.Simo- son 31. A GardenofIntegrals,FrankE.Burk 32. A Guideto ComplexVariables(MAA Guides#1),Steven G. Krantz 33. SinkorFloat?ThoughtProblemsin MathandPhysics,Keith Kendig 34. Biscuitsof NumberTheory,Arthur T. BenjaminandEzraBrown 35. UncommonMathematicalExcursions:PolynomiaandRelatedRealms,DanKalman 36. When Lessis More: Visualizing BasicInequalities, Claudi Alsina andRoger B. Nelsen 37. A Guideto AdvancedRealAnalysis(MAA Guides#2),Gerald B.Folland 38. A Guideto RealVariables(MAA Guides#3), Steven G.Krantz 39. Voltaire’s Riddle: Microme(cid:19)gas and the measure of all things, Andrew J. Simoson 40. A Guideto Topology,(MAA Guides#4), StevenG. Krantz 41. A Guideto ElementaryNumberTheory,(MAA Guides#5), UnderwoodDudley 42. CharmingProofs:AJourneyintoElegantMathematics,ClaudiAlsinaandRoger B. Nelsen 43. MathematicsandSports,editedbyJosephA. Gallian 44. A Guideto AdvancedLinearAlgebra,(MAA Guides#6),Steven H. Weintraub 45. Iconsof Mathematics:AnExplorationofTwentyKeyImages,ClaudiAlsinaand Roger B.Nelsen 46. A Guideto PlaneAlgebraicCurves,(MAA Guides#7),Keith Kendig 47. NewHorizonsinGeometry,Tom M. Apostol andMamikonA. Mnatsakanian 48. A Guideto Groups,Rings,andFields,(MAA Guides#8),FernandoQ. Gouve^a 49. A Guideto FunctionalAnalysis,(MAA Guides#9),Steven G. Krantz MathematicalAssociationof America P.O. Box 91112 Washington,DC20090-1112 1-800-331-1MAA FAX: 1-301-206-9789 PREFACE Is it fun to solve problems, and is solving problems about somethinga good way to learn something?The answers seem to be yes, providedtheproblems are neithertoo hard nor too easy. Thebook is addressed to students(and teachers) of undergraduatelinear algebra|itmightsupplementbutnot(I hope)replacemyoldFinite-Dimen- sionalVectorSpaces.Itlargelyfollowsthatoldbookinorganizationandlevel and order|but only \largely"|the principle is often violated. This is not a step-by-step textbook|the problems vary back and forth between subjects, theyvaryback and forthfromeasy tohardand back again. Thelocationof a problem is not always a hint to what methods might be appropriate to solve it or how hard it is. Words like \hard" and \easy" are subjective of course. I tried to make some of the problems accessible to any interested grade school student, and at the same time to insert some that might stump even a professional expert (at least for a minute or two). Correspondingly, the statements of the prob- lems, and the introductions that precede and the solutions that follow them sometimes laboriously explain elementary concepts, and, at other times as- sume that you are at home with the language and attitude of mathematics at the research level. Example: sometimes I assume that you know nothing, and carefullyexplaintheassociative law, butat othertimesI assume thatthe word \topology", while it may not refer to something that you are an expert in, refers to something that you have heard about. The solutionsare intrinsicparts of the exposition.You are urged to look at the solution of each problem even if you can solve the problem without doing so|the solution sometimes contains comments that couldn’t be made inthestatementof theproblem,or even inthehint,withoutgiving too much of the show away. vii viii LINEARALGEBRAPROBLEMBOOK I hope youwillenjoy tryingto solve theproblems, I hope youwilllearn something by doing so, and I hope you will have fun. CONTENTS Preface .............................................................vi Chapter 1. Scalars ...................................................1 1. Double addition 2. Half doubleaddition 3. Exponentiation 4. Complex numbers 5. Affine transformations 6. Matrix multiplication 7. Modular multiplication 8. Small operations 9. Identityelements 10. Complex inverses 11. Affine inverses 12. Matrix inverses 13. Abelian groups 14. Groups 15. Independentgroup axioms 16. Fields 17. Additionand multiplicationin fields 18. Distributivefailure 19. Finitefields Chapter 2. Vectors ..................................................17 20. Vector spaces 21. Examples 22. Linear combinations 23. Subspaces 24. Unions of subspaces ix