Textbook 2: Applied Linear Algebra

MATH 401: APPLICATIONS OF LINEAR ALGEBRASection: 0301Lectures: TuTh 9:30am – 10:45am, MTH B0423Office hours: Tu 11:00 – 11:59am or by appointmentTextbook 1: Linear Algebra and its applications (4th edition), by David C. Lay,ISBN: 9780321385178Textbook 2: Applied Linear Algebra (1st edition), by Peter J. Olver and ChehrzadShakiban, ISBN: 9780131473829Prerequisites: C- or better in one of MATH461, MATH240, MATH341Instructor: Yuri LimaEmail: yurilima@gmail.comOffice: Mathematics 4117Webpage: http://www2.math.umd.edu/ yurilima/math401.htmlDetailed syllabusFIRST MIDTERM: Chapters 1, 2, 4, except Sections 2.4, 2.6, 2.7, 4.8.SECOND MIDTERM: Chapters 5, 6, 7, except Sections 5.4, 5.8, 6.8, 7.4, 7.5;applications to graphs.1/28 – Introduction, systems of linear equations, row reduction: 1.1, 1.2. Various applications: Math, electrical network, economics, computer graphics,airline industry. Basic definitions: linear equation, system of equations, solution set. Example: 2 2 matrix and its solution set. Matrix notation: coefficient matrix and augmented matrix. Example 1, page 5. Row operations: interchange, multiplication and linear combination.1/30 – Alternative interpretations of systems of linear equations: 1.3,1.4, 1.5. Review: systems of linear equations, augmented matrix, row reduction. Echelon form, reduced echelon form, pivot position. Solutions of systems of linear equations: trichotomy. Alternative interpretation 1: vectorial equation a1 x1 · · · an xn b. Solution set non-empty b Span(x1 , · · · , xn ). Some examples of Span(x1 , · · · , xn ) for n 2, 3. Alternative interpretation 2: matrix equation Ax b, where A coeff. matrix.1

2MATH 401: APPLICATIONS OF LINEAR ALGEBRA Alternative interpretation 3: linear transformation  : Rn Rm via Âx Ax. What is a linear transformation, and why is  so?2/4 – Applications of linear systems: 1.6, 1.10. Review: three different interpretations of systems of linear equations. Leontief input–output model. Example with three products. Balancing chemical equations. Ammonia synthesis (Haber process): N2 2H2 2NH3 . Methane decomposition: CH4 2O2 CO2 2H2 O. Electrical networks: Ohm’s formula (V RI) and Kirhhoff’s formula. Example 2, page 83. Networks on graphs (somewhat similar to electrical networks): in out. Difference equations xk 1 Axk . Example: Fibonacci sequence.2/6 – Matrix algebra (basic sum/product operations, inverse) 2.1, 2.2. Review: applications of systems of linear equations. Matrix operations: sum, product, transpose. Basic properties of matrix operations. Inverse. Example with 2 2 matrices. Uniqueness of inverse, if it exists. Elementary matrices: relation with I, and invertibility.2/11 – Inverse: 2.3. Review: matrix algebra, elementary matrices. Lemma: A, B invertible AB invertible. Corollary: The product of elementary matrices is invertible. Theorem: A invertible Ax b always has solution A is row equivalentto I. Scholium 1: if A is row reduced to I via E1 , . . . , Ep , then A 1 E1 1 · · · Ep 1 . Scholium 2: algorithm to calculate A 1 . Theorem 8, page 112: invertibility in terms of algebra, row reduction, and lineartransformation.2/13 – NO CLASS.2/18 – LU decomposition, vector spaces, subspaces: 2.5, 4.1. Review: row reduction via matrix products; Theorem 8, page 112. LU decomposition. Application: computers use LU decomposition to solve systems of linear equations. Vector space: definition. Example 1, page 191: Rn . Example 4, page 192: Pn real polynomials of degree n. Counterexample: real polynomials of degree exactly n. Example 5, page 192: {f : [0, 1] R}. Counterexample: {f : [0, 1] R : f (0) 1}. Subspace: definition.

MATH 401: APPLICATIONS OF LINEAR ALGEBRA3 Example: subspaces of R2 .2/20 – Subspaces, linear independence, bases: 4.1 (2.8), 4.3 (1.7). Review: vector spaces and subspaces. Example 6, page 193: zero subspace. Example 7, page 193: Pk Pn when k n. Example: subspaces of Rn . Subspace spanned by a set. Example: span on R2 , R3 . Linear independence: definition. Example: three vectors in R2 . Fact: in Rn , linear independence is equivalent to solving an equation Ax 0.2/25 – Linear independence, basis, dimension: 4.3, 4.5 (2.9). Review: span, linear independence. Example: {1, x, . . . , xn } is linearly independent in Pn . Fact: if S is linearly dependent, then there is v S s.t. span(S) span(S\{v}). Basis: definition. Example 6, page 209. Spanning set theorem: Theorem 5, page 210. Theorem: if V has a basis with n elements, then every of basis of V has nelements. (We will prove this theorem next class.) Dimension: definition. Examples: dim Rn n, dim Pn n 1. Properties of bases: Theorems 11 and 12, page 227.2/27 – Coordinates, linear transformations: 4.4, 4.2 (1.8). Review: span, linear independence, basis, dimension. Conclude proof of Theorems 11 and 12, page 227. Fact: p n vectors in Rn are linearly dependent. Unique representation theorem: Theorem 7, page 216. Coordinates in a basis B. Thus vector spaces look like Rn . Example: coordinates in the basis {1, x, . . . , xn } of Pn . Linear transformations: definition. Example: a matrix A of size m n defines T : Rn Rm . Example: if dim V n, then a basis B defines T : V Rn . Null space. Lemma: the null space is a subspace of the domain. Example: the null space of matrix A is the set of solutions of Ax 0.3/4 – Linear transformations: 4.2. Review: coordinates, linear transformation, null space. Lemma: the null space of a matrix has dimension equal to the number of nonpivot columns. Range. Example: the range of a matrix A. Lemma: the range is a subspace of the codomain. Exercise: what are the null space and range of a coordinate map T : V Rn ?

4MATH 401: APPLICATIONS OF LINEAR ALGEBRA Theorem: if V has a basis with n elements, then every of basis of V has nelements. (Proof.)3/6 – Rank, matrix of linear transformation: 4.6 (2.9), 1.9. Review: null space, range.Rank: definition.Fact: if A has column vectors v1 , . . . , vn , then range(A) span(v1 , . . . , vn ).Lemma: the rank of a matrix is equal to the number of pivot columns.The matrix of a linear transformation T : V W (wrt basis of V, W ).Application in computer graphics: the matrices of dilation, shear and rotation.3/7 – Change of basis, stochastic matrices: 4.7, 4.9. Review: rank, matrix of linear transformation.The rank theorem: Theorem 14, page 233.Change of basis: matrix P satisfying [v]R P [v]S .Fact: if [v]R P [v]S , then [v]S P 1 [v]R .Change of basis: Theorem 15, page 240.Example: check Homework 4.Stochastic matrix P and its associated graph.Examples: economics, mathematical biology, queueing theory, genetics, GooglePageRank, random walks.Stationary vector: probability vector x s.t. P x x.Perron-Frobenius theorem (first version): Let P be stochastic with positive entries. Then P has a unique stationary.Perron-Frobenius theorem (second version): Let P be stochastic s.t. some P khas positive entries. Then P has a unique stationary vector.Examples: in economics, the stationary vector represents an equilibrium; in arandom walk, the stationary vector represents the frequency of visits to the vertices.3/11 – Markov chains, applications to computer graphics: 4.9, 2.7. Review: stochastic matrix graph, examples, Perron-Frobenius theorem. Markov chain: {P n x}, where P stochastic matrix and x probability vector. Perron Frobenius theorem: Let P be stochastic s.t. P k has positive entries forsome k 0. Then P has a unique stationary probability vector x, and for anyother probability vector y it holds that P n y x. In economics, mathematical biology, queueing theory, genetics: x equilibrium. In Google PageRank, random walks: x frequency of visits to vertices. Computer graphics: dilation, shearing and rotation are linear, but translationsare not. Homogeneous coordinates: (x, y) R2 (x, y, 1) R3 . Translation on R2 linear transformation on R3 . Dilation, shearing, rotation, translation are linear on homogeneous coordinates.3/13: Midterm 1.3/18 and 3/20: Spring break.

MATH 401: APPLICATIONS OF LINEAR ALGEBRA53/25: Eingenvalues, eigenvectors, characteristic equation – 5.1, 5.2, 5.3. Example: population dynamics. Definition: eigenvalue and eigenvector. Example: triangular matrix. How to find them in general? Crash course in determinants: Theorem 3, page 275. Characteristic equation: it tells what are the eigenvalues. Eigenvectors: row reduce the homogeneous system (A λI)v 0.3/27: Characteristic equation, complex eigenvalues – 5.3, 5.5. Review: eigenvalue, eigenvector, characteristic equation. Definition: diagonalizable matrix. If P change of basis, then A P DP 1 . The reverse is true. Theorem 6, page 284: if A has n distinct eigenvalues, then it is diagonalizable. Counterexample: diagonal matrix with equal entries. Theorem 7, page 285. Example 3, page 283. Complex eigenvalues. If λ a bi is eigenvalue with eigenvector v wi,span(v, w), then A preserves a band on this plane it acts according to the matrix. b a a b rotation dilation. b a4/1: Discrete dynamical systems – 5.6. Review: diagonalization (equivalence, sufficient condition, sufficient and necessary conditions), complex eigenvalues. Remember population dynamics: update of population according to vk 1 Avk . Other instances: chaos theory (butterfly effect), control theory, cosmology. If A is diagonalizable, then vk has a precise description in terms of v0 and theeigenvalues/eingenvectors of A. Example: all possibilities for 2 2 matrix, with notions of saddle, attractor,repeller.4/3: Applications to differential equations, applications to graphs (additional topic) – 5.7. Differential equations: x00 3x0 2x 0 x0 Ax. More generally, systems of linear differential equations lead to x0 Ax. Solution set: {x : x0 Ax}. Superposition principle: the solution set is a subspace. Fact: the dimension of the solution set equals the dimension of A. How to get n linearly independent solutions? If A diagonal, it is easy: decoupled system. If not, look for eigenvalues/eigenvectors. They define eigenfunctions. In the example x00 3x0 2x 0, x c1 et c2 e2t . Graphs: G (V, E), where V vertices and E non-oriented edges. How to count L(k) # of closed loops of length k? Adjacency matrix A. Property: If Ak (akij ), then akij # of paths of length k from i to j.