Lab07. Matrix Determinants

EE231002 Introduction to Programming
Lab07. Matrix Determinants

Given an N × N square matrix Ai,j , 1 ≤ i, j ≤ N, then the determinant can be defined by
the Leibniz formula as
det(A) = ∑
σ∈SN
sgn(σ)
∏
N
i=1
Ai,σi
. (7.1)
where SN is the set of all permutations of {1, 2, · · · , N}, σ is one possible permutation in SN , and
σi
is the ith element of the permutation σ. In Lab 5, the Pandita algorithm has been introduced.
Given a permutation σ
(m)
, the Pandita algorithm generates the next lexicographic permutation
σ
(m+1) with σ
(1) = {1, 2, · · · , N}. The function sgn(σ
(m)
) is defined as the following.
sgn(σ
(m)
) = {
1, if m = 1,
(−1)t × sgn(σ
(m−1)), otherwise.
(7.2)
where t is the number of swaps needed for the Pandita algorithm to generate the next permutation.
An example of N = 3 case is listed in the following table.
SN σ t sgn(σ
(m)
) product
σ
(1) 1 2 3 0 1 A1,1 A2,2 A3,3
σ
(2) 1 3 2 1 -1 A1,1 A2,3 A3,2
σ
(3) 2 1 3 2 -1 A1,2 A2,1 A3,3
σ
(4) 2 3 1 1 1 A1,2 A2,3 A3,1
σ
(5) 3 1 2 2 1 A1,3 A2,1 A3,2
σ
(6) 3 2 1 1 -1 A1,3 A2,2 A3,1
In this assignment, you need to write a C program to calculate the determinant of an N ×N
square matrix using Equations (7.1) and (7.2). Since the Pandita algorithm has been introduced
in Lab05, you are requested to write a function to generate the next lexicographic permutation
using that algorithm. The declaration of Pandita algorithm is as following.
int Pandita(int A[N]);
The function takes the permutation array A[N] as input and rearranges it for the next permutation. It then returns sgn(σ
(m)
) as the output. If it reach the end of the permutation, then it
returns 0 to terminate the determinant calculation. To facilitate writing of this assignment, the
size of the matrix N should be defined as a macro.
#if !defined(N)
#define N 3
#endif
1
Twelve matrices with various dimensions have been provided for you to test your program.
They are mat1.in, mat2.in, · · · , mat12.in. You should open each file to find the dimension of
the matrix and then compile your program with the right dimension as
$ gcc -DN=3 lab07.c
$ ./a.out < mat1.in
The last line uses the unix input redirection method to read input directly from the file mat1.in.
In this way, we do not need to retype the matrix every time we execute the program. Example
program compilation and execution is shown below.
$ gcc -DN=3 lab07.c
$ ./a.out < mat1.in
Input matrix is
1 2 3
4 5 6
7 8 9
Det = 0
Notes.
1. Create a directory lab07 and use it as the working directory.
2. Name your program source file as lab07.c.
3. The first few lines of your program should be comments as the following.
/* EE231002 Lab07. Matrix Determinants
ID, Name
Date:
*/
4. After you finish verifying your program, you can submit your source code by
$ ∼ee2310/bin/submit lab07 lab07.c
If you see a ”submitted successfully” message, then you are done. In case you want to
check which file and at what time you submitted your labs, you can type in the following
command:
$ ∼ee2310/bin/subrec lab07
It will show the last few submission records.
2