Linear Algebra and Differential EquationsMath 21bHarvard UniversityFall 2004Oliver Knill• Instructor: Oliver Knill (http://www.math.harvard.edu/˜knill)• Office: 434, Science Center• Office hours: MWF 15:00-16:00• E-mail: [email protected]• Phone: 5-5549• Classroom: 309• Classtime: MWF 11-12• CA: Tien Anh Nguyen, e-mail tanguyen@fas• Course page: http://www.courses.fas.harvard.edu/˜ math21b/• Midterms Wed Oct 27 6:30pm, Wed, Dec 1, 6:00pm• Textbook: Linear Algebra and its applications by Otto Bretscher (third edition)• Grade: Midterms 20% each, homework: 20 %, Final: 40 %.• Homework: Due at beginning of each class.Oliver Knill. 9/26/20049/20/2004, USE OF LINEAR ALGEBRA I Math 21b, O. KnillThis is not a list of topics covered in the course. It is rather a lose selection of subjects for which linear algebrais useful or relevant. The aim is to convince you that it is worth learning this subject. Most of this handoutdoes not make much sense yet to you because the objects are not defined yet. You can look at this page at theend of the course again, when some of the content will become more interesting.1 234GRAPHS, NETWORKS. Linear al-gebra can be used to understandnetworks. A network is a collec-tion of nodes connected by edgesand are also called graphs. The ad-jacency matrix of a graph is de-fined by an array of numbers. Onedefines Aij= 1 if there is an edgefrom node i to node j in the graph.Otherwise the entry is zero. A prob-lem using such matrices appeared ona blackboard at MIT in the movie”Good will hunting”.How does the array of numbers helpto understand the network. One ap-plication is that one can read off thenumber of n-step walks in the graphwhich start at the vertex i and endat the vertex j. It is given by Anij,where Anis the n-th power of thematrix A. You will learn to computewith matrices as with numbers.CHEMISTRY, MECHANICSComplicated objects like abridge (the picture shows StorrowDrive connection bridge which ispart of the ”big dig”), or a molecule(i.e. a protein) can be modeled byfinitely many parts (bridge elementsor atoms) coupled with attractiveand repelling forces. The vibrationsof the system are described by adifferential equation ˙x = Ax, wherex(t) is a vector which depends ontime. Differential equations are animportant part of this course.The solution x(t) = exp(At) of thedifferential equation ˙x = Ax can beunderstood and computed by find-ing the eigenvalues of the matrix A.Knowing these frequencies is impor-tant for the design of a mechani-cal object because the engineer candamp dangerous frequencies. Inchemistry or medicine, the knowl-edge of the vibration resonances al-lows to determine the shape of amolecule.QUANTUM COMPUTING Aquantum computer is a quantummechanical system which is used toperform computations. The state xof a machine is no more a sequenceof bits like in a classical computerbut a sequence of qubits, whereeach qubit is a vector. The memoryof the computer can be representedas a vector. Each computation stepis a multiplication x 7→ Ax with asuitable matrix A.Theoretically, quantum computa-tions could speed up conventionalcomputations significantly. Theycould be used for example for cryp-tological purposes. Freely availablequantum computer language (QCL)interpreters can simulate quantumcomputers with an arbitrary num-ber of qubits.CHAOS THEORY. Dynamicalsystems theory deals with theiteration of maps or the analysis ofsolutions of differential equations.At each time t, one has a mapT (t) on the vector space. Thelinear approximation DT (t) iscalled Jacobean is a matrix. If thelargest eigenvalue of DT (t) growsexponentially in t, then the systemshows ”sensitive dependence oninitial conditions” which is alsocalled ”chaos”.Examples of dynamical systems areour solar system or the stars in agalaxy, electrons in a plasma or par-ticles in a fluid. The theoreticalstudy is intrinsically linked to linearalgebra because stability propertiesoften depends on linear approxima-tions.USE OF LINEAR ALGEBRA II Math 21b, O. KnillCODING, ERROR CORRECTIONCoding theory is used for encryp-tion or error correction. For encryp-tion, data x are maped by a mapT into code y=Tx. T usually is a”trapdoor function”: it is hard toget x back when y is known. In thesecond case, a code is a linear sub-space X of a vector space and T isa map describing the transmissionwith errors. The projection onto thesubspace X corrects the error.Linear algebra enters in differentways, often directly because the ob-jects are vectors but also indirectlylike for example in algorithms whichaim at cracking encryption schemes.DATA COMPRESSION Image-(i.e. JPG), video- (MPG4) andsound compression algorithms(i.e. MP3) make use of lineartransformations like the Fouriertransform. In all cases, the com-pression makes use of the fact thatin the Fourier space, informationcan be cut away without disturbingthe main information.Typically, a picture, a sound ora movie is cut into smaller junks.These parts are represented by vec-tors. If U denotes the Fourier trans-form and P is a cutoff function, theny = P Ux is transferred or stored ona CD or DVD. The receiver obtainsback UTy which is close to x in thesense that the human eye or ear doesnot notice a big difference.SOLVING SYSTEMS OR EQUA-TIONS When extremizing a func-tion f on data which satisfy a con-straint g(x) = 0, the method ofLagrange multipliers asks to solvea nonlinear system of equations∇f(x) = λ∇g(x), g(x) = 0 for the(n + 1) unknowns (x, l), where ∇fis the gradient of f.Solving systems of nonlinear equa-tions can be tricky. Already for sys-tems of polynomial equations, onehas to work with linear spaces ofpolynomials. Even if the Lagrangesystem is a linear system, the taskof solving it can be done more ef-ficiently using a solid foundation oflinear algebra.GAMES Moving around in a worlddescribed in a computer game re-quires rotations and translations tobe implemented efficiently. Hard-ware acceleration can help to handlethis.Rotations are represented by matri-ces which are called orthogonal.For example, if an object located at(0, 0, 0), turning around the y-axesby an angle φ, every point in the ob-ject gets transformed by the matrixcos(φ) 0 sin(φ)0 1 0− sin(φ) 0 cos(φ)CRYPTOLOGY. Much of currentcryptological security is based onthe difficulty to factor large integersn. One of the basic ideas going backto Fermat is to find integers x suchthat x2mod n is a small square
View Full Document
Unlocking...