# Matrix Analysis Horn Homework Online

## Instructor

Prof. Arvind K. Saibaba Email: asaibab AT ncsu DOT edu
Department of Mathematics
Office Hours: T-W 4:00-5:15 PM, SAS Hall 3118

A detailed copy of the syllabus can be found here.

Vector spaces, linear transformations and matrices, orthogonality, orthogonal transformations with emphasis on rotations and reflections, matrix norms, projectors, least squares, generalized inverses, definite matrices, singular values.

Prerequisites: MA 405, or equivalent.

## Lectures

Classes will be held from Wednesday, August 16th - Friday December 1st. The rough schedule is posted here, and is subject to change.

 Date Topic Reading Action Items Wednesday 8/16 Introduction Friday 8/18 Gaussian elimination Meyer 1.2 - 1.3 Monday 8/21 Echelon forms Meyer 1.2 - 1.3 Wednesday 8/23 Matrix Algebra - I Meyer 3.2 - 3.7 Friday 8/ 25 Matrix Algebra - II Meyer 3.2 - 3.7 Monday 8 / 28 Exam 0 Come prepared! Wednesday 8/30 LU Factorization Meyer 3.10 Friday 9/1 LU Cholesky decomposition Meyer 3.10, Ipsen 3.6 Monday 9/ 4 Labor day (no class) Wednesday 9/6 Cholesky decomposition Ipsen 3.6 Friday 9/8 Pivoted LU factorization Meyer 3.10 Homework 1 due Monday 9/ 11 Vector Spaces Meyer 4.1-4.2 Wednesday 9/13 Four fundamental subspaces Meyer 4.2 Friday 9/15 Independence, Basis, Dimension Meyer 4.3-4.4 Monday 9/ 18 Matrix products, Dimension formulas Meyer 4.4 Wednesday 9/20 Dimension formulas Meyer 4.4 Friday 9/22 Fundamental theorem of linear algebra Meyer 4.4 Homework 2 due Monday 9/25 Fundamental theorem of linear algebra Meyer 4.4 Wednesday 9/27 Problem solving session Friday 9/29 Exam 1 Come prepared! Monday 10/ 2 Rank of matrix products Meyer 4.5 Wednesday 10/4 CX/CUR + Lin. Trans. Meyer 4.7 Friday 10/6 Fall break (no class) Monday 10/ 9 Coordinates Meyer 4.7 Wednesday 10/11 Change of Basis Meyer 4.8 Friday 10/13 Normed vector spaces Meyer 5.1 Homework 3 due Monday 10/ 16 Vector and matrix norms Meyer 5.1-5.2 Wednesday 10/18 Matrix norms Meyer 5.2 Friday 10/20 Matrix norms, Perturbations Ipsen 2.5 Monday 10/23 Conditioning of additionmultiplication Ipsen 2.7 Wednesday 10/25 Conditioning of inverses, linear systems Ipsen 2.8, 3.2 Friday 10/27 Inner Product Spaces Meyer 5.3 Homework 4 due Monday 10/30 Orthogonality Meyer 5.4 Wednesday 11/1 Problem solving session Friday 11/3 Exam 2 Come prepared! Monday 11/ 6 Orthogonality Meyer 5.4-5.6 Wednesday 11/8 QR factorization Meyer 5.7 Friday 11/10 Complementary subspaces Meyer 5.9 Monday 11/ 13 Orthogonal decomposition Meyer 5.11 Wednesday 11/15 SVD-I Meyer 5.12 Friday 11/17 SVD-II Meyer 5.12 Homework 5 due Monday 11/ 20 SVD-III Meyer 5.12 Wednesday 11/22 Thanksgiving break (no class) Friday 11/24 Thanksgiving break (no class) Monday 11/27 Least Squares-I Meyer 4.6 and 5.13 Wednesday 11/29 Least Squares-II Meyer 4.6 and 5.13 Friday 12/1 Problem solving session Homework 6 due

## Textbooks

The course will build on material from several different sources.

• Matrix Analysis and Applied Linear Algebra by Carl D. Meyer (Required)

• Numerical Matrix Methods by Ilse C.F. Ipsen (Required)

• Matrix Analysis by Horn and Johnson, Second Edition

## Study Guides and Practice Exams

• Study guide for Prerequisites exam here. Last year's exam here and solutions here.

• Problem Session on 8/25 here and solutions here.

• Study Guide for Exam 1 here (updated 9/27). Practice Exam pdf and solutions here.

• Problem Session Solutions 9/27 here

• Study Guide for Exam 2 here. Practice Exam pdf. Solutions here.

• Problem Session Solutions 11/2 here

• Study Guide for Final Exam here. Practice Final Exam here. Solutions here.

• Problem Session Problems 12/1 here and solutions here. Updated 12/10

## Exams

• Prerequisites exam pdf and solutions pdf. 8/28.

• Exam 1 pdf and solutions pdf. 9/29.

• Exam 2 pdf and solutions pdf. 11/3.

## Homeworks

• Homework 1 pdf. Due date September 8, 2017. Solutions pdf

• Homework 2 pdf. Due date September 22, 2017. Solutions pdf

• Homework 3 pdf. Due date October 13, 2017.

• Homework 4 pdf. Due date October 27, 2017. Solutions pdf

• Homework 5 pdf (Modified November 15, 2017). Due date November 17, 2017. Solutions pdf

• Homework 6 pdf. Due date December 1, 2017. Solutions pdf

• Topics in Matrix Analysis, R. A. Horn and C. R. Johnson

• Matrix Analysis, R. Bhatia link (Available online to NC State students)

• Linear Algebra in Action, Harry Dym, AMS (Great reference for use of complex analysis)

Monday, Wednesday, Friday 3:00 - 3:50 PM, SAS Hall 1218

This book can be purchased on SIAM on-line store, enter the coupon code: BKCMAD.
SIAM members get 30% discount, all NC State Students qualify for free memberships.

This book can be purchased on SIAM on-line store, see earlier note about membership discounts

### 3 May 2017

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

### 1 May 2017

Nonnegative matrices.
The Perron-Frobenium Theorem
Intro to Markov chains

### 28 April 2017

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$.

### 26 April 2017

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

### 24 April 2017

Intro to Markov Chains
Intro to positive matrices
If $A>0$, then $\rho(A)$ is an eigenvalue

### 20 April 2017

Bounds on $\|f(A)\|$ using eigenvalues and eigenvectors, numerical range, pseudospectra

### 18 April 2017

Pseudospectra and eigenvalue conditioning
Bauer-Fike theorems, eigenvalue condition numbers.

### 17 April 2017

Pseudospectra
Notes on pseudospectra (work in progress): chapter5.pdf (updated 18 April).

### 14 April 2017

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

### 12 April 2017

Properties of the numerical range, $W(A)$
Johnson's algorithm for approximating the boundary of $W(A)$

### 10 April 2017

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

### 7 April 2017

Transient growth in linear dynamical systems: cancellation effects

### 5 April 2017

Asymptotic stability of solutions to $x'(t) = A x(t)$
Potential for transient growth and sensitivity of the eigenvalues of $A$

### 3 April 2017

Functions of matrices: properties of the exponential of a matrix

### 31 March 2017

Functions of matrices: the exponential of a matrix

### 29 March 2017

Functions of matrices: three definitions
Some course notes: chapter4.pdf (updated 17 April).

### 27 March 2017

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

### 22 March 2017

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

### 21 March 2017

(Empirical) Principal Component Analysis

### 20 March 2017

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

### 17 March 2017

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.

### 15 March 2017

Introduction to the singular value decomposition (SVD)
The matrix norm equals the largest singular value: $\|A\| = s_1$.

### 13 March 2017

Postive semi-definite matrices have unique $k$th roots: $A^{1/k} = \sum_{j=1}^n +(\lambda_j)^{1/k} u_j^{} u_j^*$.

### 27 February 2017

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.

### 24 February 2017

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

### 22 February 2017

Section 2.3: Hermitian matrices
Courant--Fischer characterization of eigenvalues of Hermitian matrices
Some course notes: chapter2.pdf (updated 1 April).

### 20 February 2017

Section 2.2: Cauchy Interlacing Theorem for Hermitian matrices
Some course notes: chapter2.pdf (updated 1 April).

### 17 February 2017

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

### 15 February 2017

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.

### 13 February 2017

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

### 10 February 2017

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

### 8 February 2017

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$.

### 6 February 2017

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

### 3 February 2017

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.

### 1 February 2017

Section 1.7: Damped systems in mechanics
shm.m, shmeig.m: MATLAB demos for the damped pendulum

### 30 January 2017

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

### 27 January 2017

Some course notes: chapter1.pdf (updated 29 March).
Section 1.3: The resolvent $R(z) := (zI-A)^{-1}$ and the existence of eigenvalues

### 25 January 2017

Some course notes: chapter1.pdf (updated 29 March).

### 20 January 2017

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"

### 18 January 2017

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]

### Project Specification

Posted 27 February 2017. Due 6 May 2017. (Declare your project by 23 March 2017)

### Pledged Problem Set 1

Posted 25 April 2017. Due 3 May 2017.
hwp2.pdf: assignment
solp2.pdf: solutions
sept11.m: MATLAB routine for Problem 4

### Problem Set 5

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

### Problem Set 4

Posted 28 March 2017. Due 4 April 2017. (Late work due 5 April 2017.)
hw4.pdf: assignment
sol4.pdf: solutions

### Problem Set 3

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)

### Pledged Problem Set 1

Posted 17 February 2017. Due 24 Feburary 2017.
hwp1.pdf: assignment
solp1.pdf: solutions

### Problem Set 2

Posted 6 February 2017. Due 14 Feburary 2017.
hw2.pdf: assignment
sol2.pdf: solutions

### Problem Set 1

Posted 25 January 2017. Due 1 Feburary 2017.
hw1.pdf: assignment
sol1.pdf: solutions

### Full Course Contract

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

### Honor Code

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."

### Text Books

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.

• Roger A. Horn and Charles R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, 2012.
This comprehensive reference book is well-suited for those intending to pursue research in matrix theory and related fields.

• Carl Meyer, Matrix Analysis and Applied Linear Algebra, SIAM, 2001.
Available via Virginia Tech library (2 hour reserve): QA188 .M495 2000
This textbook is oriented toward advanced undergraduates/beginning graduate students. Those who need a refresher on basic linear algebra concepts will find this a more approachable text.

### Supplemental Books

You might enjoy dipping in to a few of these supplmental titles

• Rajendra Bhatia, Matrix Analysis, Springer, 1997.
This book gives particularly strong coverage to eigenvalue majorization and classical eigenvalue perturbation theory.

• Harry Dym, Linear Algebra in Action, 2nd ed., AMS, 2013.
Available via Virginia Tech library (2 hour reserve): QA184 .D96 2014
This book makes particularly good use of complex analysis as a fundamental tool for matrix analysis.

• Roger A. Horn and Charles R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991.
This companion to their Matrix Analyis text provides a detailed treatment of the field of values, Sylvester and Lyapunov equations, and functions of matrices, among other topics.

• Peter Lancaster and Miron Tismenetsky, Theory of Matrices, with Applications, 2nd ed., Academic Press, 1985.
Classic text on advanced matrix theory, particularly strong on canonical forms and matrix polynomials.

• Peter Lax, Linear Algebra and Its Applications, Wiley, 2007.
Strong on matrix calculus, avoidance of eigenvalue crossings, abstract normed vector spaces.

### Accommodations

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.