MATH 5524 is a graduate survey of applicable topics in matrix analysis. Students are expected to arrive with a foundation in basic linear algebra at the undergraduate level. Topics will include: spectral theory, variational properties of eigenvalues, singluar values, eigenvalue perturbation theory, functions of matrices and dynamical systems, nonnegative matrices and Perron-Frobenius theory.
Classes: |
Monday/Wednesday/Friday, 12:20-1:10pm, McBryde 328 |
Instructor: |
Mark Embree, embree@vt.edu, 575 McBryde |
Office Hours: |
Monday 4-5:30pm, Thursday 1:30-3pm, or by appointment |
Piazza: |
The course Piazza page provides a forum for class discussions. |
Markov chains and card shuffling
riffle_sim.m:
MATLAB demo of riffle shuffling
riffle.m:
MATLAB code by Jonsson and Trefethen giving the transition matrix for the riffle shuffle
Nonnegative matrices.
The Perron-Frobenium Theorem
Intro to Markov chains
Positive matrices.
If $A>0$, then $\rho(A)\in\sigma(A)$ only has $1\times 1$ Jordan blocks.
If $A>0$, then $\rho(A)\in\sigma(A)$ is a simple eigenvalue.
If $A>0$ and $Ay = \lambda y$ with $y\ge 0$, then $\lambda=\rho(A)$ and $y>0$.
Positive matrices.
If $A>0$ and $A x = \lambda x$ with $|\lambda|=\rho(A)$, then $|x|>0$.
If $A>0$ and $A x = \lambda x$ with $|\lambda|=\rho(A)$, then $\lambda=\rho(A)$.
Intro to Markov Chains
Intro to positive matrices
If $A>0$, then $\rho(A)$ is an eigenvalue
Bounds on $\|f(A)\|$ using eigenvalues and eigenvectors, numerical range, pseudospectra
Pseudospectra and eigenvalue conditioning
Bauer-Fike theorems, eigenvalue condition numbers.
Pseudospectra
Download EigTool from GitHub.
Notes on pseudospectra (work in progress): chapter5.pdf (updated 18 April).
The derivative of an eigenvalue for diagonalizable matrices
The eigenvalues of a Jordan block with a perturbed corner entry
Notes on Gerschgorin's Theorem: chapter5.pdf (updated 18 April).
Properties of the numerical range, $W(A)$
Johnson's algorithm for approximating the boundary of $W(A)$
The numerical range (field of values) of matrix and its connection to $\|e^{tA}\|$
To do: hw5.pdf, Problem Set 5 is due on Tuesday, 18 April (5pm).
Transient growth in linear dynamical systems: cancellation effects
Asymptotic stability of solutions to $x'(t) = A x(t)$
Potential for transient growth and sensitivity of the eigenvalues of $A$
Functions of matrices: properties of the exponential of a matrix
Functions of matrices: the exponential of a matrix
Functions of matrices: three definitions
Some course notes: chapter4.pdf (updated 17 April).
Singular value potpourri:
- Schatten $p$ norms: $\|A\|_{S-p} = (s_1^p + \cdots + s_r^p)^{1/p}$
- Singular value inequalities, e.g. $s_{j+k-1}(A+B) \le s_j(A)+s_k(B)$.
To do: hw4.pdf, Problem Set 4 is due on Tuesday, 4 April (5pm).
Using the SVD to find the minimal norm solutions to
$Ax=b$ and $\min_x \|Ax-b\|$
The Moore-Penrose pseudoinverse
See Section 3.2 of the course notes: chapter3.pdf (updated 1 April).
(Empirical) Principal Component Analysis
Optimal low-rank approximations from the SVD
Introduction to Principal Component Analysis
Some course notes: chapter2.pdf (updated 1 April).
Some course notes: chapter3.pdf (updated 1 April).
Three flavors of the SVD:
- the dyadic decomposition $A = \sum_{j=1}^r s_j^{} u_j^{ } v_j^*$;
- the skinny SVD $A = U\Sigma V^*$ with $\Sigma$ square;
- the full SVD $A = U\Sigma V^*$ with $U$ and $V$ both unitary.
The polar decomposition of a square matrix: $A = H Q$ where $H=U\Sigma U^*$ is positive semidefinite and $Q=UV^*$ is unitary.
Introduction to the singular value decomposition (SVD)
The matrix norm equals the largest singular value: $\|A\| = s_1$.
Postive semi-definite matrices have unique $k$th roots: $A^{1/k} = \sum_{j=1}^n +(\lambda_j)^{1/k} u_j^{} u_j^*$.
Congruent matrices, Sylvester's Law of Inertia, spectrum slicing
No class on March 1 and 3 (instructor traveling). Make-up lectures will be offered after Spring Break.
To do: project.pdf. Start thinking about your class project; select by 23 March.
Section 2.4: Two examples illustrating the scarcity of double eigenvalues
Eigenvalues of Jacobi matrices
Eigenvalues of parameterized Hermitian systems
avoid_ex0.m,
avoid_ex1.m,
avoid_ex2.m:
MATLAB demos showing eigenvalue avoidance
Section 2.3: Hermitian matrices
Courant--Fischer characterization of eigenvalues of Hermitian matrices
Some course notes: chapter2.pdf (updated 1 April).
Section 2.2: Cauchy Interlacing Theorem for Hermitian matrices
Some course notes: chapter2.pdf (updated 1 April).
Section 2.1:
Variational characterization of eigenvalues of Hermitian matrices.
Solutions to Problem Set 2: sol2.pdf
To do: hwp1.pdf, Pledged Problem Set 1 is due on Friday, 24 February (5pm).
Section 1.8: The Jordan Canonical Form
Jordan form clean-up: algebraic and geometric multiplicity; why we never compute the Jordan form
jordex1.m, jordex2.m: Try computing the Jordan form of these matrices...
Golub and Wilkinson, Ill-Conditioned Eigensystems and the Computation of the Jordan Canonical Form, 1976.
Section 1.8: The Jordan Canonical Form
Derivation of the Jordan form: second half of proof ($\rho \ne 0$)
Fletcher and Sorensen, An Algorithmic Derivation of the Jordan Canonical Form, 1983.
Some course notes: chapter1.pdf (updated 29 March).
Section 1.8: The Jordan Canonical Form
Derivation of the Jordan form: first half of proof ($\rho = 0$)
Fletcher and Sorensen, An Algorithmic Derivation of the Jordan Canonical Form, 1983.
Some course notes: chapter1.pdf (updated 29 March).
Section 1.8: The Jordan Canonical Form
Spectral projectors and nilpotents: $P_j = V_j \widehat{V}_j^*$ and $D_j = V_j R_j \widehat{V}_j^*$
Spectral representation $A = \sum \lambda_j P_j + D_j$.
Section 1.8: The Jordan Canonical Form
Block diagonalization: $A = V {\rm diag}(T_1, \ldots, T_p) V^{-1}$.
Fletcher and Sorensen, An Algorithmic Derivation of the Jordan Canonical Form, 1983.
Solutions to Problem Set 1: sol1.pdf
To do: hw2.pdf, Problem Set 2 is due on Tuesday, 14 February (5pm).
Section 1.8: The Jordan Canonical Form
Theorem: The Sylvester equation $AX-XB=C$ has a unique solution if and only if $\sigma(A)\cap\sigma(B) = \emptyset$.
Proof: The Bartels-Stewart algorithm.
Section 1.7: Damped systems in mechanics
shm.m, shmeig.m: MATLAB demos for the damped pendulum
Section 1.4: Reduction to triangular form (Schur decomposition)
Section 1.5: Spectral Theorem for Hermitian matrices
schur_proof.m: MATLAB implementation of the proof of the Schur decomposition
Wikipedia page on Issai Schur (1875-1841)
Some course notes: chapter1.pdf (updated 29 March).
Section 1.3: The resolvent $R(z) := (zI-A)^{-1}$ and the existence of eigenvalues
Wikipedia page on Liouville's Theorem
Some course notes: chapter1.pdf (updated 29 March).
Section 1.3: Proof of the Neumann series for inverting $I-E$ when $\|E\|<1$
To do: hw1.pdf, Problem Set 1 is due on Wednesday, 1 February (5pm).
Note: Thursday office hours have moved to 1:30-3pm.
Some course notes: chapter1.pdf (updated 29 March).
Section 1.1: Special matrices: Hermitian, unitary, subunitary, projectors
Section 1.2: Eigenvalues in mechanics
pendulum_demo.m: MATLAB demo of the $n$ modes of an $n$ mass pendulum.
Some course notes: chapter1.pdf (updated 29 March).
Section 1.1: Vector norm, Cauchy-Schwarz, Triangle inequality, induced matrix norm
A good demo: See Cleve Moler's blog post about "eigshow"
Review of the course contract and discussion of book options.
Some course notes: chapter1.pdf (comments/corrections welcome).
Section 1.1: Notation and preliminaries
Section 1.2: Eigenvalues and eigenvectors [today: overview of diagonalization]
Posted 27 February 2017. Due 6 May 2017. (Declare your project by 23 March 2017)
project.pdf: speficiation and grading rubric
Posted 25 April 2017. Due 3 May 2017.
hwp2.pdf: assignment
solp2.pdf: solutions
sept11.m: MATLAB routine for Problem 4
Posted 11 April 2017. Due 18 April 2017. (Late work due 19 April 2017.)
hw5.pdf: assignment
sol5.pdf: solutions
pop.m: MATLAB routine for Problem 4
Posted 28 March 2017. Due 4 April 2017. (Late work due 5 April 2017.)
hw4.pdf: assignment
sol4.pdf: solutions
Posted 15 March 2017. Due 1 April 2017.
hw3.pdf: assignment
cow.mat, planck.mat: MATLAB data files for Problem 4
(cow_A0.csv,
cow_B0.csv,
planck_A0.csv,
planck_B0.csv:
same data, but in .csv format for use with other systems)
Posted 17 February 2017. Due 24 Feburary 2017.
hwp1.pdf: assignment
solp1.pdf: solutions
Posted 6 February 2017. Due 14 Feburary 2017.
hw2.pdf: assignment
sol2.pdf: solutions
Posted 25 January 2017. Due 1 Feburary 2017.
hw1.pdf: assignment
sol1.pdf: solutions
Download a copy of the electronic version of the course contract and tentative schedule.
Final course grades will be thus allocated:
50%: standard problem sets (collaboration encouraged)
35%: pledged problem sets (no collaboration permitted)
15%: end-of-semester project
Virginia Tech's Honor Code applies to all work in this course. Students must uphold the highest ethical standards, abiding by our Honor Code: "As a Hokie, I will conduct myself with honor and integrity at all times. I will not lie, cheat, or steal, nor will I accept the actions of those who do."
From the Office for Undergraduate Academic Integrity:
"Students enrolled in this course are responsible for abiding by the Honor Code. A student who has doubts about how the Honor Code applies to any assignment is responsible for obtaining specific guidance from the course instructor before submitting the assignment for evaluation. Ignorance of the rules does not exclude any member of the University community from the requirements and expectations of the Honor Code. For additional information about the Honor Code, please visit:
www.honorsystem.vt.edu."
While we will not closely follow any single textbook, students are encouraged
to obtain one of the following books, each of which covers most of the topics
we will cover in the lectures.
You might enjoy dipping in to a few of these supplmental titles
Any student with special needs or circumstances requiring accommodation in this course is encouraged to contact the instructor during the first week of class, as well as the Dean of Students. We will ensure that these needs are appropriately addressed.