**Student Mathematical Library**

Volume: 53;
2010;
182 pp;
Softcover

MSC: Primary 05; 68; 15;

Print ISBN: 978-0-8218-4977-4

Product Code: STML/53

List Price: $38.00

Individual Price: $30.40

**Electronic ISBN: 978-1-4704-1636-2
Product Code: STML/53.E**

List Price: $38.00

Individual Price: $30.40

#### You may also like

#### Supplemental Materials

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

Share this page
*Jiří Matoušek*

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.

#### Table of Contents

# Table of Contents

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

- Cover Cover11 free
- Title page i2 free
- Contents iii4 free
- Preface v6 free
- Notation ix10 free
- Fibonacci numbers, quickly 112 free
- Fibonacci numbers, the formula 314
- The clubs of Oddtown 516
- Same-size intersections 718
- Error-correcting codes 1122
- Odd distances 1728
- Are these distances Euclidean? 1930
- Packing complete bipartite graphs 2334
- Equiangular lines 2738
- Where is the triangle? 3142
- Checking matrix multiplication 3546
- Tiling a rectangle by squares 3950
- Three Petersens are not enough 4152
- Petersen, Hoffman–Singleton, and maybe 57 4556
- Only two distances 5162
- Covering a cube minus one vertex 5566
- Medium-size intersection is hard to avoid 5768
- On the difficulty of reducing the diameter 6172
- The end of the small coins 6778
- Walking in the yard 7182
- Counting spanning trees 7788
- In how many ways can a man tile a board? 8596
- More bricks—more walls? 97108
- Perfect matchings and determinants 107118
- Turning a ladder over a finite field 113124
- Counting compositions 119130
- Is it associative? 125136
- The secret agent and umbrella 131142
- Shannon capacity of the union: a tale of two fields 139150
- Equilateral sets 147158
- Cutting cheaply using eigenvectors 153164
- Rotating the cube 163174
- Set pairs and exterior products 171182
- Index 179190 free
- Back Cover Back Cover1194

#### Readership

Undergraduates, graduate students and research mathematicians interested in combinatorics, graph theory, theoretical computer science, and geometry.

#### Reviews

Finding examples of "linear algebra in action" that are both accessible and convincing is difficult. Thirty-three Miniatures is an attempt to present some usable examples. . . . For me, the biggest impact of the book came from noticing the tools that are used. Many linear algebra textbooks, including the one I use, delay discussion of inner products and transpose matrices till later in the course, which sometimes means they don't get discussed at all. Seeing how often the transpose matrix shows up in Matousek's miniatures made me realize space must be made for it. Similarly, the theorem relating the rank of the product of two matrices to the ranks of the factors plays a big role here. Most linear algebra instructors would benefit from this kind of insight. . . . Thirty-three Miniatures would be an excellent book for an informal seminar offered to students after their first linear algebra course. It may also be the germ of many interesting undergraduate talks. And it's fun as well.

-- Fernando Q. Gouvêa, MAA Reviews

[This book] is an excellent collection of clever applications of linear algebra to various areas of (primarily) discrete/combinatiorial mathematics. ... The style of exposition is very lively, with fairly standard usage of terminologies and notations. ... Highly recommended.

-- Choice