MATRIX ALGEBRA & APPLS
MATRIX ALGEBRA & APPLS MA 322
Popular in Course
verified elite notetaker
Popular in Mathematics (M)
This 19 page Class Notes was uploaded by Kennith Herman on Friday October 23, 2015. The Class Notes belongs to MA 322 at University of Kentucky taught by A. Sathaye in Fall. Since its upload, it has received 27 views. For similar materials see /class/228134/ma-322-university-of-kentucky in Mathematics (M) at University of Kentucky.
Reviews for MATRIX ALGEBRA & APPLS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/23/15
MA322 Sathaye Notes on Linear Algebra Chapter 1 Spring 2008 Some of the notations below are enhanced versions of the book notations We also include material taught in the course which may be slightly different from the book 1 Conventions A linear equation in variables 11 zn will be assumed to be prearranged as a111 drawn b where the coefficients a1a2 amb are assumed to be numbers or scalers in a eld F If convenient we may also assume parameters involved in these coefficients either by an agreement or by assuming the eld F to having been enlarged to accept them Thus 21 7 3y 5 as well as tr 7 l 7 t2y t2 t 5 may both be accepted as linear equations in z y The rst may also be considered linear in zyt but not the second one E0 Augmented matrix To each linear equation in 11 zn we associate a row vector with n 1 entries a1 a2 an I Given a system of several equations we stack their corresponding rows into a matrix called the augmented matrix of the system of linear equations Sometimes the last column of the augmented matrix is separated by a vertical line to indicate the equality signs but the book avoids this marker We may sometimes add it for convenience 3 Pivots and related concepts We shall make the following formal notations for precision 0 Given a row which has at least one non zero entry its pivot position is the column number of the rst non zero entry in it For a row full of zeros the pivot position is de ned to Thus the pivot position for 0 0 2 0 73 is 3 whereas it is 00 for 0 0 0 0 0 For a matrix we de ne its pivot positions as a sequence of the pivot positions of its rows Thus we see that the pivot positions of the following matrices l 2 0 l 2 0 0 2 0 0 1 5 1 0 0 0 0 0 0 2 7 0 0 7 2 l 7 are respectively 12 2 l 13 200 l Pivots or leading entries For a non zero row its pivot or the leading entry is said to the entry in its pivot position For a zero row we say that the pivot is missing We shall say that a sequence of pivot positions is strict if it consists of a strictly increasing sequence of positive integers which may be followed by 00 repeated some number of times Note that the 00 part may be absent if there are no zero rows and the integer part may be absent for a zero matrix Echelon forms A matrix is said to be in a row echelon form REF provided the sequence of its pivot positions is strict It is said to be in a reduced row echelon form RREF if every pivot is l and moreover it is the only non zero entry in its column Elementary Row operations We shall use the following notations In the following 239 j are different row numbers of a matrix M and c is a number 7 The operation Ri lt gt Rj swaps the ith row Ri with the jth row Rj Sometimes this may be shortened as Pij where P reminds of the word permute All other rows stay the same 7 The operation Bi 7 ch modi es the row Ri by adding 5 times Rj to it All other rows stay the same 7 lf 5 f 0 then the operation cRi replaces the ithe row by 5 times itself All other rows stay the same 4 The main use of elementary operations is that if M is an augmented matrix of a system of linear equations then the set of solutions of the system transformed by elementary row operations is the same as the original Thus the main idea of solving systems of linear equations is to transform the associated augmented matrix into a form which lets us simply read off the solutions This is exactly the RREF As an intermediate step we also discuss a form from which the nal solutions can be quickly deduced rather than read off This is the REF We shall discuss the algorithm to derive these forms next 5 The Gauss Elimination Here are the steps of the Gauss Elimination algorithm Convention and notation We will be working with the active part of a given matrix M and reduce it to to REF in a sequence of steps At the beginning7 the whole matrix is active and as we proceed7 we shall declare certain rows and columns inactive This means then that they are not used in further pivot calculations Also7 any further row transformations will be such that they do not change the inactive rows Main Lemma Consider non zero rows Ri7Rj with i f j Suppose that Ri7Rj have the same pivot position and that their pivot entries are respectively chef Then the operation Rj 7 fRi produces a new jth row whose pivot position is bigger than that of Bi Moreover7 suppose that the pivot position of Bi is less than or equal to that of Rj for each j gt i then repeated application of the Lemma gives that the pivot position of Bi is strictly less than the pivot position of all the new rows Rj with j gt i This transformation leaves all the rst 239 rows unchanged 0 Start Assume that the whole matrix is active 0 Cleanup If there is no active row left7 then go to the end Otherwise7 suppose that Ri is the rst active row By swapping it7 if necessary7 with some Rj with j gt i arrange that the pivot position of Bi is less than or equal to all the pivot positions of Rj for j gt i o If Ri is the zero row7 then clearly all the rows Rj with j gt i are also zero Declare all rows inactive and go to end Otherwise7 apply the Main Lemma to arrange that the pivot positions of all Rj with j gt i are bigger than the pivot position of Bi Note that this does not disturb the inactive part 0 Set the Ri as inactive Go to the Cleanup step 0 End Note that the pivot positions of the inactive matrix always stay strict and hence we end up with an REF when the whole matrix becomes inactive 533 When the matrix is in REF7 the pivot positions is an increasing sequence of positive integers followed by a sequence of 00 Of course7 either of these can be empty The number of nite pivot positions in the REF is called the rank of the matrix It does not depend on the process used to get the REF This invariance will be proved later Starting with REF7 it is possible to get the reduced form RREF as follows 0 First make all pivot entries equal to l by dividing the corresponding pivot rows by the pivot entries Explicitly7 if Ci is the pivot entry in Ri then use the operation 0 i 0 Note that REF implies that all entries below a pivot are already 0 Use the cleanup operations to make all entries above each pivot using the pivot entry 1 This may be described as cleaning the pivot column This cleaning is best done in reverse order7 ie cleaning the columns with pivots from last to the rst 00 Vectors We de ne 99 to be the set of columns of n tuples of real numbers This 99 can be also given a geometric interpretation by thinking of the n entries as the n coordinates of points in an n dimensional space For 1 E 99 we shall make the convention that vi is the ith entry of v for i l7 n Thus if n 2 and 75 vlt 6 gt7thenv175 andv26 The set 99 has a natural addition de ned by componentwise addition Thus 1 vi wi There is also a scalar multiplication so that for any 5 E 9 and v E 99 we have 51 de ned as a vector with 0101 cvi There is a natural subtraction v 7 w which is realized to be the same as v 70w 1 1For those who know these terms we state The addition is commutative and asoociative the scalar multiplication is associative with respect to scalars Cd39u cd39u Also the addition is distributive over the scalar multiplication Addition has an identity namely the zero Vector with all zero entries and thus the addition operation makes an additive group The scalar multiplication also has a multiplicative unit 1 such that 11 1 for all 1 Later any set with operations having such properties will be declared as an abstract Vector space H Members of 99 are called vectors and geometrically may be thought of as an arrow pointing from the origin towards the point whose coordinates are the n entries of the column 1 2 In general an arrow from a point Pa b to a point Qc d can be identi ed with the vector corresponding to Q 7 P For example when n 2 a column lt gt describes an arrow from the origin 00 towards the point 12 1 c 7 a name y d 7 b For convenience we may say that the point Pa b is associated with a vector W lt i Then the addition can be given a geometric interpretation thus Given vectors 1 w associated with the points P Q let 0 denote the origin Then the vector v w is associated witb a point R such that OPRQ is a parallelogram A vector 51 is associated with a point P1 on the line joining O and P such that the distance 0P1 between 0 and P1 is lclOP Moreover if c gt 0 then P P1 lie on the same side of 0 while they lie on the opposite sides if c lt 0 New Perspective on Linear Equations Given vectors v1 vr in 9 we de ne a linear combination of them to be a vector of the form 51111 52112 crvr Collectively we de ne the span Spanv1 vT 01111 C2v2 crvr l 5102 CT 6 In this notation it is easy to see that given an augmented matrix Alb belonging to a linear system of equations in 11 17 we can say that the system of equation is BasicEquation zlAl z2A2 zTAT b where A1 A2 AT are the columns of the matrix A They are members of 99 if A has n rows In other words solving the system of euuations is the same as expressing b as a linear combination of A1 AT In other words the system has a solution iff b is a member of the SpanA1 AT If X denotes the column of T numbers 11 zT then it is a member of 9 We de ne AX to be the left hand side of the above basic equation Thus given a matrix with n rows and T columns we say that for a column X the product AX is de ned iff X has exactly T entries In other words as a matrix X has T rows and 1 column More generally if B is any matrix with T rows and 8 columns B1 B2 B5 then we de ne the product AB The matrix with columns AB1AB2 ABS Thus the resulting matrix AB has n rows and 8 columns Note that for AB to make sense the number of columns of A must be equal to the number of rows of Applications to solutions of systems of equations We know that given a system Alb where A has n rows and T columns we can say that 0 Consistency condition The system has a solution iff when put in REF every pivot is in one of the rst T columns This condition is the same as saying that the rst non zero entry in a row does not occur on the right hand side of our equation 0 Uniqueness condition Assuming that the system is consistent it has a unique solution iff there are no free variables Equivalently the number of pivots in REF equals the number 7 Using this we have two very simple yet powerful conclusions In expanded form we write our system thus 11 A i b or 11A1ITATb H where A1 AT are the columns of A in order Suppose d is the number of pivots in an REF of A Note that we are not including b in the calculation of this number We shall write TankA d This will be proved to be independent of our choice of row transformations later If d n then the consistency condition is satis ed regardless of the right hand side In other words every vector in 99 is in the span of columns of A Proof Reduce Alb to REF We have d n pivots so every row ofthe REF has a pivot on the left hand side of the equation Thus the system is consistent regardless of what b is Hence evary b E 99 is in the span of columns of A If d T then there are no free variables Thus either the system is inconsistent or it has a unique solution Proof Evident Now assume T n ie the matrix A is square Then we have two possible cases Either d T n or d lt T n In the rst situation we get to claim that Alb has a unique solution for all b Naturally such matrices A are important They are called non singular or invertible We can make a formula for the solution of Alb for such matrices In the second situation depending on b either the system has no solution or in nitely many The matrix A is said to be singular in such cases Matrices as Linear Transformations Given any map T 9 A 9 we say T is a linear transformation if the following conditions hold TX Y TX TY and TkX kTX where X Y are any vectors in 9 and k is any real number The simplest example of a linear transformation is obtained when we take a matrix A with n rows and T columns De ne TX AX for any X E 9 the two properties are easily veri ed by de nition of the matrix multiplication Conversely it is possible to prove the following Theorem Given any linear transformation T 9 A 9 there is a well de ned matrix A such that TX AX for all X Proof First we prepare some useful notation We de ne a sequence of vectors ei e as follows For each i l2 has only zero entries except for one 1 in the ith place n we de ne e to be the vector which Thus for example when n 3 we have 1 0 0 6i 0 eg 1 eg 0 0 0 1 Similarly when n 2 we have 1 q0 Important shortened notation Often it is tedious to keep on writing the superscript for these mm H H O So we may simply write 61 62 63 in place of 6 63 6 if we know that we are working in 993 Similarly we will simply use 61 62 in place of 6 6 if we are working in 992 If we are working with two different spaces at the same time then we nd it convenient to give new names to these We will say that ee eZ is a standard basis of 9quot Important Observation Every X can be uniquely expressed as me Inez In Thus for example when n 3 using shortened notation we get 11 I2 1161 1262 1363 13 Now consider the standard basis 61 en of 99 in shortened notation Construct a matrix A Whose columns are Tel Ten in order We claim that TX AX for all X E 9 Note that X1161zn6n and by the de nition of a linear transformation we see that TX 11Tel znTen But the right hand side of the last equation is exactly 11 A i AX This proves our claim It is easy to see that if matrices AB satisfy AX BX for each X E 9 then A B Hint Take X to be successively 61 en and deduce that A and B have identical columns Thus it makes sense to make CorollaryDe nition The matrix A such that TX AX is uniquely de ned by T and is de ned to be the standard matrix for the linear transformation T We use the notation MT to denote the matrix A Example Suppose T 9 A 993 is de ned by I 211I2 TltltI1gtgt 1712 2 311512 Then 1 2 61 lt 0 gt and hence Tel l 3 Similarly 0 l 62 lt gt and hence T 2 fl l 5 Thus 2 MT 1 71 3 It is easy to verify that 2 l 2 TltI1gt 171 lt11 or TX 171 X 12 3 12 3 12 Properties of Linear Transformation H Let T be a linear transformation from 99 to 9 as before We shall de ne T to be surjective if it is an onto map This means that every I 6 9 can be written as TX for some Xi Thus if A is the standard matrix MT then this is equivalent to the condition that Alb is consistent for all 12 From what we already observed the condition for surjectivity is thus d T where d TankAl Note that the number of pivots in an REF of any matrix has to be less than or equal its number of rows as well as its number of columns since different pivots are in different rows and differnt columnsl Hence TankA d S minn T In particular we note that if n lt T then d S minnT lt T and the map cannot be surjectivel Note that we need to do extra calculations if n T We also de ne T to be injective if it is one to one as a map This means if TX TY then X Y As before using the standard matrix A MT we see that TXTY iff AXAY iff AX7Y0 where the matrix 0 by convention is the matrix with all zero entries or the so called zero matrix Thus setting X 7 Y Z we can reformulate the condition of injectivity as AZ 0 implies Z 0 This means that the system AlO always has a unique solution 0 or as discussed before in REF there are no free variablesl From what we already observed the condition for injectivity is thus d n where d TankAl As before we can deduce that if n gt T then d S min nT lt n and thus the map T is not injectivei As before the case n T needs further evidence l Independence of vectors Given T vectors v1 vT in 9 we de ne them to be linearly dependent if 11111 Invn 0 for some 11 In such that at least one of the 11 is non zero If we build a matrix A with columns v1 vT then this condition is seen to mean that the linear system described by AlO has a non zero solutionl Thus the system must have more than one solutions since setting all 11 0 is an obvious solution From what we already know this is equivalent to TankA lt T or the linear transformation de ned by TX AX is not injectivei We may simply write vb vT is a linearly dependent set if this condition is satis ed It can be shown that the condition can also be expressed by saying that one of the vi is a linear combination of the rest The idea is to note that if 11111 zivi1TvT 0 and Il 7 0 then we can write where vi does not appear on the right hand side Moreover by choosing the last i with 11 7 0 we may even make a stronger looking claim that vi is a linear combination of v1 1571 These descriptions are useful when we are trying prove properties of linearly dependent vectors The set of vectors vb vr is de ned to be linearly independent if it is not linearly dependents Equivalently the rank of the corresponding matrix A with columns vi equals T or that the associated transformation T is injectivei Here are some simple observations that can be made from these de nitions Let S be the set of vectors v1vr in 997K o If one of the vectors v1 vT is the zero vector then the set S is linearly dependenti If one of the vi is a multiple of another vj then the set S is linearly dependenti If one of the vi is a linear combination of some other members of S then the set S is linearly dependenti If a subset of S is linearly dependent7 then S is linearly dependenti If 7 gt n than S is linearly dependenti If S is contained in a linearly independent set of vectors 51 then it is linearly independent MA322 Sathaye Notes on Vector Spaces 081008 Here is a summary of concepts involved with vector spaces 1 Vector Space A vector space over a eld k is a non empty set V together with a well de ned addition UH and a scalar multiplication 9 by elements of the eld 16 satisfying the following axioms 0 Operations For all u v E V and c E k we have u v E V and cu E V Sometimes we write 5 u but this is often omitted 0 Addition properties The addition is commutative uv vu and associative uvw uvw o Additive identity and inverse There is a zero vector denoted 0 such that u 0 0 u u for all u Moreover for each u there is a uquot such that u uquot 0 The uquot can be shown to be uniquely de ned by u and is denoted as iu The zero vector is also shown to be unique 0 Distributivity and unitariness The two operations interact naturally Cu v cu 51 0 du cu du cdu Cdu Moreover 1u u for all u In this course the eld k is usually 9 the eld of real numbers In that case we drop the phrase over the eld 99 to Subspace If V is a vector space over k and W is a non empty subset then we say that W is a subspace of V if we have 0 For all 101102 6 W we have wl WQ 6 W o ForallcekandwEWwehavecwEW We note that the vector 0 will always belong to a subspace as soon as it is non empty since w E W implies 0w 0 E W by the second subspace condition above Hence you may replace the condition of W being non empty by the simpler condition 0 E W as done in the book 9 A challenging example Here is an exotic example of a vector space which should be studied to verify your understanding of the above definition Let V 9 be made into a vector space over the usual eld of real numbers 9 as follows 0 We define a new addition 69 on V by the formula 1 69 w v w 7 1 where the operations on the right hand side are the usual operations in real numbers 0 We define a new scalar multiplication D by 9 on V by the formula c G v 51 l 7 c where as before the operations on the right are the usual operations in real numbers It is instructive to verify all the axioms from these de nitions You should also identify what 71 means This example should be kept in mind while analyzing all the following concepts You should also make an enhanced version of this example by taking V to be 99 as the set but using the above de nitions of addition and scalar multiplication suitably generalized 1Can you make other examples of such weird operations Here is a general hint and secret of all such constructions Let V be any vector space over a eld k Let 1b be any bijective map of V to itself De ne a new vector space W which uses the same V as an underlying set but de nes operations as follows wi 69 m 1 w1 w2 and sew wilcwwv It can be shown that W is a vector space isomorphic to V which means essentially the same as V See below for explanation of isomorphic Can you guess the 1b for the displayed example 4 A Universal example Let S be any non empty set and consider F33 S A k l where 0 for all except nitely many 8 E S It can be shown that every vector space can be described in this manner but nding such an explicit S can be tedious and it is better to use the basic de nition If k 9 we may drop it from the notation It is easy to verify how F1 is a vector space by de ning gs 98 and cfs cfs The extra condition on f is not necessary but it is essential if you want to claim that every vector space has a standard structure 5 Basic examples Here are some of the standard examples 0 Euclidean spaces The space 16 consisting of all ntuples of elements of 6 usually written as a column This can be described as F15 where S is the set 1 2 3 n A typical function f in the vector space may f 1 be displayed as This leads to the usual notation for k fn o The case of an in nite S If we take S l2 n the set of natural numbers then we nd it convenient to display f 6 F5 as f1 f2z f312 fn 1z Note that the description of F5 implies that after some large enough exponent N the coef cients are all zero and we have a set of polynomials The book denotes F by the symbol IR A general notation for F3 is also Hz which is the ring of polynomials in z with coef cients in k where we have chosen to ignore the usual multiplication of polynomials We now note that if we keep the same set S 1 2 n but drop the special condition on functions we get a much bigger set name y H f S A Is As before any such f E H be displayed as f3x2 fn Dz Since there is no special condition on the function we now get power series The general notation for this set is k 1 the ring of power series in z with coef cients in k where as before we ignore the usual product of power series It can be shown that H F713 for some convenient set T but nding such a T is a dauting taskl There is also a well known subset of H when k 9 namely the set of convergent power series To write it as F is an even more daunting task 6 Basic structures in a vector space Now let V be a kvector space ie vectore space over a eld k Foe any subset A C V we de ne its span Span A 51111 cmvm where Ci 6 lav E A and m is some non negative integer Note that Span A can be described as the set of all possible linear combinations of elements of A Note that even when A is in nite we only allow nitely many elements of it at a time Also note that m is allowed to be zero and it gives the combination 0 by a standard convention We say that a set A spans V or is a spanning set for V if Span A V A subset A C V is said to be linearly dependent if there are elements v1 Um E A such that 51v1 cmvm 0 for some cl cm 6 k with at least one non zero element c among them In application other convenient forms of this condition are used One such version is A subset A C V is said to be linearly dependent if there is some 1 E A such that v is a linear combination of some elements wl wr E A which are distinct from v A compact way of saying this is to write that v E Span A A set A C V is said to be linearly independent if it is not linearly dependent We often drop the word linearly from these terms A subset A C V is said to be a basis of V if Span A V and A is linearly independent We say that V is nite dimensional if it has a nite basis The number of elements in a basis is said to be the dimension of V We write dim V or dimk V if we wish to identify k We will soon argue that the dimension is a well de ned number for any vector space ie every basis of a vector space has the same number of elements However for in nite dimensional spaces we need to make a ner notion of cardinality which distinguishes between different in nite sets 7 Homomorphisms Isomorphisms and Automorphisms Given kvector spaces VW a map T V A W is said to be a linear transformation if it satis es these two conditions 0 Tv1 112 Tv1 Tv2 for all v1v2 E V o Tcv cTv for all c E k and v E V We may also use the term homomorphism meaning similar structure to denote such a map There are two concepts associated with the notion of a linear transformation homomorphism First is the image of T which can be formally denoted as TV Tv l v E V Second is the Kernel of T which can be de ned as KETT UEV Tv0 It is easy to verify that both the Kernel and the Image are respectively subspaces of V and W The homomorphism T is injective or one to one 77 iff Ker T 0 where we have used a slightly abused notation 0 in place of This abuse is routinely done The homomorphism T surjective or onto if TV W ie W is its total image The homomorphism T is said to be an isomorphism if it is both injective and surjective ie bijective The word iso denotes sameness and the concept says that the two vector spaces with an isomorphism mapping one to the other are essentially the same They can be treated as replacements for each other in analyzing their properties An isomorphism of V to itself is called an automorphism 8 A Fundamental Theorem This is the fundamental theorem in the theory of vector spaces Let V be a vector space with a spanning set A Then there is a subset B of A such that B is a basis of V We shall give a complete proof in case A is nite and a partial proof in case A is in nite Proof If A is independent then it is a basis and we are done If A is dependent then there is some vector v E A which is a linear combination of vectors in A1 A v We now claim that Span A Span A1 by the following argument Proof of Claim Note that any w E Span A can be written as w 51 wl where c E k and wl E Span A1 By assumption 1 E Span A1 so 51 and hence w belongs to Span A1 Thus Span A C Span A1 Clearly Span A1 C Span A since A1 C A This shows Span A Span A1 2Two sets A B are said to have the same cardinality if there is a bijective map from A to B As the example of the sets 1 2 13 n and 2 46 2n shows a set can have the same cardinality as a proper subset This suggests that one has to be very careful in dealing with in nite cardinalities Thus if V Span A and A is dependent then we get a proper subset A1 of A such that V Span All We can now apply the same argument to A1 and either get a basis or a smaller spanning set Agi In case A is a nite set to begin with this cannot continue inde nitely and we must get a basis at some stage We remark that we may run into an empty subset of A in case the vector space is the zero space However in this case the whole set A can only be 0 or empty and we have nothing to argue It is also possible to do the above proof in a reversed process We can start with independent subsets of A and enlarge them as much as possible We argue that eventually we should get a basis In case the set A is in nite we need a more general inductive principle called Zorn s Lemmai The proof proceeds by building a maximal subset A of A with the property that A is itself independent but any set bewteen A and A is dependent Then it is easy to see that A is itself a basis for Span A Vi 3 50 Coordinates Let V be a vector space with a basis Al We show that V is isomorphic to F2 Note that by the de nition of the basis every vector w E V has a unique expression w 51111 crvr for some v1vrEAandclcrek For any 1 E A we de ne the vcoordinate of w with respect to A by the formula wvA Ci if v vi and 0 if v is not among the v1 vri Now we de ne the map 39i39 V A F by WK wvA It is not hard to see that this is indeed an isomorphism The main trick is to note that from the de nition of FIX given any f E F we can see that the element w veA fvv is a well de ned member of our vector space Span Al Our de nition of 39i39 makes w This shows surjectivityi lnjectivity is obvious Thus we have shown why every vector space is essentially of the form F3 for some set S O i Dimension formulas The next important result in vector spaces is that any basis of a vector space has exactly the same number of elements interpreted as the same cardinality for in nite bases i This number is the dimension of the vector space We only describe the argument when we have one nite basis Let A B be two bases of a vector space V where A consists of n vectors We shall construct a sequence of bases A0 A1A2 An such that A0 A but An C B and each Ai has exactly n of elements Now since An is a basis and contained in the basis B it must be equal to B thus B has n elements as we r We shall arrange our Ai to have at least their rst 239 elements coming from B and we shall prove this by induction on ii Thus the case i 0 is clear since A0 A satis es the condition Assume that 0 lt m lt n and we have Am with its rst m elements in B Let V1 be the span of the rst m elements of Ami Clearly V1 is strictly smaller than V since otherwise the basis Am would be contained in V1 making it dependenti Now by the same reasoning we must have at least one vector w E B which is not V1 and let us write it as a combination of elements of Am say w u v where u is a combination of the rst m elements of Am and v of the remaining elements of Ami Now 1 f 0 for otherwise the independence of B is contradicted Consider Am1 Am where vi is one of the vectors appearing the combination of vi It is easy to see that m1 is a new basis with m 1 elements from B namely w and the rst m elements of Ami We shall make them the rst m 1 elements of Am1i We are thus nished by induction Now we come to the most useful theorem in dimension theory of vector spaces 3The idea of this proof is as follows Suppose we have a subset Aquot of A which is independent but which is maximal in the sense any bigger subset of A containing Aquot is dependent In this case it is not hard to see that Span Aquot Span A Thus Aquot is the desired basis H Theorem Let T V A W be a surjective linear transformation of vector spaces Then dimV dimW dimKer Ti Proof Select a basis A1 of Ker T and a set A2 such that TA2 gives a basis of Wi This is done using the surjectivity of Ti Now it is possible to argue that A A1 U142 is a basis of Vi Here is the outline First show that Span A Vi Let 1 6 Vi Then Tv E Span TA2i Thus we have ug E Span A2 such that Tv Tu2 or v 7 ug ul 6 Ker Ti Then ul 6 Span A1 and thus 1 ul ug is in Span A1 UAgi The independence of the set A is argued thusi Suppose some non trivial combination of elements of A is zero Write the combination as ul ug 0 where ul 6 Span A1 and ug E Span Agi Taking the image by T we see that Tu1 u2 Tu1 Tu2 0 Tu2i Since TA2 is a basis of W we see that Tu2 is a trivial combination and hence ug is also a trivial combinationi Thus ug 0 From independence of A1 it follows that ul is also the trivial combination Now note that A1A2 are disjoint sets since otherwise a basis of W will contain a zero vector the image of a common element Hence for nite dimensional V we get that the number of elements of A equals the sum of the number of elements of A1 and A2 This proves the formula Note Our proof did not use the nite dimensionality of the vector spaces It is needed only to count the elements of A as those of A1 and those of A2 i Connection with kni Consider a nite dimentional kvector space V and a basis B which we write as a formal vector of vectors in Vi We construct a map V A k as follows Given 1 clvl cnvn E V we shall write The resulting vector shall be called the coordinate vector of v with respect to the ordered basis Bi This is best remembered by a natural identity 1 BMB This is to be interpreted as the usual product of a row with a column generalized for our vector entriesi lfCw1 wn is also a basis of V then we get the identities wi Blw1l37 39 39 39 7wn BlwnlB and putting these together we may write E0 The matrix 101 wnlg is a transformation matrix between bases B and C and may be conveniently denoted as 133 Thus we have a suggestive notational display 0 BPBCT It can be imagined that the B at the foot of PE cancels B and leaves us C Now we use this to compare the B and C coordinates for the same vector in v 6 Vi Note Blle v Clvlc BPBClvlo Comparing the rst and the last terms we see Matrix of a transformation Finally7 we make the matrix for a transformation T V A W where we have chosen speci c bases B for V and C for Wi We can write TB CM for some matrix M which is constructed as follows Let the vectors in B be v1 v2 41m in order and write wl Tv1 wm Tvmi Then the i th column of M is simply the Ccoordinate vector of wi ire Tvici Thus we see that TB Tv1 Tvm CMi For 1 E V we see that v EM and hence Tv TBUB so that TW TBlle CMlle and this shows that Two MMB This shows that on the coordinate level7 the map T is simply a multiplication by Mr This imitates the work in 997K MA322 080930 Matrices Special matrices Notes on Chapter 2 We begin by de ning addition scalar multiplication and product for matrices A matrix A is an m gtlt n array of numbers also called scalars with some convention and we say m r0wnumA or number of rows of A and n colnumA or number of rows of A We make a convention to write A Amm to indicate these numbers and say that A has type or size m gtlt n In general for a given matrix A7 we write AM for the entry in its 2th row and jth column Naturally7 we assume 1 S 239 S r0wnumA and 1 S j S colnumA This is sometimes written as Azj if the expressions for m are complicated or if subscripts are inconvenient Given two matrices AB7 we de ne A B only if they have the same type and then A B def AM Bij The resulting matrix has the same type as either of them Given a matrix A and a scalar 57 we de ne 5A by 8AM def 5AM and this has the same type as A Given matrices AB we de ne the product AB only if colnumA r0wnumB If this common number is 717 then we have ABlj def Z AikBkj where 1 S 239 S r0wnumA and 1 S j S colnumB k1 Note that AB 31 BA in general In fact it is possible that AB is de ned but BA is not Even when both are de ned7 they may have di erent sizes By 0 we denote a zero matrix or a matrix with all entries zero These matrices can be of di erent sizes7 but the same symbol is used and the size has to be deduced from the context By I we denote the identity matrix which is de ned by By convention I is always a square 71 gtlt 71 matrix and we may identify the size by writing I In The important property of the Identity matrix is that AI A and IB B for any matrices AB provided the equations make sense ie the I has appropriate size Elementary matrices Diagonal Matrices Permutation matrices Let p 71 q be chosen with 1 S pq S 71 Let c be a numberscalar De ne a square 71 gtlt 71 matrix Eqc by 0 The entry in the p th row and q th column is c o The entries along the main diagonal are 1 These are respectively the 11 22 7171 entries 0 All other entries are zero Thus using 71 3 we get 10 0 10 4 10 0 17332 0 1 2 Ef 34 0 1 0 E 15 0 1 0 0 01 0 01 5 01 Note An easy way to remember these matrices is this To understand Eqc start with the identity matrix In and perform the row operation Rn ch on it Convention To simplify the notation we often drop the superscript n It is also customary to drop all notation and simply name them as E1 E2 etc after having identi ed each This is what the book does We will have need to use matrices for which all entries off the main di agonal are zero These can be identi ed by just specifying the diagonal entries and we write them as d2agcl 02 Cn For example 1 0 0 2 0 0 d2ag113 0 1 0 dz39ag222 0 2 0 0 0 3 0 0 2 Note that d2ag222 is also equal to 2I3 2dz39ag111 but in gen eral you cannot simply a diagonal matrix if the diagonal entries are different However it is easy to see that the matrix d2agcl02cn can be also constructed by starting with the identity In and multiplying its rows successively by 0102 cn Let 239 71 j be chosen with 1 3 27 3 n We de ne the matrix P by swapping the 24th row of In with its j th row Thus HOOD OOHO OHOO OOOH 100 P233 00113144 010 As before we drop the superscript 71 when convenient Voodoo Principle lnve rses An important principle of working with matrices is what I like to call the voodoo principle Row operations If you wish to do something to the rows of a matrix M do it to an appropriate In which has the same number of rows as the matrix M and multiply by the result on the left of A Here are some examples The reader should check all the details Let 1 M2 3 gt4gtOOIO If you wish to swap its rst two rows then multiply it by 13132 Thus you can check szM WHM 3 2 4 To perform R2 7 2R1 multiply by E 172 To multiply the third row by multiply by diag1 1 To make the sum of all three rows multiply by lt 1 1 1 Column operations You can make column operations by the same principle Take an iden tity matrix with the same number of columns as the given matrix and do the operations on it Then multiply by the result on right of A Thus to swap the columns of the above matrix M calculate M13122 Similarly the operation 027201 can be carried out by right multiplying by the matrix T Note that this matrix is E12272 Do note how the row and column notations differ in the notation for the E matrices Do consider the effect of left multiplying by diag1 2 3 and right mul tiplying by diag1 2 A matrix A is said to be invertible or non singular if 0 A is a square 71 gtlt 71 matrix and 0 There is some matrix M such that MA I I Note that by de nition of matrix products M must have type 71 gtlt n In view of our observation of the voodoo principle we see that our usual sequence of row operations can be accomplished by left multiplying by a product of matrices which are elementary diagonal or permutation matrices Note that we do not allow 0 in our diagonal matrices Finding lnverses Thus7 if A is a square matrix of rank 717 then its RREF will be In and we can take M to product of the row transformation matrices Conversely7 we now show that an invertible matrix A must have rank 71 If AX B is a system of linear equations and A is invertible7 then we see that MAX MB or InX MB7 so that X B Thus the equation AX B is solvable for all B 6 3 We know that this implies that A has rank n Thus7 we have shown that a square matrix A Anxn is invertible if and only if A has rank 71 Note It is possible to weaken the idea of invertible by talking about left or right invertible by de ning One sided invertibility A matrix H Hngtltn is said to be left invertible if GH In for some matrix G which has to be of type 71 gtlt The matrix H is said to be right invertible if there is a matrix K such that HK Im Note that necessarily K has to be type 71 gtlt m Let r be the rank of H It can be shown that H is left invertible if and only if r n Similarly7 H is right invertible if and only if r m Given a square matrix A Angtltn7 the standard method to decide if it is invertible is this Start with an augmented matrix AlIn Perform row operations lead ing to RREF of A If you get a zero row on the A side7 then A is not invertible as its rank would be less than n Otherwise7 the RREF of A must be In Thus AlIn transforms to InlM for some matrix M Since we know that all the row operations can be accomplished by left multiplication by some matrix7 we know that the matrix used must be M7 so MAlMIn7 ie MA In At the same time7 we can visualize AlIn as a system of equations AX In where X is now an n gtlt 71 matrix Multiplying by M we see MAX MIn or InX M ie X M Thus we have shown that MA In implies AM In as well So7 an invertible matrix is both left and right invertible7 using the same matrix M Thus7 it makes sense to de ne Inverse of a matrix If A is an invertible matrix7 then the matrix M for which MA AM In is uniqely de ned and we call it the inverse of A It is denoted by A l Special lnverses What is the proof of uniqueness Suppose we have two different matri ces M1 M2 satisfying equations Think of MlAMg By grouping these terms differently M1AM2 MlAM2 M1AM2 it is easy to see that the product is equal to M1 as well M2 Hence M1 M2 lnverses of some special matrices can be calculated easily and should be remembered Each is easy to check by direct calculation or better by interpreting it as a row operation All are invertible with inverse A diagonal matrix diagcl02 0 is invertible if and only if none of the c are zero Then the inverse is diagcf1c 1c1 P is its own inverse Thus Pg I In general matrices whose powers are equal to identity are called unipotent lf AB are invertible of the same type then AB is invertible and its inverse is B lA l Notice the change of order it is crucial This extends to a sequence of invertible matrices as well A1A2 As 1 A1A2 1A1 1 a Fora2gtlt2matrixAltC 2 gt we set A ad 7 be its deter minant Then A is invertible if and only if A 31 0 and the inverse when i i 1 d 7b A7 01sg1venbyZltiC a General square matrix A Later we shall de ne the determinants of arbitrary sizes and develop the following test for invertibility Matrix A Amm is invertible if and only if its determinant detA A is non zero Moreover there is a matrix Audi called the adjoint of A which can be calculated by several subdeterminants of A and the formula for the inverse will be iAadj this is of great theoretical interest but often the row reduction method is more practical In fact calculation of determinants is also made ef cient by row transformations and hence it is not faster to calculate the adjoint from de nition Determinants have a product formula detAB detA detB This coupled with the above test for invertibility gives us the result that a product of square matrices is invertible if and only if each is Challenge 1 Given that AB has an inverse M say what are the inverses of A and B Make a formula in terms of AB M Challenge 2 Assume that A1 AT are square matrices of the same type Given A1A2 A1A I prove that A2 AT1ATA1 I LU decomposition Suppose a matrix A is such that its REF can be obtained without swapping rows Then the elementary matrices used to reach the REF are of a special form called lower triangular We de ne a square matrix to be lower triangular if all the entries above the diagonal are zero If in addition all the diagonal entries are 1 then it is said to be a unit lower triangular matrix An upper triangular and unit upper triangular matrix are de ned simi larly All elementary matrices are evidently unit lower triangular ifz39 lt j Of course ifz39 gt j then they are unit upper triangular A little thought can show the following o If L1 L2 are lower triangular matrices of the same type then so is their product Ditto for upper triangular Further if L1L2 are unit lower triangular then so is their prod uct Ditto for upper triangular Thus if A can be put into REF without swapping rows then we can say that L1A is in REF for some unit lower triangular matrix L1 The matrix L1 is a product of unit lower triangular matrices used in our operations Also it is clear that the nal REF must be upper triangular Follows from the de nition of REF think about it Thus we may denote L1A as U to denote an upper triangular matrix Note that this U need not be unit upper triangular unless our matrix was invertible to begin with Thus our row reduction algorithm proves L1A U or A LU where L Lfl This factorization is used in ef cient solutions of systems especially of large size Moreover the calculation of the matrix L does not need any additional work it is a matter of simply recording the multipliers used in the right spots We shall discuss this in detail later