Advanced linear algebra lecture notes pdf

linear algebra 1 & 2 course notes version 3.0 and the elementary linear algebra lecture notes
LaylaChadwick Profile Pic
LaylaChadwick,New Zealand,Teacher
Published Date:15-07-2017
Your Website URL(Optional)
Comment
Linear Algebra I - Lectures Notes - Spring 2013 Shmuel Friedland Oce: 715 SEO, phone: 413-2176, e:mail: friedlanuic.edu, web: http://www.math.uic.edu/friedlan April 28, 2013 Remarks on the notes: These notes are updated during the course. For 2012 version view http://www2.math.uic.edu/friedlan/math320lec.pdf Preface: Linear Algebra is used in many areas as: engineering, biology, medicine, business, statistics, physics, mathematics, numerical analysis and humanities. The reason: many real world systems consist of many parts which interact linearly. Analysis of such systems involves the notions and the tools from Linear Algebra. These notes of linear algebra course emphasize the mathematical rigour over the applications, contrary to many books on linear algebra for engineers. My main goal in writing these notes was to give to the student a concise overview of the main concepts,ideas and results that usually are covered in the rst course on linear algebra for mathematicians. These notes should be viewed as a supplementary notes to a regular book for linear algebra, as for example 1. Main Topics of the Course  SYSTEMS OF EQUATIONS  VECTOR SPACES  LINEAR TRANSFORMATIONS  DETERMINANTS  INNER PRODUCT SPACES  EIGENVALUES  JORDAN CANONICAL FORM-RUDIMENTS Text: Jim He eron, Linear Algebra, and Solutions Available for free download ftp://joshua.smcvt.edu/pub/he eron/book/book.pdf ftp://joshua.smcvt.edu/pub/he eron/book/jhanswer.pdf Software: MatLab,Maple, Matematica 1Contents 1 Linear equations and matrices 4 1.1 System of Linear Equation . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Equivalent systems of equations . . . . . . . . . . . . . 6 1.1.3 Elementary operations . . . . . . . . . . . . . . . . . . 6 1.1.4 Triangular systems . . . . . . . . . . . . . . . . . . . . 7 1.2 Matrix formalism for solving systems of linear equations . . . 8 1.2.1 The Coecient Matrix of the system . . . . . . . . . . 8 1.2.2 Elementary row operations . . . . . . . . . . . . . . . . 8 1.2.3 Row Echelon Form . . . . . . . . . . . . . . . . . . . . 9 1.2.4 Solution of linear systems . . . . . . . . . . . . . . . . 11 1.2.5 Reduced row echelon form . . . . . . . . . . . . . . . . 12 1.3 Operations on vectors and matrices . . . . . . . . . . . . . . . 15 1.3.1 Operations on vectors . . . . . . . . . . . . . . . . . . 15 1.3.2 Application to solutions of linear systems . . . . . . . . 16 1.3.3 Products of matrices with vectors . . . . . . . . . . . . 17 1.3.4 Row equivalence of matrices . . . . . . . . . . . . . . . 18 2 Vector Spaces 19 2.1 De nition of a vector space . . . . . . . . . . . . . . . . . . . . 19 2.2 Examples of vector spaces . . . . . . . . . . . . . . . . . . . . 19 2.3 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Examples of subspaces . . . . . . . . . . . . . . . . . . . . . . 21 2.5 Linear combination & span . . . . . . . . . . . . . . . . . . . 21 2.6 Spanning sets of vector spaces . . . . . . . . . . . . . . . . . . 22 2.7 Linear Independence . . . . . . . . . . . . . . . . . . . . . . . 23 2.8 Basis and dimension . . . . . . . . . . . . . . . . . . . . . . . 24 2.9 Row and column spaces of matrices . . . . . . . . . . . . . . . 26 2.10 An example for a basis of N(A) . . . . . . . . . . . . . . . . . 27 2.11 Useful facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.12 The spaceP . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 n 2.13 Sum of two subspaces . . . . . . . . . . . . . . . . . . . . . . . 28 2.14 Sums of many subspaces . . . . . . . . . . . . . . . . . . . . . 29 2.15 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.16 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.17 Vector spaces over elds . . . . . . . . . . . . . . . . . . . . . 31 3 Linear transformations 32 3.1 One-to-one and onto maps . . . . . . . . . . . . . . . . . . . . 32 3.2 Isomorphism of vector spaces . . . . . . . . . . . . . . . . . . 33 3.3 Iso. of n. dim. vector spaces . . . . . . . . . . . . . . . . . . 33 n 3.4 Isomorphisms ofR . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 23.6 Linear Transformations (Homomorphisms) . . . . . . . . . . . 34 3.7 Rank-nullity theorem . . . . . . . . . . . . . . . . . . . . . . . 35 3.8 Matrix representations of linear transformations . . . . . . . . 36 3.9 Composition of maps . . . . . . . . . . . . . . . . . . . . . . . 36 3.10 Product of matrices . . . . . . . . . . . . . . . . . . . . . . . . 37 3.11 Transpose of a matrix A . . . . . . . . . . . . . . . . . . . . 38 3.12 Symmetric Matrices . . . . . . . . . . . . . . . . . . . . . . . . 39 3.13 Powers of square matrices and Markov chains . . . . . . . . . 39 3.14 Inverses of square matrices . . . . . . . . . . . . . . . . . . . . 40 3.15 Elementary Matrices . . . . . . . . . . . . . . . . . . . . . . . 41 3.16 ERO in terms of Elementary Matrices . . . . . . . . . . . . . . 43 3.17 Matrix inverse as products of elementary matrices . . . . . . . 43 1 3.18 Gauss-Jordan algorithm for A . . . . . . . . . . . . . . . . . 43 3.19 Change of basis . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.20 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.21 Change of the representation matrix under the change of bases 46 3.22 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.23 Equivalence of matrices . . . . . . . . . . . . . . . . . . . . . . 48 4 Inner product spaces 49 n 4.1 Scalar Product inR . . . . . . . . . . . . . . . . . . . . . . . 49 4.2 Cauchy-Schwarz inequality . . . . . . . . . . . . . . . . . . . . 49 4.3 Scalar and vector projection . . . . . . . . . . . . . . . . . . . 50 4.4 Orthogonal subspaces . . . . . . . . . . . . . . . . . . . . . . . 50 4.5 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.6 Projection on a subspace . . . . . . . . . . . . . . . . . . . . . 51 4.7 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.8 Finding the projection on span . . . . . . . . . . . . . . . . . 53 4.9 The best t line . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.10 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.11 Orthonormal sets . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.12 Orthogonal Matrices . . . . . . . . . . . . . . . . . . . . . . . 56 4.13 Gram-Schmidt orthogonolization process . . . . . . . . . . . . 57 4.14 Explanation of G-S process . . . . . . . . . . . . . . . . . . . . 57 4.15 An example of G-S process . . . . . . . . . . . . . . . . . . . . 58 4.16 QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.17 An example of QR algorithm . . . . . . . . . . . . . . . . . . 59 4.18 Inner Product Spaces . . . . . . . . . . . . . . . . . . . . . . . 59 4.19 Examples of IPS . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.20 Length and angle in IPS . . . . . . . . . . . . . . . . . . . . . 60 4.21 Orthonormal sets in IPS . . . . . . . . . . . . . . . . . . . . . 61 4.22 Fourier series . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.23 Short biographies of related mathematcians . . . . . . . . . . 61 4.23.1 Johann Carl Friedrich Gauss . . . . . . . . . . . . . . . 61 4.23.2 Augustin Louis Cauchy . . . . . . . . . . . . . . . . . . 62 34.23.3 Hermann Amandus Schwarz . . . . . . . . . . . . . . . 62 4.23.4 Viktor Yakovlevich Bunyakovsky . . . . . . . . . . . . 63 4.23.5 Gram and Schmidt . . . . . . . . . . . . . . . . . . . . 63 4.23.6 Jean Baptiste Joseph Fourier . . . . . . . . . . . . . . 63 4.23.7 J. Peter Gustav Lejeune Dirichlet . . . . . . . . . . . . 64 4.23.8 David Hilbert . . . . . . . . . . . . . . . . . . . . . . . 64 5 DETERMINANTS 64 5.1 Introduction to determinant . . . . . . . . . . . . . . . . . . . 64 5.2 Determinant as a multilinear function . . . . . . . . . . . . . . 65 5.3 Computing determinants using elementary row or columns op- erations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.4 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.5 S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2 5.6 S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3 5.7 Rigorous de nition of determinant . . . . . . . . . . . . . . . . 71 5.8 Cases n = 2; 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.9 Minors and Cofactors . . . . . . . . . . . . . . . . . . . . . . . 72 5.10 Examples of Laplace expansions . . . . . . . . . . . . . . . . . 72 5.11 Adjoint Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.12 The properties of the adjoint matrix . . . . . . . . . . . . . . 74 5.13 Cramer's Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 5.14 History of determinants . . . . . . . . . . . . . . . . . . . . . 76 6 Eigenvalues and Eigenvectors 77 6.1 De nition of eigenvalues and eigenvectors . . . . . . . . . . . . 77 6.2 Examples of eigenvalues and eigenvectors . . . . . . . . . . . . 78 6.3 Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.4 Characteristic polynomials of upper triangular matrices . . . . 80 6.5 Defective matrices . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.6 An examples of a diagonable matrix . . . . . . . . . . . . . . . 83 6.7 Powers of diagonable matrices . . . . . . . . . . . . . . . . . . 83 6.8 Systems of linear ordinary di erential equations . . . . . . . . 84 6.9 Initial conditions . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.10 Complex eigenvalues of real matrices . . . . . . . . . . . . . . 86 6.11 Second Order Linear Di erential Systems . . . . . . . . . . . . 86 6.12 Exponential of a Matrix . . . . . . . . . . . . . . . . . . . . . 87 6.13 Examples of exponential of matrices . . . . . . . . . . . . . . . 87 1 Linear equations and matrices The object of this section is to study a set of m linear equations in n real variables x ;:::;x . It is convenient to group n variable in one quantity: 1 n (x ;x ;:::;x ), which is called a row vector. For reasons that will be seen 1 2 n 4later we will consider a column vector denoted by x, for which we either the round brackets ( ) or the straight brackets : 2 3 0 1 x x 1 1 6 7 B C x x 2 2 6 7 B C x := (x ;x ;:::;x ) = = : (1.1) 6 7 B C 1 2 n . . . . 4 5 A . . x x n n We will denote by x the row vector (x ;x ;:::;x ). We denote the set of 1 2 n n 1 2 all column vectors x by R . So R = R all the points on the real line; R 3 n are all points in the plane; R all points in 3-dimensional space. R is called n n-dimensional space. It is hard to visualizeR for n 4, but we ca study it eciently using mathematical tools. We will learn how to determine when a given system is linear equations in n R is unsolvable or solvable, when the solution is unique or not unique, and how to express compactly all the solutions of the given system. 1.1 System of Linear Equation a x + a x + ::: + a x =b 11 1 12 2 1n n 1 a x + a x + ::: + a x =b 21 1 22 2 2n n 2 (1.2) . . . . . . . . . . . . . . . . . . . . . a x + a x + ::: + a x =b m1 1 m2 2 mn n m 1.1.1 Examples A trivial equation in n variables is 0x + 0x +::: + 0x = 0: (1.3) 1 2 n n Clearly, every vector x2R satis es this equation. Sometimes, when we see such an equation in our system of equations, we delete this equations from the given system. This will not change the form of the solutions. The following system of n equations in n unknowns x =b ; x =b ; x =b : (1.4) 1 1 2 2 n n clearly has a unique solution x = (b ;:::;b ) . 1 n Next consider the equation 0x + 0x +::: + 0x = 1: (1.5) 1 2 n Clearly, this equation does not have any solution, i.e. none. Consider m linear equations in n = 2 unknowns we assume that none of this equations is a trivial equation, i.e. of the form (1.3) for n = 2. Assume rst that m = 1, i.e. we have one equation in two variables. Then the set of 52 solutions is a line inR . So the number of solutions is in nite, many, and can be parametrized by one real parameter. Suppose next thatm = 2. Then if the two lines are not parallel the system of two equations in two unknowns has a unique solution. This is the generic case, i.e. if we let the coecients a ;a ;a ;a to be chosen at random by 11 12 21 22 computer. (The values of b ;b are not relevant.) If the two lines are parallel 1 2 but not the identical we do not have a solution. If the two lines are identical, the system of solutions is a line. Ifm 3, then in general, (generically), we would not have a solution, since usually three pairwise distinct lines would not intersect in one point. However, if all the lines chosen were passing through a given point then this system is solvable. For more speci c examples see 1, Chapter One, Section I 1.1.2 Equivalent systems of equations Suppose we have two systems of linear equation in the same number of vari- 0 ables, say n, but perhaps a di erent numbers of equations say m and m respectively. Then these two systems are called equivalent if the two systems n have the same set of solutions. I.e. a vector x2R is a solution to one system if and only if it is a solution to the second system. Our solution of a given system boils down to nd an equivalent system for which we can easy determine if the system is solvable or not, and if solvable we can describe easily the set of all solutions of this system. A trivial example of two equivalent systems is as follows. Example 1.1 Consider the system (1.2). Then the following new system is equivalent to (1.2): 1. Add to the system (1.2) a nite number of trivial equations of the form (1.3). 2. Assume that the system (1.2) has a nite number of trivial equations of the form (1.3). Delete some of these trivial equations The main result of this Chapter is that two systems of linear equations are equivalent if and and only if each of the system is equivalent to another system, where the nal two systems are related by Example 1.1. 1.1.3 Elementary operations De nition 1.2 The following three operations on the given system of lin- ear equations are called elementary. 1. Change the order of the equations. 2. Multiply an equation by a nonzero number. 63. Add (subtract) from one equation a multiple of another equation. Lemma 1.3 Suppose that a system of linear equations, named system II, was obtained from a system of linear equations, named system I, by using a sequence of elementary operations. Then we can perform a sequence of ele- mentary operations on system II to obtain system I. In particular, the systems I and II are equivalent. Proof. It is enough to show the lemma when perform. We now observe that all elementary operations are reversible. Namely performing one elementary operation and then the second one of the same type will give back the original system: change twice the order of the equations i and j;, multiply equation i 1 bya6= 0 and then multiply equationi by ; add equationj timesa to equation a i =6 j and subtract equation j times a to equation i =6 j. Hence if x satis es system I it satis es system II and vice versa. 2 1.1.4 Triangular systems An example x + 2x = 5 1 2 2x + 3x = 8 1 2 Subtract 2 times row 1 from row 2. He eron notation:  2  . My 2 1 2 notations: R 2R R , or R R 2R , or R R 2R . Obtain a 2 1 2 2 2 1 2 2 1 new system x + 2x = 5 1 2 x =2 2 Find rst the solution of the second equation: x = 2. Substitutex to the rst 2 2 equation: x + 2 2 = 5)x = 5 4 = 1. Unique solution (x ;x ) = (1; 2). 1 1 1 2 A general triangular system of linear equations is the following system of n equations in n unknowns: a x + a x + ::: + a x =b 11 1 12 2 1n n 1 + a x + ::: + a x =b 22 2 2n n 2 (1.6) . . . . . . . . . . . . . . . . . . . . . ::: a x =b nn n n with n pivots: a 6= 0; a 6= 0;:::a 6= 0: 11 22 nn Solve the system by back substitution from down to up: b n x = ; n a nn a x +b (n1)n n n1 x = ; (1.7) n1 a (n1)(n1) a x :::a x +b i(i+1) i+1 in n i x = ; i a ii i =n 2;:::; 1: 71.2 Matrix formalism for solving systems of linear equa- tions In this subsection we introduce matrix formalism which allows us to nd an equivalent form of the system (1.2) from which we can nd if the system is solvable or not, and if solvable, to nd a compact way to describe the sets of its solution. The main advantage of this notation is that it does not uses the variables x ;:::;x and easily adopted for programming on a computer. 1 n 1.2.1 The Coecient Matrix of the system Consider the system (1.2). The information given in the left-hand side of this system can be neatly written in terms on mn coecient matrix 2 3 a a ::: a 11 12 1n 6 7 a a ::: a 21 22 2n 6 7 A =6 7 (1.8) . . . . . . . . 4 5 . . . . a a ::: a m1 m2 mn mn We denote the set of allmn matrices with real entries asR . Note that the right-hand side of (1.2) is given by a column vector b := (b ;b ;:::;b ) . 1 2 m Hence the matrix that describes completely the system (1.2) is called the augmented matrix and denoted by Ajb, and sometimes (Ajb). 2 3 a a ::: a j b 11 12 1n 1 6 7 a a ::: a j b 21 22 2n 2 6 7 Ajb =6 7 (1.9) . . . . . . . . . . 4 5 . . . . j . a a ::: a j b m1 m2 mn m One can view an augmented matrix Ajb as an m (n + 1) matrix C. Sometimes we will use the notationA for anymp matrix. So in this context A can be either a coecient matrix or an augmented matrix, and no ambiguity should arise. 1.2.2 Elementary row operations It is easy to see that elementary operations on a system of linear equations discussed inx1.1.3 are equivalent to the following elementary row operations on the augmented matrix corresponding to the system (1.2). De nition 1.4 (Elementary Row Operations-ERO) Let C be given mp matrix. Then the following three operations are called ERO and denoted as follows. 1. Interchange the rows i and j, where i =6 j R R ; (  ): i j i j 82. Multiply the row i by a nonzero number a =6 0 aR R; (R aR; a  ): i i i i i j 3. Replace the row i by its sum with a multiple the row j =6 i R +aR R; (R R +aR ;  +a  ): i j i i i j i j i The following lemma is the analog of Lemma 1.3 and its proof is similar. Lemma 1.5 The elementary row operations are reversible. More precisely 1. R R is the inverse of R R , i j i j 1 2. R R is the inverse of aR R i i i i a 3. R aR R is the inverse of R +aR R . i j i i j i 1.2.3 Row Echelon Form De nition 1.6 A matrix C is in a row echelon form (REF) if it satis es the following conditions 1. The rst nonzero entry in each row is 1. This entry is called a pivot. 2. If row k does not consists entirely of zeros, then the number of leading zero entries in row k + 1 is greater than the number of leading zeros in row k. 3. Zero rows appear below the rows having nonzero entries. Lemma 1.7 Every matrix can be brought to a REF using ERO. m;p Constructive proof of existence of REF. Let C = c . ij i=j=1 When we modify the entries of C by ERO we rename call this matrix C 0. Set ` = 1 and i = 1. 1 1. If c = 0 GOTO 3. i` i 1 2. Divide row i by c : R R , (Note: c = 1.) i` i i i` i i c i` i a. Subtract c times row i from row j i:c R +R R for j` j` i j j i i j =i + 1;:::;p. c. If ` =p or i =m GOTO END i d. Set i =i + 1, i.e. i + 1i and ` =` + 1. i i1 f. GOTO 1. 3. Ifc =::: =c = 0, andc 6= 0 for somek,ikm: R R i` (k1)` k` i k i i i GOTO 2. 4. ` + 1` . GOTO 1. i i 9END 2 The steps in the constructive proof of Lemma 1.7 is called Gauss Elimina- tion Here are a few examples of REF. 2 3 1 a b c 4 5 0 1 d e (1.10) 0 0 0 1 Note the REF of a matrix is not unique in general. For example by using elementary row operation of the form Rt R for 1ij one can always i ij j bring the above matrix in the row echelon form to the following matrix in a row echelon form. 2 3 1 0 f 0 4 5 0 1 g 0 : (1.11) 0 0 0 1 2 3 0 1 a b 4 5 0 0 1 c (1.12) 0 0 0 0 Five possible REF of (abcd) (1 4 matrix): (1uvw) if a =6 0; (0 1pq) if a = 0; b6= 0; (0 0 1r) if a =b = 0; c =6 0; (0 0 0 1) if a =b =c = 0; d =6 0; (0 0 0 0) if a =b =c =d = 0: De nition 1.8 Let U = u be an mp matrix in a REF. Then the ij number of pivots is called the rank of U, and denoted by rankU. Lemma 1.9 Let U = u be an mp matrix in a REF. Then ij 1. rankU = 0 if and only if U = 0. 2. rankU min(m;p). 3. If m rankU then the last m rankU rows of U are zero rows. Proof. Clearly, U does not have pivots if and only if U = 0. There are no two pivots on the same row or column. Hence rankUm and rankUp. Assume that r := rankU 1. Then the pivot number j is located on the row j in the column ` . So j 1` :::` p is the column location of pivots, r = rankU: (1.13) 1 r Hence the last m rankU rows of U are zero rows. 2 10Lemma 1.10 LetB be anmp matrix and assume thatB can be brought to a row echelon matrixU. Then rankU and the location of the pivots in (1.13) do not depend on a particular choice of U. Proof. We prove the lemma by induction on p where m is xed. For p = 1 we have two choices. If A = 0 then U = 0 and r = 0. If A6= 0 then U = (1; 0;:::; 0) ;r = 1;` = 1. So the lemma hods for p = 1. Suppose that 1 z m the lemma holds for p =q and let p =q + 1. So B = Cjc where B is mp m matrix and c2R . Let U = Vjv be a REF of B. Hence V is a row echelon 0 form of C. By the induction assumption, the number of pivots r of V and 0 their column location depend only on C, hence on B. If the last mr rows 0 0 of U are zero, i.e. rankU = rankV = r then U has r pivots located in the columnsf1;:::;p 1g and the induction hypothesis implies that the location of the pivots and their number depends only on B. Otherwise C must have 0 an additional pivot on the columnp located at the rowr + 1 = rankU. Again the number of the pivots of U and their location depends only on C. 2 De nition 1.11 Let B be an mp matrix. Then the rank of B, denoted by rankB, is the number of pivots of a REF of B. 1.2.4 Solution of linear systems De nition 1.12 Let A := Ajb be the augmented m (n + 1) matrix representing the system (1.2). Suppose thatC = Cjc is a REF ofA. Assume that C has k-pivots in the columns 1` :::` n. Then the variable 1 k x ;:::;x corresponding to these pivots are called the lead variables. The ` ` 1 k other variables are called free variables. n Recall thatf :R R is called an ane function iff(x) =a x +:::+a x +b. 1 1 n n f is called a linear function if b = 0. The following theorem describes exactly the set of all solutions of (1.2). Theorem 1.13 Let A := Ajb be the augmented m (n + 1) matrix rep- resenting the system (1.2). Suppose that C = Cjc be a REF of A. Then the system (1.2) is solvable if and only if C does not have a pivot in the last column n + 1. Assume that (1.2) is solvable. Then each lead variable is a unique ane function in free variables. These ane functions can be determined as follows. 1. Consider the linear system corresponding to C. Move all the free vari- ables to the right-hand side of the system. Then one obtains a triangular system in lead variables, where the right-had side are ane functions in free variables. 2. Solve this triangular system by back substitution. 11In particular, for the solvable system we have the following alternative. 1. The system has a unique solution if and only if there are no free variables. 2. The system has many solutions, (in nite number), if and only if there is at least one free variable. Proof. We consider the linear system equations corresponding to C. As ERO on A correspond to EO on the system (1.2) it follows that the system represented byC is equivalent to (1.2). Suppose rst thatC has a pivot in the last column. So the corresponding row of C which contains the pivot on the column n + 1 is (0; 1:::; 0; 1) . The corresponding linear equation is of the form (1.5). This equation is unsolvable, hence the whole system corresponding to C is unsolvable. Therefore the system (1.2) is unsolvable. Assume now thatC does not have a pivot in the last column. Move all the free variables to the right-hand side of the system given byC. It is a triangular system in the lead variables where the right-hand side of each equation is an ane function in the free variables. Now use back substitution to express each lead variable as an ane function of the free variables. Each solution of the system is determined by the value of the free variables which can be chosen arbitrary. Hence, the system has a unique solution if and only if it has no free variables. The system has many solutions if and only if it has at least one free variable. 2 Consider the following example of C: 2 3 1 2 3 1 j 0 4 5 0 1 3 1 j 4 (1.14) 0 0 0 1 j 5 x ;x ;x are lead variables, x is a free variable. 1 2 4 3 x = 5; 4 x + 3x +x = 4)x =3x x + 4) 2 3 4 2 3 4 x =3x 1; 2 3 x 2x + 3x +x = 0)x = 2x 3x +x = 2(3x 1) 3x + 5) 1 2 3 4 1 2 3 4 3 3 x =9x + 3: 1 3 1.2.5 Reduced row echelon form Among all row echelon forms U of a given matrix C there is one special REF which is called reduced row echelon form denoted by RREF. De nition 1.14 Let U be a matrix in a row echelon form. Then U is an RREF if 1 is a pivot on the column k of U then all other elements on the column k of U are zero. 12Here are two examples of 3 4 matrices in RREF 2 3 2 3 1 0 b 0 0 1 0 b 4 5 4 5 0 1 d 0 ; 0 0 1 c 0 0 0 1 0 0 0 0 Bringing a matrix to RREF is called Gauss-Jordan reduction. Here is a constructive algorithm to nd a RREF of C. Gauss-Jordan algorithm for RREF. m;p Let C = c . ij i=j=1 When we modify the entries of C by ERO we rename call this matrix C 0. Set ` = 1 and i = 1. 1 1. If c = 0 GOTO 3. i` i 1 2. Divide row i by c : R R , (Note: c = 1.) i` i i i` i i c i` i a. Subtract c times row i from row j =6 i:c R +R R for j` j` i j j i i j = 1;:::;i 1;i + 1;:::;p. c. If ` =p or i =m GOTO END i d. Set i =i + 1, i.e. i + 1i and ` =` + 1. i i1 f. GOTO 1. 3. Ifc =::: =c = 0, andc =6 0 for somek,ikm: R R i` (k1)` k` i k i i i GOTO 2. 4. ` + 1` . GOTO 1. i i END The advantage in bringing the augmented matrix A = Ajb to RREF C is that if (1.2) is solvable then its solution is given quite straightforward using C. We need to use the following notation. Notation 1.15 Let S and T be a subsets of a set X. Then the set TnS is the set of elements of T which are not S. (TnS may be empty set.) Theorem 1.16 Let A := Ajb be the augmented m (n + 1) matrix rep- resenting the system (1.2). Suppose that C = Cjc be a RREF of A. Then the system (1.2) is solvable if and only if C does not have a pivot in the last column n + 1. Assume that (1.2) is solvable. Then each lead variable is a unique ane function in free variables determined as follows. The leading variable x ap- ` i pears only in the equation i, for 1ir =rankA. Shift all other variables in the equation, (which are free variables), to the other side of equation to obtain x as an ane function in free variables. ` i Proof. Since RREF is a row echelon form, Theorem 1.13 yields that (1.2) is solvable if and only if C does not have a pivot in the last column n + 1. 13 Assume that C does not have a pivot in the last column n + 1. So all the pivots of C appear in C. Hence rankA = rankC = rankC = rankA(= r). mn The pivots ofC = c 2R are located at rowi and the column` , denote ij i as (i;` ), for i = 1;:::;r. Since C is also in RREF, in the column ` there is i i only one nonzero element which is equal 1 and is located in the row i. Consider the system of linear equations corresponding toC, which is equiv- alent to (1.2). Hence the lead variable ` appears only in the ith equation. i Left hand-side of this equation is of the form x plus an linear function in ` i free variables whose indices are greater than x . The right-hand is c , where ` i i c = (c ;:::;c ) . Hence by moving the free variables to the right-hand side 1 m we obtain the exact form of x . ` i X x =c c x ; for i = 1;:::;r: (1.15) ` i ij j i j2f` ;` +1;:::;mgnfj ;j ;:::;j g i i ` ` ` r 1 2 (Sof`;` + 1;:::;mg consist of m ` + 1 integers from j to m, while i i i ` i fj ;j ;:::;j g consist of the columns of the pivots in C.) 2 ` ` ` 1 2 r Example 2 3 1 0 b 0 j u 4 5 0 1 d 0 j v 0 0 0 1 j w x ;x ;x lead variables x free variable 1 2 4 3 x +bx =u)x =bx +u; 1 3 1 3 x +dx =v)x =dx +v; 2 3 2 3 x =w: 4 De nition 1.17 The system (1.2) is called homogeneous if b = 0, i.e. b = ::: = b = 0. A homogeneous system of linear equations has a solution 1 m x = 0, which is called a trivial solution. Let A be a square n n. A is called nonsingular if the corresponding homogeneous system of n equations in n unknowns has only solution x = 0. Otherwise A is called singular. Theorem 1.18 Let A be an mn matrix. Then it RREF is unique. Proof. Let U be a RRREF of A. Consider the augmented matrix A := Aj0 corresponding to the homogeneous system of equations. Clearly U = Uj0 is a RREF of A. Put the free variables on the other side of the homo- geneous system corresponding to U to nd the solution of the homogeneous system corresponding toA, where each lead variable is a linear function of the free variables. Note that the exact formulas for the lead variables determine uniquely the columns of the RREF which correspond to the free variables. 14Assume thatU is another RREF of A. Lemma 1.10 yields that U andU 1 1 have the same pivots. Hence U and U have the same columns which corre- 1 spond to pivots. By considering the homogeneous system of linear equations corresponding toU = Uj0 we nd also the solution of the homogeneous sys- 1 1 temA, by writing down the lead variables as linear functions in free variables. Since U and U give rise to the same lead and free variables, we deduce that 1 the each linear function in free variables corresponding to a lead variable x ` i corresponding toU andU are equal. That is the matricesU andU have the 1 1 same row i for i = 1;:::; rankA. All other rows of U and U are zero rows. 1 Hence U =U . 2 1 nn Corollary 1.19 A2 R is nonsingular if and only if rankA = n, i.e. the RREF of A is the identity matrix 2 3 1 0 ::: 0 0 6 7 0 1 ::: 0 0 6 7 nn I = 2R : (1.16) 6 7 n . . . . . . . . 4 5 . . . . 0 0 ::: 0 1 Proof. A is nonsingular if and only if no free variables. So rankA =n and the RREF is I . 2 n 1.3 Operations on vectors and matrices 1.3.1 Operations on vectors Vectors: Row Vector (x ;x ;:::;x ) is 1n matrix. Column Vector u = 1 2 n 2 3 u 1 6 7 u 2 6 7 is m 1 matrix. For convenience of notation we denote column 6 7 . . 4 5 . u m vector u as u = (u ;u ;:::;u ) . 1 2 m The coordinates of a vector and real numbers are called scalars. In these notes scalars are denoted by small Latin letters, while vector are in a di er- ent font: a; b; c; d; x; y; z; u; v; w are vectors, while a;b;c;d;x;y;z;u;v;w are scalars. The rules for multiplications of vector by scalars and additions of vectors are: a(x ;:::;x ) := (ax ;:::;ax ); 1 n 1 n (x ;:::;x ) + (y ;:::;y ) := 1 n 1 n (x +y ;:::;x +y ): 1 1 n n 15n The set of all vectors withn coordinates is denoted byR , usually we will view n the vectors inR as column vectors. The operations with column vectors are similar as with the row vectors. 0 1 u 1 B C u 2 B C au =aB C; . . A . u m 0 1 0 1 u v 1 1 B C B C u v 2 2 B C B C u + v = + := B C B C . . . . A A . . u v m m 0 1 u +v 1 1 B C u +v 2 2 B C B C . . A . u +v m m The zero vector 0 has all its coordinate 0. x := (1)x := (x ;:::;x ), 1 n x + (x) = x x = 0. 1.3.2 Application to solutions of linear systems Theorem 1.20 Consider the system (1.2) ofm equations withn unknowns. Then the following hold. 1. Assume that (1.2) is homogeneous, i.e. b = 0. If x and y are solutions of a homogeneous system thensx; x +y;sx +ty are solutions of this ho- mogeneous system for any scalars s;t. Suppose furthermore that nm. Then this homogeneous system has a nontrivial solution, i.e. a solution x =6 0. 2. Assume that (1.2) is solvable. Let x is a solution of nonhomogeneous 0 (1.2). Then all solutions of (1.2) are of the form x + x where x is the 0 general solution of the homogeneous system corresponding to (1.2) with b = 0. In particular the general solution of (1.2) obtained by reducing A to a REF is always of the following form nrankA X x + t c : (1.17) 0 j j j=1 q := n rankA is the number of free variables. (So q 0.) Here x 0 is obtained by letting all free variables to be zero, (if q 0). Rename the free variables of (1.2) as t ;:::;t . Then c is the solution of (1.2) 1 q j 16obtained by solving the homogeneous system corresponding to Aj0, by setting the free variable t to be 1 and all other free variables be 0 for j j = 1;:::;q. Hence (1.2) has a unique solution if and only if q = 0, which implies that mn. Proof. Consider the homogeneous system corresponding to Aj0. Assume that x; y are solutions. Then it is straightforward to see that sx and x + y are also solutions. Hence sx +ty is also a solution. Suppose now that (1.2) is solvable and x is it solution. Assume that 0 y is a solution of (1.2). Then it is straightforward to show that x := y x is a solution to homogeneous system corresponding to Aj0. Vice versa 0 if x is a solution to homogeneous system corresponding to Aj0 then it is straightforward to see that x + x is a solution to (1.2). 0 To nd a general solution of (1.2) bring the augmented matrix Ab to a REF Ujd. The assumption that the system is solvable means thatd does not have a pivot. Set all free variables to be 0. Solve the triangular system in lead variables to obtain the solution x . The general solution of the homogeneous 0 system corresponding to Aj0 is the general solution of the homogeneous sys- tem corresponding to Uj0. Now nd the general solution by shifting all free variables to the right hand-side and solve the lead variables as linear func- P q tions in free variables t ;:::;t . This solution is of the form t c . It is 1 q j j j=1 straightforward to see that c can be obtained by nding the unique values of j lead variables when we let t = 1 and all other free variables are set to 0. j Finally, x is a unique solution if and only if there are no free variables. So 0 we must have that mn. 2 1.3.3 Products of matrices with vectors 3 Recall the de nition of the scalar product inR : (u ;u ;u ) (x ;x ;x ) =u x +u x +u x : 1 2 3 1 2 3 1 1 2 2 3 3 We now de ne the product of a row vector with a column vector with the same number of coordinates: 2 3 x 1 6 7 x 2 6 7 u x = (u u :::u ) =u x +u x +::: +u x : 6 7 1 2 n . 1 1 2 2 n n . 4 5 . x n 17n Next we de ne the product of mn A and column vector x2R : 2 32 3 a a ::: a x 11 12 1n 1 6 76 7 a a ::: a x 21 22 2n 2 6 76 7 Ax = = 6 76 7 . . . . . . . . . . 4 54 5 . . . . . a a ::: a x m1 m2 mn n 2 3 a x +a x +::: +a x 11 1 12 2 1n n 6 7 a x +a x +::: +a x 21 1 22 2 2n n 6 7 m 2R : 6 7 . . 4 5 . a x +a x +::: +a x m1 1 m2 2 nn n The system of m equations in n unknowns (1.2) a x + a x + ::: + a x =b 11 1 12 2 1n n 1 a x + a x + ::: + a x =b 21 1 22 2 2n n 2 . . . . . . . . . . . . . . . . . . . . . a x + a x + ::: + a x =b m1 1 m2 2 mn n m can be compactly written as Ax = b: (1.18) n A is an mn coecient matrix, x2R is the columns vector of unknowns m and b2R is the given column vector. mn n It is straightforward to see that for A2R ; x; y2R ;s;t2R we have A(x + y) =Ax +Ay; (1.19) A(sx) =s(Ax); (1.20) A(sx +ty) =s(Ax) +t(Ay): (1.21) With these notations it is straightforward to see that any solution of (1.18) is of the form x = x + y where Ax = b and Ay = 0. Moreover if y; z satisfy 0 0 the homogeneous system Ay =Az = 0 then A(sy +tz) =s(Ay) +t(Az) =s0 +t0 = 0: This observation gives a simple proof of Theorem 1.20. 1.3.4 Row equivalence of matrices mn De nition 1.21 Let A;B 2 R . B iss called row equivalent to A, denoted by BA, if B can be obtained from A using ERO. mn Theorem 1.22 Let A;B2R . Then 1. BA () AB. 2. BA if and only if A and B have the same RREF. 18Proof. Since ERO are reversible we deduce 1. Suppose that BA. Use ERO to bring B to A. Now use ERO to bring A to RREF, which is a matrix C. Since RREF is unique it follows that B has C as is RREF. Vice versa suppose that A and B have the same RREF C. First use ERO onB to bring it to C. Now bringC using ERO to A. So we obtained A from B using ERO. 2 2 Vector Spaces 2.1 De nition of a vector space A set V is called a vector space if: I. For each x; y2 V, x + y is an element of V. (Addition) II. For each x2 V and a2 R, ax is an element of V. (Multiplication by scalar) The two operations satisfy the following laws: 1. x + y = y + x, commutative law. 2. (x + y) + z = x + (y + z), associative law. 3. x + 0 = x for each x, neutral element 0. 4. x + (x) = 0, unique anti element. 5. a(x + y) =ax +ay for each x; y, distributive law. 6. (a +b)x =ax +bx, distributive law. 7. (ab)x =a(bx), distributive law. 8. 1x = x. Lemma 2.1 Let V be a vector space. Then 0x = 0. Proof. 0x = (0 + 0)x = 0x + 0x) 0 = 0x 0x = 0x. 2 2.2 Examples of vector spaces 1. R - Real Line. 2 2. R = Plane. 3 3. R - Three dimensional space. n 4. R - n-dimensional space. mn 5. R - The space of mn matrices. 19mn Here we add two matrices A = a ;B = b 2R coordinatewise. ij ij 2 3 a +b a +b ::: a +b 11 11 12 12 1n 1n 6 7 a +b a +b ::: a +b 21 21 22 22 2n 2n 6 7 A +B = 6 7 . . . . . . . . 4 5 . . . . a +b a +b ::: a +b m1 m1 m2 m2 mn mn AlsobA := ba . The zero matrix 0 , also simply denoted as 0, is anmn ij mn matrix whose all entries are equal to 0: 2 3 0 0 ::: 0 6 7 0 0 ::: 0 6 7 0 = 0 = 6 7 mn . . . . . . . . 4 5 . . . . 0 0 ::: 0 SoA =(a ) := (a ) = (1)A and A + (A) = AA = 0; AB = ij ij A + (B). n 6. P - Space of polynomials of degree at most n: P :=fp(x) = a x + n n n n2 a x +::: +a x +ag. The neutral element is the zero polynomial. n2 1 0 7. Ca;b - Space of continuous functions on the interval a;b. The neutral function is the zero function. Note. The examples 1 - 6 are nite dimensional vector spaces. 7 - is in nite dimensional vector space. 2.3 Subspaces Let V be a vector space. A subset W of V is called a subspace of V if the following two conditions hold: a. For any x; y2 W) x + y2 W, b. For any x2 W; a2R)ax2 W. Note: The zero vector 02 W since by the condition a: for any x2 W one has 0 = 0x2 W. Equivalently: W V is a subspace () W is a vector space with respect to the addition and the multiplication by a scalar de ned in. V. The following result is strightforward. Proposition 2.2 The above conditions a. and b. are equivalent to one condition: If x; y2 U then ax +by2 U for any scalars a;b. 20

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.