Introduction to Linear Algebra
Gilbert Strang
This new fifth edition has become more than a textbook for the basic linear algebra course. That is its first purpose and always will be. The new chapters about applications of the SVD, probability and statistics, and Principal Component Analysis in finance and genetics, make it also a textbook for a second course, plus a resource at work. Linear algebra has become central in modern applied mathematics. This book supports the value of understanding linear algebra.
Introduction to Linear Algebra, Fifth Edition includes challenge problems to complement the review problems that have been highly praised in previous editions. The basic course is followed by eight applications: differential equations in engineering, graphs and networks, statistics, Fourier methods and the FFT, linear programming, computer graphics, cryptography, Principal Component Analysis, and singular values.
Audience: Thousands of teachers in colleges and universities and now high schools are using this book, which truly explains this crucial subject. This text is for readers everywhere, with support from the websites and video lectures. Every chapter begins with a summary for efficient review.
Contents: Chap. 1: Introduction to Vectors; Chap. 2: Solving Linear Equations; Chap. 3: Vector Spaces and Subspaces; Chap. 4: Orthogonality; Chap. 5: Determinants; Chap. 6: Eigenvalues and Eigenvectors; Chap. 7: Singular Value Decomposition; Chap. 8: Linear Transformations; Chap. 9: Complex Vectors and Matrices; Chap. 10: Applications; Chap. 11: Numerical Linear Algebra; Chap. 12: Linear Algebra in Probability and Statistics; Matrix Factorizations; Index; Six Great Theorems.
 Open in Browser
 Checking other formats...
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle
Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.
You may be interested in Powered by Rec2Me
Most frequently terms


INTRODUCTI N TO LINEAR ALGEBRA Fifth Edition GILBERT STRANG Massachusetts Institute of Technology WELLESLEY  CAMBRIDGE PRESS Box 812060 Wellesley MA 02482 Introduction to Linear Algebra, 5th Edition Copyright ©2016 by Gilbert Strang ISBN 9780980232776 All rights reserved. No part of this book may be reproduced or stored or transmitted by any means, including photocopying, without written permission from Wellesley  Cambridge Press. Translation in any language is strictly prohibited authorized translations are arranged by the publisher. BTEX typesetting by Ashley C. Fernandes (info@problemsolvingpathway.com) Printed in the United States of America 9876543 QA184.S78 2016 512'.5 9314092 Other texts from Wellesley  Cambridge Press Computational Science and Engineering, Gilbert Strang ISBN 9780961408817 Wavelets and Filter Banks, Gilbert Strang and Truong Nguyen ISBN 9780961408879 Introduction to Applied Mathematics, Gilbert Strang ISBN 9780961408800 Calculus Third Edition (2017), Gilbert Strang ISBN 9780980232752 Algorithms for Global Positioning, Kai Borre & Gilbert Strang ISBN 9780980232738 Essays in Linear Algebra, Gilbert Strang ISBN 9780980232769 Differential Equations and Linear Algebra, Gilbert Strang ISBN 9780980232790 An Analysis of the Finite Element Method, 2008 edition, Gilbert Strang and George Fix ISBN 9780980232707 Wellesley  Cambridge Press Box 812060 Wellesley MA 02482 USA www.wellesleycambridge.com linearalgebrabook@gmail.com math.mit.edu/�gs phone(781)4318488 fax(617)2534358 The website for this book is math.mit.edu/linearalgebra. The Solution Manual can be printed from that website. Course material including syllabus and exams and also videotaped lectures are available on the book website and the teaching website: web.mit.edu/18.06 Linear Algebra is included in MI T's OpenCourseWare site ocw.mit.edu. This provides video lectures of the full linear algebra course 18.06 and 18.06 SC. MATLAB® is a registered trademark of The Math; Works, Inc. The front cover captures a central idea of linear algebra. Ax = bis solvable when bis in the(red)column space of A. One particular solution y is in the(yellow)row space: Ay = b. Add any vector z from the(green)nullspace of A: Az = 0. The complete solution is x = y + z. Then Ax = Ay + Az = b. The cover design was the inspiration of Lois Sellers and Gail Corbett. Preface I am happy for you to see this Fifth Edition of Introduction to Linear Algebra. This is the text for my video lectures on MIT's OpenCourseWare (ocw.mit.edu and also YouTube). I hope those lectures will be useful to you (maybe even enjoyable!). Hundreds of coll�ges and universities have chosen this textbook for their basic linear algebra course. A sabbatical gave me a chance to prepare two new chapters about probability and statistics and understanding data. Thousands of other improvements too probably only noticed by the author. . . Here is a new addition for students and all readers: Every section opens with a brief summary to explain its contents. When you read a new section, and when you revisit a section to review and organize it in your mind, those lines are a quick guide and an aid to memory. Another big change comes on this book's website math.mit.edu/linearalgebra. That site now contains solutions to the Problem Sets in the book. With unlimited space, this is much more flexible than printing short solutions. There are three key websites : ocw.mit.edu Messages come from thousands of students and faculty about linear algebra on this OpenCourseWare site. The 18.06 and 18.06 SC courses include video lectures of a complete semester of classes. Those lectures offer an independent review of the whole subject based on this textbookthe professor's time stays free and the student's time can be 2 a.m. (The reader doesn't have to be in a class at all.) Six million viewers around the world have seen these videos (amazing). I hope you find them helpful. web.mit.edu/18.06 This site has homeworks and exams (with solutions) for the current course as it is taught, and as far back as 1996. There are also review questions, Java demos, Teaching Codes, and short essays (and the video lectures). My goal is to make this book as useful to you as possible, with all the course material we can provide. math.mit.edu/linearalgebra This has become an active website. It now has Solutions to Exerciseswith space to explain ideas. There are also new exercises from many dif ferent sourcespractice problems, development of textbook examples, codes in MATLAB and Julia and Python, plus whole collections of exams (18.06 and others) for review. Please visit this linear algebra site. Send suggestions to linearalgebrabook@gmail.com V vi Preface The Fifth Edition The cover shows the Four Fundamental Subspacesthe row space and nullspace are on the left side, the column space and the nullspace of A T are on the right. It is not usual to put the central ideas of the subject on display like this! When you meet those four spaces in Chapter 3, you will understand why that picture is so central to linear algebra. Those were named the Four Fundamental Subspaces in my first book, and they start from a matrix A. Each row of A is a vector in ndimensional space. When the matrix has m rows, each column is a vector in mdimensional space. The crucial operation in linear algebra is to take linear combinations of column vectors. This is exactly the result of a matrixvector multiplication. Ax is a combination of the columns of A. When we take all combinations Ax of the column vectors, we get the column space. If this space includes the vector b, we can solve the equation Ax = b. May I call special attention to Section 1.3, where these ideas come earlywith two specific examples. You are not expected to catch every detail of vector spaces in one day! But you will see the first matrices in the book, and a picture of their column spaces. There is even an inverse matrix and its connection to calculus. You will be learning the language of linear algebra in the best and most efficient way: by using it. Every section of the basic course ends with a large collection of review problems. They ask you to use the ideas in that sectionthe dimension of the column space, a basis for that space, the rank and inverse and determinant and eigenvalues of A. Many problems look for computations by hand on a small matrix, and they have been highly praised. The Challenge Problems go a step further, and sometimes deeper. Let me give four examples: Section 2.1: Which row exchanges of a Sudoku matrix produce another Sudoku matrix? Section 2.7: If Pis a permutation matrix, why is some power p k equal to I? Section 3.4: If Ax= band Cx = b have the same solutions for every b, does A equal C? Section 4.1: What conditions on the four vectors r, n, c, £ allow them to be bases for the row space, the nullspace, the column space, and the left nullspace of a 2 by 2 matrix? The Start of the Course The equation Ax = b uses the language of linear combinations right away. The vector Ax is a combination of the columns of A. The equation is asking for a combination that produces b. The solution vector x comes at three levels and all are important: 1. Direct solution to find x by forward elimination and back substitution. 2. Matrix solution using the inverse matrix: x = A 1 b (if A has an inverse). 3. Particular solution (to Ay = b) plus nullspace solution (to Az = 0). That vector space solution x = y + z is shown on the cover of the book. Preface vii Direct elimination is the most frequently used algorithm in scientific computing. The matrix A becomes triangularthen solutions come quickly. We also see bases for the four subspaces. But don't spend forever on practicing elimination . . . good ideas are coming. The speed of every new supercomputer is tested on Ax = b : pure linear algebra. But even a supercomputer doesn't want the inverse matrix: too slow. Inverses give the simplest formula x = Alb but not the top speed. And everyone must know that determinants are even slowerthere is no way a linear algebra course should begin with formulas for the determinant of an n by n matrix. Those formulas have a place, but not first place. Structure of the Textbook Already in this preface, you can see the style of the book and its goal. That goal is serious, to explain this beautiful and usefulpart of mathematics. You will see how the applications of linear algebra reinforce the key ideas. This book moves gradually and steadily from numbers to vectors to subspaceseach level comes naturally and everyone can get it. Here are 12 points about learning and teaching from this book : 1. Chapter 1 starts with vectors and dot products. If the class has met them before, focus quickly on linear combinations. Section 1.3 provides three independent vectors whose combinations fill all of 3dimensional space, and three dependent vectors in a plane. Those two examples are the beginning of linear algebra. 2. Chapter 2 shows the row picture and the column picture of Ax = b. The heart of linear algebra is in that connection between the rows of A and the columns of A : the same numbers but very different pictures. Then begins the algebra of matrices: an elimination matrix E multiplies A to produce a zero. The goal is to capture the whole processstart with A, multiply by E's, end with U. Elimination is seen in the beautiful form A = LU. The lower triangular L holds the forward elimination steps, and U is upper triangular for back substitution. 3. Chapter 3 is linear algebra at the best level: subspaces. The column space contains all linear combinations of the columns. The crucial question is: How many of those columns are needed? The answer tells us the dimension of the column space, and the key information about A. We reach the Fundamental Theorem of Linear Algebra. 4. With more equations than unknowns, it is almost sure that Ax = b has no solution. We cannot throw out every measurement that is close but not perfectly exact! When we solve by least squares, the key will be the matrix A T A. This wonderful matrix appears everywhere in applied mathematics, when A is rectangular. 5. Determinants give formulas for all that has come beforeCramer's Rule, inverse matrices, volumes inn dimensions. We don't need those formulas to com pute. They slow us down. But det A = 0 tells when a matrix is singular : this is the key to eigenvalues. vm Preface 6. Section 6 .1 explains eigenvalues for 2 by 2 matrices. Many courses want to see eigenvalues early. It is completely reasonable to come here directly from Chapter 3, because the determinant is easy for a 2 by 2 matrix. The key equation is Ax= >.x. Eigenvalues and eigenvectors are an astonishing way to understand a square matrix. They are not for Ax = b, they are for dynamic equations like du/ dt = Au. The idea is always the same: follow the eigenvectors. In those special directions, A acts like a single number (the eigenvalue>.) and the problem is onedimensional. An essential highlight of Chapter 6 is diagonalizing a symmetric matrix. When all the eigenvalues are positive, the matrix is "positive definite". This key idea connects the whole coursepositive pivots and determinants and eigenvalues and energy. I work hard to reach this point in the book and to explain it by examples. 7. Chapter 7 is new. It introduces singular values and singular vectors. They separate all martices into simple pieces, ranked in order of their importance. You will see one way to compress an image. Especially you can analyze a matrix full of data. 8. Chapter 8 explains linear transformations. This is geometry without axes, algebra with no coordinates. When we choose a basis, we reach the best possible matrix. 9. Chapter 9 moves from real numbers and vectors to complex vectors and matrices. The Fourier matrix F is the most important complex matrix we will ever see. And the Fast Fourier Transform (multiplying quickly by F and p 1) is revolutionary. 10. Chapter 10 is full of applications, more than any single course could need: 10.1 Graphs and Networksleading to the edgenode matrix for Kirchhoff's Laws 10.2 Matrices in Engineeringdifferential equations parallel to matrix equations 10.3 Markov Matricesas in Google's PageRank algorithm 10.4 Linear Programminga new requirement x 2'. 0 and minimization of the cost 10.5 Fourier Serieslinear algebra for functions and digital signal processing 10.6 Computer Graphicsmatrices move and rotate and compress images 10.7 Linear Algebra in C ryptographythis new section was fun to write. The Hill Cipher is not too secure. It uses modular arithmetic: integers from O to p  1. 5. Multiplication gives 4 x 5 1 (mod 19). For decoding this gives 4 1 = = 11. How should computing be included in a linear algebra course? It can open a new understanding of matricesevery class will find a balance. MATLAB and Maple and Mathematica are powerful in different ways. Julia and P ython are free and directly accessible on the Web. Those newer languages are powerful too ! Basic commands begin in Chapter 2. Then Chapter 11 moves toward professional al gorithms.You can upload and download codes for this course on the website. 12. Chapter 12 on Probability and Statistics is new, with truly important applications. When random variables are not independent we get covariance matrices. Fortunately they are symmetric positive definite. The linear algebra in Chapter 6 is needed now. ix Preface The Variety of Linear Algebra Calculus is mostly about one special operation (the derivative) and its inverse (the integral). Of course I admit that calculus could be important .... But so many applications of math ematics are discrete rather than continuous, digital rather than analog. The century of data has begun! You will find a lighthearted essay called "Too Much Calculus" on my website. The truth is that vectors and matrices have become the language to know. Part of that language is the wonderful variety of matrices. Let me give three examples: Orthogonal matrix Symmetric matrix 1 2 1 0 0 1 2 1 0  � ol 1 1 2 1 l � 1 1 1 1 1 1 1 1 Triangular matrix �1 l� � � �1 1 1 0 0 1 1 0 0 0 1 A key goal is learning to "read" a matrix. You need to see the meaning in the numbers. This is really the essence of mathematicspatterns and their meaning. I have used italics and boldface to pick out the key words on each page. I know there are times when you want to read quickly, looking for the important lines. May I end with this thought for professors. You might feel that the direction is right, and wonder if your students are ready. Just give them a chance! Literally thousands of students have written to me, frequently with suggestions and surprisingly often with thanks. They know this course has a purpose, because the professor and the book are on their side. Linear algebra is a fantastic subject, enjoy it. Help With This Book The greatest encouragement of all is the feeling that you are doing something worthwhile with your life. Hundreds of generous readers have sent ideas and examples and corrections (and favorite matrices) that appear in this book. Thank you all. One person has helped with every word in this book. He is Ashley C. Fernandes, who prepared the Jb.T]3X files. It is now six books that he has allowed me to write and rewrite, aiming for accuracy and also for life. Working with friends is a happy way to live. Friends inside and outside the MIT math department have been wonderful. Alan Edelman for Julia and much more, Alex Townsend for the flag examples in 7.1, and Peter Kempthorne for the finance example in 7.3: those stand out. Don Spickler's website on cryptography is simply excellent. I thank Jon Bloom, Jack Dongarra, Hilary Finucane, Pavel Grinfeld, Randy LeVeque, David Vogan, Liang Wang, and Karen Willcox. The "eigenfaces" in 7.3 came from Matthew Turk and Jeff Jauregui. And the big step to singular values was accelerated by Raj Rao's great course at Michigan. This book owes so much to my happy sabbatical in Oxford. Thank you, Nick Trefethen and everyone. Especially you the reader! Best wishes in your work. X Preface Background of the Author This is my 9th textbook on linear algebra, and I hesitate to write about myself. It is the mathematics that is important, and the reader. The next paragraphs add something brief and personal, as a way to say that textbooks are written by people. I was born in Chicago and went to school in Washington and Cincinnati and St. Louis. My college was MIT (and my linear algebra course was extremely abstract). After that came Oxford and UCLA, then back to MIT for a very long time. I don't know how many thousands of students have taken 18.06 (more than 6 million when you include the videos on ocw.mit.edu). The time for a fresh approach was right, because this fantastic subject was only revealed to math majorswe needed to open linear algebra to the world. I am so grateful for a life of teaching mathematics, more than I could possibly tell you. Gilbert Strang PS I hope the next book (2018 ?) will include Learning from Data. This subject is grow ing quickly, especially "deep learning". By knowing a function on a training set of old data, we approximate the function on new data. The approximation only uses one simple non linear function f(x) = max(0, x). It is n matrix multiplications that we optimize to make the learning deep: X1 = f(A1x + b1), X2 = f(A2x1 + b2), ..., Xn = f(An X n 1 + bn ) Those are n 1 hidden layers between the input x and the output Xn which approximates F(x) on the training set. THE MATRIX ALPHABET A B C D E F H I J K L M N Any Matrix Basis Matrix Cofactor Matrix p p Diagonal Matrix Elimination Matrix Q R R Fourier Matrix Hadamard Matrix T Identity Matrix Jordan Matrix Stiffness Matrix Lower Triangular Matrix Markov Matrix Nullspace Matrix s u u V X A :E Permutation Matrix Projection Matrix Orthogonal Matrix Upper Triangular Matrix Reduced Echelon Matrix Symmetric Matrix Linear Transformation Upper Triangular Matrix Left Singular Vectors Right Singular Vectors Eigenvector Matrix Eigenvalue Matrix Singular Value Matrix Chapter 1 Introduction to Vectors The heart of linear algebra is in two operationsboth with vectors. We add vectors to get v + w. We multiply them by numbers c and d to get cv and dw. Combining those two operations (adding cv to dw) gives the linear combination cv + dw. Linear combination Example v + w = [ � ] +[� ] [ !] is the combination with c = d = l Linear combinations are allimportant in this subject! Sometimes we want one partic ular combination, the specific choice c = 2 and d = l that produces cv + dw = ( 4, 5). Other times we want all the combinations of v and w (coming from all c and d). The vectors cv lie along a line. When w is not on that line, the combinations cv + dw fill the whole twodimensional plane. Starting from four vectors u, v, w, z in four dimensional space, their combinations cu + dv + ew + f z are likely to fill the space but not always. The vectors and their combinations could lie in a plane or on a line. Chapter 1 explains these central ideas, on which everything builds. We start with two dimensional vectors and threedimensional vectors, which are reasonable to draw. Then we move into higher dimensions. The really impressive feature of linear algebra is how smoothly it takes that step into ndimensional space. Your mental picture stays completely correct, even if drawing a tendimensional vector is impossible. This is where the book is going (into ndimensional space). The first steps are the operations in Sections 1.1 and 1.2. Then Section 1.3 outlines three fundamental ideas. 1.1 Vector addition v + w and linear combinations cv + dw. 1.2 The dot product v · w of two vectors and the length 11 v 11 = �1.3 Matrices A, linear equations Ax = b, solutions x = A  I b. 1 2 Chapter 1. Introduction to Vectors 1.1 Vectors and Linear Combinations 1 3v + 5wis a typical linear combination cv + dwof the vectors v and w. 2 For v = [ ] and w = [ � ] that combination is 3 � ] � [ 3 The vector [ � ] = [ � ] +[�] 4 The combinations c [ � ] +d [ 5 The comb;nations c [ +d [ +5 [�] = [ � ! �� ] = [ � ]. � goes across to x = 2 and up to y = 3 in the xy plane. � ] fill the whole xy plane. They produce every [ : ] . t] !] t l· [ ! ]· fill a plane ill xyz space. Same plandoc [ C + 2d = 1 6 But c+ 3d = 0 hasno solut;on because ;,s rights;de [ � ] ;, not onthat plane. c+4d = 0 "You can't add apples and oranges." In a strange way, this is the reason for vectors. We have two separate numbers v1 and v2. That pair produces a twodimensional vector v: v1 = first component of v v2 = second component of v Column vector v We write v as a column, not as a row. The main point so far is to have a single letter v (in boldface italic) for this pair of numbers v1 and v2 (in lightface italic). Even if we don't add v1 to v2 , we do add vectors. The first components of v and w stay separate from the second components: VECTOR ADDITION v = [ �� ] and w = [ :� ] add to v + w = [ V1 V2 + W1 + W2 ] Subtraction follows the same idea: The components of v  ware v1  w1 and v2  w2. The other basic operation is scalar multiplication. Vectors can be multiplied by 2 or by 1 or by any number c. To find 2v, multiply each component of v by 2: SCALAR MULTIPLICATION 2v 2v = [ 1 ] = V 2v2 +V V v = [  i ] v2 The components of cv are cv1 and cv2. The number c is called a "scalar". Notice that the sum of v and v is the zero vector. This is 0, which is not the same as the number zero! The vector O has components O and 0. Forgive me for hammering away at the difference between a vector and its components. Linear algebra is built on these operations v + w and cv and dwadding vectors and multiplying by scalars. 3 1.1. Vectors and Linear Combinations Linear Combinations Now we combine addition with scalar multiplication to produce a "linear combination" of v and w. Multiply v by c and multiply w by d. Then add cv + dw. The sum of cv and dw is a linear combination cv + dw. Four special linear combinations are: sum, difference, zero, and a scalar multiple cv: lv + lw lv lw 0v+0w cv+0w sum of vectors in Figure 1.1a difference of vectors in Figure 1.1b zero vector vector cv in the direction of v The zero vector is always a possible combination (its coefficients are zero). Every time we see a "space" of vectors, that zero vector will be included. This big view, taking all the combinations of v and w, is linear algebra at work. The figures show how you can visualize vectors. For algebra, we just need the com ponents (like 4 and 2). That vector v is represented by an arrow. The arrow goes v 1 = 4 units to the right and v2 = 2 units up. It ends at the point whose x, y coordinates are 4, 2. This point is another representation of the vectorso we have three ways to describe v: Represent vector v Two numbers Arrow from (0, 0) Point in the plane We add using the numbers. We visualize v + w using arrows: Vector addition (head to tail) At the end of v,place the start of w. � = [ �] V = [ �] ��[�] 4 Figure 1.1: Vector addition v + w = (3, 4) produces the diagonal of a parallelogram. The reverse of w is w. The linear combination on the right is v  w = (5, 0). We travel along v and then along w. Or we take the diagonal shortcut along v + w. We could also go along w and then v. In other words, w + v gives the same answer as v + w. These are different ways along the parallelogram (in this example it is a rectangle). 4 Chapter 1. Introduction to Vectors Vectors in Three Dimensions A vector with two components corresponds to a point in the xy plane. The components of v are the coordinates of the point: x = v1 and y = v2. The arrow ends at this point (v1,v2), when it starts from (0,0). Now we allow vectors to have three components (v1,v2,v3). The xy plane is replaced by threedimensional xyz space. Here are typical vectors (still column vectors but with three components): ·� Ul and w� m and v+w� m. The vector v corresponds to an arrow in 3space. Usually the arrow starts at the "origin", where the xyz axes meet and the coordinates are (0,0,0). The arrow ends at the point with coordinates v 1, v 2, v3• There is a perfect match between the column vector and the arrow from the origin and the point where the arrow ends. The vector ( x, y) in the plane is different from ( x, y, 0) in 3space ! z y 2 HJ (3,2) X 3 X rn Figu,e 1.2, Vectorn [;] and [;] correspond to points ( x, y) and ( x, y, z). From now on j] v� [ is also written a, v � (1, 1, 1). The reason for the row form (in parentheses) is to save space. But v = (l, 1, 1) is not a row vector! It is in actuality a column vector, just temporarily lying down. The row vector [ 1 1 1] is absolutely different, even though it has the same three components. That 1 by 3 row vector is the "transpose" of the 3 by 1 column vector v. 5 1. 1. Vectors and Linear Combinations In three dimensions, v + w is still found a component at a time. The sum has components V1 + w1 and v2 + w2 and V3 + W3. You see how to add vectors in 4 or 5 or n dimensions. When w starts at the end of v, the third side is v + w. The other way around the parallelogram is w + v. Question: Do the four sides all lie in the same plane? Yes. And the sum v + w  v  w goes completely around to produce the __ vector. A typical linear combination of three vectors in three dimensions is u + 4v  2w: Linear combination Multiply by 1, 4, :2 Then add The Important Questions For one vector u, the only linear combinations are the multiples cu. For two vectors, the combinations are cu+ dv. For three vectors, the combinations are cu + dv + ew. Will you take the big step from one combination to all combinations? Every c and d and e are allowed. Suppose the vectors u, v, w are in threedimensional space: 1. What is the picture of all combinations cu? 2. What is the picture of all combinations cu + dv? 3. What is the picture of all combinations cu+ dv + ew? The answers ·depend on the particular vectors u, v, and w. If they were zero vectors (a very extreme case), then every combination would be zero. If they are typical nonzero vectors (components chosen at random), here are the three answers. This is the key to our subject: 1. The combinations cu fill a line through (0, 0, 0). 2. The combinations cu+ dv fill a plane through (0, 0, 0). 3. The combinations cu+ dv + ew fill threedimensional space. The zero vector (0, 0, 0) is on the line because c can be zero. It is on the plane because c and d could both be zero. The line of vectors cu is infinitely long (forward and backward). It is the plane of all cu + dv (combining two vectors in threedimensional space) that I especially ask you to think about. Adding all cu on one line to all dv on the other line fills in the plane in Figure 1.3. When we include a third vector w, the multiples ew give a third line. Suppose that third line is not in the plane of u and v. Then combining all ew with all cu+ dv fills up the whole threedimensional space. This is the typical situation! Line, then plane, then space. But other possibilities exist. When w happens to be cu + dv, that third vector w is in the plane of the first two. The combinations of u, v, w will not go outside that uv plane. We do not get the full threedimensional space. Please think about the special cases in Problem 1. 6 Chapter 1. Introduction to Vectors Plane from allcu+dv Line containing allcu (a) (b) Figure 1.3: (a) Line through u. (b) The plane containing the lines through u and v. • REVIEW OF THE KEY IDEAS • 1. A vector v in twodimensional space has two components v 1 and v2. 2. v + w = ( v1 + w1, v2 + w2) and cv = ( cv1, cv2) are found a component at a time. 3. A linear combination of three vectors u and v and w is cu+ dv + ew. 4. Take all linear combinations of u, or u and v, or u, v, w. In three dimensions, those combinations typically fill a line, then a plane, then the whole space R3 . • WORKED EXAMPLES • 1.1 A The linear combinations of v = (l,1,0) and w = (0,1,1) fill a plane in R3 . Describe that plane. Find a vector that is not a combination of v and wnot on the plane. Solution The plane of v and w contains all combinations cv + dw. The vectors in that plane allow any c and d. The plane of Figure 1.3 fills in between the two lines. Combffiations cv + dw  e [ i] +d [ : ]  [ +] fill a pfane. Four vectors in that plane are (0,0,0) and (2,3,1) and (5,7,2) and (7r,27r,7r). The second component c + d is always the sum of the first and third components. Like most vectors, (1,2,3) is not in the plane, because 2 =/ 1 + 3. Another description of this plane through (0,0,0) is to know that n = (1, 1,1) is perpendicular to the plane. Section 1.2 will confirm that 90 ° angle by testing dot products: v · n = 0 and w · n = 0. Perpendicular vectors have zero dot products. 7 1.1. Vectors and Linear Combinations 1.1 B For v = (l, 0) and w = (0, 1), describe all points cv with (1) whole numbers c (2) nonnegative numbers c 2: 0. Then add all vectors dw and describe all cv + dw. Solution (1) The vectors cv = (c, 0) with whole numbers c are equally spaced points along the x axis (the direction of v). They include (2, 0), ( 1, 0), (0, 0), (1, 0), (2, 0). (2) The vectors cv with c 2: 0 fill a halfline. It is the positive x axis. This halfline starts at (0, 0) where c = 0. It includes (100, 0) and (1r, 0) but not (100, 0). (1') Adding all vectors dw = (0, d) puts a vertical line through those equally spaced cv. We have infinitely many parallel lines from (whole number c, any number d). (2') Adding all vectors dw puts a vertical line through every cv on the halfline. Now we have a halfplane. The right half of the xy plane has any x 2'. 0 and any y. 1.1 C Find two equations for c and d so that the linear combination cv + dw equals b: b=[�]Solution In applying mathematics, many problems have two parts: 1 Modeling part Express the problem by a set of equations. 2 Computational part Solve those equations by a fast and accurate algorithm. Here we are only asked for the first part (the equations). Chapter 2 is devoted to the second part (the solution). Our example fits into a fundamental model for linear algebra: Find n numbers C1, ... , Cn so that C1 V1 + · · · + Cn Vn = b. For n = 2 we will find a formula for the e's. The "elimination method" in Chapter 2 succeeds far beyond n = 1000. For n greater than 1 billion, see Chapter 11. Here n = 2: Vector equation +dw = b CV The required equations for c and d just come from the two components separately: Two ordinary equations 2c  d = l c+ 2d = 0 Each equation produces a line. The two lines cross at the solution c = see this also as a matrix equation, since that is where we are going : 2 by 2 matrix 2 1 3, d = 3. Why not 8 Chapter 1. Introduction to Vectors Problem Set 1.1 Problems 19 are about addition of vectors and linear combinations. 1 Describe geometrically (line,plane,or all of R3) all linear combinations of 2 Draw v=[ 3 If v+ w =[ �] and v  w =[!],compute and draw the vectors v and w. 4 From v =[ � ] and w =[;],find the components of 3v+wand cv+ dw. 5 Compute u+ v+wand 2u+ 2v+ w. How do you know u, v, w lie in a plane? 1] and w= [ �] and v+w and vw in a single xy plane. These lie in a plane because w = cu + dv. Find c and d 6 Every combination of v = ( 1 ,  2 , 1 ) and w = (0, 1 ,  1 ) has components that add to __ . Find c and d so that cv+ dw = (3, 3, 6). Why is (3, 3, 6) impossible? 7 In the xy plane mark all nine of these linear combinations: c[�]+d[�] with c=0, 1 , 2 and d=0, 1 , 2 . 8 The parallelogram in Figure 1.1 has diagonal v+ w. What is its other diagonal? What is the sum of the two diagonals? Draw that vector sum. 9 If three corners of a parallelogram are (1, 1), (4, 2 ),and (1, 3),what are all three of the possible fourth corners? Draw two of them. Problems 1014 are about special vectors on cubes and clocks in Figure 1.4. 10 Which point of the cube is i+ j? Which point is the vector sum of i = (1, 0, 0) and j = (0, 1 , 0) and k = (0, 0, 1)? Describe all points (x, y, z) in the cube. 11 Four corners of this unit cube are (0, 0, 0), ( 1 , 0, 0), (0, 1, 0), (0, 0, 1). What are the other four corners? Find the coordinates of the center point of the cube. The center points of the six faces are __ . The cube has how many edges? 12 Review Question. In xyz space, where is the plane of all linear combinations of i = ( 1 , 0, 0) and i + j = ( 1 , 1 , 0)? 9 1.1. Vectors and Linear Combinations k � = (0, 0, 1)  .. j+k � / I  po,}j = (0, 1, 0) I/ i = (1,0,0) Notice the illusion Is (0, 0, 0) a top or a bottom comer? Figure 1.4: Unit cube from i,j, k and twelve clock vectors. 13 (a) What is the sum V of the twelve vectors that go from the center of a clock to the hours 1:00, 2:00, ..., 12:00? (b) If the 2:00 vector is removed, why do the 11 remaining vectors add to 8:00? (c) What are the x, y components of that 2:00 vector v = ( cos 0, sin 0)? 14 Suppose the twelve vectors start from 6:00 at the bottom instead of (0, 0) at the center. The vector to 12:00 is doubled to (0, 2). The new twelve vectors add to __ . Problems 1519 go further with linear combinations of v and w (Figure 1.Sa). 15 Figure I.Sa shows½ v +½ w. Mark the points¾ v +¼wand ¼ v +¼wand v + w. 16 Mark the point �v + 2w and any other combination cv + dw with c + d = l. Draw the line of all combinations that have c + d = l. 17 Locate½ v +½wand� v +� w. The combinations cv + cw fill out what line? 18 Restricted by O 19 Restricted only by c :::0: 0 and d 2 0 draw the "cone" of all combinations cv + dw. s cs 1 and O S d s 1, shade in all combinations cv + dw. w u w V V (a) Figure 1.5: Problems 1519 in a plane (b) Problems 2025 in 3dimensional space 10 Chapter l. Introduction to Vectors Problems 2025 deal with u, v, win threedimensional space {see Figure L5b). 20 Locate ½ u + ½ v + ½ w and ½ u + ½ w in Figure 1.5b. Challenge problem: Under what restrictions on c, d, e, will the combinations cu + dv + ew fill in the dashed triangle? To stay in the triangle, one requirement is c :2: 0, d :2'. 0, e :2: 0. 21 The three sides of the dashed triangle are v  u and w  v and u  w. Their sum is __ . Draw the headtotail addition around a plane triangle of (3, 1) plus (1, 1) plus (2, 2). 22 Shade in the pyramid of combinations cu + dv + ew with c :2: 0, d :2'. 0, e :2: 0 and c + d + e :::; 1. Mark the vector ½ ( u + v + w) as inside or outside this pyramid. 23 If you look at all combinations of those u, v, and w, is there any vector that can't be produced from cu+ dv + ew? Different answer if u, v, ware all in __ . 24 Which vectors are combinations of u and v, and also combinations of v and w? 25 Draw vectors u, v, w so that their combinations cu + dv + ew fill only a line. Find vectors u, v, w so that their combinations cu+ dv + ew fill only a plane. 26 What combination c [ �] +d [ !] 1 produces [ :] ? Express this question as two equations for the coefficients c and d in the linear combination. Challenge Problems 27 How many corners does a cube have in 4 dimensions? How many 3D faces? How many edges? A typical corner is (0, 0, 1, 0). A typical edge goes to (0, 1, 0, 0). 28 Find vectors v and w so that v + w = (4, 5, 6) and v  w = (2, 5, 8). This is a question with __ unknown numbers, and an equal number of equations to find those numbers. 29 Find two different combinations of the three vectors u = (1, 3) and v = (2, 7) and w = (1, 5) that produce b = (0, 1). Slightly delicate question: If I take any three vectors u, v, w in the plane, will there always be two different combinations that produce b = (0, 1)? 30 The linear combinations of v = ( a, b) and w = ( c, d) fill the plane unless __ . Find four vectors u, v, w, z with four components each so that their combinations cu+ dv + ew + f z produce all vectors (b 1, b2, b3, b4) in fourdimensional space. 31 Write down three equations for c, d, e so that cu+ dv + ew = b. Can you somehow find c, d, e for this b ? w [n 11 1.2. Lengths and Dot Products 1.2 Lengths and Dot Products 1 The"dot product"ofv= [ �] andw= [:] isv·w=(1)(4) +(2)(5)= 4+ 10=14. 2 v= [ !] 2 and w= [ ! ] 4 3 The length squa,ed of v � [ 4 Then u= = = � vl4 V V are perpendicular because v· w is zero: (1)(4) +(3)(4) +(2)(4)= 0. !] is v, v � 1 + 9 + 4 � 14. The length is 11•11 [1l 1 v14 � has length I Jul = I 1. Check 5 The angle0 betweenv andw hascos0= V •W llvll llwll 6 The angle between [ � ] and [ � ] hascos0= (1) 7 All angles have I cos0I :::; 1. So all vectors have I 1 14 + 9 14 + � v'u. = 1. 14 4 . tv'2) . That angle is0= 45 °. v· I !I I wl :::; I v Iw J l 1I The first section backed off from multiplying vectors. Now we go forward to define the "dot product" ofv and w. This multiplication involves the separate products vt w 1 and v2w 2, but it doesn't stop there. Those two numbers are added to produce one number v· w. This is the geometry section (lengths of vectors and cosines of angles between them). Thedotproductorinnerproductofv= (v1,v2) andw= (w1,w2) is the numbervw : (1) Example 1 The vectors v=(4, 2) andw=( 1, 2) have a zero dot product: Dot product is zero Perpendicular vectors In mathematics, zero is always a special number. For dot products, it means that these two vectors are perpendicular. The angle between them is 90° . When we drew them in Figure 1. 1, we saw a rectangle (not just any parallelogram). The clearest example of perpendicular vectors is i=(1, 0) along the x axis and j=(0, 1) up they axis. Again the dot product is i· j= 0+ 0= 0. Those vectors i and j form a right angle. 12 Chapter 1. Introduction to Vectors The dot product of v = (1, 2) and w = (3,1) is 5. Soon v · w will reveal the angle between v and w (not go 0 ). Please check that w ·vis also 5. The dot product w · v equals v · w. The order of v and w makes no difference. Example 2 Put a weight of 4 at the point x = 1 (left of zero) and a weight of 2 at the point x = 2 (right of zero). The x axis will balance on the center point (like a seesaw). The weights balance because the dot product is (4) (1) + ( 2) ( 2) = 0. This example is typical of engineering and science. The vector of weights is (w 1, w2) = (4, 2). The vector of distances from the center is ( v 1, v 2) = (1, 2). The weights times the distances, w 1 v 1 and w2 v2, give the "moments". The equation for the seesaw to balance is W1V1 + W2V2 = 0. Example 3 Dot products enter in economics and business. We have three goods to buy and sell. Their prices are (p 1, P2,p3) for each unitthis is the "price vector" p. The quantities we buy or sell are (q1,q2,q3)positive when we sell, negative when we buy. Selling q1 units at the price p1 brings in q1p1. The total income (quantities q times prices p) is the dot product q ·pin three dimensions: Income = (qi,q2,q3) · (p1,P2,p3) = q1p1 + q2p2 + q3p3 = dot product. A zero dot product means that "the books balance". Total sales equal total purchases if q · p = 0. Then p is perpendicular to q (in threedimensional space). A supermarket with thousands of goods goes quickly into high dimensions. Small note: Spreadsheets have become essential in management. They compute linear combinations and dot products. What you see on the screen is a matrix. Main point For v · w, multiply each Vi times Wi. Then v · w = v 1w 1 + · · · + VnWn. Lengths and Unit Vectors An important case is the dot product of a vector with itself. In this case v equals w. When the vector is v = (1, 2,3), the dot product with itself is v · v = llvll 2 = 14: Dot product v · v Length squared Instead of a go o angle between vectors we have 0 ° . The answer is not zero because v is not perpendicular to itself. The dot product v · v gives the length ofv squared. DEFINITION The length llvll of a vector vis the square root of v · v: length = llvll =�= (vf + v� + ... + v;) 1 12 . 13 1.2. Lengths and Dot Products In two dimensions the length is v'vf + V§. In three dimensions it is v'vf + V§ + v�. By the calculation above, the length of v = (1, 2, 3) is llvll = /14. Here llvll = � is just the ordinary length of the arrow that represents the vector. If the components are 1 and 2, the arrow is the third side of a right triangle (Figure 1.6 ). The Pythagoras formula a 2 + b 2 = c2 connects the three sides: 12 + 22 = llvll 2 . For the length of v = (1, 2, 3) , we used the right triangle formula twice. The vector This base vector is perpendicular to (0, 0, 3) that goes (1, 2, 0) in the base has length straight up. So the diagonal of the box has length llvll = v5+9 = /14. The length of a fourdimensional vector would be v'vf + V§ + v� + v�. Thus the vec tor (1, 1, 1, 1) has length )12 + 12 + 12 + 12 = 2. This is the diagonal through a unit cube in fourdimensional space. That diagonal in n dimensions has length fa. v'5. (0,0, 3) I      ""1 / (1,2) (0,2) 2 ( V•V 14 vf +vi+v� 12 + 22 12 + 22 + 32  " I (1,2, 3) has length .JT4 I I I I I I I I (0,2,0) :('1,2,0)has length ,Js (1,0) (1,0,0) Figure 1.6: The length VV:V of twodimensional and threedimensional vectors. The word "unit" is always indicating that some measurement equals "one". The unit price is the price for one item. A unit cube has sides of length one. A unit circle is a circle with radius one. Now we see the meaning of a "unit vector". DEFINITION A unit vector u is a vector whose length equals one. Then u · u = 1. An example in four dimensions is u = ( ½, ½, ½, ½) . Then u · u is ¾ + ¾ We divided v = (1, 1, 1, 1) by its length llvll = 2 to get this unit vector. +¾+ ¾ = 1. Example 4 The standard unit vectors along the x and y axes are written i and j. In the xy plane, the unit vector that makes an angle "theta" with the x axis is (cos 0, sin 0): Unit vectors i = [�] and j = [�] and u = [ ��:!] . When 0 = 0, the horizontal vector u is i. When 0 = 90° (or � radians), the vertical vector is j. At any angle, the components cos 0 and sin 0 produce u · u = 1 because 14 Chapter 1. Introduction to Vectors cos2 0 + sin 2 0 = 1. These vectors reach out to the unit circle in Figure 1.7. Thus cos 0 and sin 0 are simply the coordinates of that point at angle 0 on the unit circle. Since (2, 2, 1) has length 3, the vector ( ½) has length l. Check that u · u ½ + ½ + ½ = l. For a unit vector, divide any nonzero vector v by its length llvll l, i, Unit vector u = v I 11 v 11 j =(0,1) is a unit vector in the same direction as v. v=(l,1) j 1 , 1 )= ../2 ../2 i =(l,O) u= ( i c s0 u= [ � ] sm 0 V M cos 0 Unit vectors i Unit circle j Figure 1.7: The coordinate vectors i and j. The unit vector u at angle 45 ° (left) divides v = (1, 1) by its length llvll = \/'2. The unit vector u = (cos 0, sin 0) is at angle 0. The Angle Between Two Vectors We stated that perpendicular vectors have v · w = 0. The dot product is zero when the angle is go 0 • To explain this, we have to connect angles to dot products. Then we show how v · w finds the angle between any two nonzero vector s v and w. Right angles The dot product is v · w = 0 when v is perpendicular to w. Proof When v and w are perpendicular, they form two sides of a right triangle. The third side is v  w (the hypotenuse going across in Figure 1.8). The Pythagoras Law for the sides of a right triangle is a 2 + b 2 = c2 : 2 2 2 llvll + llwll = llv  wll Writing out the formulas for those lengths in two dimensions, this equation is Perpendicular vectors Pythagoras (2) (3)  The right side begins with vf 2v1 w1 + wf. Then vf and wf are on both sides of the equa tion and they cancel, leaving 2v1w1. Also v� and w� cancel, leaving 2v2w2. (In three dimensions there would be 2v3w3.) Now divide by 2 to see v  w = 0: 0 = 2v1w1  2v2w2 which leads to V1W1 + V2W2 = 0. (4) Conclusion Right angles produce v · w = 0. The dot product is zero when the angle is 0 = go 0 • Then cos 0 = 0. The zero vector v = 0 is perpendicular to every vector w because O · w is always zero. 15 1.2. Lengths and Dot Products Now suppose v · w is not zero. It may be positive, it may be negative. The sign of v · w immediately tells whether we are below or above a right angle. The angle is less than go 0 when v · w is positive. The angle is above go 0 when v · w is negative. The right side of Figure 1.8 shows a typical vector v = (3, 1). The angle with w = (1,3) is less than go o because v · w = 6 is positive. V •W �v · w =0 > 0 V ....   angle with v in this halfplane greater than 90 ° in this halfplane Figure 1.8: Perpendicular vectors have v · w = 0. Then llvll 2 + llwll 2 = llv  wll 2 . The borderline is where vectors are perpendicular to v. On that dividing line between plus and minus, (1, 3) is perpendicular to (3,1). The dot product is zero. The dot product reveals the exact angle 0. For unit vectors u and U, the sign of u · U tells whether 0 < go 0 or 0 > go 0 • More than that, the dot product u · U is the cosine of 0. This remains true in n dimensions. Unit vectors u and U at angle 0 have u · U = cos 0. Certainly lu · UI ::::; 1. Remember that cos 0 is never greater than 1. It is never less than 1. The dot product of unit vectors is between 1 and 1. The cosine of 0 is revealed by u · U. Figure 1.9 shows this clearly when the vectors are u = (cos0,sin0) and i = (1,0). The dot product is u · i = cos0. That is the cosine of the angle between them. After rotation through any angle a, these are still unit vectors. The vector i = (1,0) rotates to (cos a,sin a). The vector u rotates to (cos /3,sin /3) with /3 = a + 0. Their dot product is cos a cos /3 + sin a sin /3. From trigonometry this is cos(/3  a) = cos 0. u = c� s [ 0] [c� s /3 ] =u smf3 sm0 (.�/ �l�CI, 0={3a COSCJ, _ ] U sina  [ Figure 1.9: Unit vectors: u · U is the cosine of 0 (the angle between). 16 Chapter 1. Introduction to Vectors What if vand ware not unit vectors? Divide by their lengths to get u = v/llvll and U = w/llwll Then the dot product of those unit vectors u and U gives cos 0. COSINE FORMULA V •W If v and w are nonzero vectors then  =cos0. llvll llwll (5) Whatever the angle, this dot product of v/llvll with w/llwll never exceeds one. That is the "Schwarz inequality" Iv· wl ::::; llvll llwll for dot productsor more correctly the CauchySchwarzBuniakowsky inequality. It was found in France and Germany and Russia (and maybe elsewhereit is the most important inequality in mathematics). Since I cosBJ never exceeds 1, the cosine formula gives two great inequalities: s:; llvll llwll SCHWARZ INEQUALITY lv·wl TRIANGLE INEQUALITY llv + wll ::::; llvll + llwll Example 5 Find cos 0 for v = [ � ] and w = [ � ] and check both inequalities. Solution The dot product is v · w = 4. Both v and w have length )5. The cosine is 4 /5. cosB = V •W Jjvjj Jjwjj 4 )5)5 4 5 By the Schwarz inequality, v · w = 4 is less than jjvjj llwll = 5. By the triangle inequality, side 3 = jjv + wjj is less than side 1 + side 2. For v + w = (3, 3) the three sides are yl8 < + )5. Square this triangle inequality to get 18 < 20. v5 Example 6 The dot product of v = (a, b) and w = (b, a) is 2ab. Both lengths are I !vi 11lwl I says that 2ab s:; a 2 + b 2 . This is more famous if we write x = a 2 and y = b 2 . The "geometric mean" vxfi is not larger than the "arithmetic mean" = average ½ ( x + y). v'a 2 + b 2 . The Schwarz inequality v · w s:; Geometric mean ::::; Arithmetic mean ab a2 + b2 s:; 2 becomes x+y FY s:;  . 2 Example 5 had a = 2 and b = 1. So x = 4 and y = 1. The geometric mean ,.jxfj = 2 is below the arithmetic mean ½ (1 + 4) = 2.5. Notes on Computing MATLAB, Python and Julia work directly with whole vectors, not their components. When v and w have been defined, v + w is immediately understood. Input v and w as rowsthe prime ' transposes them to columns. 2v + 3w becomes 2 * v + 3 * w. The result will be printed unless the line ends in a semicolon. 17 1.2. Lengths and Dot Products MATLAB v= [2 3 4]' ; w = [1 1 1]' ; u= 2 * v + 3 * w The dot product v· w is a row vector times a column vector (use * instead of·) : Instead of [;] · [ �] we more often see [ 1 2 ] [ �] or v1 *w The length of v is known to MATLAB as norm (v). This is sqrt (v' * v). Then find the cosine from the dot product v 1 * w and the angle (in radians) that has that cosine: cosine= v' * w/(norm (v) * norm (w)) angle = acos (cosine) Cosine formula The arc cosine An Mfile would create a new function cosine (v, w). Python and Julia are open source. • REVIEW OF THE KEY IDEAS • 1. The dot product v • w multiplies each component Vi by wi and adds all viwi. 2. The length 11 v 11 is the square root of v· v. Then u = v/11 v 11 is a unit vector : length 1. 3. The dot product is v· w = 0 when vectors v and w are perpendicular. 4. The cosine of 0 (the angle between any nonzero v and w) never exceeds I: Cosine cosB = V •W llvll llwll Schwarz inequality • WORKED EXAMPLES Iv· wl::; llvll llwll • 1.2 A For the vectors v = (3, 4) and w = (4, 3) test the Schwarz inequality on v · w and the triangle inequality on llv + wll Find cos0 for the angle between v and w. Which v and w give equality Iv· wl=llvll llwll and llv + wll=llvll + llwll? The dot product is v · w = (3)(4) + (4)(3) = 24. The length of v is = llvll v9 + 16 = 5 and also llwll = 5. The sum v + w= (7, 7) has length 7v12 < 10. Solution Triangle inequality ::; llvll llwll is llv + wll::; llvll + llwll Cosine of angle cos 0 = �: Schwarz inequality Iv· wl 24 < 25. is 7v12 < 5 + 5. Thin angle from v = (3, 4) tow = (4, 3) Equality: One vector is a multiple of the other as in w = cv. Then the angle is 0 ° or 180 ° . In this case I cos01 = 1 and Iv· wl equals llvll llwll If the angle is 0° , as in w = 2v, then llv + wll=llvll + llwll (both sides give 3llvll ). This v, 2v, 3v triangle is flat! 18 Chapter 1. Introduction to Vectors 1.2 B Find a unit vector u in the direction of v = (3, 4). Find a unit vector U that is perpendicular to u. How many possibilities for U? For a unit vector u, divide v by its length llvll = 5. For a perpendicular vector V we can choose (4, 3) since the dot product v ·Vis (3)(4) + (4)(3) = 0. For a unit vector perpendicular to u, divide V by its length IIVII: Solution u = 3 4) M = (5'5 V uU=O The only other perpendicular unit vector would be U t, = ( ¾). 1.2 C Find a vector x = (c, d) that has dot products x · r = 1 and x · s = 0 with two given vectors r = (2, 1) ands = (1, 2). Solution Those two dot products give linear equations for c and d. Then x X • T X • S =l =0 is is 2c  d = l  c+ 2d = 0 = (c, d). The same equations as in Worked Example 1.1 C = (x1, ..., Xn) inndimensional space Section 1.1 would start with columns vj · The goal is to produce x 1 v1 + · · · + XnVn = b. This section would start from rows ri . Now the goal is to find x with x ·T i = bi . Comment onn equations for x Soon the v's will be the columns of a matrix A, and the r's will be the rows of A. Then the (one and only) problem will be to solve Ax = b. Problem Set 1.2 1 Calculate the dot products u ·v and u ·w and u · (v + w) and w ·v: V = [ !] w = [;]. 2 Compute the lengths llull and llvll and llwll of those vectors. Check the Schwarz inequalities lu·vi::::; llull llvll and Iv·wl ::::; llvll llwll. 3 Find unit vectors in the directions of v and w in Problem 1, and the cosine of the angle 0. Choose vectors a, b, c that make 0 ° , 90 ° , and 180 ° angles with w. 4 For any unit vectors v and w, find the dot products (actual numbers) of (a) v and v 5 (b) v + w and v  w (c) v  2w and v + 2w Find unit vectors u1 and u2 in the directions of v = (l, 3) and w Find unit vectors U 1 and U 2 that are perpendicular to u1 and u2. = (2, 1, 2). 19 l .2. Lengths and Dot Products 6 (a ) Describe every vector w = ( w 1, w 2) that is perpendicular to v = ( 2, 1). (b) All vectors perpendicular to V = (1, 1, 1) lie on a __ in 3 dimensions. (c) The vectors perpendicular to both (1, 1, 1) and (1, 2, 3) lie on a _ 7 Find the angle 0 (from its cosine) between these pairs of vectors: (a) (c) 8 _. V V = = [�] [�] and w= and w = [�] [�] (b) (d) [j] V V = [�] and w � and w = True or false (give a reason if true or find a counterexample if false): Hl [=� l (a) If u = (1, 1, 1) is perpendicular to v and w, then vis parallel tow. (b) If u is perpendicular to v and w, then u is perpendicular to v + 2w. (c) If u and v are perpendicular unit vectors then llu  v/1 = ,v2. Yes! 9 The slopes of the arrows from (0, 0) to (v 1, v2 and (w 1, w 2 are v 2 /v 1 and w 2 /w 1. ) ) is 1. Show that v · w = 0 and Suppose the product v2w 2 / v 1w 1 of those slopes the vectors are perpendicular.(The line y = 4x is perpendicular to y = x.) ¼ 10 Draw arrows from (0, 0) to the points v = (1, 2) and w = (2, 1). Multiply their slopes.That answer is a signal that v · w = 0 and the arrows are __ . 11 If v · w is negative, what does this say about the angle between v and w? Draw a 3dimensional vector v (an arrow), and show where to find all w's with v · w < 0. 12 With v = (1, 1) and w = (1, 5) choose a number c so that w  cv is perpendicular to v. Then find the formula for c starting from any nonzero v and w. 13 Find nonzero vectors v and w that are perpendicular to (1, 0, 1) and to each other. 14 Find nonzero vectors u, v, w that are perpendicular to (1, 1, 1, 1) and to each other. 15 The geometric mean of x = 2 and y = 8 is vX'fJ = 4.The arithmetic mean is larger: ½ ( x + y) = __ .This would come in Example 6 from the Schwarz inequality for v = ( J2, VS) and w = ( VS, J2).Find cos0 for this v and w. 16 How long is the vector v = (1, 1, ..., 1) in 9 dimensions? Find a unit vector u in the same direction as v and a unit vector w that is perpendicular to v. 17 What are the cosines of the angles a, f3, 0 between the vector ( 1, 0, 1) and the unit vectors i, j, k along the axes? Check the formula cos2 a + cos 2 f3 + cos 2 0 = 1. 20 Chapter 1. Introduction to Vectors Problems 1828 lead to the main facts about lengths and angles in triangles. 18 The parallelogram with sides v = ( 4, 2) and w = ( 1, 2) is a rectangle. Check the Pythagoras formula a 2 + b 2 = c2 which is for right triangles only: (length of v )2 19 + (length of w) 2 = (length of v + w) 2 . (Rules for dot products) These equations are simple but useful: = W • V (2) U • (V + W) = U • V + U • W (3) (CV) • W = c(V • W) Use (2) with u = v + w to prove llv + wll 2 = v · v + 2v · w + w · w. (1) V • 20 W The "Law of Cosines" comes from (v  w) · (v  w) = v · v  2v · w + w · Cosine Law 2 2 llv  wll = llvll  2 llvll llwll cos0 w: + llwll 2 Draw a triangle with sides v and w and v  w. Which of the angles is 0 ? 21 The triangle inequality says: (length of v + w) :::; (length of v) + (length of w). Problem 19 found llv + wll 2 = llvll 2 + 2v · w + llwll 2 . Increase that v · w to llvll llwll to show that II side 311 can not exceed II side 111 + II side 211: Triangle inequality 2 llv + wll :::; (llvll + llwll) 2 or llv + wll :::; llvll + llwll w = (w1, w2) v 22 = (v1, Vz) The Schwarz inequality Iv · wl :::; llvll llwll by algebra instead of trigonometry: (a) Multiply out both sides of (V1 W1 + V2 W2) 2 :::; (Vi+ V§) (Wi + W§). (b) Show that the difference between those two sides equals (v1w2  v2w1) 2 . This cannot be negative since it is a squareso the inequality is true. 23 The figure shows that cosa = vi/llvll and sina = v2 /llvll Similarly cos/3 is __ and sin /3 is __ . The angle 0 is /3  a. Substitute into the trigonometry formula cos/3 cos a+ sin/3 sin a for cos(/3 a) to find cos 0 = v · w/llvll llwll 21 1.2. Lengths and Dot Products 24 Oneline proofofthe inequality lu · UI$ 1 for unit vectors (u1, u2) and ( U1, U2) : u21+ u21 u22+ u22 =l . + lu·U l $lu1IIU1l+lu2IIU2I$ 2 2 Put (u1,u2) = ( .6, .8) and (U1, U2) = ( .8, .6) in that whole line and find cos 0 . 25 Why is I cos 01 never greater than 1 in the first place? 26 (Recommended) Draw a parallelogram 27 Parallelogram with two sides v and w. Show that the squared diagonal lengths llv+ wll 2 + //v add to the sum of four squared w/1 2 2 side lengths2llvl/ +2//wll 2 . 28 Ifv = (1,2) draw all vectors w = (x, y) in the xy plane with v · w Why do those w's lie along a line? Which is the shortest w? 29 (Recommended) If//v/I = 5 andIlw/ I = 3 , what are the smallest and largest possible values ofI/v  w//? What are the smallest and largest possible values ofv · w? = x+2y = 5. Challenge Problems 30 Can three vectors in the xy plane have u · v < 0 and v · w < 0 and u · w < O? I don't know how many vectors in xyz space can have all negative dot products. (Four ofthose vectors in the plane would certainly be impossible . ..). 31 Pick any numbers that add to x+ y+ z = 0. Find the angle between your vec tor v = (x, y, z) and the vector w = (z, x, y). Challenge question: Explain why v · w///v// 1/wll is always½ 32 How could you prove {/xfii$ ½(x+y+ z) ( geometric mean$ arithmetic mean) ? 33 Find 4 perpendicular unit vectors of the form ( ± ½, 34 Usingv = randn(3, 1) in MATLAB, create a random unit vector u = v///vll Using V = randn(3, 30) create 30 more random unit vectors UJ. What is the average size ofthe dot products Iu · UjI? In calculus, the average is f0,r I cos 0Id0/ 1r =2/ 7f. ± ½, ± ½, ± ½): Choose+ or. 22 Chapter 1. Introduction to Vectors 1.3 Matrices 2 l 4 ] is a 3 by 2 matrix: m = 3 rows and n = 2 columns. 6 1 A= [ : 2 Ax _ [ 1 : 2 : ] [ :� ] is a combination of the columns Ax = x1 3 The 3 components of Ax are dot products of the 3 rows of A with the vector x : [ � � l [ ; ] [ � : ; ! � : : l [ �� l · Row at a time 4 Equations in matrix form Ax = b : 5 [ � � 6 ] [ :� ] [ 5 · 7 + 6· 8 83 b1 2x1 + 5x2 = b1 _ ] replaces b2 3 X1 + 7X2  b2 5 The solution to Ax = b can be written as x = A  1 b. But some matrices don't allow A  1. This section starts with three vectors u, v, w. I will combine them using matrices. Three vectors Their linear combinations in threedimensional space are x1 u + x2 v + x3 w: Combination of the vectors Now something important: Rewrite that combination using a matrix. The vectors u, v, w go into the columns of the matrix A. That matrix "multiplies" the vector (x1, x2, x3) : Matrix times vector Combination of columns 0 1 1 (2) The numbers x1, x2, x3 are the components of a vector x. The matrix A times the vector x is the same as the combination x1 u + x2v + x3 w of the three columns in equation (1). This is more than a definition of Ax, because the rewriting brings a crucial change in viewpoint. At first, the numbers x1, x2, x 3 were multiplying the vectors. Now the 23 1.3. Matrices matrix is multiplying those numbers. The matrix A acts on the vector x. The output Ax is a combination b of the columns of A. To see that action, I will write b 1, b 2, b3 for the components of Ax : Ax= [ � 0 � � 1 1 l [ :� l [ :  l [ � l X1 X3 X3  :1'2 = b. (3) b3 The input is x and the output is b = Ax. This A is a "difference matrix" because b contains differences of the input vector x. The top difference is x1  x0 = x 1  0. Here is an example to show differences of x = (1, 4, 9): squares in x, odd numbers in b. (4) That pattern would continue for a 4 by 4 difference matrix. The next square would be x4 = 16. The next difference would be x4  x3 = 16  9 = 7 (the next odd number). The matrix finds all the differences 1, 3, 5, 7 at once. Important Note: Multiplication a row at a time. You may already have learned about multiplying Ax, a matrix times a vector. Probably it was explained differently, using the rows instead of the columns. The usual way takes the dot product of each row with x: Ax is also dot products Ax with rows = (5) Those dot products are the same x1 and x2  x1 and X 3  x2 that we wrote in equation (3). The new way is to work with Ax a column at a time. Linear combinations are the key to linear algebra, and the output Ax is a linear combination of the columns of A. With numbers, you can multiply Ax by rows. With letters, columns are the good way. Chapter 2 will repeat these rules of matrix multiplication, and explain the ideas. Linear Equations One more change in viewpoint is crucial. Up to now, the numbers x 1, x2, x 3 were known. The right hand side b was not known. We found that vector of differences by multiplying A times x. Now we think of bas known and we look for x. Old question: Compute the linear combination x 1 u + x 2 v + X 3 W to find b. New question: Which combination of u, v, w produces a particular vector b? This is the inverse problemto find the input x that gives the desired output b = Ax. You have seen this before, as a system of linear equations for x 1, x2, x 3 • The right hand sides of the equations are b 1, b2, b3 . I will now solve that system Ax= b to find x 1, x2, x 3 : 24 Chapter 1. Introduction to Vectors Equations Ax=b Solution 1 X = A b X 1 =b 1 X2 =b 1 + b2 (6) X3 =bi+b2+b3. Let me admit right awaymost linear systems are not so easy to solve. In this example, the first equation decided x1 = b 1 . Then the second equation produced x2 = b 1 +b2. The equations can be solved in order (top to bottom) because A is a triangular matrix. Look at two specific choices 0, 0, 0 and 1, 3, 5 of the right sides b1, b2, b 3 : b= [!] gives x = 5 [!] . [i +3 ] = 9 1+3+5 The first solution (all zeros) is more important than it looks. In words: If the output is b = 0, then the input must be x = 0. That statement is true for this matrix A. It is not true for all matrices. Our second example will show (for a different matrix C) how we can have Cx = 0 when C =/ 0 and x =/ 0. This matrix A is "invertible". From b we can recover x. We write x as A 1 b. The Inverse Matrix Let me repeat the solution x in equation (6). A sum matrix will appear! 2 Ax = bis solved by [ :: ] = [ �� +b b 1 +b2+b3 X3 ] =[i 1 (7) If the differences of the x's are the b's, the sums of the b's are the x's. That was true for the odd numbers b = (1, 3, 5) and the squares x = (1, 4, 9). It is true for all vectors. The sum matrix in equation (7) is the inverse A 1 of the difference matrix A. Example: The differences of x = (1, 2, 3) are b = (1, 1, 1). Sob= Ax and x = A 1 b: Equation (7) for the solution vector x = ( x 1, x 2, x 3) tells us two important facts: 1. For every b there is one solution to Ax =b. 2. The matrix A 1 produces x =A 1 b. The next chapters ask about other equations Ax = b. Is there a solution? How to find it? Note on calculus. Let me connect these special matrices to calculus. The vector x changes to a function x(t). The differences Ax become the derivative dx/dt = b(t). In the inverse direction, the sums A 1 b become the integral of b(t). Sums of differences are like integrals of derivatives. 25 1.3. Matrices The Fundamental Theorem of Calculus says : integration is the inverse of differentiation . Ax t dx =band x(t) = r bdt. Jo dt = b and x = A  1 b (8) The differences of squares 0, 1, 4, 9 are odd numbers 1, 3, 5. The derivative of x(t) = t2 is 2t. A perfect analogy would have produced the even numbers b = 2, 4, 6 at times t = 1, 2, 3. But differences are not the same as derivatives, and our matrix A produces not 2t but 2t  1 : Backward x(t)  x(t  1) = t2  (t  1) 2 = t2  (t2  2t+ 1) = 2t  l. (9) The Problem Set will follow up to show that "forward differences" produce 2t + l. The best choice (not always seen in calculus courses) is a centered difference that uses x(t + 1)  x(t  1). Divide that .6.x by the distance .6.t from t  1 to t+ 1, which is 2: (t + 1) 2  (t  1) 2  = 2t exactly. (10) 2 Difference matrices are great. Centered is the best. Our second example is not invertible. Centered difference of x ( t) = t2 Cyclic Differences This example keeps the same columns u and v but changes w to a new vector w*: Second example Now the linear combinations of u, v, w* lead to a cyclic difference matrix C: X1  X3 Cyclic [ X 2  X1 X3  X 2 l = b. (11) This matrix C is not triangular. It is not so simple to solve for x when we are given b. Actually it is impossible to find the solution to Cx = b, because the three equations either have infinitely many solutions (sometimes) or else no solution (usually): Cx=O Infinitely manyx [ X1  X3 x2  x1 �� l [l = 0 0 0 is solved by all vectors [ l [l X1 x2 � C c C . (12) Every constant vector like x = (3, 3, 3) has zero differences when we go cyclically. The undetermined constant c is exactly like the + C that we add to integrals. The cyclic dif ferences cycle around to x 1  x 3 in the first component, instead of starting from x 0 = 0. 26 Chapter 1. Introduction to Vectors The more likely possibility for Cx = bis no solution x at all: Cx=b X1 X3 [ X2 X1 X3 X2 l Left sides add to 0 Right sides add to 9 No solution x1, x2, X3 (13) Look at this example geometrically. No combination of u, v, and w* will produce the vector b = (1, 3, 5). The combinations don't fill the whole threedimensional space. The right sides must have b 1 + b 2 + b 3 = 0 to allow a solution to Cx = b, because the left sides x 1  X3, x2  x 1, and X3  x2 always add to zero. Put that in different words : All linear combinations x 1 u + x 2 v + x3w* lie on the plane given by b 1 + b2 + b3 = 0. This subject is suddenly connecting algebra with geometry. Linear combinations can fill all of space, or only a plane. We need a picture to show the crucial difference between u, v, w (the first example) and u, v, w* (all in the same plane). 3 W= U= [ i] w* UJ 2 v= I [!] 3 u Figure 1.10: Independent vectors u, v, w. Dependent vectors u, v, w* in a plane. Independence and Dependence Figure 1.10 shows those column vectors, first of the matrix A and then of C. The first two columns u and v are the same in both pictures. If we only look at the combinations of those two vectors, we will get a twodimensional plane. The key question is whether the third vector is in that plane: Independence w is not in the plane of u and v. Dependence w* is in the plane of u and v. The important point is that the new vector w* is a linear combination of u and v: u+v+w* =0 W* 1 _ [0 1 l = uv. (14) 27 1.3. Matrices All three vectors u, v, w* have components adding to zero. Then all their combinations will have b 1 + b 2 + b 3 = 0 (as we saw above, by adding the three equations). This is the equation for the plane containing all combinations of u and v. By including w* we get no new vectors because w* is already on that plane. The original w = (0, 0, 1) is not on the plane: 0 + 0 + 1 =/ 0. The combinations of u, v, w fill the whole threedimensional space. We know this already, because the solution x = A 1 b in equation (6) gave the right combination to produce any b. The two matrices A and C, with third columns wand w*, allowed me to mention two key words of linear algebra: independence and dependence. The first half of the course will develop these ideas much furtherI am happy if you see them early in the two examples: u, v, ware independent. No combination except Ou+Ov+Ow= 0 gives b u, v, w* are dependent. Other combinations like u + v + w* give b = 0. = 0. You can picture this in three dimensions. The three vectors lie in a plane or they don't. Chapter 2 has n vectors in ndimensional space. Independence or dependence is the key point. The vectors go into the columns of an n by n matrix: Independent columns: Ax = 0 has one solution. A is an invertible matrix. Dependent columns: Cx = 0 has many solutions. C is a singular matrix. Eventually we will have n vectors in mdimensional space. The matrix A with those n columns is now rectangular (m by n). Understanding Ax=bis the problem of Chapter 3. • REVIEW OF THE KEY IDEAS • 1. Matrix times vector: Ax = combination of the columns of A. 2. The solution to Ax = b is x = A  lb, when A is an invertible matrix. 3. The cyclic matrix C has no inverse. Its three columns lie in the same plane. Those dependent columns add to the zero vector. Cx = 0 has many solutions. 4. This section is looking ahead to key ideas, not fully explained yet. • WORKED EXAMPLES • 1.3 A Change the southwest entry a31 of A (row 3, column 1) to a3 1 = 1: Ax=b X1 X1 + X2 X1  X2 + X3 Find the solution x for any b. From x = A  1 b read off the inverse matrix A  i. 28 l. Introduction to Vectors Ax=b frorri top to bottom: Solution Solve the (linear triangular) first x1 = ib then x2 = b1 + b2 then x 3 = b2 + This says that x= A1 b = [ _ 1 0 b3 1 0 _1 :: 1 l b1 2 : ,? : [ ; 3 1 0 This is good practice to see the columns of the inverse matrix multiplying ib, b2, and b3. The first column of A1 is the solution for b= (1, 0, 0). The second column is the solution for b= (0, 1, 0). The third column x of is the solution for Ax=b= (0, 0, 1). The three columns of A are still independent. They don't lie in a plane. The combiany threenations of those three columns, using the come from x= dimensional vector b= (bi , 2b, 3b). Those 1.3 B This E is an elimination matrix. E has a subtraction and E1 has an addition. E= b=Ex The first equation is x1 = ib. The second equation is x 2 Rb 1 to b 2, because the elimination matrix subtracted 1 £ 1 [ £ O 1J [ � �] = b2. The inverse will add = 1.3 C Change C from a cyclic difference to a centered difference producing x 3  :i:1: Cx=b (15) Cx = b can only be solved when b1 + b3 = T . 2  x 2 = 0. That is a plane of vectors b in threedimensional space. Each column of C is in the plane, the matrix has no inverse. So this plane contains all combinations of those columns (which are all the vectors Cx). I included the zeros so you could see that this C produces "centered differences". Row i of Cx is Xi+l (right of center) minus Xi 1 (left of center). Here is 4 by 4: Cx=b Centered differences (16) Surprisingly this matrix is now invertible! The first and last rows tell you :r:2 and i: : 3. Then the middle rows give x1 and x4. It is possible to write down the inverse matrix c 1. But 5 by 5 will be singular (not invertible) again ... 29 1.3. Matrices Problem Set 1.3 1 2 3 Find the linear combination 3s 1 + 4s2 + 5s3 = b. Then write bas a matrixvector multiplication Sx, with 3, 4, 5 in x. Compute the three dot products(row of S) • x: s, � rn s, � rn s, � m go into the columns of s. Solve these equations Sy= b with s 1, s2, s3 in the columns of S: S is a sum matrix. The sum of the first 5 odd numbers is Solve these three equations for Y1, Y2, y3 in terms of c1, c2, c3: Sy=c 4 5 6 Write the solution y as a matrix A= independent or dependent? s 1 times the vector c. Are the columns of S Find a combination x1w1 + x2w2 + x 3 w 3 that gives the zero vector with x1 = 1: Those vectors are (independent) (dependent). The three vectors lie in a The matrix W with those three columns is not invertible. The rows of that matrix W produce three vectors(/ write them as columns): Linear algebra says that these vectors must also lie in a plane. There must be many combinations with y1r1 + y2r2 + y3r3 = 0. Find two sets of y's. Which numbers c give dependent columns so a combination of columns equals zero ? c c 1 5l 3 6 maybe always independent for c =I 0 ? 30 7 Chapter 1. Introduction to Vectors If the columns combine into Ax = 0 then each of the rows has r · x = 0: The three rows also lie in a plane. Why is that plane perpendicular to x? 8 Moving to a 4 by 4 difference equation Ax = , find the four components x 1, x 2, x 3 , x 4. Then write this solution as x = A  1 b tobfind the inverse matrix : Ax= 9 10 What is the cyclic 4 by 4 difference matrix C ? It will have 1 and 1 in each row and each column. Find all solutions x = (x 1, x 2 , x 3 , x 4) to Cx = 0. The four columns of C lie in a "threedimensional hyperplane" inside fourdimensional space. A forward difference matrix 6. is upper triangular: 6.z 11 12 = b. = [ 0� 0� 1� l [ ;� l [ ;: = ;� l [ � l 0  Z3 Z3 Find z1, z2, z3 from b1, b2 , b3 . What is the inverse matrix in z Show that the forward differences ( t As in calculus, the difference ( t + l which is + r b3 = . b = 6_l b? l )2  t2 are 2 t+ 1 = odd numbers. tn will begin with the derivative of tn , The last lines of the Worked Example say that the 4 by 4 centered difference matrix in (16) is invertible. Solve Cx = (b 1, b2 , b 3 , b4) to find its inverse in x = c 1 b. Challenge Problems 13 14 The very last words say that the 5 by 5 centered difference matrix is not invertible. Write down the 5 equations Cx = b. Find a combination of left sides that gives zero. What combination of b 1, b2 , b3, b4, b5 must be zero? (The 5 columns lie on a "4dimensional hyperplane" in 5dimensional space. Hard to visualize.) If (a, b) is a multiple of ( c, d) with abed =f. 0, show that (a, c) is a multiple of (b, d). This is surprisingly important; two columns are falling on one line. You could use numbers first to see how a, b, c, d are related. The question will lead to: If [ : !] has dependent rows, then it also has dependent columns. Chapter 2 Solving Linear Equations 2.1 Vectors and Linear Equations 1 The column picture of Ax = b: a combination of n columns of A produces the vector b. 2 This is a vector equation Ax= x 1a1 + · · · + X n an = b: the columns of A are a1, a2, ... , an . 3 When b = 0, a combination Ax of the columns is zero: one possibility is x = (0, ..., 0). 4 The row picture of Ax= b: m equations from m rows give m planes meeting at x. 5 A dot product gives the equation of each plane : (row 1) · x = b 1 , ..., (row rn) · x = b m . 6 When b = 0, all the planes (row i) · x = 0 go through the center point x = (0, 0, ..., 0). The central problem of linear algebra is to solve a system of equations. Those equations are linear, which means that the unknowns are only multiplied by numberswe never see x times y. Our first linear system is small. But you will see how far it leads: Tuo equations Tuo unknowns X 3x + 2y 2y 1 11 (1) We begin a row at a time. The first equation x  2y = 1 produces a straight line in the xy plane. The point x = l, y = 0 is on the line because it solves that equation. The point x = 3, y = l is also on the line because 3  2 = 1. If we choose x = 101 we find y = 50. The slope of this particular line is because y increases by 1 when x changes by 2. But slopes are important in calculus and this is linear algebra! Figure 2.1 will show that first line x  2y = 1. The second line in this "row picture" comes from the second equation 3x + 2y = 11. You can't miss the point x = 3, y = l where the two lines meet. That point ( 3, 1) lies on both lines and solves both equations. ½, 31 32 Chapter 2. Solving Linear Equations y 1 3x+2y=ll X  2y 3 1 =1 2 3 Figure 2.1: Row picture: The point (3, 1) where the lines meet solves both equations. ROWS The row picture shows two lines meeting at a single point (the solution). Turn now to the column picture. I want to recognize the same linear system as a "vector equation". Instead of numbers we need to see vectors. If you separate the original system into its columns instead of its rows, you get a vector equation: Combination equals b (2) This has two column vectors on the left side. The problem is to find the combination of those vectors that equals the vector on the right. We are multiplying the first column by x and the second column by y, and adding. With the right choices x= 3 and y= 1 (the same numbers as before), this produces 3 (column 1) + 1 (column 2) = b. Figure 2.2 is the "column picture" of two equations in two unknowns. The first part shows the two separate columns, and that first column multiplied by 3. This multiplication by a scalar (a number) is one of the two basic operations in linear algebra: Scalar multiplication If the components of a vector v are v1 and v2, then cv has components cv1 and cv2. The other basic operation is vector addition. We add the first components and the second components separately. The vector sum is (1, 11), the desired vector b. Vector addition The right side of Figure 2.2 shows this addition. Two vectors are in black. The sum along the diagonal is the vector b= ( 1, 11) on the right side of the linear equations. 33 2.1. Vectors and Linear Equations [!] I , , [f' rn = 3 (column 1) 3(column 1) ' I + l(column 2) = b I column2 I b I Figure 2.2: Column picture: A combination of columns produces the right side (1, 11). To repeat: The left side of the vector equation is a linear combination of the columns. The problem is to find the right coefficients x = 3 and y = l. We are combining scalar multiplication and vector addition into one step. That step is crucially important, because it contains both of the basic operations: Multiply by 3 and 1, then add. Linear combination Of course the solution x = 3, y = l is the same as in the row picture. I don't know which picture you prefer! I suspect that the two intersecting lines are more familiar at first. You may like the row picture better, but only for one day. My own preference is to combine column vectors. It is a lot easier to see a combination of four vectors in fourdimensional space, than to visualize how four hyperplanes might possibly meet at a point. (Even one hyp erplane is hard enough. . . ) The coefficient matrix on the left side of the equations is the 2 by 2 matrix A: Coefficient matrix A 1 = [ 3 2 2 ]. This is very typical of linear algebra, to look at a matrix by rows and by columns. Its rows give the row picture and its columns give the column picture. Same numbers, different pictures, same equations. We combine those equations into a matrix problem Ax = b: Matrix equation Ax=b 34 Chapter 2. Solving Linear Equations The row picture deals with the two rows of A. The column picture combines the columns. The numbers x = 3 and y = l go into x. Here is matrixvector multiplication: Dot products with rows Combination of columns Ax=b is Looking ahead This chapter is going to solve n equations in n unknowns (for any n). I am not going at top speed, because smaller systems allow examples and pictures and a complete understanding. You are free to go faster, as long as matrix multiplication and inversion become clear. Those two ideas will be the keys to invertible matrices. I can list four steps to understanding elimination using matrices. 1. Elimination goes from A to a triangular U by a sequence of matrix steps Eij . 2. The triangular system is solved by back substitution: working bottom to top. 3. In matrix language A is factored into LU = (lower triangular) (upper triangular). 4. Elimination succeeds if A is invertible. (But it may need row exchanges.) The mostused algorithm in computational science takes those steps (MATLAB calls it lu). Its quickest form is backslash: x = A\ b. But linear algebra goes beyond square invertible matrices! Form by n matrices, Ax = 0 may have many solutions. Those solutions will go into a vector space. The rank of A leads to the dimension of that vector space. All this comes in Chapter 3, and I don't want to hurry. But I must get there. Three Equations in Three Unknowns The three unknowns are x, y, z. We have three linear equations: Ax =b X 2x 6x + + 2y 5y 3y + + + 3z 2z z 6 4 2 (3) We look for numbers x, y, z that solve all three equations at once. Those desired numbers might or might not exist. For this system, they do exist. When the number of unknowns matches the number of equations, in this case 3 = 3, there is usually one solution. Before solving the problem, we visualize it both ways: ROW The row picture shows three planes meeting at a single point. COLUMN The column picture combines three columns to produce b = (6, 4, 2). In the row picture, each equation produces a plane in threedimensional space. The first plane in Figure 2.3 comes from the first equation x + 2y + 3z = 6. That plane crosses the x and y and z axes at the points (6, 0, 0) and (0, 3, 0) and (0, 0, 2). Those three points solve the equation and they determine the whole plane. 35 2.1. Vectors and Linear Equations The vector (x,y, z) = (0,0,0) does not solve x + 2y + 3z = 6. Therefore that plane does not contain the origin. The plane x + 2y + 3z = 0 does pass through the origin, and it is parallel to x + 2y + 3z = 6. When the right side increases to 6, the parallel plane moves away from the origin. The second plane is given by the second equation 2x + 5y + 2z = 4. It intersects the first plane in a line L. The usual result of two equations in three unknowns is a line L of solutions. (Not if the equations were x + 2y + 3z = 6 and x + 2y + 3z = 0.) The third equation gives a third plane. It cuts the line L at a single point. That point lies on all three planes and it solves all three equations. It is harder to draw this triple intersection point than to imagine it. The three planes meet at the solution (which we haven't found yet). The column form will now show immediately why z = 2. z z L Solution L L IO+y planex +2y +3z=6 plane 2x + 5y + 2z = 4 X X m 3rd plane 6x 3y + z = 2 (0,0, 2) is on all three planes Figure 2.3: Row picture: Two planes meet at a line L. Three planes meet at a point. The column picture starts with the vector form of the equations Ax = b: Combine columns (4) The unknowns are the coefficients x, y, z. We want to multiply the three column vectors by the correct numbers x, y, z to produce b = (6,4, 2). Figure 2.4 shows this column picture. Linear combinations of those columns can pro duce any vector b! The combination that produces b = (6,4, 2) is just 2 times the third column. The coefficients we need are x = 0, y = 0, and z = 2. The three planes in the row picture meet at that same solution point (0,0, 2): Correct combination (x,y,z) = (0,0,2) 36 Chapter 2. Solving Linear Equations mcolumn I U]column2 2 times column 3 is b Figure 2.4: Column picture: Combine the columns with weights (x, y, z) = (0, 0, 2). The Matrix Form of the Equations We have three rows in the row picture and three columns in the column picture (plus the right side). The three rows and three columns contain nine numbers. These nine numbers fill a 3 by 3 matrix A: 2 5 3 The "coefficient matrix" in Ax = b is :] The capital letter A stands for all nine coefficients (in this square array). The letter b denotes the column vector with components 6, 4, 2. The unknown x is also a column vector, with components x, y, z. (We use boldface because it is a vector, x because it is unknown.) By rows the equations were (3), by columns they were (4), and by matrices they are (5): Matrix equation Ax =b � [ � 6 3 (5) Basic question: What does it mean to "multiply A times x"? We can multiply by rows or by columns. Either way, Ax = b must be a correct statement of the three equations. You do the same nine multiplications either way. Multiplication by rows Ax comes from dot products, each row times the column x: Ax = [( row I) • x ( row 2) · x ( row 3) · x l . (6) 37 2.1. Vectors and Linear Equations Multiplication by columns Ax is a combination of column vectors: Ax= x (column 1)+ y (column 2)+ z (column 3). (7) When we substitute the solution x = (0, 0, 2), the multiplication Ax produces b: 1 2 [ 2 5 6 3 The dot product from the first row is (1, 2, 3) · (0, 0, 2) = 6. The other rows give dot products 4 and 2. This book sees Ax as a combination of the columns of A. Example 1 Here are 3 by 3 matrices A and I = identity, with three 1 's and six O's: If you are a row person, the dot product of (1, 0, 0) with (4, 5, 6) is 4. If you are a column person, the linear combination Ax is 4 times the first column (1, 1, 1). In that matrix A, the second and third columns are zero vectors. The other matrix I is special. It has ones on the "main diagonal". Whatever vector this matrix multiplies, that vector is not changed. This is like multiplication by 1, but for matrices and vectors. The exceptional matrix in this example is the 3 by 3 identity matrix: always yields the multiplication Ix = x . Matrix Notation The first row of a 2 by 2 matrix contains a11 and a12. The second row contains a21 and a22. The first index gives the row number, so that aij is an entry in row i. The second index j gives the column number. But those subscripts are not very convenient on a keyboard! Instead of aij we type A(i,j). The entry a 57 = A(5, 7) would be in row 5, column 7. a12 a22 ] [  A(l, 1 ) A(2, 1) A(l, 2) ] A(2, 2) For an m by n matrix, the row index i goes from 1 to m. The column index j stops at n. There are mn entries aij = A(i, j). A square matrix of order n has n 2 entries. 38 Chapter 2. Solving Linear Equations Multiplication in MATLAB I want to express A and x and their product Ax using MATLAB commands. This is a first step in learning that language (and others). I begin by defining A and x. A vector x in R n is an n by 1 matrix (as in this book). Enter matrices a row at a time, and use a semicolon to signal the end of a row. Or enter by columns and transpose by 1 : A= [1 2 3; x = [0 0 2] 2 1 or 5 2; 6 3 1] x = [ 0; 0; 2 ] Here are three ways to multiply Ax in MATLAB. In reality, A * MATLAB is a high level language, and it works with matrices: Matrix multiplication x is the good way to do it. b=A*x We can also pick out the first row of A (as a smaller matrix!). The notation for that 3 by 3 submatrix is A(l, :). Here the colon symbol: keeps all columns of row 1. Row at a time b = [ A(l, :) * x; A(2, :) * x; A(3, :) * x] Each entry of b is a dot product, row times column, 1 by 3 matrix times 3 by 1 matrix. The other way to multiply uses the columns of A. The first column is the 3 by 1 submatrix A(: , 1). Now the colon symbol : comes first, to keep all rows of column 1. This column multiplies x(l) and the other columns multiply x(2) and x(3): Column at a time b = A(: , 1) * x(l) +A(: , 2) * x(2) +A(: , 3) * x(3) I think that matrices are stored by columns. Then multiplying a column at a time will be a little faster. So A * x is actually executed by columns. Programming Languages for Mathematics and Statistics Here are five more important languages and their commands for the multiplication Ax : Julia Python R Mathematica Maple A*X dot(A, x) A%*%X A.x A*X julialang.org python.org rproject.org wolfram.com/mathematica maplesoft.com Julia, Python, and R are free and open source languages. R is developed particularly for applications in statistics. Other software for statistics (SAS, JMP, and many more) is described on Wikipedia's Comparison of Statistical Packages. Mathematica and Maple allow symbolic entries a, b, x, ... and not only real numbers. As in MATLAB's Symbolic Toolbox, they work with symbolic expressions like x2  x. The power of Mathematica is seen in Wolfram Alpha. 39 2.1. Vectors and Linear Equations Julia combines the high productivity of SciPy or R for technical computing with per formance comparable to C or Fortran. It can call Python and C/Fortran libraries. But it doesn't rely on "vectorized" library functions for speed; Julia is designed to be fast. I entered juliabox.org. I clicked Sign in via Google to access my gmail space. Then I clicked new at the right and chose a Julia notebook. I chose 0.4.5 and not one under development. The Julia command line came up immediately. As a novice, I computed 1 + 1. To see the answer I pressed Shift+Enter. I also learned that 1.0 + 1.0 uses floating point, much faster for a large problem. The website math.mit.edu/linearalgebra will show part of the power of Julia and Python and R. Python is a popular generalpurpose programming language. When combined with packages like NumPy and the SciPy library, it provides a fullfeatured environment for technical computing. NumPy has the basic linear algebra commands. Download the Ana conda Python distribution from https://www.continuum.io (a prepackaged collection of Python and most important mathematical libraries, with a graphical installer). R is free software for statistical computing and graphics. To download and install R, go to rproject.org (prefix https://www.). Commands are prompted by> and R is a scripted language. It works with lists that can be shaped into vectors and matrices. It is important to recommend RStudio for editing and graphing (and help resources). When you download from www.RStudio.com, a window opens for R commandsplus windows for editing and managing files and plots. Tell R the form of the matrix as well as the list of numerical entries: >A= matrix (c (1, 2, 3, 2, 5, 2, 6, 3, 1), nrow = 3, byrow = TRUE) > x = matrix ( c (0, 0, 2), nrow = 3) To see A and x, type their names at the new prompt>. To multiply type b =A%* %x. Transpose by t(A) and use as.matrix to turn a vector into a matrix. MATLAB and Julia have a cleaner syntax for matrix computations than R. But R has become very familiar and widely used. The website for this book has space for proper demos (including the Manipulate command) of MATLAB and Julia and Python and R. • REVIEW OF THE KEY IDEAS • 1. The basic operations on vectors are multiplication cv and vector addition v + w. 2. Together those operations give linear combinations cv + dw. 3. Matrixvector multiplication Ax can be computed by dot products, a row at a time. But Ax must be understood as a combination of the columns of A. 4. Column picture: Ax = b asks for a combination of columns to produce b. 5. Row picture: Each equation in Ax = b gives a line (n = 2) or a plane (n = 3) or a "hyperplane" (n > 3). They intersect at the solution or solutions, if any. 40 Chapter 2. Solving Linear Equations • WORKED EXAMPLES • 2.1 A Describe the column picture of these three equations Ax = b. Solve by careful inspection of the columns (instead of elimination): ! �� ! �:: =� �i [:] [=�] 2: which is [� � 3x + 5y + 6z = 5 3 5 6 z 5 The column picture asks for a linear combination that produces b from the Solution three columns of A. In this example b is minus the second column. So the solution is x = 0, y = 1, z = 0. To show that (0, 1, 0) is the only solution we have to know that "A is invertible" and "the columns are independent" and "the determinant isn't zero." Those words are not yet defined but the test comes from elimination: We need (and for this matrix we find) a full set of three nonzero pivots. Suppose the right side changes to b = (4, 4, 8) = sum of the first two columns. Then the good combination has x = 1, y = 1, z = 0. The solution becomes x = (1, 1, 0). 2.1 B This system has no solution. The planes in the row picture don't meet at a point. . No combination of the three columns produces b. How to show this? x+3y+5z = 4 X + 2y 3z = 5 2x + 5y + 2z = 8 Idea Add (equation 1) + (equation 2)  (equation 3). The result is O = 1. This system cannot have a solution. We could say: The vector (1, 1, 1) is orthogonal to all three columns of A but not orthogonal to b. (1) Are any two of the three planes parallel? What are the equations of planes parallel to x+3y+5z=4? = ( 1, 1, 1). How do those dot products show that no combination of columns equals b? (2) Take the dot product of each column of A (and also b) with y (3) Find three different right side vectors b* and b** and b*** that do allow solutions. Solution (1) The planes don't meet at a point, even though no two planes are parallel. For a plane parallel to x + 3y + 5z = 4, change the "4". The parallel plane x + 3y + 5z = 0 goes through the origin (0, 0, 0). And the equation multiplied by any nonzero con stant still gives the same plane, as in 2x + 6y + lOz = 8. (2) The dot product of each column of A with y = (1, 1, 1) is zero. On the right side, y · b = (1, 1, 1) · (4, 5, 8) = 1 is not zero. Ax = bled to 0 = 1: no solution. (3) There is a solution when bis a combination of the columns. These three choices of bhave solutions including x* = (1, 0, 0) and x** = (1, 1, 1) and x*** = (0, 0, 0): b' � m� fiIBt column b" � m� Sllffi of columns b'" � m 41 2.1. Vectors and Linear Equations Problem Set 2.1 Problems 18 are about the row and column pictures of Ax 1 = b. With A = I (the identity matrix) draw the planes in the row picture. Three sides of a box meet at the solutionx= (x,y,z) = (2,3,4): lx + Oy+Oz= 2 Ox+ ly+Oz= 3 Ox+Oy + lz = 4 or [l 0 0 1 0 0 Draw the vectors in the column picture. Two times column 1 plus three times column 2 plus four times column 3 equals the right side b. 2 If the equations in Problem 1 are multiplied by 2,3,4 they become DX= B: 2x + Oy+Oz= 4 Ox+ 3y+Oz= 9 Ox + Oy + 4z = 16 DX� or [� � �l m ui � B Why is the row picture the same? Is the solution X the same asx? What is changed in the column picturethe columns or the right combination to give B? 3 If equation 1 is added to equation 2, which of these are changed: the planes in the row picture, the vectors in the column picture, the coefficient matrix, the solution? The new equations in Problem 1 would be x = 2, x + y = 5, z = 4. 4 Find a point with z = 2 on the intersection line of the planes x + y + 3z=6 and x  y + z=4. Find the point with z= 0. Find a third point halfway between. 5 The first of these equations plus the second equals the third: x+ y+ z=2 + 2y+ Z = 3 2x + 3y + 2z= 5. X The first two planes meet along a line. The third plane contains that line, because if x, y, z satisfy the first two equations then they also __ . The equations have infinitely many solutions (the whole line L). Find three solutions on L. 6 Move the third plane in Problem 5 to a parallel plane 2x + 3y + 2z = 9. Now the three equations have no solutionwhy not? The first two planes meet along the line L, but the third plane doesn't __ that line. 7 In Problem 5 the columns are (1,1,2) and (1,2,3) and (1,1,2). This is a "singular case" because the third column is . Find two combinations of the columns that give b = (2,3, 5). This is only possible for b = (4,6, c) if c = __ . 42 8 Chapter 2. Solving Linear Equations Normally 4 "planes" in 4dimensional space meet at a __ . Normally 4 col umn vectors in 4dimensional space can combine to produce b. What combination of (1, 0, 0, 0), (1, 1, 0, 0), (1, 1, 1, 0), (1, 1, 1, 1) produces b = (3, 3, 3, 2)? What 4 equations for x, y, z, t are you solving? Problems 914 are about multiplying matrices and vectors. 9 Compute each Ax by dot products of the rows with the column vector: (a) 10 2 [ ; rim (b) 4 1 3 1 0 2 1 1 2 0 1 [l �1 rn Compute each Ax in Problem 9 as a combination of the columns: How many separate multiplications for Ax, when the matrix is "3 by 3"? 11 Find the two components of Ax by rows or by columns: [� �] [i] 12 13 14 and [: 1�J [n and Multiply A times x to find three components of Ax: 2 0 [� i] rn. [! i] [�] [l il Ul [l l] [:] 0 1 0 and 1 2 3 and (a) A matrix with m rows and n columns multiplies a vector with __ components to produce a vector with __ components. (b) The planes from the m equations Ax = b are in __ dimensional space. The combination of the columns of A is in __ dimensional space. Write 2x + 3y + z + 5t = 8 as a matrix A (how many rows?) multiplying the column vector x = (x, y, z, t) to produce b. The solutions x fill a plane or "hyperplane" in 4dimensional space. The plane is 3dimensional with no 4D volume. Problems 1522 ask for matrices that act in special ways on vectors. 15 (a) What is the 2 by 2 identity matrix? I times [;] equals [;]. (b) What is the 2 by 2 exchange matrix? P times [;] equals [ �]. 43 2.1. Vectors and Linear Equations 16 (a) What2by2matrixRrotates every vector by90° ? Rtimes[;]is[_�] (b) What2by2matrixR2 rotates every vector by 180° ? 17 Find the matrix P that multiplies (x,y,z) to give (y,z,x). Find the matrix Q that multiplies (y,z,x) to bring back (x,y,z). 18 What 2 by 2 matrix E subtracts the first component from the second component? What 3 by 3 matrix does the same? E [!] rnJ and 19 What 3 by 3 matrix E multiplies (x,y, z) to give (x,y,z + x )? What matrix E 1 multiplies (x,y,z) to give (x,y,z  x)? If you multiply (3,4,5) by E and then multiply by E 1, the two results are (_ _ ) and ( __ ). 20 What 2 by 2 matrix Pi projects the vector (x,y) onto the x axis to produce (x, O)? What matrix A projects onto they axis to produce (0, y)? If you multiply (5,7) by Pi and then multiply by P2 , you get (__ ) and (__ ). 21 What 2 by 2 matrix R rotates every vector through 45° ? The vector (1,0) goes to (/2/2,/2/2). The vector (0,1) goes to (/2/2,/2/2). Those determine the matrix. Draw these particular vectors in the xy plane and find R. 22 Write the dot product of (1,4,5) and (x, y, z) as a matrix multiplication Ax. The matrix A has one row. The solutions to Ax = 0 lie on a __ perpendicular to the vector __ . The columns of A are only in __ dimensional space. 23 In MATLAB notation, write the commands that define this matrix A and the column vectors x and b. What command would test whether or not Ax = b? A= [� �] b = [�] 24 The MATLAB commands A = eye(3) and v = [ 3 : 5]' produce the 3 by 3 identity matrix and the column vector (3,4,5). What are the outputs from Aw and v'*v? (Computer not needed!) If you ask for wA, what happens? 25 If you multiply the 4by 4allones matrix A= ones(4) and the column v= ones(4, 1), what is A*v? (Computer not needed.) If you multiply B = eye(4) + ones(4) times w= zeros(4, 1) + 2*ones(4, 1), what is B*w? 44 Chapter 2. Solving Linear Equations Questions 2628 review the row and column pictures in 2, 3, and 4 dimensions. 26 Draw the row and column pictures for the equations x  2y = 0, x + y = 6. 27 For two linear equations in three unknowns x, y, z, the row picture will show (2 or 3) (lines or planes) in (2 or 3)dimensional space. The column picture is in (2 or 3) dimensional space. The solutions normally lie on a __ . 28 For four linear equations in two unknowns x and y, the row picture shows four __ . The column picture is in __ dimensional space. The equations have no solution unless the vector on the right side is a combination of __ . 29 Start with the vector u0 = (1, 0). Multiply again and again by the same "Markov matrix" A= [.8 .3; .2 .7]. The next three vectors are u 1, u2, u 3: Ui = [·8 .3] [l] [·8] .2 .7 0 .2 What property do you notice for all four vectors uo, u 1, u2, u3? 30 Challenge Problems Continue Problem 29 from u 0 = (1, 0) to u 7, and also from v0 = (0, 1) to v 7. What do you notice about u7 and v 7? Here are two MATLAB codes, with while and for. They plot u 0 to u7 and v 0 to v7. You can use other languages: u = [1 ; OJ; A= [.8 .3; .2 .7); x = u; k = [O : 7]; while size(x,2) <= 7 u = A*u; x = [xu]; end plot(k, x) v = [0; 1); A= [.8 .3; .2 .7]; X = v; k = [0 : 7]; for j = 1 : 7 v = A*v; x = [xv]; end plot(k, x) The u's and v's are approaching a steady state vectors. Guess that vector and check that As = s. If you start withs, you stay withs. 31 Invent a 3 by 3 magic matrix M3 with entries 1, 2, ..., 9. All rows and columns and diagonals add to 15. The first row could be 8, 3, 4. What is M3 times (1, 1, l)? What is M4 times (1, 1, 1, 1) if a 4 by 4 magic matrix has entries 1, ..., 16? 32 Suppose u and v are the first two columns of a 3 by 3 matrix A. Which third columns w would make this matrix singular? Describe a typical column picture of Ax = b in that singular case, and a typical row picture (for a random b). 2.1. Vectors and Linear Equations 33 45 Multiplication by A is a "linear transformation". Those words mean: If w is a combination of u and v, then Aw is the same combination of Au and Av. It is this "linearity" Aw=cAu + dAv that gives us the name "linear algebra". Problem: If u = [ � ] and v = [ � ] then Au and Av are the columns of A. 34 35 Combine w=cu+ dv. If w = [ � ] how is Aw connected to Au and Av? Start from the four equations xi+l + 2xi  Xil = i (for i = 1, 2, 3, 4 with x 0 = x 5 = 0). Write those equations in their matrix form Ax = b. Can you solve themforx1,x2,x3,x4? A 9 by 9 Sudoku matrix S has the numbers 1, ..., 9 in every row and every column, and in every 3 by 3 block. For the allones vector x = (1, ..., 1), what is Sx? A better question is: Which row exchanges will produce another Sudoku matrix? Also, which exchanges of block rows give another Sudoku matrix? Section 2.7 will look at all possible permutations (reorderings) of the rows. I can see 6 orders for the first 3 rows, all giving Sudoku matrices. Also 6 permutations of the next 3 rows, and of the last 3 rows. And 6 block permutations of the block rows? 46 Chapter 2. Solving Linear Equations 2.2 The Idea of Elimination 1 For rn = n = 3, there are three equations Ax= band three unknowns x1, x2, x3. 2 The first two equations are aux1 + · · · = b1 and a21x1 + · · · = b2. 3 Multiply the first equation by a2i/ au and subtract from the second : then x1 is eliminated. 4 The comer entry au is the first "pivot " and the ratio a2i/ au is the first "multiplier." 5 Eliminate x1 from every remaining equation i by subtracting aii/ au times the first equation. 6 Now the last n  1 equations contain n  1 unknowns x2, ..., Xn. Repeat to eliminate x2. 7 Elimination breaks down if zero appears in the pivot. Exchanging two equations may save it. This chapter explains a systematic way to solve linear equations. The method is called "elimination", and you can see it immediately in our 2 by 2 example. Before elimination, x and y appear in both equations. After elimination, the first unknown x has disappeared from the second equation 8y = 8: Before X 3x 2y = + 2y = 1 11 (multiply equation 1 by 3)