László Babai's Summer 2015 Math REU page

Apprentice program: Linear Algebra and Combinatorics
(June 22 - July 24, weeks 1 - 5)

Press your browser's "REFRESH" button to get the current version of this page.

What is NEW?

Notes complete, including detailed notes for the last class (7-24).

TA office hours in the Theory Lounge, Ryerson 162:

7-22 Wednesday 2:00 Abby
7-21 Tuesday 12:00 Angela
7-20 Monday 12:30 Angela
7-17 Friday 1:30 Abby
7-16 Thursday 2:15 Tim
7-14 Tuesday 12:00 Angela

Course information

Instructor: László Babai
Office: Ry 164
Email: laci@cs.uwaukeegan.edu
(Oops! wrong town - to be eligible, you must guess the right one.
Oh, you are just a poor little bot? I am sooo sorry.)

TAs: Sean Howe, Abigail Ward, Angela Wu, Tim Black
Email: seanphk@math.etc, arward12@jmail.etc (sorry, I keep confusinj some letters of the alphabet...), yuwanish@jamil.com (oh, more typos) timwhite@jmail.etc (oh, got name worng)

Instructor Wednesday and Friday, June 24 and 26: Madhur Tulsiani
Email: (concatenation of mad and hurt) at ttic dot edu.

Schedule: Every day 9:30 - 12:00, Ry-251. First week: MWF instructors, TuTh TAs (problem session). Second week: MTh TAs, TuWF instructor. Please send me email if you find that this schedule is in conflict with Peter May's REU 2015 website.
The problem sessions are an integral part of the course. Come prepared, contribute your thoughts. Send me email if you find a mistake in the notes.


Notes for class 25 (last class), Fri July 24 (rational roots of polynomials with integer coefficients, conclusion of the proof of the Hoffman-Singleton Theorem, operator norm, random walks/finite Markov Chains, eigenvalue gaps vs. mixing rate, Singular Value Decomposition, closest low-rank approximation of a matrix, transpose of a linear map, Hermitian spaces, adjoint (conjugate-transpose) matrix, Hermitian, unitary, and normal matrices, complex version of the Spectral Theorem)

Notes for class 24, Thu July 23 (direct sum of subspaces, matrices vs. invariant subspaces, similarity to triangular matrix, polynomials of matrices, the Cayley--Hamilton Theorem, girth of graphs, adjacency matrix, the Hoffman--Singleton Theorem)

Notes for class 23, Wed July 22 (Eventown Theorem, maximal totally isotropic subspaces, perp of an invariant subspace of a symmetric transformaion is an invariant subspace, conclusion of the proof of the Spectral Theorem: proving that argmax of the Rayleigh quotient is an eigenvector, orthogonal similarity, characteristic polynomial of block-diagonal and block-triangular matrices)

Problems for class 22, Tue July 21, posted in advance.

Notes for class 21, Mon July 20 (curve in general position, dot product geometry over an arbitrary field, perpendicular subspace and its dimension, totally isotropic subspaces and their dimension, Eventown, Oddtown, invariant subspaces in Euclidean space, proof of Spectral Theorem (first part: induction))

Problems for class 20, Fri July 17, posted in advance.

Notes for class 19, Thu July 16, posted in advance: priority probems for this problem session

Notes for class 18, Wed July 15 (Euclidean spaces, Gram-Schmidt orthogonalization, orthogonal functions, orthogonal polynomials, interlacing, log-concavity, orthogonal and symmetric transformations and matrices, Spectral Theorem stated, matchings polynomial, Heilmann-Lieb Theorem)

Notes for class 17, Tue July 14, posted in advance: priority probems for this problem session

Notes for class 16, Mon July 13 (change of basis)

Notes for class 15, Fri July 10 (affine subspace, systems of linear equations, transpose, rank of product, right and left inverses, factoring real polynomials, matrices vs. linear maps, rotation matrix)

Notes for class 13, Wed July 8 (polynomials, degree, Division Theorem, multiple roots, complex roots of unity, systems of homogeneous linear equations, trace of a matrix, characteristic polynomial, eigenvalues, algebraic vs. geometric multiplicity, similar matrices, diagonalizability, eigenbasis)

Notes for class 12, Tue July 7 (problem session; new problems added for Thursday: Algebra Dragon strikes Again! and a really small maximal system of clubs in Clubtown, among others)

Notes for class 11, Mon July 6

Notes for class 10, Fri July 3

Notes for class 9, Thu July 2 (problem session)

Notes for class 8, Wed July 1

Notes for class 7, Tue June 30

Notes for class 6, Mon June 29 (problem session)

Notes for class 5, Fri June 26

Notes for class 4, Thu June 25 (problem session)

Notes for class 3, Wed June 24

Notes for class 2, Tue June 23 (problem session)

Notes for class 1, Mon June 22


Feel free to contact the instructor regarding the problems assigned. If you like solving simple but challenging problems, check out the instructor's 2012 REU problem sets:

Linear algebra and general math puzzle problems

Additional links:

My home page

Back to top