Applications of Linear Algebra | Summer 2024

Applications of Linear Algebra

Summer 2024

This course explores applications of tools from linear algebra in combinatorics, geometry, algorithms, and graph theory. We will emphasize proofs and proof techniques. The goal is to use the applications as a backdrop to practice and review linear algebra skills, but also to develop a an understanding of new proof techniques and recognize how to apply them in new settings as well.

Logsitically, this course is a special summer offering meant for advanced students of the IITM online BS program in Data Science and undergraduate students of IIT Gandhinagar. Anyone with a background in linear algebra and an interest in the material is welcome to follow along.

A little linear algerba won’t hurt. Try starting here if you have never encountered linear algebra concepts before:

  1. The Linear Algebra course on Khan Academy
  2. The 3blue1brown Playlist on the “Essence of Linear Algebra”
  3. An interactive introduction from Brilliant.

We will closely follow Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra. Additional pointers to tangents and related material will be listed on the individual notes pages.

Class recordings and slides will be shared on this website as we go along. Notes will be made available on a best-effort basis.

  • The pre-requisite assignment does not contribute to the course grade.
  • The assignments are worth 45% of the final grade (best 3 out of 4, 10% each).
  • The course project is a visualization-based programming project worth 15% of the final grade.
  • The midsem exam is worth 15% of the final grade.
  • The endsem exam is worth 25% of the final grade.
  • The lectures will be held between 4PM and 6PM on the indicated dates.
  • The venue will be announced shortly.
  • The course is hybrid, and students who are joining us remotely can attend classes in real-time over Zoom.
  • The Zoom link will be shared over email with registered participants.
  • The video recordings of the classes will be made available on this website as we go along.
Date Lecture Slides Notes Video
17 May, 2024 01. Oddtown, Eventown, and Same-Size Intersections and Medium-Size Intersections
19 May, 2024 02. Erdős-Ko-Rado Theorem and Sperner's theorem
21 May, 2024 03. An introduction to VC Dimension
23 May, 2024 04. The Sauer-Shelah Lemma
25 May, 2024 05. Computing Fibonacci Numbers, Quickly
27 May, 2024 06. Review and Recap
04 Jun, 2024 07. Finding Triangles · The Schwartz–Zippel theorem · Perfect Matchings and Determinants
06 Jun, 2024 08. In How Many Ways Can a Man Tile a Board? · Counting Compositions · Is it Associative?
12 Jun, 2024 09. Turning a Ladder Over a Finite Field
14 Jun, 2024 10. Equilateral Sets · Two Distances
16 Jun, 2024 11. Are These Distances Euclidean?
18 Jun, 2024 12. Rotating the Cube
20 Jun, 2024 13. Odd Distances · Tiling a Rectangle by Squares · Covering a Cube Minus One Vertex
22 Jun, 2024 14. Review and Recap
24 Jun, 2024 15. Packing Complete Bipartite Graphs · Three Petersens Are Not Enough
26 Jun, 2024 16. Counting Spanning Trees
28 Jun, 2024 17. Cutting Cheaply Using Eigenvectors
30 Jun, 2024 18. Petersen, Hoffman–Singleton, and Maybe 57
02 Jul, 2024 19. The Secret Agent and the Umbrella
04 Jul, 2024 20. Shannon Capacity of the Union: A Tale of Two Fields
No matching items
Issued Assessment Problems Solutions Due
10 May, 2024 Assignment 0 (Pre-Requsites)
20 May, 2024 Assignment 1 (Set Systems)
03 Jun, 2024 Assignment 2 (Randomized Algorithms)
12 Jun, 2024 Assignment 3 (Geometry)
22 Jun, 2024 Assignment 4 (Graphs)
No matching items