This volume contains a collection of clever mathematical applications of linear algebra, mainly in combinatorics, geometry, and algorithms. Each chapter covers a single main result with motivation and full proof in at most ten pages and can be read independently of all other chapters (with minor exceptions), assuming only a modest background in linear algebra. The topics include a number of well-known mathematical gems, such as Hamming codes, the matrix-tree theorem, the Lovász bound on the Shannon capacity, and a counterexample to Borsuk's conjecture, as well as other, perhaps less popular but similarly beautiful results, e.g., fast associativity testing, a lemma of Steinitz on ordering vectors, a monotonicity result for integer partitions, or a bound for set pairs via exterior products. The simpler results in the first part of the book provide ample material to liven up an undergraduate course of linear algebra. The more advanced parts can be used for a graduate course of linear-algebraic methods or for seminar presentations.
Jirí Matoušek: Charles University, Prague, Czech Republic
Preface Notation Miniature 1. Fibonacci Numbers, Quickly 1 Miniature 2. Fibonacci Numbers, the Formula 3 Miniature 3. The Clubs of Oddtown 5 Miniature 4. Same-Size Intersections 7 Miniature 5. Error-Correcting Codes 11 Miniature 6. Odd Distances 17 Miniature 7. Are These Distances Euclidean? 19 Miniature 8. Packing Complete Bipartite Graphs 23 Miniature 9. Equiangular Lines 27 Miniature 10. Where is the Triangle? 31 Miniature 11. Checking Matrix Multiplication 35 Miniature 12. Tiling a Rectangle by Squares 39 Miniature 13. Three Petersens Are Not Enough 41 Miniature 14. Petersen, Hoffman–Singleton, and Maybe 57 45 Miniature 15. Only Two Distances 51 Miniature 16. Covering a Cube Minus One Vertex 55 Miniature 17. Medium-Size Intersection Is Hard To Avoid 57 Miniature 18. On the Difficulty of Reducing the Diameter 61 Miniature 19. The End of the Small Coins 67 Miniature 20. Walking in the Yard 71 Miniature 21. Counting Spanning Trees 77 Miniature 22. In How Many Ways Can a Man Tile a Board? 85 Miniature 23. More Bricks—More Walls? 97 Miniature 24. Perfect Matchings and Determinants 107 Miniature 25. Turning a Ladder Over a Finite Field 113 Miniature 26. Counting Compositions 119 Miniature 27. Is It Associative? 125 Miniature 28. The Secret Agent and the Umbrella 131 Miniature 29. Shannon Capacity of the Union: A Tale of Two Fields 139 Miniature 30. Equilateral Sets 147 Miniature 31. Cutting Cheaply Using Eigenvectors 153 Miniature 32. Rotating the Cube 163 Miniature 33. Set Pairs and Exterior Products 171 Index 179