Linear algebra has many applications in mathematics, and in science and engineering in general. It is less often associated with results in discrete mathematics. In this course we will meet some such results in my area of interest, combinatorics and algorithms. The appearance of linear algebra methods in these results is often unexpected, and leads to some beautiful proofs.
The course is meant for undergraduate students. Third year students who have taken second year linear algebra will have no problem to follow. I will also review some necessary linear algebra, so that students who have only taken freshman linear algebra can follow with a bit of effort.
Each result I present will be self-contained, so this course is very suitable for students who only want to audit it and can't be present in every class.
The course is cross-listed and offered as both CS492A (Special Topics in Computer Science) and MAS480B (Special Topics in Mathematics).
Lectures are given in English. The class meets Monday, Wednesday, and Friday from 10:00 to 10:50 in room 2445 (classroom 4) in the Computer Science Building (E3-1).
Students should enroll for the course on Moodle. This will allow you to see your grades as soon as I have computed them, instead of when they are released on CAIS.
We have two forums for the course on Moodle:
Students will be graded based on homeworks (40%), a final exam (40%), and participation (20%). There will be no midterm exam.
There will be a final exam on Friday, May 7, from 10:00 to 11:00 in our usual class room.
The exam is open book: You can bring one copy of the lecture notes by Jiří Matoušek. No other references are allowed.
This class will be based on lecture notes written by Jiří Matoušek. The lecture notes are not publicly available, but will be provided to students in the course.
Here is a rough list of what we will cover in each week of the semester.
| Week 1 | Fibonacci numbers |
| Week 2 | Set systems with prescribed intersection patterns |
| Week 3 | Are these distances Euclidean? |
| Week 4 | Complete graphs from bipartite graphs |
| Week 5 | Counting spanning trees |
| Week 6 | Error-correcting codes |
| Week 7 | Checking computations |
| Week 8 | No class (midterm exam week) |
| Week 9 | Petersen, Hoffman-Singleton, and maybe 57 |
| Week 10 | Point sets with only two distances |
| Week 11 | A result from discrepancy theory |
| Week 12 | Tilings |
| Week 13 | Kakeya's conjecture for finite fields |
| Week 14 | Shannon capacity of a graph |
| Week 15 | Rotating the cube |
| Week 16 | Final Exam week |
The material covered in the lectures so far:
| 02-01 | Introduction, Odd distances, Clubs of Oddtown | Ch. 6, Ch. 3 |
| 02-03 | Fibonacci numbers | Ch. 1, Ch. 2 |
| 02-05 | Walking in the yard | Ch. 20 |
| 02-10 | Complete graph from bipartite graphs | Ch. 8 |
| 02-17 | Vector spaces, Tiling a rectangle | Ch. 12 |
| 02-19 | Linear codes | Ch. 5 |
| 02-22 | Equiangular lines, same-size intersection | Ch. 9, Ch. 4 |
| 02-24 | Covering a cube, Only two distances | Ch. 16, Ch. 15 |
| 02-26 | Joints and Lines | arXiv:0906.0558 |
| 03-03 | Three Petersen graphs are not enough | Ch. 13 |
| 03-05 | Petersen, Hoffman-Singleton, perhaps 57 | Ch. 14 |
| 03-08 | Counting spanning trees I | Ch. 21 |
| 03-10 | Counting spanning trees II, Medium-size intersection | Ch. 21, Ch. 17 |
| 03-12 | Borsuk's question | Ch. 18 |
| 03-17 | Counting tilings I | Ch. 22 |
| 03-19 | Counting tilings II | Ch. 22 |
| 03-29 | Integer partitions I | Ch. 23 |
| 03-31 | Integer partitions II | Ch. 23 |
| 04-02 | Find the triangle, Checking matrix multiplication | Ch. 10, Ch. 11 |
| 04-05 | Perfect matchings | Ch. 24 |
| 04-07 | Counting compositions | Ch. 26 |
| 04-09 | Is it associative? | CH. 27 |
| 04-12 | Spectral partitioning I | Ch. 31 |
| 04-14 | Spectral partitioning II | Ch. 31 |
| 04-16 | Sauer's lemma | Smolensky's paper |
| 04-21 | Euclidean distances | Ch. 7, Ch. 30 |
| 04-23 | More on Euclidean distances | Ch. 30 |
| 04-26 | Shannon Capacity I | Ch. 28 |
| 04-28 | Shannon Capacity II | Ch. 28 |
| 04-30 | Review Homework 2 | |
| 05-07 | Final exam | |
| 05-10 | Review Homework 3 and exam |
There will be a few homework assignments in this course. You will have one or two weeks to complete an assignment. Homeworks must be submitted on paper and must be handed in at the beginning of class.