$\newcommand{\zzz}{\mathbb Z}$ $\newcommand{\rrr}{\mathbb R}$ $\newcommand{\ccc}{\mathbb C}$ $\newcommand{\eee}{\mathrm e}$ $\newcommand{\vf}{\varphi}$ $\newcommand{\ol}{\overline}$ $\newcommand{\onto}{\twoheadrightarrow}$ $\newcommand{\normal}{\triangleleft}$ $\DeclareMathOperator{\lcm}{\mathrm lcm}$ $\DeclareMathOperator{\var}{\mathrm Var}$ $\DeclareMathOperator{\period}{\mathrm per}$ $\DeclareMathOperator{\rank}{\mathrm rk}$ $\DeclareMathOperator{\trace}{\mathrm Tr}$

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

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


Class home


Preview of last class (Friday, July 21)


Class notes by Allen Yuan

Friday, July 21 (week 5, class 5 - lecture)

Thursday, July 20 (week 5, class 4 - mixed)

Wednesday, July 19 (week 5, class 3 - lecture)

Tuesday, July 18 (week 5, class 2 - mixed)

Monday, July 17 (week 5, class 1 - lecture)

The problem set that was due Mon July 17

Friday, July 14 (week 4, class 5 - lecture)

Thursday, July 13 (week 4, class 4 - mixed)

Wednesday, July 12 (week 4, class 3 - lecture)

Tuesday, July 11 (week 4, class 2 - mixed)

HW clarification. Let $\psi:V\onto W$ be a linear map from $V$ onto $W$ with kernel $K$. For $S\subseteq V$ we shall refer to $\psi(S)$ as the "shadow" of $S$.
Let $\vf: V\to V$ be a linear transformation; assume $K$ is $\vf$-invariant. We wish to define the "shadow" $\ol{\vf} : W\to W$, a linear transformation of $W$ working on the shadows "like $\vf$ works on the originals." The precise requirement is that if $v\in V$ then $\ol{\vf}(\psi(v))=\psi(\vf(v))$ (the $\ol{\vf}$-image of the shadow is the shadow of the $\vf$-image). We show that if $K$ is $\vf$-invariant then such a $\ol{\vf}$ exists and is unique.
Uniqueness is clear; the only way we can define $\ol{\vf}(w)$ for $w\in W$ is by setting $\ol{\vf}(w)= \psi(\vf(v))$ for some $v\in\psi^{-1}(w)$. To prove existence, we define $\ol{\vf}(w)$ to be $\psi(\vf(v))$ for some $v\in\psi^{-1}(w)$ and hope for the best. What can go wrong? The trouble is, $v$ is not unique. What if we pick another vector, $v'\in\psi^{-1}(w)$. Prove: it does not matter: for any $v,v'\in\psi^{-1}(w)$ we have $\psi(\vf(v))=\psi(\vf(v'))$. Indicate where you use the assumption that $K$ is $\vf$-invariant.

Monday, July 10 (week 4, class 1 - mixed)

Friday, July 7 (week 3, class 3 - mixed)

Thursday, July 6 (week 3, class 2 - mixed)     Read the exact statement of two HW problems below.


For polynomials $f,g$ the notation gcd$(f,g)\neq 1$ means these two polynomials are not relatively prime, i.e., they have a common divisor of positive degree.
HW (multiple roots). Let $f$ be a polynomial over the complex numbers. Prove: $f$ has a multiple root if and only if gcd$(f,f')\neq 1$.

HW (Fibonacci-type sequences). We say that the infinite sequence $(a_0,a_1,a_2,\dots)$ of real numbers is a Fibonacci-type sequence if for all $n\ge 2$ we have $a_n = a_{n-1}+a_{n-2}$. Let Fib denote the set of all Fibonacci-type sequences.
(a1) Prove that Fib is a subspace of the space of all sequences; determine its dimension. (a2) Prove that Fib is invariant under left shift operator $S$, i.e., $S(\text{Fib})\subseteq\text{Fib}$.
(b) Let $\overline{S}:\text{Fib} \to \text{Fib}$ denote the restriction of $S$ to Fib. So $\overline{S}$ is a linear transformation of Fib that shifts the Fibonacci-type sequences to the left. Find the eigenvalues and an eigenbasis for $\overline{S}$.


Wednesday, July 5 (week 3, class 1 - lecture)

Friday, June 30 (week 2, class 5 - mixed)

Thursday, June 29 (week 2, class 4 - lecture)

Wednesday, June 28 (week 2, class 3 - lecture)

Tuesday, June 27 (week 2, class 2 - problem session)

Instructor's comments on two problems, one stated, the other discussed in the problem session.


Here is a more accurate statement of the "chromatic polynomial" homework problem.

HW. For a graph $G=(V,E)$ and $t\ge 1$ let $f_G(t)$ be the number of legal colorings of $G$ from a given set of $t$ colors (i.e., the number of functions $g:V\to [t]$ such that $g$ is a legal coloring of $G$). (Note: the coloring $g$ is not required to use all the $t$ available colors; in particular, the quantity $f_G(t)$ will be positive for $t > n$.) Prove: the function $f_G(t)$ is a polynomial in $t$.     This problem is due Monday, July 3.

To make sure you refer to the right definition of the function $f_G(t)$, remember that for the empty graph $G={\overline K}_n$ we have $f_{{\overline K}_n}(t) = t^n$ and for the complete graph $G=K_n$ we have $f_{K_n}(t)=t(t-1)\cdots(t-n+1)$.


Here is a more accurate description of the coloring algorithm discussed in the problem session.

Greedy coloring algorithm
Input: graph $G=(V,E)$ where $V=[n]$
Initialize empty array $c[1,\dots,n]$ (: $c[i]$ will be the color of vertex $i$ :)
for $i=1$ to $n$
    let $c(i)$ be the smallest positive integer not in the set $\{c(j)\mid j< i, j\sim i\}$ (first color not used by any left neighbor of $i$)
end(for)
return array $c$

Ths is clearly a legal coloring of $G$.

DO The greedy coloring algorithm uses no more than $1+\deg_{\max}$ colors.


Monday, June 26 (week 2, class 1 - problem session)

Friday, June 23 (week 1, class 5 - lecture)

Thursday, June 22 (week 1, class 4 - lecture)

Wednesday, June 21 (week 1, class 3 - problem session)

Tuesday, June 20 (week 1, class 2 - lecture)

Monday, June 19 (week 1, class 1 - lecture)


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

“Graph Theory” notes    by Angela Wu


Course home

Instructor's home page

Back to top