Integral Determinant

Write a program to find the determinant of an integral square matrix. Note that the determinant of a square matrix can be defined recursively as follows: the determinant of a 1×1 matrix M = (a1,1) is just the value |M| = a1,1; further, the determinant of an n × n matrix is ∑n i=1 A straightforward method of calculating the determinant of an n×n matrix by the recursive method will end up with n! multiplications, a very time-consuming algorithm. To give you a feeling about this, note that 15! = 1,307,674,368,000. To reduce the time complexity, there are two ways of modifying the original matrix for easier computation.

1. Exchanging two columns (or rows) of a matrix will change the sign of the determinant; for example 12=−21 34 43
2. Multiplying one column by any constant, and add them to another column will not change the value of the determinant; for example: 213 213+2×2 456=456+4×2 789 789+7×2 Using the above methods, you shall be able to write a program for computing the determinants of matrices, even for a size like 30×30, very efficiently. Below is an example to show how this can be done: 235 23−25−2×2 211 112 167=16−17−1×2=155=−551 489 48−49−4×2 441 144 (−1)i+1 · |M1,j |. |M | = Here the notation M1,i is the (n − 1) × (n − 1) matrix by removing the first row and the i-th column of the original n × n matrix M. 1 1−1 2−1×2 1 0 0 0 −9 =− 4 5−5 1−5×2 =− 5 0 −9 =− 14−14−1×2 13 2 Note that the answer shall be an integer. That is, all the operations needed are just integer oper- ations; by reducing to floating numbers would result in the round-off errors, which will be considered as the wrong answer. Do not worry about the problem of integral overflows problem. You can assume that the given data set will not cause the integer overflow problem. What is emphasized here is the required integer precision. Input Several sets of integral matrices. The inputs are just a list of integers. Within each set, the first integer (in a single line) represents the size of the matrix, n, which can be as large as 30, indication an n × n matrix. After n, there will be n lines representing the n rows of the matrix; each line (row) contains exactly n integers. Thus, there is totally n2 integers for the particular matrix. These matrices will occur repeatedly in the input as the pattern described above. An integer n = 0 (zero) signifies the end of input. 32 =−27

2/2 Output For each matrix of the input, calculate its (integral) determinant and output them in a line. Output a single star (*) to signify the end of outputs. Sample Input 2 52 34 3 235 167 489 0 Sample Output 14 -27 *