Assignment 16 - Computing Determinants

Getting Started

Please refer to this page for information on how to work on your assignment.
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 is available on Wikipedia.
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 are some details of the implementation:
- The modnum variable has a modulo number which is computed. This number is 92 in the examples above, but it actually is a random number drawn at each run of the program.
- The size variable 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 matrix variable just contains the matrix. This is implemented as an array of arrays in JavaScript and each array consists of as many elements as the value of the size variable.
- The rowadd(matrix, m, n, p) function adds the n^th row p times to the m^th 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. Of course it yields the wrong result when the matrix is not of the required form.
- The matrixprint(matrix) function prints the matrix in the variable of the same name.
So the general idea is to use above variables and the rowadd() function 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.
Test your program

Run the program several times and compare the values of the solution and determinant variables 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.

JavaScript Starts Here.

JavaScript Ends Here.