Math 113: Linear algebra and matrix theory (spring 2006)

From the course bulletin: Algebraic properties of matrices and their interpretation in geometric terms. the relationship between the algebraic and geometric points of view and matters fundamental to the study and solution of linear equations. Topics: linear equations, vector spaces, linear dependence, bases and coordinate systems; linear transformations and matrices; similarity; eigenvectors and eigenvalues; diagonalization.

Warning: This course will be taught quite theoretically, and at a fast pace! As a result, the homework will be heavy too. If you are interested mainly in applications to other fields, or prefer to deal only with concrete objects, you should take Math 103 instead.

Lectures: Tuesday and Thursday 11 am - 12:15 pm. Location as of Thursday January 12: 380-Y.

Professor: Ravi Vakil, Room 383-M (third floor of math building).

Course assistant: Robin Koytcheff,, Room 381-N (first floor of math building).

Course graders: Theo Johnson-Freyd,, and Charles Hallford, (If you have questions about grading, please contact Theo.)

Office hours: Monday 2:05-4:05 pm (Robin Koytcheff, 381-N), Tuesday 1-2 pm (Robin Koytcheff, 381-N), Tuesday 2-3:30 pm (Ravi Vakil, 383-N) (except March 14), Wednesday 2:05-3 pm (Robin Koytcheff, 381-N). Office hours on the week of the final exam are announced below. There will be three hours on each of Sunday March 19, Monday March 20, and Tuesday March 21, in either the afternoon or the evening.

Text: The textbook for the course will be the notes A (terse) introduction to linear algebra, by Prof. Katznelson (who taught this class in the fall).

You are certainly encouraged to look at other references, to find one that suits your point of view. The best way to do this is to browse in the library. Here are two books that some people like: Hoffman and Kunze, Linear Algebra; and Nering, Linear Algebra and Matrix Theory. Both should be on 3-day reserve at the Math and CS library. Another book recommended by Robin is Axler's Linear Algebra Done Right. Warning: The bookstore has "Hoffman and Kunze" advertised as the text for this class. This is not the case!

E-mail list: I will maintain an e-mail list to sporadically send you important messages. If you are not on the e-mail list and wish to be, please let me know. (And similarly, let me know if you wished to be removed.) This is not the same list as those officially enrolled on Axess.


  • Homework 30% (posted below)
  • Mid-term 25% (in class, tentatively Thursday, February 2, graded in time for the drop deadline Sunday, February 5)
  • Final exam 45% (Thursday, March 23, 3:30-6:30 pm, in 370-370)

    What we'll cover: We will hopefully cover most of the following: Chapters 1, 2 (emphasizing 2.6 less), 3, 4. Chapter 5 up to 5.3. Hopefully 6.1, and perhaps more of 6. As much of the appendix as we need. We will largely move linearly through the text, so you should read one section ahead of where we are.

    What we've done so far: (This paragraph will be only sporadically updated.)
    Week 1: We discussed maps, groups, and fields. We went through 1.1, except for tensor products.
    Week 2: We discussed until the end of chapter I.
    Week 3 and Week 4: We discussed up until change of basis (II.4.5). The midterm took place in week week 4.
    Week 5: We skipped 2.6, and finished most of chapter 3.
    Week 6 and 7: We discussed determinants (chapter 4), with topics in a slightly different order than in the book.

    Homework will be due on Thursday outside my office door, by 9 pm (when the building will be locked). You can also hand it in during class. Theo promises not to pick up the homework before 10 am on Friday, so you'll have a little grace period. No lates will be accepted. I'll ignore one of the problem sets, so save that for when you come down with a bug, or have an especially busy time. If you do all the problem sets, I'll drop the lowest score. Solutions will usually be posted on the Saturday after the problem sets are due (link to be added soon). If you have any questions about the grading, please first ask Theo. If you have further questions, please let me know.

  • Problem set 1 (due Thurs. January 19). Solutions.
    1. (A first proof problem.) Show (using the axioms of a vector space) that 0 times any vector v in a vector space is the zero vector 0. (I don't know how to make arrows in html, so my vectors are in bold face.)
    2. Recall our definition of quotient space V/W, where W is a subspace of vector space W. We defined V/W as a set, and claimed that it is in fact a vector space. We showed how to multiply an element [v] of V/W by a scalar, and showed that our definition was independent of our "name" for that element. Show similarly how to add two elements of V/W. (This is largely stated in the text. I want you to carefully explain how this works, showing that you understand why such an argument is necessary.)
    Do problems I.1.1, I.1.2, I.1.3, I.1.4, I.1.5, I.2.1, I.2.2, I.2.3, I.2.6, I.2.7 in the text. (All references are to the January 1 version.) You can do I.1.6 in place of any three of the above questions; and you do I.1.7 in place of any three as well. (In I.1.5, I.1.6, and I.2.2, that backslash symbol means "minus" for sets. In I.1.6, you are required to verify the first sentence. In I.1.7 (a), you are required to verify the statement.) The I.2 problems will require reading ahead.

  • Problem set 2 (due Thurs. January 26). Solutions.
    1. Show that any two vector spaces over a field F of dimension 10 are isomorphic.
    I.2.9, I.2.12, I.2.15, I.3.1 (explain why you have found all such matrices), I.3.2, I.3.3 (define "degrees of freedom" in any sensible way), I.3.5, I.3.7, I.3.9. You can do I.2.17 in place of any three above the above questions; and you can do I.3.10 in place of any three as well.

  • Problem set 3 (due Thurs. February 9). Solutions.
    II.1.1, II.1.2, II.1.3, II.3.2, II.3.3, II.3.5, II.3.12, II.4.2. If you scored less than 4/6 on the last problem on the midterm, you can solve that problem in place of any two of the above.

  • Problem set 4 (due Thurs. February 16). Solutions.
    Do problem 1, as well as seven of the remaining nine problems. (Or if you'd like, do all the problems, and the lowest two scores, not including problem 1, will be dropped.)
    1. Suppose T: V --> W is a linear map, and T*: W* --> V* is the adjoint. Explain why (Tv, w*) = (v, T* w*) for every vector v in V and w* in W*.
    2. Let A be the 2x2 matrix with entries 2, 1 (in the top row), 1, 2 (in the bottom row). (a) Find 2 non-zero vectors v and w such that A v = v and A w = 3 w. (b) Find a diagonal matrix D such that A is similar to D. (Hint: use (a).)
    3. (In this problem, the row vectors should be read as column vectors. I hope this isn't too confusing!) Notice that v1 = [1 2] and v2 = [2 3] form a basis for F^2, as do w1 = [1 0] and w2 = [2 -1]. Suppose a1 and a2 are elements of F, and a1 v1 + a2 v2 = b1 w1 + b2 w2. Find b1 and b2 in terms of a1 and a2. Describe your answer in the form of a matrix. Explain how to interpret your answer as a change of basis matrix.
    4. Consider the linear map F^{100} --> F^{101} given by e_i --> f_i + f_{i+1}. Suppose the adjoint map sends f*_{50} to a_1 e*_1 + ... + a_{100} e*_{100}. Find a_1, ..., a_{100}. (This is just a fancy way seeing if you can figure out what the adjoint does in this case.)
    II.3.13, II.5.1, II.5.2, II.5.9, III.1.1, III.1.2.

  • Problem set 5 (due Thurs. February 23). Solutions.
    III.1.7, III.2.1, III.2.3, IV.1.1, IV.1.2, IV.2.2, IV.5.3, IV.5.9.

  • Problem set 6 (due Thurs. March 2). Solutions.
    IV.4.2 (This will involve figuring out what T-invariant means. Possible hint for the problem: choose a convenient basis. What does the matrix corresponding to T look like with respect to this basis?). IV.5.1. IV.5.2. IV.5.5. IV.5.8 (the second sentence should read: "In other words, if the characteristic polynomial of (a_{i,j}) is equal to (-1)^n product_{j=1}^n (lambda - lambda_j) then sum lambda_j = sum a_{i,i}."). IV.5.10 (this is an example of a "sparse" matrix, in which most entries are zero, and finding the determinant requires less compouting power). IV.5.11. IV.5.12 (feel free to add the additional assumption that the alpha_j's can be made, although strictly speaking it isn't necessary).

  • Problem set 7 (due Thurs. March 9). Solutions.
    1. Prove part (c) of the Spectral Mapping Theorem (p. 66). (Don't just copy out the proof in the book --- it is a bit telegraphic! Piece together a proof that you understand.)
    2. The next three problems will let you see why taking powers of diagonal and more generally upper-triangular matrices is not so hard, and why that makes taking powers of general matrices not so hard too. Consider the 2x2 diagonal matrix with diagonal entries 2 and 3. Then computing its 100th power is easy: it is the diagonal matrix with entries 2^{100} and 3^{100}.
    (a) Suppose C is an invertible nxn matrix and A is any nxn matrix. Show that (C A C^{-1})^{100} = C A^{100} C^{-1}. (Thus if we can diagonalize a matrix, then taking powers is easy.)
    (b) Let B be the 2x2 matrix
    0 1
    1 1.
    If the field F is the field of rational numbers Q, show that B cannot be diagonalized. Diagonalize B over the real numbers R. (This will be a bit messy.)
    3. (a) Using 2(a) and the diagonalization in 2(b), give an expression for B^n.
    (b) Recall that the Fibonacci numbers are defined by F_0 = 0, F_1 = 1, and for n at least 2, F_n = F_{n-1} + F_{n-2}. Give an expression for B^n in terms of Fibonacci numbers. (Hint: first compute B, B^2, B^3, B^4, and look for the pattern.) Hence using 3(a), give a formula for the nth Fibonacci number! (Hint: the square root of 5 will appear in your formula.)
    4. What is the top right entry in the 100th power of the 3x3 matrix A, given by
    2 1 0
    0 2 1
    0 0 2?
    (Possible hint: first try the same problem with a new matrix A', with 1's in the diagonal instead of 2's. Take the first few powers of A', and look for a pattern. Then take the first powers of A, and look for a pattern.) We will soon see that if you know the answer to this, you will be able to take any power of any matrix.
    Do problems V.I.2, V.1.4, V.2.1, V.2.2.

  • Problem set 8 (due Thurs. March 16). Solutions to appear at some point.
    V.2.4, V.2.5, V.2.6, V.2.7, V.2.10, V.2.11, V.3.1, V.3.6

    Please come discuss the problems during office hours!

    Midterm: The midterm will take place in class on Thursday, February 2, from 11:05 to 12:15. The midterm is a closed-book exam, and you may use pens and pencils, but no calculators. I will have bonus office hours on Wednesday, from 3 to 5 pm.

    Here is the practice midterm. Here is the actual midterm. Some solutions are here (excepting B4, whose solution appears on problem set 3). Many other solutions are possible! I'm happy to discuss solutions to any of the problems.

    Final exam: The final exam will be on Thursday, March 23, 3:30-6:30 pm, in 370-370. It is a closed-book exam, and you may use pens and pencils, but no calculators. Here is the practice final.

    Bonus office hours: Sunday March 19 for 3 hours (Robin Koytcheff; the precise time will be announced here). Monday March 20, 7-10 pm (Ravi Vakil). Tuesday March 21, 2-5 pm (Ravi Vakil). GOOD LUCK!

    Ravi Vakil
    Department of Mathematics Rm. 383-M
    Stanford University
    Stanford, CA
    Phone: 650-723-7850 (but e-mail is better)
    Fax: 650-725-4066