Linear algebra via the discrete Laplacian
The key problem in most linear algebra teaching is that it is \emph{dry}
and \emph{formal}: definitions and theorems without \emph{any} interesting examples
or further directions. The Steinitz exchange lemma, but not discrete Fourier theory.
I don't know the origin of this style; perhaps it comes from Bourbaki's axiomatic approach,
or is congenial to algebraists.
Instead, I suggest using the discrete Laplacian as a rich example.
This is a \emph{perfect} topic to study:
- tractible and concrete
- illustrates and teaches basic linear algebra concepts
- illustrates and leads to very beautiful and important classical mathematics,
- ...and current research topics
This is a topic every mathematician should know,
and is (part of) how everyone should learn linear algebra.
- Discrete Fourier theory
...and representation theory more generally
...and atomic orbitals (pretty!)
- PDEs, especially Laplacian and heat equation
...including boundary conditions
- probability / stochastic
Fancy:
- Ising model
- Loop quantum gravity
General principles:
- discrete analogs of continuous
(more accurately, the discrete/continuous interplay)
[Discrete problems are much more *tractible*:
the heat equation on a graph is just a few numbers,
rather than an *abstract* operator]
- replace equations with functions (here, operators)
...and study the function to understand how to solve the equation
(- more deeply, )
- understand geometry by studying operators
(geometric analysis; esp. inverse spectral theory)
- operators arise in combinatorics!
Linear algebra:
- space with natural vector structure, but not algebra
(dimensional: heat + heat squared is meaningless)
- expand/closure
problems stated as about integers or positive numbers,
which are solved by including reals (inc. negatives)
- eigenvectors, eigenvalues, and diagonalization
- spaces without natural bases
- spectral theorem (b/c self-adjoint)
Consider $n$ dwarves, seating around a table, each with a bowl of gruel.
(Picture of table, with dwarves and gruel, and ellipses to indicate ``$n$'')
EG of *guessing* eigenvectors, say on
*from geometric considerations* (?) (symmetry at least)
(ansatz!)
Interpretations:
- heat
- diffusion / random walk
Examples:
- line, with free and fixed boundary
- circle (Fourier!)
Note how circle is *easier* b/c it's homogeneous
...and also has underlying group structure
(it's a Cayley graph)
[likewise infinite line instead of segment]
- cube
time-to-reach other corner (stopping time? return time?)
EG of "solve by general method; has clever solution due to special structure"
pose as:
+ solve as a heat equation
+ now solve cleverly (hint: work forward from starting state: write distro after n steps,
esp. for small n (0,1,2,3,...);
hint: compare state after 1 step and 3 steps)
---------------------------------------------------------------------
Self-adjoint:
hence
- diagonalizable
- over the reals
- with orthogonal eigenspaces
---------------------------------------------------------------------
!! Orthogonality !!
Eigenspaces are orthogonal b/c the operator is self-adjoint;
OTOH, for circle (and homogeneous spaces?) orthogonality ``comes from''
representation theory.
Hmmm...feels a bit too slick: why are representations / characters
solutions of Laplacian?
---------------------------------------------------------------------
EG of triangle ($C_3$, aka, $\bZ/3$)
Over reals, has eigenspaces $V_1 = (1,1,1)$
and $V_{-1/2} = V_1^\perp$
...which doesn't have a standard basis!
1 basis is $(1,-1/2,-1/2)$, cyclically permuted
(and this has a relation: v_1+v_2+v_3=0)
...but other is $(0,1/2,-1/2)$
...or any other abc!
Over complexes, there's a natural basis coming from representation theory,
and you can take its real and complex parts (which yield $(1,-1/2,-1/2)$ and $(0,1/2,-1/2)$)
---------------------------------------------------------------------
*** distinguish what is of general interest from
*** what is specific to this case;
esp., results on stochastic matrices (Perron-Frobenius) are cute but inessential
---------------------------------------------------------------------
BTW, Laplacian is a Markov chain (discrete time Markov process)
("ergodic" in Markov language iff not bipartite)
It's not reversible.
mixing?
Perron-Frobenius
doubly stochastic b/c stochastic & symmetric
---------------------------------------------------------------------
NB:
- a connected bipartite graph has a single coloring (up to inverting; so exactly 2)
This is combinatorially obvious (coloring a single vertex determines
all neighbors -- and by connectivity this determines all)
but surprising in contrast to higher colorings
Hence you only get a single -1 eigenvector on a bipartite graph,
corresponding to the essentially unique coloring.
This is a great eg of a *subtle* point:
- don't just think "colorable", think *set* of colorings
(and esp. their number)
- it's constrained in bipartite, but not generally!