Math 1b — Nonnegative solutions to a system over the realsJanuary 8, 2010We may ask whether a (nonhomogeneous) system of linear equations with real coeffi-cients has a solution in nonnegative real numbers. This question is part of the subject oflinear programming and has many applications.The system of equations (1) on the first page of the notes on “Basic matrices andsolutions; pivot operations”, though it has many solutions, has no nonnegative solutions.This is clear from the first equation in (4): If x5is nonnegative, then x4is strictly negative.Theorem. If a (real) system of linear equations has a nonnegative s olution, then it has abasic solution which is nonnegative.If the coefficient matrix of the system is r×n, then there are at mostnr choices for thedependent variables and so there can be at mostnr basic solutions. We could theoreticallygo through the basic solutions one by one and check whether any are nonnegative. If wehave a system of 50 equations in 100 variables, there are potentially10050 basic solutions,so this is not practical.We will describe a method (an algorithm) to find a nonnegative basic solution or else aproof that none exist. (However, our discussion will not be complete, so it will not providea proof of the theorem above.)To find a nonnegative solution of Ax = b, or a proof that none exist: Start withthe matrixM =A b.Use pivot operations or individual elementary row operations to make the “A-part” of thematrix basic. (∗) If the enties in the last column are nonnegative, then the correspondingbasic solution is nonnegative and we stop. Otherwise, there is a negative entry in the lastcolumn, say in row i. If all other entries in row i are positive, there are no nonnegativesolutions of the i-th equation, and we stop. If there is another negative entry in row i,pick one, say in columns j, and pivot on position (i, j) to get a new matrix representingan equivalent system of equations. Go to (∗).To make this into an algorithm, we must be sure that we finish after a finite numberof pivots. If we are not careful, we can repeatedly return to a basic matrix we have metbefore and end up cycling forever. This will probably not happen in the exercises I assign.But in general, one must choose the pivot position with more care to ensure no matrix isrepeated. This is really important, but we will not discuss it in this course, or at least notat this time.We will be content to know one nonnegative solution, if such exists. We do not try todescribe all nonnegative solutions. That is a very time-consuming task in general.The following page shows this algorithm in action for three systems of 5 linear equa-tions. For the first system, described by A, there are no nonnegative solutions because theequation corresponding to the first row of Out[6] isx1+ (8591/16552)x3+ (19167/16552)x4= −(989/16552)and this equation, all by itself, has no nonnegative solutions.I tried many systems with five equations and seven variables, but the ones I tried hadNO nonnegative solutions. Bad luck. Then I tried a few with nine variables until I foundone, described by the matrix F, that did have nonnegative solutions. The basic solutioncorresponding to Out[126] isx1=18512077,x2=0,x3=0,x4=13772077,x5=662077,x6=0,x7=862077,x8=0,x9=542077.In[1]:=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@@iDDD, 8k, Length@mD<D;mDIn[2]:=rand@m_,n_D := Table@RandomInteger@10D, 8i, m<, 8j, n<DIn[3]:=MatrixForm@A = rand@5, 8DDOut[3]//MatrixForm=1 87 941041030 092745 510119072 86 133371 66 28705In[4]:=MatrixForm@A = RowReduce@ADDOut[4]//MatrixForm=10000−5715557320255571249555701000−4115555722 0192778517 931277850010072985557−18 0912778584812778500010−27785557−571727785−10 628277850000132415557−351827 785−56727 785In[5]:=MatrixForm@A = pivot@A, 4, 6DDOut[5]//MatrixForm=100−571277800859113 89021076945010−41152778001524113 890841769450013649138900−82766945−48596945000−5557277801571713890531469450007610−1130−715In[6]:=MatrixForm@A = pivot@A, 3, 7DDOut[6]//MatrixForm=10859116 5521916716 552000−98916 552011524116 5521552116 552000939716 55200−69458276−18 24582760014859827600571716552−18 0911655201086651655200−509316552593116552100−416116552In[9]:=MatrixForm@B = rand@5, 8DDOut[9]//MatrixForm=820 88 682985 44 8610658 510081793 96 7061610710143In[10]:=MatrixForm@B = RowReduce@BDDOut[10]//MatrixForm=1000079544327835401000−1235648−731324−12496480010014296486373241919648000101255432247216122943200001−81432592−15191296−94612592In[11]:=MatrixForm@B = pivot@B, 2, 6DDOut[11]//MatrixForm=194812350000−17212357112350 −6481235000114621235124912350142912351000−7961235903123507534940100−567247−232470 −81434940001062912470−5841235In[15]:=MatrixForm@B = pivot@B, 4, 7DDOut[15]//MatrixForm=16389450 −1722835000179283502479450146228350102731283506899451 −7962835000214728350 −2513780 −2475670012356703700233210100−121210In[123]:=MatrixForm@F = rand@5, 10DDOut[123]//MatrixForm=20 179326 8 775 051159 8 1029 062739 2 625 60094102 2010882092 106In[124]:=MatrixForm@F = RowReduce@FDDOut[124]//MatrixForm=1000078121372925854811 481854814522137394542740100043672137−283213736412137−19342137−62213700100−694213756678548−1717854818402137213427400010−6106213764678548−18851854836072137315542740000153652137−2205427445002137−14332137−1521372 math1b-nonneg3.nbIn[125]:=MatrixForm@F = pivot@F, 2, 7DDOut[125]//MatrixForm=1292511320006391113201626283−9395662402830 −2137283000−43672831 −364128319342836228305667113210011213113202357283−2077566−272830646711320109981113204261566−19715661622830 −2205566001−30855660 −256556680828330283In[126]:=MatrixForm@F = pivot@F, 3, 9DDOut[126]//MatrixForm=16662077−9392077002425207704113207701851207703680207738682077006264207715493207708620770 −56674154−566207700−11 21341540 −471420771542077039974154−1971207710−242141540 −155941540137720770 −341541616207701937341540809341540662077math1b-nonneg3.nb