ELEMENTARY LINEAR ALGEBRA - Number theory

1 ELEMENTARYLINEAR ALGEBRAK. R. MATTHEWSDEPARTMENT OF MATHEMATICSUNIVERSITY OF QUEENSLANDC orrected Version, 27th April2013 Comments to the author at 1 LINEAR Introduction to LINEAR equationsAlinear equationinnunknownsx1, x2, , xnis an equation of the forma1x1+a2x2+ +anxn=b,wherea1, a2, .. , an, bare given real example, withxandyinstead ofx1andx2, the LINEAR equation2x+ 3y= 6 describes the line passing through the points (3,0) and (0,2).Similarly, withx, yandzinstead ofx1, x2andx3, the LINEAR equa-tion 2x+ 3y+ 4z= 12 describes the plane passing through the points(6,0,0),(0,4,0),(0,0,3).Asystemofm LINEAR equations innunknownsx1, x2, , xnis a familyof LINEAR equationsa11x1+a12x2+ +a1nxn=b1a21x1+a22x2+ +a2nxn= +am2x2+ +amnxn= wish to determine if such a system has a solution, that is tofindout if there exist numbersx1, x2, , xnwhich satisfy each of the equationssimultaneously.

2 We say that the system isconsistentif it has a the system is 1. LINEAR EQUATIONSNote that the above system can be written concisely asnXj=1aijxj=bi, i= 1,2, , matrix a11a12 a1na21a22 amn is called thecoefficient matrixof the system, while the matrix a11a12 a1nb1a21a22 amnbm is called theaugmented matrixof the , solving a system of LINEAR equations in two (or three)unknowns is equivalent to determining whether or not a family of lines (orplanes) has a common point of the equation2x+ 3y= The equation 2x+ 3y= 6 is equivalent to 2x= 6 3yorx= 3 32y, whereyis arbitrary. So there are infinitely many the systemx+y+z= 1x y+z= We subtract the second equation from the first, to get 2y= 1andy=12. Thenx=y z=12 z, wherezis arbitrary. Again there areinfinitely many a polynomial of the formy=a0+a1x+a2x2+a3x3which passes through the points ( 3, 2),( 1,2),(1,5),(2,1).

3 INTRODUCTION TO LINEAR EQUATIONS3 Solution. Whenxhas the values 3, 1,1,2, thenytakes correspondingvalues 2,2,5,1 and we get four equations in the unknownsa0, a1, a2, a3:a0 3a1+ 9a2 27a3= 2a0 a1+a2 a3= 2a0+a1+a2+a3= 5a0+ 2a1+ 4a2+ 8a3= 1,with unique solutiona0= 93/20, a1= 221/120, a2= 23/20, a3= 41 the required polynomial isy=9320+221120x 2320x2 [26, pages 33 35] there are examples of systems of LINEAR equationswhich arise from simple electrical networks using Kirchhoff s laws for elec-trical a system consisting of a single LINEAR equation is easy. However ifwe are dealing with two or more equations, it is desirable to have a systematicmethod of determining if the system is consistent and to find all of restricting ourselves to LINEAR equations with rational or realcoefficients, our theory goes over to the more general case where the coef-ficients belong to an arbitraryfield.

4 AfieldFis a setFwhich possessesoperations ofadditionandmultiplicationwhich satisfy the familiar rules ofrational arithmetic. There are ten basic properties that a field must have:THE FIELD (a+b) +c=a+ (b+c) for alla, b, cinF;2. (ab)c=a(bc) for alla, b, cinF; +b=b+afor alla, binF; alla, binF;5. there exists an element 0 inFsuch that 0 +a=afor allainF;6. there exists an element 1 inFsuch that 1a=afor allainF;7. to everyainF, there corresponds anadditive inverse ainF, satis-fyinga+ ( a) = 0;4 CHAPTER 1. LINEAR EQUATIONS8. to every non zeroainF, there corresponds amultiplicative inversea 1inF, satisfyingaa 1= 1; (b+c) =ab+acfor alla, b, cinF;10. 06= standard definitions such asa b=a+ ( b) andab=ab 1forb6= 0, we have the following familiar rules: (a+b) = ( a) + ( b),(ab) 1=a 1b 1; ( a) =a,(a 1) 1=a; (a b) =b a,(ab) 1=ba;ab+cd=ad+bcbd;abcd=acbd;abac=bc,a bc =acb; (ab) = ( a)b=a( b); ab = ab=a b;0a= 0;( a) 1= (a 1).

5 Fields which have only finitely many elements are of great interest inmany parts of mathematics and its applications, for exampleto coding the-ory. It is easy to construct fields containing exactlypelements, wherepisa prime Number . First we must explain the idea ofmodular additionandmodular multiplication. Ifais an integer, we definea(modp) to be theleast remainder on dividingabyp: That is, ifa=bp+r, wherebandrareintegers and 0 r < p, thena(modp) = example, 1 (mod 2) = 1,3 (mod 3) = 0,5 (mod 3) = addition and multiplication modpare defined bya b= (a+b) (modp)a b= (ab) (modp). SOLVING LINEAR EQUATIONS5 For example, withp= 7, we have 3 4 = 7 (mod 7) = 0 and 3 5 =15 (mod 7) = 1. Here are the complete addition and multiplication tablesmod 7: 0 1 2 3 4 5 6001234561123456022345601334560124456012 35560123466012345 0 1 2 3 4 5 6000000001012345620246135303625144041526 35053164260654321If we now letZp={0,1.}

6 , p 1}, then it can be proved thatZpformsa field under the operations of modular addition and multiplication example, the additive inverse of 3 inZ7is 4, so we write 3 = 4 whencalculating inZ7. Also the multiplicative inverse of 3 inZ7is 5 , so we write3 1= 5 when calculating practice, we writea banda basa+bandabora bwhen dealingwith LINEAR equations simplest field isZ2, which consists of two elements 0,1 with additionsatisfying 1+1 = 0. So inZ2, 1 = 1 and the arithmetic involved in solvingequations overZ2is very the following system overZ2:x+y+z= 0x+z= We add the first equation to the second to gety= 1. Thenx=1 z= 1 +z, withzarbitrary. Hence the solutions are (x, y, z) = (1,1,0)and (0,1,1).We useQandRto denote the fields of rational and real numbers, re-spectively. Unless otherwise stated, the field used will Solving LINEAR equationsWe show how to solve any system of LINEAR equations over an arbitrary field,using theGAUSS JORDAN algorithm.

7 We first need to define some 1. LINEAR EQUATIONSDEFINITION (Row echelon form)A matrix is inrow echelonformif(i) all zero rows (if any) are at the bottom of the matrix and(ii) if two successive rows are non zero, the second row starts with morezeros than the first (moving from left to right).For example, the matrix 0 1 0 00 0 1 00 0 0 00 0 0 0 is in row echelon form, whereas the matrix 0 1 0 00 1 0 00 0 0 00 0 0 0 is not in row echelon of any size is always in row echelon (Reduced row echelon form)A matrix is inre-duced row echelon formif1. it is in row echelon form,2. the leading (leftmost non zero) entry in each non zero row is 1,3. all other elements of the column in which the leading entry1 occursare example the matrices 1 00 1 and 0 1 2 0 0 20 0 0 1 0 30 0 0 0 1 40 0 0 0 0 0 are in reduced row echelon form, whereas the matrices 1 0 00 1 00 0 2 and 1 2 00 1 00 0 0 SOLVING LINEAR EQUATIONS7are not in reduced row echelon form, but are in row echelon of any size is always in reduced row echelon a matrix is in reduced row echelon form, it is useful to denotethe column numbers in which the leading entries 1 occur, byc1, c2.

8 , cr,with the remaining column numbers being denoted bycr+1, .. , cn, whereris the Number of non zero rows. For example, in the 4 6 matrix above,we haver= 3, c1= 2, c2= 4, c3= 5, c4= 1, c5= 3, c6= following operations are the ones used on systems of LINEAR equationsand do not change the ( ELEMENTARY row operations)Three types ofel-ementary row operationscan be performed on matrices:1. Interchanging two rows:Ri Rjinterchanges Multiplying a row by a non zero scalar:Ri tRimultiplies rowiby the non zero Adding a multiple of one row to another row:Rj Rj+tRiaddsttimes rowito (Row equivalence)MatrixAisrow equivalenttomatrixBifBis obtained fromAby a sequence of ELEMENTARY row from left to right,A= 1 2 02 1 11 1 2 R2 R2+ 2R3 1 2 04 1 51 1 2 R2 R3 1 2 01 1 24 1 5 R1 2R1 2 4 01 1 24 1 5 = row equivalent toB.

9 ClearlyBis also row equivalent toA, byperforming the inverse row operationsR1 12R1, R2 R3, R2 R2 is not difficult to prove that ifAandBare row equivalent augmentedmatrices of two systems of LINEAR equations, then the two systems have the8 CHAPTER 1. LINEAR EQUATIONS same solution sets a solution of the one system is a solutionof the example the systems whose augmented matrices areAandBin theabove example are respectively x+ 2y= 02x+y= 1x y= 2and 2x+ 4y= 0x y= 24x y= 5and these systems have precisely the same The Gauss Jordan algorithmWe now describe theGAUSS JORDAN ALGORITHM. This is a processwhich starts with a given matrixAand produces a matrixBin reduced row echelon form, which is row equivalent toA. IfAis the augmented matrixof a system of LINEAR equations, thenBwill be a much simpler matrix thanAfrom which the consistency or inconsistency of the corresponding systemis immediately apparent and in fact the complete solution ofthe system canbe read the first non zero column moving from left to right, (columnc1)and select a non zero entry from this column.

10 By interchanging rows, ifnecessary, ensure that the first entry in this column is non zero. Multiplyrow 1 by the multiplicative inverse ofa1c1thereby convertinga1c1to 1. Foreach non zero elementaic1, i >1, (if any) in columnc1, add aic1timesrow 1 to rowi, thereby ensuring that all elements in columnc1, apart fromthe first, are 2. If the matrix obtained at Step 1 has its 2nd, .. , mth rows allzero, the matrix is in reduced row echelon form. Otherwise suppose thatthe first column which has a non zero element in the rows below the first iscolumnc2. Thenc1< c2. By interchanging rows below the first, if necessary,ensure thata2c2is non zero. Then converta2c2to 1 and by adding suitablemultiples of row 2 to the remaing rows, where necessary, ensure that allremaining elements in columnc2are process is repeated and will eventually stop afterrsteps, eitherbecause we run out of rows, or because we run out of non zero columns.