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

by 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.

Genres: Mathematics

182 pages, Paperback

First published June 18, 2010

Reviews

[Swati · Rating 5 out of 5]

Oh what an absolute delight to read. I had a terribly tedious flight - during the pandemic, hence made terrible by the mask-wearing for 30+ hours - and this book kept me sane, engaged, and even happy, throughout the journey. I think my favourite "miniatures" were counting triangles in a graph in n^omega time using matrix multiplication as well as the one about "oddtown" -- both are very clever.

If you have taken any linear algebra, this is a great book to read, since you get to see it applied in a wide range of problems where you wouldn't really expect any linear algebra! Not at all surprised by the quality, to be frank. I've read Matousek's books on SDPs and LPs, and both are just as phenomenal. When you read a book you enjoy loving and then realize the author is no more, that's when you really mourn the author. I hope I can inculcate Matousek's excellent expository skills in my writing. Some day.

[Stefan · Rating 5 out of 5]

A gem of a book, which is a strong reminder of how elegant and how much fun mathematics can be.

[Leonardo · Rating 5 out of 5]

Una excelente colección de aplicaciones de álgebra lineal en teoría de gráficas, geometría discreta y computación.

En este libro Maousek muestra 33 aplicaciones de álgebra lineal básica a distintos problemas matemáticos. Cada una de las aplicaciones está contenida en un capítulo independiente que se puede leer prácticamente sin haber leido lo demás. Incluso dentro de cada capítulo hay pequeños recordatorios de las herramientas de álgebra lineal que se usan.

El formato es muy cómodo y motivacional. Al inicio de cada capítulo se da una pequeña introducción y se enuncia el problema a tratar. Matousek explica los aspectos interesantes del problema y lo pone en contexto con otros problemas del área. Si la demostración del capítulo es larga, se comienza con un pequeño resumen de la estrategia que se usará. Si no, se pasa directamente a las ideas pricipales y se comienza a trabajar. Debido a la motivación previa y a la forma en la que se redacta, las demostaciones son muy transparentes.

Una cosa muy valiosa de este libro es que en verdad sirve como punto de entrada para los argumentos más difíciles. Por ejemplo, en algunas ocasiones Matousek sacrifica una mejor cota de un problema para tener a cambio una explicación más clara. Para los lectores interesados, al final de cada capítulo hay bibliografía en donde se pueden revisar las mejores cotas a los problemas que se tratan.

[Zohreh Jafari · Rating 4 out of 5]

A beautiful book with many neat proofs for Algorithmic theorems. Just there are few errors and some ambiguity in explanations.

[Abbas Mehrabian · Rating 5 out of 5]

Very well-written book, full of new ideas. I have written a review (in Persian) in my blog: http://bi-nahayat.persianblog.ir/post...