MATRIX ALGEBRA & APPLS
MATRIX ALGEBRA & APPLS MA 322
Popular in Course
Popular in Mathematics (M)
This 9 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 33 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 Satrage Notes on Linear Algebra Chapter 1 Fall 2009 Summary of topics by section 11 Convert a system of linear equations to an augmented matrix and back Solution set of a system of equations Elementary row operations and de nition of row equivalent matrices related by elementary row operations The two fundamental problems existence and uniqueness of solutions The 0100 principle The mechanism of the Gauss Jordan elimination Calculating REF and RREF using proper notations Pij R 613ka Calculating solution from REF backsubstitution or reading off the solution from RREF Vectors7 3E de nitions of linear combination and Span De nition of matrix product AX where X is a column vector7 or more generally a matrix of appropriate size Interpretation of a linear system as an equation AX B Condition for AX B being solvable for all B in terms of rank of A or ColA Consistency condition Linearity of the map X a AX AX 0 has a non trivial solution iff rank of A is less than the number of its columns colnumA Solution set of AX B has the form X pvh where p is some single solution of AX B and Uh is any solution of AX 0 Setting up and solving practical systems De nition of linear dependence and independence of vectors Calculations using REF Linear transformations De nition and construction based on desired properties Matrix of a linear transformation 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 E0 Conventions A linear equation in variables 1739 zn will be assumed to be prearranged as a l anzn b where the coef cients a1 a2 7a 7 b are assumed to be numbers or scalers in a eld F These 77numbers77 may be allowed to have a few parameters Thus 2x By 5 as well as tz 1 7 HM t2 t 5 may both be accepted as linear equations in my if we agree that t is a parameter Augmented matrix To each linear equation in 1739 an we associate a row vector with n 1 entries can b gt Given a system of several equations7 we stack their corresponding rows into a matrix called the augmented matrix of the system of linear equations Sometimes7 the last column of the lt01 a2 augmented matrix is separated by a vertical line to indicate the equality signs7 but the book avoids this marker We may sometimes add it for convenience We may also add in a title row with variable names for convenience only 3 Pivots and related concepts We shall make the following formal notations for precision Given a row which has at least one non zero entry7 its pivot is the rst nonzero entry in it The book calls the corresponding column7 the pivot column We shall call the column number as the pc number 77 of that row For a row full of zeros7 there is no pivot and the pc number 77 is de ned to be 00 Thus7 the pc number for lt 0 0 2 0 3 gt is 3 whereas it is 00 for lt 0 0 0 0 0 For a matrix7 we de ne its pc sequence of the sequence of its pc numbers Thus7 we see that the pc sequence of the following matrices 120 120 020 015 100 000 027 007 217 are respectively 1221132oo1 We shall say that a pc sequence 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 absent7 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 its pc sequence of its pivot positions is strict It is said to be in a reduced row echelon form RREF if every pivot is 1 and moreover it is the only non zero entry in its column Elementary Row operations We shall use the following notations In the following 2397j are different row numbers of a matrix M and c is a number i The operation RZ lt gt Rj swaps the 24th row RZ with the j th row Rj Sometimes7 this may be shortened as P where P reminds of the word permute All other rows stay the same i The operation RZ CRJ39 modi es the row RZ by adding 0 times Rj to it All other rows stay the same i lf 0 31 07 then the operation CR replaces the i the row by 0 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 equations7 then the set of solutions of the system transformed by elementary row operations is the same as the original Thus7 the main idea of solving systems of linear equations is to transform the associated aug mented matrix into a form which lets us simply read off the solutions This is exactly the RREF As an intermediate step7 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 1 E0 3 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 REF in a sequence of steps At the beginning7 the whole matrix is active and as we proceed7 we shall declare certain rows as 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 Put713 with 2 31 j Suppose that RhRj have the same pc numbers and that their pivot entries are respectively chcj Then the operation Bi 7 produces a new jth row whose pc number is bigger than that of Bi Moreover7 suppose that the pc number of Bi is less than or equal to that of Bi for each j gt 27 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 2 This transformation leaves all the rst 2 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 R is the rst active row By swapping it7 if necessary7 with some Rj with j gt 2 arrange that the pc number of Bi is less than or equal to all the pc numbers of Bi for j gt2 o If R is the zero row7 then clearly all the rows Rj with j gt 2 are also zero Declare all rows inactive and go to end Otherwise7 apply the Main Lemma to arrange that the pivot positions of all R with j gt 2 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 pc numbers of the inactive matrix always stay strict and hence we end up with an REF when the whole matrix becomes inactive When the matrix is in REF7 the pc numbers 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 1 by dividing the corresponding pivot rows by the pivot entries Explicitly7 if c is the pivot entry in Ri then use the operation 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 4 Vectors We de ne 3 to be the set of columns of n tuples of real numbers This 3 can be also given a geometric interpretation by thinking of the 71 entries as the n coordinates of points in an n dimensional space For 1 6 3 let us make a temporary convention that Di is the t th entry of 1 for t 17 71 Thusifn2and1 lt 7 gt7then11175 andvg6 The set 3 has a natural addition de ned by componentwise addition Thus 1 wi vi wi There is also a scalar multiplication so that for any 0 6 3E and 1 6 3 we have Ci de ned as a vector with Cil cm There is a natural subtraction 1 7 w which is realized to be the same as 1 71w 1 Members of 3 are called vectors and geometrically may be thought of as an arrow pointing from the origin towards the point whose coordinates are the 71 entries of the column For example7 when n 27 a column lt i gt describes an arrow from the origin 07 0 towards the point 17 2 In general an arrow from a point Pab to a point Qcd can be identi ed with the vector corresponding to Q 7 P7 namely lt I Then the addition can be given a geometric interpretation thus Given vectors 1111 associated with the points P7 Q7 let 0 denote the origin Then the vector 1 w is associated witb a point B such that OPRQ is a parallelogram A vector Cl is associated with a point P1 on the line joining O and P such that the distance 0P1 between 0 and P1 is lclOP Moreover7 if c gt 0 then P7131 lie on the same side of 07 while they lie on the opposite sides if c lt 0 For convenience7 we may say that the point Pab is associated with a vector W lt a 9 New Perspective on Linear Equations Given vectors 111 31 in 3 we de ne a linear combination of them to be a vector of the form 01111 0212 07117 Collectively7 we de ne the span Spani h 39 71M 0101 62112 39 CTU l 017027 39 39 707 E In this notation7 it is easy to see that given an augmented matrix Alb belonging to a linear system of equations in 1 7x7 we can say that the system of equation is Bastc Equation xlAl ngg xTAT b where A1 A2 7A are the columns of the matrix A They are members of 3 if A has 71 rows 1For those who know these terms7 we state The addition is commutative and asoociativei the scalar multiplication is associative with respect to scalars Cdv cdvi Also the addition is distributive over the scalar multiplication Addition has an identity7 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 v for all vi Later7 any set with operations having such properties will be declared as an abstract vector space 03 In other words solving the system of euuations is the same as expressing b as a linear combination of A1 A In other words the system has a solution iff b is a member ofthe SpanA1 A If X denotes the column of 7 numbers zl We de ne AX to be the left hand side of the above basic equation Thus given a matrix with 71 rows and 7 columns we say that for a column X the product AX is de ned iff X has exactly 7 entries In other words as a matrix X has 7 rows and 1 column x then it is a member of 3 More generally if B is any matrix with 7 rows and 5 columns B1 B2 B5 then we de ne the product AB The matrix with columns AB1AB2 AB5 Thus the resulting matrix AB has 71 rows and 5 columns Note that for AB to make sense the number of columns of A must be equal to the number of rows of B Applications to solutions of systems of equations We know that given a system Alb where A has 71 rows and 7 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 7 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 r Using this we have two very simple yet powerful conclusions In expanded form we write our system thus 1 A f b or 7 1A1rArb where A1 A 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 rankA 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 3 is in the span of columns of A Proof Reduce Alb to REF We have d n pivots so every row of the 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 6 3 is in the span of columns of A If d r then there are no free variables Thus either the system is inconsistent or it has a unique solution Proof Evidentl Either Now assume 7 n ie the matrix A is square Then we have two possible cases drnordltrn 5 In the rst situation7 we get to claim that Alb has a unique solution for all b Naturally7 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 situation7 depending on b7 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 3 a 3 we say T is a linear transformation if the following conditions hold TX Y TX TY where XY are any vectors in 3 and k is any real number and TkX kTX The simplest example of a linear transformation is obtained when we take a matrix A with 71 rows and 7 columns De ne TX AX for any X 6 3B the two properties are easily veri ed by de nition of the matrix multiplication Conversely7 it is possible to prove the following Theorem Given any linear transformation T 3 a 3 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 6 e as follows For each 239 17 27 the vector which has only zero entries except for one 1 in the 24th place 7n we de ne e to be Thus7 for example7 when n 3 we have 1 0 0 ei 0 63 1 763 0 0 0 1 Similarly7 when n 2 we have Important shortened notation Often7 it is tedious to keep on writing the superscript for these So7 we may simply write 61 62 63 in place of ei 6 6 if we know that we are working in 35 Similarly7 we will simply use 61 62 in place of 6 6 if we are working in 39 If we are working with two different spaces at the same time7 then we nd it convenient to give new names to these We will say that 1263 e is a standard basis of 3 7 n 1 n Important Observation Every X f can be uniquely expressed as 16 wnen zn Thus for example7 when n 37 using shortened notation we get 1 2 151 252353 3 Now consider the standard basis 61 6 of 3 in shortened notation Construct a matrix A whose columns are T617 7Ten in order We claim that TX AX for all X 6 3 Note that XI16196n6n and by the de nition of a linear transformation we see that TX x1T61 anen But the right hand side of the last equation is exactly 1 A g AX n This proves our claim It is easy to see that if matrices AB satisfy AX BX for each X 6 3 then A B Hint Take X to be successively 61 7 en and deduce that A and B have identical columns Thus7 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 3E2 a 3E3 is de ned by x 2961 962 1 1 7 2 2 31 Sig Then 1 2 61 lt gt and hence T61 1 0 3 Similarly 00 1 62 lt 0 gt and hence T62 71 1 5 Thus 2 1 MT 1 1 3 5 It is easy to verify that 2 1 2 1 T 951 1 71 1 or TX 1 71 X 2 3 5 2 3 5 Properties of Linear Transformation Let T be a linear transformation from 3 to 3 as before We shall de ne T to be surjective if it is an onto map This means that every b 6 3 can be written as TX for some X Thus if A is the standard matrix MT then this is equivalent to the condition that Alb is consistent for all b From what we already observed the condition for surjectivity is thus d r where d rankA 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 columns Hence rankA d S minnr In particular we note that if n lt r then d S minnr lt r and the map cannot be surjective Note that we need to do extra calculations if n r 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 TX TY iff AX AY iff AX i Y 0 where the matrix 0 by convention is the matrix with all zero entries or the so called zero matrix Thus setting XiY Z we can reformulate the condition of injectivity as AZ 0 implies Z 0 This means that the system A10 always has a unique solution 0 or as discussed before in REF there are no free variables From what we already observed the condition for injectivity is thus d n where d rankA As before we can deduce that if n gt r then d 3 min 717quot lt n and thus the map T is not injective As before the case n 7 needs further evidence 8 9 Independence of vectors Given 7 vectors Ulv in 3 we de ne them to be linearly dependent if 101 xnvn 0 for some 139 n such that at least one of the x is non zero If we build a matrix A with columns 111 m then this condition is seen to mean that the linear system described by A O has a non zero solution Thus the system must have more than one solutions since setting all x 0 is an obvious solution From what we already know this is equivalent to rankA lt r or the linear transformation de ned by TX AX is not injective We may simply write 01 UT 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 1 is a linear combination of the rest The idea is to note that if 101 145 are 0 and x 7 0 then we can write where 1 does not appear on the right hand side Moreover by choosing the last 239 with s 7 0 we may even make a stronger looking claim that 1 is a linear combination of 111 451 These descriptions are useful when we are trying prove properties of linearly dependent vectors The set of vectors U1quot39UT is de ned to be linearly independent if it is not linearly dependent Equivalently the rank of the corresponding matrix A with columns 1 equals 7 or that the associated transformation T is injective Here are some simple observations that can be made from these de nitions Let S be the set of vectors 011 in 3 o If one of the vectors 111 1 is the zero vector then the set S is linearly dependent o If one of the 1 is a multiple of another 117 then the set S is linearly dependent If one of the 1 is a linear combination of some other members of S then the set S is linearly dependent If a subset of S is linearly dependent then S is linearly dependent o If r gt 71 than S is linearly dependent o If S is contained in a linearly independent set of vectors S1 then it is linearly independent