Assignment 20 - Computing Determinants

1. General Outline
   The main goal of this assignment is to compute the determinant of a matrix. Here the computations are not done in the integers itself, but in the ring modulo some fixed number. If this number is 92, then addition, substraction and multiplication have arguments and results in the set {0,1,2,...,90,91} and work as the following examples show:

        5 + 8  ==  13
       22 + 8  ==  30
       90 + 8  ==   6
   
        4 - 3  ==   1
        4 - 6  ==  90
        8 - 9  ==  91
   
       16 * 4  ==  64
       16 * 6  ==   4
       32 * 6  ==   8
       23 * 8  ==   0
   

   The task is now to compute in this modified arithmetic the determinant of a matrix. Although there is a complicated polynomial to compute the determinant directly, this polynomial is very large and therefore mathematicians do other methods to compute it: They transform the matrix with operations which preserve the determinant until the lower triangle of the matrix below the diagonal consists entirely of zeros. Then the determinant is just the product of the elements in the diagonal. The goal of this assignment is to program this for some randomly chosen matrix and then to display this new matrix. So a sample output of the correct program would be the following.

   Computing the determinant.
   Computations modulo 92; the matrix has size 11 times 11.
   The solution is 69.
   Printing the matrix.
   57 34 85 56  8 69 87 67 80 88 51 
   20 40 48 80 57 88 50 18 76 60 89 
   57 73 10  7 11 41 55 36  2 80 32 
   43 64 11 41 11 42 35 67 26 12 72 
   48 17 64 88 14 32 32  0 88 16  8 
   58 12 80 55  5  6 34  5  1 29 12 
   46 53 68 43 52 50 65 83  6 76 49 
   86 18 54 70 75 78 30 73 56 44 72 
   30 26 22  8 24  1 14 43 15 46 69 
   74 65 65 11 10 69 70 63 52 15 50 
   25 55 53 50 13 35 37  9 65 83 75 
   Printing the matrix.
    1 66 65 68 19 33 17 21 68 28 38 
    0  1 87 41 70 60 10 61 26 48 16 
    0  0  1 22 77  9 68 57 24 72 13 
    0  0  0  1 23 59 78 26 74 28 23 
    0  0  0  0  1 32 78 46 84 64 77 
    0  0  0  0  0  1 24 70 53 23 78 
    0  0  0  0  0  0  1 67  9 83 85 
    0  0  0  0  0  0  0  1 48 47 91 
    0  0  0  0  0  0  0  0  1 75  0 
    0  0  0  0  0  0  0  0  0  3 19 
    0  0  0  0  0  0  0  0  0  0 23 
   The determinant is 69.
   

   What is missing in the given assignment is the routine to transform the matrix and this should be programmed. Further information on matrices are found on the page of the dictionary Wikipedia
2. The algorithm.
   The algorithm chosen here is suitable for matrices of small finite rings obtained by computing modulo some small natural number (like 92 in the above example). This algorithm would not work with real numbers. Somehow, it has the advantage that it does not need the division which indeed is not available in all cases, as there might be factors of 0; for example 2, 4, 8, 23 and 46 in the case of computing modulo 92. The underlying idea of the implementation is the following:

      If one adds or substracts rows in a matrix, then the
      determinant of the matrix does not change. So, for computations
      modulo 92, the following matrices have all the same determinant
      as each of them is obtained from the previous one by adding to
      one row or substacting from one row the multiple of some other row.
   
         1  3  2  8
         2  6 90  1
         1  6 90  4
         3 15 90 20
         
         1  3  2  8
         0  0 86 77    row 0 twice substracted from row 1
         0  3 88 88    row 0 substracted from row 2
         0  6 84 88    row 0 three times substracted from row 3
   
         1  3  2  8
         0  0 86 77
         0  3 88 88
         0  0  0  4    row 2 twice substracted from row 3
           
         1  3  2  8
         0  3 82 73    row 2 added to row 1
         0  3 88 88
         0  0  0  4
       
         1  3  2  8
         0  3 82 73
         0  0  6 15    row 1 substracted from row 2
         0  0  0  4
   
       All these matrices have the determinant 1*3*6*4 which is
       72 modulo 92.
   

   These examples illustrate that one can in principle obtain a matrix in the desired form. The task is now to implement this systematically. Here some details of the implimentation.
   • The variable "modnum" has a number modulo which is computed. This number is 92 in the examples above, but indeed it is a random number drawn at each run of the program.
   • The variable "size" has the size of the matrix, that is the numbers of rows and the number of columns. The number of entries of the matrix is size*size.
   • The variable "matrix" is just containing the matrix. This is implemented as an array of arrays in Java Script and each array consists of as many elements as the value of the variable "size".
   • The function "rowadd(matrix,m,n,p)" adds the n-th row p times to the m-th row of the matrix in the variable of the same name. This function ignores calls where m and n have the same value, thus calling this function cannot change the value of the determinant. Note that you can use the value -1 for p in the case that you want to substract and the value +1 in the case that you want to add the n-th row to the m-th row.
   • The routine to multiply the diagonal elements is already implemented. It yealds of course the wrong result when the matrix is not of the required form.
   • The function "matrixprint(matrix)" prints the matrix in the variable of the same name.
   So the general idea is to use above variables and the function rowadd in order to do suitable additions and substractions of rows until all entries below the diagonal are 0. To work out the details and to implement this is the task of this assignment.
3. Test your program.
   Run the program several times and compare the values of the variables "solution" and "determinant" when output by the program. If they are always equal, it is likely that the programmed solution is correct.
   
   You can hand in the program after checking its correctness by showing it to the lecturer.