Please refer to this page for information on how to work on your assignment.
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 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:
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.
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
.
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.
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.
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.
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.