You may have solved linear equation early in the school. Problems involving solving sets of linear equation are very important in the field of Engineering and Mathematics. Let us consider that we have a system of linear equations a11 x1 +a12 a21 x1 +a22 a31 x1 +a32 We can solve it by reducing technique: Step 1: x2 +a13 x3 =c1 x2 +a23 x3 =c2 x2 +a33 x3 =c3 Step 2: a11 x1 + a12 a11 x2 x2 x2
a11 a11 a23−a21a13 x3 = c2−a21c1 a11 x1 + a12 a11 +a13 x3=c1 a11 a11
a23 x3 = c2 + a33 x3 = c3 a13 x3=c1 x2 a21 x1 + a22 x2 a31 x1 + a32 x2 a22 − a21 a12 a11 a11 a11 a33−a31a13 x3 = c3−a31c1 a32 − a31 a12 a11 a11 a11 This can be made more effective using matrix method. The set of equation for n unknowns can be Now do as step 1 for second row and so on. written as a11 x1 +a12 x2 +a13 x3 +...+a1n xn =c1 a21 x1 +a22 x2 +a23 x3 +...+a2n xn =c2 a31 x1 +a32 x2 +a33 x3 +...+a3n xn =c3 . . . ... . = . an1 x1 +an2 x2 +an3 x3 +...+ann xn =cn In matrix form a11 a12 a13 ... a1n x1 c1 aaa...axc 23 2n 2 2 a31 a32 a33 ... a3n x2 =c2 21 22 . . . .. . . . ....... an1 an2 an3 ... ann xn cn Compactly [A] ∗ {X} = {C} From this we can solve values of X’s. The matrix [AC] is called an augmented (see example below) matrix. If after elimination process the rank of matrix [A] and rank of matrix [AC] not equals, the system is called inconsistent and it does not have a solution. If the matrix is consistent and number of unknowns is greater then rank of matrix then the matrix system has arbitarily many solutions containing (NumberOfUnknowns-rank) arbitary constants. Rank of a matrix is defined as the number of non zero rows of a matrix system. Otherwise if the rank and number of unknows equals then the system has been solved. For example let a system of equations be
2/5 9x1 +4x2 + x3 =−17 x1 − 2x2 − 6x3 = 14 x1 + 6x2 = 4 This sets of equation can be written as 9 4 1 −17 1−2−6 14 1604 So the steps involving the solution is Step : 1 Step : 2 Step : 3 Step : 4 Step : 5 Step : 6 and then, the solution is Again consider this system Steps are: Step : 1 2x1 1−2−6 14 1604 9 4 1 −17 1 −2 −6 14 0 8 6 −10 0 22 55 −143 1−2−6 14 0 1 3/4 −5/4 0 0 77/2 −231/2 1 −2 −6 14 0 1 3/4 −5/4 0 0 1 −3 1 −2 0 −4 0101 0 0 1 −3 1 0 0 −2 0101 0 0 1 −3 x1 =−2,x2 =1,x3 =−3
2x2 + 2x3 = 2 4x1 16x1 + 16x2 + 16x3 = 16
4x2 + 4x3 = 4
3/5 Step : 2 2222 4444 16 16 16 16 1111 0000 0000 This system has number of unknowns 3 and rank is 1. So this system has arbitarily many solutions containing (3-1) = 2 arbitary constants. Another system Steps are: Step : 1 Step : 2 Step : 3 Step : 4 Step : 5 Step : 6 x + y = 10, x + y = 20, 2x + 2y = 50 1 1 10 1 1 20 2 2 50 1 1 10 0 0 10 0 0 30 1 1 10 0 0 10 0 0 30 1 1 10 0 0 10 001 110 000 001 110 000 001 As rank of [A] (in this case: rank(A) = 1) is not equal to the rank of augmented matrix [AC] (in this case: rank(AC) = 2) , the system has no solution. However though there are other methods to compute this solution for the matrix system, the main problem occurs are
4/5 2. Error due to wrong order of the given equation. To prevent round off error due to floating point number an approach can be used, similar to the process of doing fractional number. So we may use 1/3 as a expression of two integer, the numerator and the denominator, instead of .333333 (with loss of precision). Thus we can prevent this kind of error. Consider this set of equations This set of equations can be written as 5x3 = 10 3x2 − 3x3 = 3 2x1 − x2 + 2x3 = 7 0 0 5 10 0 3 −3 3 2 −1 2 7 Now how will you evaluate this matrix without ordering? Input The first line of input is the number of the problem. The next line contains two integers - NumberO- fUnknowns and NumberOfEquations (none of these is less then or equal to 0 and greater then 50). The next lines contains the matrix for the system of linear equations. There are number of rows equal to the NumberOfEquations and number of column equal to the NumberOfUnknowns+1. The numbers may be fractional, that is there may be numbers like 1/3 or 6/8. An problem number zero indicates the end of input. Output First print (without the quotation mark) "Solution for Matrix System # N" Here ‘N’ is the problem number as taken from input. Then on the next line, for each system of equations output the solution (if exists) expressed in the fractional form in each line. You may assume each of the numerator and denominator part will not exceed the limit of data type long long (64 bit). If there are many solutions as described above print (without the quotation mark) "Infinitely many solutions containing n arbitrary constants." (here ‘n’ is the number as described above) , and if there is no solutions print (without the quotation mark) "No Solution." Print a blank line between two systems of linear equations. Sample Input 1 33 9 4 1-17 1 -2 -6 14 1604
5/5 2 33 2222 4444 16/1 16/1 16/1 16/1 3 23 1 1 10 1 1 20 2 2 50 4 11 3 10 0 Sample Output Solution for Matrix System # 1 x[1] = -2 x[2] = 1 x[3] = -3 Solution for Matrix System # 2 Infinitely many solutions containing 2 arbitrary constants. Solution for Matrix System # 3 No Solution. Solution for Matrix System # 4 x[1] = 10/3