Math 214
Linear Systems
Spring 2008

Schedule

Ron Buckmire: 
Contact & Home & Schedule

Syllabus

Linear Algebra Toolkit

maths online

The whole focus of this section is to work toward the Spectral Theorem (Theorem 5.20) which states:  A matrix A is symmetric if and only if it is orthogonally diagonalizable.

 Definition – Symmetric – recall that A is symmetric if A^T = A (p. 149)

 Definition – Orthogonally Diagonalizable – a matrix A is orthogonally diagonalizable if there exists an orthogonal matrix Q and a diagonal matrix D such that Q^TAQ = D (p. 397)

 Showing that an orthogonally diagonalizable matrix is symmetric is relatively easy (Theorem 5.17).  But the rest of the section is trying to establish the spectral theorem going the other direction – that symmetric matrices are all orthogonally diagonalizable.

 Since we’re not working at all with complex numbers, the proof to Theorem 5.18 may not make too much sense to you.  It essentially is using the idea of complex conjugates to prove that the eigenvalues of symmetric matrices are all real.

Notice that Theorem 5.19 goes further than what we knew already.  We knew that eigenvectors for different eigenvalues were linearly independent, but this theorem says that in the case of symmetric matrices, they are in fact orthogonal to each other.

The book introduces the terminology of spectrum to refer to the set of eigenvalues.  You’ll hear this in some physical situations, and we use it more often in mathematics when we have an infinite-dimensional system (and thus often an infinite number of “eigenvalues”), but it still works in the small dimension systems we’re working with.

 The proof of the spectral theorem is fairly long and uses some notation from section 3.1 that you may wish to review – various representations of matrix multiplication and block matrix representations.  Read over this proof several times, trying to follow each step and writing out details on your own paper if needed.  You don’t have to completely master it.

 The spectral theorem leads to another factorization of the matrix A:  A = QDQ^T which on p. 402 they write in the projection form (and note this uses the outer product notation introduced on p. 145).  D is just the diagonal matrix consisting of the eigenvalues.  Q is an orthogonal matrix that is created from the eigenvectors – we take the basis for each eigenspace and then find an orthogonal basis using the Gram-Schmidt process and then normalize each vector found.  This creates the orthogonal matrix Q needed to orthogonally diagonalize A.

In the previous section, we learned that if we have an orthogonal basis for a subspace W, then we can define the orthogonal projection of a vector onto W – basically by summing the projections of the vector on to each vector in the basis – and that this projection is unique.  But how do we know we can find an orthogonal basis for any subspace W?

This section introduces a process, called the Gram-Schmidt Process, that constructs an orthogonal basis.  Theorem 5.15 lays out the process.  It looks somewhat complicated, but really it is just taking one vector at a time, and taking the component of that vector that is orthogonal to the subspace made up of all the other vectors you’ve already created.

So now, the only trick is that you have to start out with a basis – any basis – of your subspace.  Then you can “orthogonalize” (this really isn’t a word) it.  Usually finding a basis isn’t too hard, if you understand what a basis of a subspace is.

Some important notes:

• The Gram-Schmidt process does not create an orthonormal basis – it creates an orthogonal basis!
• Even if you start with all unit vectors, the output of the Gram-Schmidt process may not be an orthonormal basis, as it keeps changing the vectors (including their lengths) as you go!
• If you do need an orthonormal basis rather than just an orthogonal one, do the Gram-Schmidt process and get your orthogonal basis, and then just normalize all the vectors to unit vectors to get your orthonormal basis.

If A is an m x n matrix which has linearly independent columns, then we can create the factorization:  A = QR

• Q is a matrix with orthonormal columns – where the columns of Q are just the normalized vectors obtained from the Gram-Schmidt Process on the columns of A.  Q will be the same size as A (m x n).
• R is an upper triangular (square n x n) matrix – and can be obtained from Q^TA.
• This QR factorization has some nice applications.  We won’t explore the example of using it to numerically approximate eigenvalues of a matrix.  Time allowing, we will explore using it to solve the problem of least squares approximation of data (section 7.3).

It might be helpful for you to review Section 3.5 if you are still having difficulty with the four fundamental subspaces associated with a matrix – null(A), col(A), row(A), col(A^T), finding a basis for each as well as the dimension of each subspace.

Definition – Orthogonal Complement of a subspace

 Notice that in Example 5.8, they show that the orthogonal complement to a plane through the origin in R³ is a line through the origin.  Notice that that leaves lots of vectors in R3 not in the original subspace or the orthogonal complement of that space!

 Theorem 5.9 tells us a little more about the orthogonal complement to a space.  Note that part (c) is just saying that the only vector in BOTH the subspace and its orthogonal complement is the zero vectors – which has to be in every subspace.

 In Theorem 5.10, we return to the four fundamental subspaces and we see that the row and null spaces are orthogonal complements, and the column and the left null spaces are orthogonal complements.  That means that every vector in the row space is orthogonal to every vector in the null space and vice-versa – doesn’t this make sense if you think about how these vectors are found?

 The section on orthogonal projections is really just an extension of projecting a vector onto a line (which has one vector direction).  Now we can project onto any subspace given an orthogonal basis for that subspace.  And the formula is essentially like the one we saw in section 5.1 and earlier in the book with projections.  The last part of the definition giving the component of the vector orthogonal to the subspace, and then following on to Theorem 5.11, we see that any vector can essentially be decomposed into two pieces – one in the subspace, and one in the orthogonal complement to the subspace.

 Theorem 5.13 says that the dimension of a subspace and the dimension of the orthogonal complement must sum up to the dimension of the overall space.  So think about the example 5.8 again.  The subspace was a plane (dimension 2), and the orthogonal complement then had to be a one dimensional subspace, thus a line.

 Corollary 5.14 returns us back to the four fundamental subspaces.  Recall that the row space and the null space are in Rⁿ.  And we already knew that their dimensions added to n.  This just reiterates that result.  And note the comment following the proof that says that the dimensions of the column and left null spaces add to m.

Let’s reiterate the above with something that was in the Section 3.5 Content Goals:

·         Subspaces of R^m and Rⁿ associated with an (m x n) matrix A:

o        Column space:  col(A), a subspace of R^m with dim(col(A)) = rank(A)

o        Row space:  row(A), a subspace of Rⁿ with dim(row(A)) = rank(A)

o        Nullspace:  null(A), a subspace of Rⁿ with dim(null(A)) = n – dim(row(A))

·         The Rank Theorem for an (m x n) matrix A:

o        rank(A) + nullity(A) = dim(row(A)) + dim(null(A)) = n

o        rank(A^T) + nullity(A^T) = dim(col(A)) + dim(null(A^T)) = m

Definition – Orthogonal Set of vectors

Theorem (5.1) – If we have an orthogonal set of vectors, then they are all linearly independent

Definition – Orthogonal Basis for a subspace

Theorem (5.2) – If we have an orthogonal basis for the subspace W, then any vector w in that subspace can be written uniquely as a linear combination of the basis vectors.  The constants in this linear combination are given by quotients of those dot products as given in the statement of the theorem.

Definitions – Orthonormal Set and Orthonormal Basis – basically you just add the condition that every vector is a unit vector to the ideas already given above

Theorem (5.3) – If we have an orthonormal basis for the subspace W, then any vector w in that subspace can be written uniquely as a linear combination of the basis vectors.  The formula is given in the statement of the theorem.  Since the vectors are all unit vectors, the denominators in the formula from Theorem 5.2 are no longer needed.

Definition – Orthogonal Matrix (make sure you read the “unfortunately terminology” note next to the definition) – a square matrix whose columns form an orthonormal set

Theorems (5.4-5.8) – Results related to Orthogonal Matrices, Q:

• Q^TQ = I_n – whenever this is true, it implies that the columns of Q form an orthonormal set even if Q is not a square (and thus orthogonal) matrix
• Q^-1 = Q^T – whenever this is true, it implies that Q is an orthogonal matrix
• Q preserves length (i.e., ||Qx|| = ||x||) – thinking of Q as a linear transformation, an orthogonal matrix is a transformation that doesn’t change the length of vectors
• Q preserves the dot product (i.e., Qx ^. Qy = x ^. y) – remember that the dot product is associated with the angle between the two vectors, so thinking of Q as a linear transformation, if two vectors are transformed by Q, the angle between them does not change
• The rows of Q are also an orthonormal set
• Q^-1 is orthogonal – so thinking of Q as a linear transformation, the inverse transformation also doesn’t change the length of vectors
• det Q = | Q | = ± 1 – and this would imply that the transformation doesn’t change the area of shapes that are transformed by Q
• If l is an eigenvalue of Q, then | l | = 1 – note that this property can hold even if l is a complex eigenvalue (which we aren’t dealing with in this course)
• The product of two orthogonal matrices is also an orthogonal matrix

·        Definition & Conceptual Idea of Eigenvalues and Eigenvectors of a Matrix

·        How to find Eigenvalues – using det(A – lI) = 0 [the left hand side is called the Characteristic Polynomial – you may find the contents of Appendix D helpful in solving the characteristic polynomial for the eigenvalues if you need to brush up]

·        Cayley-Hamilton Theorem – a matrix satisfies its own Characteristic Polynomial!

·        How to find Eigenvectors (Eigenspace) – nullspace of A – lI

·        Definition of determinant – using Cofactor expansion

·        Calculating 2x2 and 3x3 determinants the quick way

·        Calculating determinants using row reduction

·        That the eigenvalues of a triangular matrix are just the diagonal elements, and the determinant is just the product of these diagonal elements

·        A matrix A is invertible if only if det(A) ≠  0; this is true if any only if 0 is not an eigenvalue of A [these are the new entries to the Fundamental Theorem of Invertible Matrices]

·        Properties of the determinant (e.g., Theorems 4.7 – 4.10)

·        Cramer’s Rule, Adjoint, calculating A^-1 using the adjoint [just need to know what these are, and be able to do it given a formula; should not memorize]

·        Finding a Cross Product using a determinant  [the rest of the Exploration section is just for you to see some of the numerous examples of using the determinant.  You are not responsible for these methods or formulae.]

·        Algebraic & geometric multiplicity of eigenvalues and the fact that a matrix is diagonalizable only if these are equal for each eigenvalue (Diagonalization Theorem).

·        Two matrices are similar (A ~ B) if we can find a P such that P^-1AP = B.  Similar matrices hold many of the same properties (e.g., Theorem 4.22).

·        A matrix A is diagonalizable if it is similar to a diagonal matrix D, i.e., P^-1AP = D

·        Definition of Linear Transformation

o       The key here is that the transformation is preserved over addition and scalar multiplication, just like every other concept in this course!

·        Every Linear Transformation has a matrix representation

·        The matrix representation can be found by having the transformation act on the standard basis vectors (see Theorem 3.31)

·        Not all linear transformations are invertible, but for those that are, matrix representation of the inverse transformation is the inverse of the matrix representation of the original transformation (see Theorem 3.33)

·        Visual and algebraic understanding of standard linear transformations in R² such as scaling, reflection, rotation

·        Definition of Subspace

·        Idea of finding a subspace in Rⁿ spanned by a set of vectors v₁, …, v_k.

·        Subspaces of R^m and Rⁿ associated with an (m x n) matrix A:

o       Column space:  col(A), a subspace of R^m with dim(col(A)) = rank(A)

o       Row space:  row(A), a subspace of Rⁿ with dim(row(A)) = rank(A)

o       Nullspace:  null(A), a subspace of Rⁿ with dim(null(A)) = n – dim(row(A))

·        Definition of Basis and Dimension of a subspace

·        Nullity:  nullity(A) = dim(null(A))

·        The Rank Theorem for an (m x n) matrix A:

o       rank(A) + nullity(A) = dim(row(A)) + dim(null(A)) = n

o       rank(A^T) + nullity(A^T) = dim(col(A)) + dim(null(A^T)) = m

·        Orthogonality of the vectors in null(A) with those in row(A) – HW #55

·        For an (n x n) matrix A to be invertible, rank(A) = n and nullity(A) = 0

·        Understand that a matrix acts as a linear transformation on a vector

·        Know what a matrix is and special classes of matrices

o       Square, diagonal, identity, symmetric

·        Be able to carry out fundamental operations on matrices

o       Matrix addition/subtraction

o       Scalar multiplication

o       Matrix multiplication

§         Relationship between size of matrices multiplied and result

§         “Normal” approach to matrix multiplication

§         Matrix-column & row-matrix representations of multiplication

§         Block partitioning of matrices for easier multiplication of certain larger matrices

o       Matrix transpose

·        Understand the algebraic properties of the fundamental operations on matrices

o       Properties of matrix addition, scalar multiplication, and matrix multiplication (summarized in Theorems 3.2 & 3.3)

o       Understanding in particular that matrix multiplication is not commutative except in very special cases

o       Properties of matrix transpose (summarized in Theorem 3.4)

·        Apply the concepts of span, linear combinations, and linear dependence & independence to the arena of matrices

·        Matrix Inverse

o       The definition (see p. 161) – note our standard notation will be A^-1, not A’

o       Uniqueness of the inverse

o       Not all matrices are invertible

o       Using it to solve Ax = b

o       When a 2x2 matrix is invertible and what its inverse is

o       Finding an inverse through Gauss-Jordan elimination

o       Properties of the matrix inverse

·        Elementary matrix

o       Note:  If you’ve been “cheating” so far with elementary row operation number 3 (see p. 70) and doing R_i Þ R_j + c R_i rather than the correct row operation R_i Þ R_i + c R_j, you will have to amend your ways.  Otherwise your transformation will not be an elementary matrix and the fundamental theorem won’t hold!

·        Fundamental Theorem of Invertible Matrices

o       This is one of those fundamental theorems that is not “fundamental” in every text book.

o       In particular, you must understand that if A is invertible, then it can be written as the product of elementary matrices (connection (a) and (e) in the theorem).

·    

 Fact that P^T = P^-1

Sections:  2.0, 2.1, 2.2 (thru p. 80, skipping Linear Systems over Z_p), 2.3, 2.4

·        Recognize linear versus nonlinear equations

·        Solve systems of linear equations with constant coefficients using

o       A graphical approach

§         As intersection of lines and planes

§         As linear combination of vectors [note that this is what Theorem 2.4 in section 2.3 is stating; and is what Problems 3 & 4 in section 2.0 were highlighting]

o       A set of algebraic equations

o       The corresponding augmented matrix, and

§         Gaussian elimination (and back substitution)

§         Gauss-Jordan elimination (and back substitution)

·        Understand that these systems have 0, 1, or infinite number of solutions

·        Elementary row operations on a system do not change the solutions to the system

·        Row echelon form and reduced row echelon form of a matrix

·        Reduced row echelon form is unique

·        Rank of a matrix, and the Rank Theorem

·        Homogeneous systems must have 1 or an infinite number of solutions (never 0 solutions), and the Rank Theorem tells us which

·        Definition of linear dependence and linear independence

o       Note that Theorems 2.5-2.7 give equivalent ways of stating a set of vectors are linearly dependent, but they also connect important concepts in this section to the idea of linear dependence/independence

o       Know how to determine if a set of vectors are linearly dependent or independent, and if the former, an expression for the dependence

·        Span of a set of vectors and the spanning set of a space

o       Note that later in the book (section 3.5) we’ll see that a “basis” is a slightly more restrictive set than the spanning set; but it’s really the set we care about

Sections:  1.1, 1.2, 1.3, Exploration: The Cross Product

·        Vector and its attributes

o       Initial point & terminal point

o       Length/norm

o       Translation invariance & standard position

·        Vector addition

o       Geometric

o       Analytic

·        Linear combination of two or more vectors

·        Dot product of two vectors

o       Length of a vector

o       Angle between vectors

o       Cauchy-Schwarz Inequality

o       Triangle Inequality

·        Orthogonal vectors

·        Projection of one vector onto another vector

·        Normal vector

·        Equation of a line/plane

o       Normal form

o       Vector form

o       Parametric form

o       General form

o       Vector form as linear combination of vectors

·        Cross product of two vectors in R³