Apprentice program: Linear Algebra and Combinatorics
(June 19 - July 21, weeks 1 - 5)
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)
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