Math 110 - Fall 05 - Lectures notes # 1 - Aug 29 (Monday)Name, class, URL (www.cs.berkeley.edu/~demmel/ma110) on boardSee Barbara Peavy in 967 Evans Hall for all enrollment issues.All course material will be on the web page. If this isinadequate, please send me email and I will put copies atCopy Central Northside.Read Course Outline on web page for course rules and grading policiesYou are responsible for reading this and knowing the rules!Text, which we will follow fairly closely:Linear Algebra, 4th Edition, by Friedberg/Insel/Spence,same as last semester.Topics (following table of contents):Chap 1: Vector spaces ("vectors" and their basic properties)Chap 2: Linear transformations ("matrices" and their basic properties)Chap 3: Elementary Matrix Operations (quickly)Chap 4: DeterminantsChap 5: Diagonalization (eigenvalues and vectors)Chap 6: Inner products, orthgonality, singular value decompositionChap 7: Jordan Form (generalizations of eigenvectors)Examples (why is linear algebra important)Linear Equations: Consider new Bay Bridge: how is it designed?How do they know it will be strong enough to hold up the traffic?If you imagine a car sitting on the end of a beam, youcan write a simple relationshipF (force from weight of car on bridge)= k (stiffness of beam) * x (how much beam bends)So if you know the weight of the car, and the stiffness of the beam,you can solve one linear equation in one unknown F=kx forx = F/k to get the amount the bridge bends, and compare thatto how much you are willing to let it bend. In a real bridgethere are many cars, many beams, and many x’s describing how eachbeam bends, and the the beams are connected. So instead ofof 1 linear equation in 1 unknown, you get thousands of linearequations in thousands of unknowns, which civil engineers have to solve.The same process applies to any important structures(buildings, airplanes, cars, certain computer chips ...).See CE 130, ME 104.1All radio, light and other electromagnetic radiation in free spacesatisfy a system of linear equations called Maxwell’s equations.These are partial differential equations, but linear nonetheless.See Ph 7B or Ph 110.EG: Aim 2 flashlights at board and observe that lit spot 1 is same whetheror not beam 2 passes through beam 1.ASK & WAIT: Can you explain this using linear algebra?Eigenvalues and Eigenvectors:ASK & WAIT: Each of you depends on an eigenvector of one of the world’slargest matrices, many times each day. How big is the matrix?Hint: what number do you see when you go to www.google.com?Schroedinger equation: every atom, molecule, your physical bodyis most acccurately described as an "eigenvector" ofSchroedinger’s equation, which is a partial differential equation.The eigenvalues correspond to energy levels, and the eigenvectorsdescribe how the electrons are distributed around all the atomicnuclei. See Ph 7C or Ph 137.What we will cover: We will concentrate on definitions, and theoremsdescribing basic properties of these linear algebra objects likelinear transformations, their inverses (when they exist),eigenvalues and eigenvectors (when they exist).In particular, you will practice reading and writing clear andcorrect mathematical proofs.We will also try to look at concepts and problem solving fromat least 2 points of view: algebra and geometry, becauselinear algebra natually incorporates and can be understood both ways:EG: One can either say:2 equations in 2 unknowns can or 2 lines in the plane can(1) have a unique solution (1) intersect in a point(2) have no solutions (2) be parallel and not intersect(3) have infinitely many solutions (3) be identicalWhat we will not cover: practical algorithms for solving linearequations, finding eigenvalues/vectors (Ma128ab, Ma221)This course is a prerequisite for such courses.Prereq: Math 54, including definitions of sets, functions (Apps A, B)2Homework will be due Thursdays at the start of section. There will bebrief weekly quizzes to make sure people are keeping up.To get started, let’s talk carefully about the numbers that we will bewriting in our vectors and matrices. As motivation:Consider solving 2*x = 1: even though there are only integers inthe equation, we can’t solve for x if we only look for x in Z =set of integers, we need Q = set of rational numbers.Consider solving x^2-2 = 0; even though there are only rational numbersin the equation, we can’t solve for rational x, we need real numbers RConsider solving x^2 + pi = 0; even though there are only real numbersin the equation, we can’t solve for real x, we need complex numbers C.DEF: A set of numbers (also called scalars) F is called a field ifthere are two binary operations + (addition) and * (multiplication)so that x+y and x*y are unique numbers in F for all x and y in F, andsuch that + and * satisfy the following conditions:(1) for all x and y in F: x+y=y+x and x*y=y*x(commutativity of addition and multiplication)(2) for all x, y, z in F: (x+y)+z = x+(y+z) and (x*y)*z = x*(y*z)(associativity of addition and multiplication)(3) There exist distinct scalars 0 and 1 such thatfor all x in F: x+0=x and x*1=x(existence of identity elements for addition, multiplication)(4) For all x in F and nonzero y in F, there exist x’ and y’ such thatx + x’ = 0 and y*y’ = 1. We denote x’ by -x, and y’ by y^(-1).(existence of inverses for addition, multiplication)(5) for all x,y,z in F: x*(y+z) = x*y + x*z(distributivity)ASK & WAIT: Is Z a field? Why?ASK & WAIT: Is Q a field?ASK & WAIT: Is R a field?ASK & WAIT: Is C a field?ASK & WAIT: Is S = {q1 + q2*sqrt(2), q1 and q2 in Q} a field?ASK & WAIT: Is A = {all roots of polynomials with integer coeffs} a field?3EG: Z2 = {0,1} with 0+0=0, 0+1=1, 1+1=0; 0*0=0, 0*1=0, 1*1=1Can show this is a field (homework!)ASK & WAIT: Does this field, with its operations, have other names?EG: Zp = {0,1,2,...,p-1} where p is a prime,x+y = x+y mod p = remainder after dividing x+y by px*y = x*y mod p = remainder after dividing x*y by pCan show this is a field (homework!)Used in cryptography (see Ma55)DEF: A field F has characteristic p if 1+1+...+1 (p times) = 0 for somepositive integer p. Otherwise F has characteristic 0.ASK & WAIT: What is the characteristic of Q?ASK & WAIT: What is the characteristic of R, C, S, A?ASK & WAIT: What is the characteristic of Z2?ASK & WAIT: What is the characteristic of Zp?EG: F(x) = rational functions in x with coefficients from another field Fof characteristic 0. So fields don’t have to be "numbers" in the