Lecture 38. The relationship between eigenvalues, determinant, and trace.

Wednesday, December 8, 2010

We define the trace of a matrix as the sum of the diagonal entries. For a linear transformation we can define the trace using an orthonormal basis. The key facts that we stated are that the trace is the sum of the eigenvalues (counting multiplicity) and the determinant is the product of the eigenvalues (also counting multiplicity). These facts can be used to read off the trace and determinant from the characteristic polynomial.

Other stuff

• Exercises.

Lecture 37. The Riesz representation theorem and the adjoint of a linear transformation.

Monday, December 6, 2010

The Riesz representation theorem tells us that every linear transformation from Cⁿ to C is given by an inner product against a unique vector. This allows us to define the adjoint of a linear transformation without resorting to matrices. In class, and in the previous exercise set, we explored the basic properties of the adjoint.

Lecture 36. The spectral theorem.

Friday, December 3, 2010

Today we proved the spectral theorem. There are some exercises for you to try.

Things to do

• Do the problems posted in the exercises below.

Other stuff

• Exercises.

Lecture 35. Complex numbers and fundamental theorem of algebra.

Wednesday, December 1, 2010

We will discuss the basics of complex numbers and talk about the fundamental theorem of algebra. We will then take a short detour into the vector space of linear transformations. For the rest of the semester we have only two goals: a proof of the Cayley-Hamilton theorem and the spectral theorem. The underlying ideas will be a bit of a mixed bacg so I will provide copies of some notes and some exercises to try each day.

Things to do

• Do the problems in the notes

Other stuff

• Notes. The notes are a little different to the things we did in class. They contain some facts about vector spaces that we saw at the beginning of the semester.

Lecture 34. Eigenvalues and eigenvectors examples.

Monday, November 29, 2010

Example of eigenvalues and eigenvectors

Lecture 33. No class.

Friday, November 19, 2010

Happy Thanksgiving.

Things to do

• Eat turkey, gravy, stuffing, sweet potato pie, cornbread, green beans, chili, ....

Lecture 32. Exam 3.

Wednesday, November 15, 2010

Lecture 31. Characteristic polynomial and Examples of eigenvalue calculations.

Monday, November 15, 2010

The roots of the characteristic polynomial are the eigenvalues of the corresponding matrix. Using the fundamental theorem of algebra we can deduce that every matrix has at most n eigenvalues. Of course there are polynomials that do not have real roots. We will deal with this problem. Over the rest of the semester polynomials will play a major role in what we do. That's why we began by looking at the relationship between eigenvalues of A and the eigenvalues of a polynomial in A.

Things to do

• Read 7.3 and make sure you look at the definition of algebraic and geometric multiplicity given in 7.3.
• Exercises for 7.3 are posted under exercises.

Lecture 30. Eigenvalues.

Friday, November 12, 2010

The search for eigenvalues can be motivated in many ways. We pick the following motivation: If someone walked up to you in the street and handed you a square matrix, what would you hope for. A diagonal matrix would seem a reasonable compromise. However a lot of matrices are not diagonal. The next best thing would be a matrix that scales an orthonormal basis of Rⁿ. A fundamental question would be which matrices have that property. The rest of our semester is devoted to answering this fairly important question.

A good starting point is to look at eigenvalues and eigenvectors. If we rewrite the definition we see that it's equivalent to the solutions of a certain equation involving the determinant. A careful analysis of the 2x2 case reveals many facts. First the equation is quadratic, so there are at most two eigenvalues. We can also find examples where there are 2 distinct eigenvalues, 1 eigenvalue, and no eigenvalues. Understanding these distinctions is the key to answering the fundamental question above.

Things to do

• Read 7.2. The quantity involving the determinant is called the characteristic equation (a bad bad name).
• Exercises for 7.2 are posted under exercises. All of these questions involve a 2x2 matrix. We have not defined the term algebraic multiplicity so you can ignore it. However, whenever you are asked to find an eigenvalue, try to find the corresponding eigenvector as well.

Lecture 29. Messing with derivatives.

Wednesday, November 10, 2010

We looked at the derivative as a linear transformation and provided the intuition for the Jacobian in the change of variables formula. This is not on the test.

We looked at some assorted facts about determinants of certain matrices. We also provided an alternative definition for the cross product and the reason we computed it using a 3x3 determinant.

Things to do

• Exercises for 6.3 are posted under exercises.

Lecture 29. Determinants and geometry.

Monday, November 8, 2010

The determinant appears frequently in geometry. The determinant of a matrix is the n-dimensional volume of the parallelepiped spanned by its columns. In two dimensions this would be the area, in three the volume and so on.

The second application appears in the change of variables formula from multi-variable calculus. The first step to understanding why this happens is to realize that the derivative is really a linear transformation. Next time we will describe this fully and also gain some intuition about the change of variables formula.

Things to do

• Read chapter 6.2, 6.3.
• Exercises for 6.2 are posted under exercises.

Lecture 28. More properties of determinants

Friday, November 5, 2010

Lecture 27. Determinants.

Wednesday, November 3, 2010

Determinants are great theoretical tool. The definition may look a little scary at first, but once we know the three key properties, everything else falls in place.

Things to do

• Read chapter 6.1. The thing that is called a pattern in the book is called a permutation by most other people. The inductive process of going from small determinants to bigger determinants is called Sarrus's rule.
• Exercises 6.1: 1, 3, 7, 11, 13, 19, 43.

Lecture 26. The minimal least-squares solution.

Monday, November 1, 2010

The minimal least-squares solution is used to solve systems that under-determined, there aren't enough equations to solve the linear system. There are two ways, that we will look at, to solve this problem: minimal energy, and sparsest solution.

I also watched an excellent video on youtube this weekend. Terry Tao (a world famous mathematician) gave a public lecture entitled the "Cosmic Distance Ladder". It's a great introduction to how discoveries are made in science and how knowledge has built up over time.

Things to do

• Try to watch a bit of the video posted above.
• Google the term Principal Components Analysis and see what happens.
• A couple of problems about subspaces for you to try.

Lecture 25. Proof of QR factorization and least-squares.

Friday, October 29, 2010

The QR factorization is proved by a careful examination of the Gram-Schmidt process applied to the columns of A.

The method of least-squares is used whenever we have a system of linear equations and we either have infinitely many solutions or no solutions. When a system is inconsistent the normal equations allow us to find solutions that minimize the error. There may be more than one such solution. There are many alternatives to finding the "best" solution. We could just choose the one closest to the origin (the minimal energy solution), or we could choose a solution that intersects the axes (sparse solutions). Each of these ideas has different properties. Sparse solutions are important in many fields. The Rice University DSP project on single-pixel cameras, which is a proof-of-concept that sparse solutions are sometimes good.

Things to do

• Here is a list of some theorems you should try to prove. They are good for practice.
• 5.4: 2, 16, 17, 18, 19, 21, 29.

Lecture 25. The Transpose Blitz.

Wednesday, October 27, 2010

The transpose of a matrix will be more important as we progress. Today we:

1. Defined the transpose
2. Related the range of the transpose to the kernel of the original matrix
3. Found a way to manipulate a dot product using transposes.
4. Showed that the matrix Q^TQ = I_n and QQ^T = projection onto the range of Q

Next time we will do more. We will prove the QR factorization. We will figure out the relationship between A and the projection onto the range of A. We will also look at the least-squares approach to solving linear systems.

Things to do

• Chapter 5.3: 13, 15, 17, 19, 41, 44 — 47.

Lecture 24. Orthogonal transformations.

Monday, October 25, 2010

A matrix is called orthogonal if and only if its columns are an orthonormal set. This is equivalent to the linear transformation being length preserving. It is also equivalent to the linear transformation preserving dot products. A square orthogonal matrix is invertible, and its inverse is given by the transpose.

Things to do

• Chapter 5.3: 5, 7, 10, 31, 35, 43.

Lecture 23. QR factorization and transposes.

Friday, October 22, 2010

The process of Gaussian elimination requires roughly n^2 row operations and n^2 back substitutions. If you think carefully about the operations, then each row operation requires us to subtract a multiple of one row from another row. This means we need to multiply the first row by a certain constant (that's n multiplications) and then subtract this from another row (n subtractions). Therefore n^2 row operations take n^3 multiplications. When you back substitute you solve n equations and each one requires at most n multiplications and n subtractions, or about n^2 multiplications in total. Back substitution is faster. We pretend here that multiplying is harder than adding and ignore the subtractions.

The QR decomposition provides us with a, potentially, faster way to solve linear systems. On Monday we will look at more properties of orthogonal matrices and see why QR may be faster.

Things to do

• Redo problem 5 on the exam and turn it in
• Study for the quiz which is on section 5.1, again
• The proof-writing assignment is postponed again.

Lecture 22. Pythagoras' theorem, parallelogram law, and Cauchy-Schwarz inequality.

Monday, October 18, 2010

We proved three basic facts in geometry using linear algebra.

Lecture 21. Orthonormal Bases and Projections

Wednesday, October 13, 2010

The best bases are ones that consist of unit length pairwise perpendicular vectors. These are called orthonormal bases. They play an extremely important role in pure and applied mathematics. Today we define the orthogonal projection onto a subspace and look at the Gram-Schmidt process. On Monday we will discuss orthogonal transformations.

Things to do

• Read chapter 5.2
• Exercises. 5.1: 1, 3, 11, 12, 16, 19, 27, 30 31
• Exercises. 5.2: 3, 11, 17, 25, 32, 36, 40, 41.
• The proof-writing assignment is postponed. It is now due Monday, 10/25. More details in class..

Lecture 20. Proof writing assignment discussion.

Monday, October 11, 2010

Discussed one possible approach to the problem for showing the function is linear on the rationals.

Things to do

• Read chapter 5.1
• For Wednesday 10/13. Submit a corrected version of quiz 4, problem 2, if you did not get it right.

Lecture 19. Google's PageRank Algorithm.

Friday, October 8, 2010

Google's PageRank algorithm appeared in 1998 and is the foundation for the world's most popular website. Google is arguably the most important source of information on the web.

The algorithm can be seen as an application of the theory of Markov chain. More modern approaches make use of the graph Laplacian. However, PageRank is elementary and powerful. It also provides a wonderful introduction to the way in which linear algebra in applied in solving real world problems.

Things to do

• Read chapter 5.1
• There is a quiz on Monday. See under quizzes.

Other stuff

• A basic intro to PageRank (updated 10/9/2010 at 10 am).

Lecture 18. The inverse of a linear transformations.

Wednesday, October 6, 2010

How to compute the inverse. Conditions for invertibility

Things to do

• Read chapter 5.1
• Exercises from 2.4: 1, 7, 9, 13, 29, 33, 67 — 75.

Lecture 17. The inverse of a linear transformations and commuting matrices.

Monday, October 4, 2010

Conditions for invertibility.

Things to do

• Read chapter 2.4.

Lecture 16. The inverse of a linear transformations and commuting matrices.

Friday, October 1, 2010

Defined the inverse of a matrix, proved that it is unique and linear and will prove that the it's square.

Things to do

• Study for the quiz.

Lecture 15. Composition of linear transformations and commuting matrices.

Wednesday, September 29, 2010

Defined the notion of commuting matrices, looked at some matrix products, more to come on Friday

Things to do

• See Monday's lecture.

Lecture 14. Matrix multiplication.

Monday, September 27, 2010

Finish up reflections and projections. Matrix multiplication and function composition.

Things to do

• Read chapter 2.3
• Exercises: 2.3: 3, 7, 11, 15, 19, 25, 29, 43 — 49, 59.

Lecture 13. Linear Transformations.

Friday, September 24, 2010

We proved that every linear transformation is given by a matrix multiplication and then looked at examples in two dimensions.

Things to do

• Read chapters 2.1 and 2.2.
• Exercises: 2.1: 1, 3, 7, 24 — 30; 2.2: 1, 4, 5, 6, 15, 24, 26, 29.
• Figure out the formula for a projection onto the line spanned by a vector
• No quiz on Monday

Lecture 12. Linear independence and dimension: problems, examples.

Monday, September 20, 2010

We worked out some conceptual problems related to linear independence and dimension.

Things to do

• Study for the exam.

Lecture 11. The dimension of a subspace, the range and kernel.

Friday, September 17, 2010

We have developed a method to find a basis for the kernel and range of a linear transformation. On Monday we will look at some subspaces and figure out their dimension.

Things to do

• Read the rest of 3.3.
• Exercises: 3.3: 1 — 19 (odd) (you don't have to do this by inspection, if you find that hard). 25, 29, 31, 35, 36.

Lecture 10. Kernel and range of a matrix.

Wednesday, September 15, 2010

Defined the range of a matrix, kernel of a matrix, and column space. We also defined a basis. We began to see how we might compute the basis of the kernel and the range. On Friday we will spend a lot of time looking at this problem.

Things to do

• Read 3.1 up to page 109 Theorem 3.1.7 (skip example 8). Read what's left of 3.2. Read Page 127 — 128 and example 3.
• Exercises: 3.1: 1, 7, 9, 13, 33; 3.2: 17; 3.3: 7, 17, 21 (basis of kernel only), 27, 29.

Lecture 9. Spanning sets.

Monday, September 13, 2010

See Lecture 10 for information.

Lecture 8. Linear independence, bases and dimension.

Friday, September 10, 2010

Things to do

• Exercises 3.2: 34, 38 (try it), 39, 47, 51 (a), 52, 53, 56.
• Read Definition 3.2.3, 3.3.1, — 3.3.4, Definition 2.1.1, and Theorem 2.1.3 for Monday. I know this means you have to jump around through the book, but we are trying to get to the important facts.
• Quiz 2 on Monday 9/13 will be about testing vectors for linear independence, and deciding whether a vector is in the span of a set of vectors.

Lecture 7. Linear independence, bases and dimension.

Monday, September 8, 2010

Things to do

No problems for today.

Lecture 6. Linear independence, bases, dimension.

Monday, September 6, 2010

We will look at linear combinations, linear independence and bases.

Things to do

• Exercises 3.2: 1 — 19 (odd), 35, 39, 42, 43, 50*, 51*. (starred problems are harder)
• Read chapter 3.2 for Wednesday.

Lecture 5. Proofs and induction.

Friday, September 3, 2010

We talked about if, then statements and saw some examples from calculus. We also talked about proof by induction.

Things to do

• There will be a quiz on 1.1 and 1.2 on Monday 9/6/2010.
• Read chapter 1.3 for Monday

Other stuff

• Notes on induction

Lecture 4. Matrix multiplication.

Wednesday, September 1, 2010

We looked again at the relationship between the rank, the number of free variables and the number of variables. We also looked at how to multiply a matrix into a vector in terms of the rows of the matrix and the columns of the matrix.

Things to do

• There will be a quiz on 1.1 and 1.2 on Friday 9/3/2010 (postponed).
• Read chapter 1.3 for Monday
• Exercises: Section 1.3: 1 — 5 (odd), 14 — 20, 24, 29, 34, 35, 37.

Lecture 3. Row reduced echelon form.

Monday, August 30, 2010

Row reduced a matrix and introduced a shorthand (using stars) to denote matrices. We also saw intuitively that the number of free variables in a RREF system is equal to the number of variables minus the number of leading ones (the rank).

Things to do

• Exercises: Section 1.2: 1 — 27 (odd), 34, 35, 36.

Lecture 2. The vector space R^n

Friday, August 27, 2010

Today we defined Rn and looked at some systems of linear equations.

Things to do

• Read section 1.2. In particular the definition of row-reduced echelon form.
• Exercises: Section 1.1: 5, 7, 12, 15, 22, 31, 32, 37; Section 1.2: 5, 18.

Lecture 1. Vector spaces.

Wednesday, August 25, 2010

Today we defined a the notion of a vector space (Definition 4.1.1 in the book). Next time we will look at linear systems and matrices and check that the set of n-dimensional vectors is a vector space.

Things to do

• Read section 1.1