Math 1b — Basic matrices and solutions; pivot operationsJanuary 6, 2010We use matrices to model systems of linear equations. For example, the system2x1− 3x2− 5x3− 7x4+2x5=7x1+ x2− 5x3+ x4− 4x5=3x1− 4x3+3x4+ x5= −4(1)has corresponding matrix2 −3 −5 −7211−51−410−43 173−4. (2)Two matrices (of the same dimensions) are row-equivalent when one can be obtainedfrom the other by a sequence of elementary row operations as described in Schneiderstarting on page 47. Important: The systems of linear equations corresponding to two rowequivalent matrices will have exactly the same set of solutions.An r by n matrix M with all nonzero rows is basic when its columns include⎛⎜⎜⎜⎜⎝100...0⎞⎟⎟⎟⎟⎠,⎛⎜⎜⎜⎜⎝010...0⎞⎟⎟⎟⎟⎠,⎛⎜⎜⎜⎜⎝001...0⎞⎟⎟⎟⎟⎠, ...,⎛⎜⎜⎜⎜⎝000...1⎞⎟⎟⎟⎟⎠(of height r)(3)in some order. A matrix with some rows of all zeros is called basic when the rows ofall zeros are at the bottom and the submatrix consisting of the nonzero rows is basic.Examples of 3 × 7 basic matrices are⎛⎝230410567180095505015⎞⎠,⎛⎝217410560884190000000⎞⎠,⎛⎝210410060180015007010⎞⎠.In the third matrix, there are several choices for the columns that contain the vectors in(2).To solve a system of linear equations, we start with the matrix M =A bofthe system (here A is the matrix of coefficients of the variables and b is the column ofscalars on the right hand side of the equations) and use row operations until we find arow-equivalent matrix M=Abin which Ais basic. If the indices of the columnsof Acontaining the vectors in (3) are j1,j2,...,jr, then the variables xj1,,xj2,,...,xjrin the new, equivalent system have been isolated in the sense that each appears withnonzero coefficient in only one of the equations. The variables xj1,,xj2,,...,xjrmay becalled “dependent” variables, since their values are determined uniquely by the values ofthe others, which may be called “free” variables. (Caution: Which variables are free andwhich are dependent depends on the basic form. This is not determined by the originalequations.)For example (see the last page), the matrix in (2) is row-equivalent to0 001 15/19−1/4100−117/38−1/4010 13/38−26/1933/19−10/19.The corresponding system of linear equations isx4+(15/19)x5= −26/19(−1/4)x1+ x2− (117/38)x5=33/19(−1/4)x1+ x3+(13/38)x5= −10/19 ,or, what is the same,x4= −(26/19) − (15/19)x5x2=33/19 + (1/4)x1+ (117/38)x5x3= −(10/19) + (1/4)x1− (13/38)x5.(4)Here x2,x3,x4are the dependent variables and x1,x5the free variables. The originalsystem of equations may now be considered as “solved” because we have described allsolutions in a simple way, in terms of two “parameters”.If we set the free variables to 0, we obtain a particular solution of the system:x1=0,x2=33/19,x3= −10/19,x4= −26/19,x5=0.This is an example of a basic solution.In general, if the coefficient matrix (not including the last column of a nonhomogeneoussystem) of a system of linear equations is basic, and the free variables are assigned thevalue 0, then the resulting solution of the system is called a basic solution.Thevaluesofthe dependent variables will be, in some order, the numbers in the last column. There willin general be many basic solutions to a system, corresponding to different basic matricesrow-equivalent to the original matrix. Exercise: What are the basic solutions of the systemabove corresponding to the basic matrices on the last page of these notes? [Caution: theterm basic solution is used in a different way in Schneider, on page 68 and elsewhere.]Notice that if a system of linear equations has a solution (at least one), then it has abasic solution. One explanation is simply that we can see whether a system has a solutionby looking at the echelon (or a basic) form, and if the system does have a solution, a basicsolution is evident. We will clarify this in class along with the assertion that a system ofequations has only finitely many basic solutions.***It is convenient to combine some elementary row operations into a single operationwe call a pivot operation. IfM =⎛⎜⎜⎝a11a12... a1na21a22... a2n...... ......am1am2... amn⎞⎟⎟⎠and aij= 0, we may pivot on position (i, j) by, first, multiplying row i by 1/aijso thatthe (i, j) position becomes 1, and then adding (or subtracting) multiples of row i from theother rows so that all entries of column j, except the entry in position (i, j) become 0.For example, if we pivot on position (1, 1) of a 3 by 2 matrix, we get⎛⎝1 a21/a110 a22− a21a12/a110 a32− a31a12/a11⎞⎠See the next page for examples of pivoting.pivot@M_,i_,j_D :=Block@8m<,m= M; m@@iDD = m@@iDD ê m@@i, jDD;Do@If@k  i, , m@@kDD = m@@kDD − m@@k, jDD m@@i DDD, 8k, Length@mD<D;mDMatrixForm@A = 882, −3, −5, −7, 2, 7<, 81, 1, −5, 1, −4, 3<, 81, 0, −4, 3, 1, −2<<D2 −3 −5 −72 711 −51 −4310 −43 1 −2MatrixForm@A = RowReduce@ADD10−40−2619401901−10−65194319000 11519−2619MatrixForm@A = pivot@A, 1, 5DD−19260381301−2013−5219 00−315260 −301310−213MatrixForm@A = pivot@A, 3, 3DD00019151 −2615−141039100 −185−1401−13300115MatrixForm@A = pivot@A, 1,