# László Babai's Summer 2017 Math REU page Apprentice program: Linear Algebra and Combinatorics (June 19 - July 21, weeks 1 - 5)

## Material covered during last class, Friday, July 21

• Proof of Singular Value Decomposition
• Low-rank approximation theorem proved    (cool applied math!) - AI: machine learning, recommender systems, etc.
• Finite Markov Chains. Evolution, stationary distribution. Perron-Frobenius Theorem: nonnegative matrix has nonnegative eigenvector. (Stated, not proved.) Corollary: Every finite MC has a stationary distribution.
• Convergence rate of naive random walk on regular graph estimated via eigenvalue gap (stated, proved).
• Hoffmann-Singleton Theorem: If $k$-regular graph of girth $\ge 5$ has $n=k^2+1$ vertices then $k\in\{1,2,3,7,57\}$    (cool math!)

As of 7-14, classes moved to Ryerson 251!

## Class notes posted

Attention! Read instructor's comments next to the link to the Tue, June 27 class notes. "Chromatic polynomial" problem due Monday, July 3.

## Text

Online text by instructor: Discover Linear Algebra

Note: our point of view will be quite different from that taken in Math 19620 -- Linear Algebra. Nevertheless, I recommend the text used in that course, by Otto Bretscher, as a helpful supplement.

For graph theory, consult the

## 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.)

Schedule: Every day 9:30 - 12:00, Ry-251 [was Eck-133 until 7-13]

Peter May's REU 2017 website has all the schedules for the REU

TAs:
Dylan Quintana     dlastname at XX
Yulun Wang           firstname at XX
Karen Butt             firstnamelastname at XX
Peter Xu                 firstnamex at XX
(XX means uwaukeegan.edu --- fix the town)
Ben Lowe               lastnameb24 at geemail (fix spelling of mail service)
Amanda Burcroff      lastname at umich.eedduu (fix spelling)

TAs' office hours: 4-5pm in Ry-162 ("Theory lounge") each day of lectures, starting Tue June 20. The dates are:
Tue June 20 (Yulun), Thu June 22 (Dylan), Fri June 23 (Yulun), Wed June 28 (Peter), Thu June 29 (Karen), Fri June 30 (Yulun), Wed July 5 (Karen), Fri July 7 (Yulun), Mon July 10 (Peter), Wed July 12 (Dylan), Fri July 14 (Dylan), Mon July 17 (Yulun), Wed July 19 (Karen)

Schedule of problem sessions (during scheduled class time):
Wed June 21 (Dylan, Peter), Mon June 26 (Peter, Yulun), Tue June 27 (Peter, Dylan), Fri June 30 (Dylan, Karen), Thu July 6 (Karen, Yulun), Tue July 11 (Yulun, Peter), Thu July 13 (Yulun, Dylan), Tue July 18 (Dylan, Amanda), Thu July 20 (Amanda, Peter)

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

## Homework policy

Homework is required for the Apprentice program!
Most linear algebra problems assigned will be from the instructor's "Discover Linear Algebra" text and will be identified like "DLA 8.3.6" for problem 8.3.6 from the text.

Three types of homework will be assigned.

• 'DO' exercises help you understand the basic concepts. As their name suggests, you are expected to solve them, typically by the next day, but DO NOT HAND THEM IN; rather, be prepared to discuss your solution in class.
• 'HW' problems are to be handed in, typeset in Latex, at the beginning of the next class unless another deadlines has been announced. Most problems have brief, elegant solutions. Clarity and elegance matter. The instructor will attempt to give you feedback, but overly complicated, lengthy solutions will be ignored for lack of grader capacity.
• Self-grading experiment. Once the solution to a HW problem has been discussed in class, please submit a sheet at the beginning of the next class, stating your rating of your solution on the following scale.
• correct, simple -- is it essentially the same or is it significantly different from the solution stated in class?
• correct but could be simplified (please briefly elaborate)
• minor error, easy to fix (please briefly elaborate)
• major error (please briefly elaborate)
• solution incomplete -- please briefly specify what was done right and what was missing or in error
• cannot decide (please explain briefly)
• Challenge problems (CH) may or may not have a deadline, but they expire once discussed in class. Unlike the HW problems, they carry no point value, but they will earn you the attention of the instructor (in addition to earning you the satisfaction at having solved them). This may come in handy, e.g., if you need a letter of reference in the future.
• Policy on collaboration. Collaboration on DO exercises is encouraged. For HW problems, collaboration is neither encouraged nor prohibited; please name your collaborators on your solution.
• Policy on web sources. You are welcome to study web resources to augment your knowledge of the subject. However, use of the web with the specific aim to solve problems is discouraged and self-defeating. On today's internet you can find virtually everything. We learn by creative problem solving, and you will deprive yourself of this experience if you keep looking up solutions on the web. In any case, if you do hand in a solution inspired by something you found on the web, please name the source. Describe the solution in your own words, do not copy from the web.