Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra

Jirí Matoušek

ISBN: 9781470454845 | Year: 2019 | Paperback | Pages: 196 | Language : English

Book Size: 140 x 216 mm | Territorial Rights: Restricted| Series American Mathematical Society

Price: 1485.00

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


`