DSA Homework 0

Roger Jang

Due date: none

Inverse of a square matrix

Problem definition

One way to find the inverse of a square matirx is by Gauss-Jordan elimination. In order to finish this homework, you need to read the description under the subtitle of "Finding the inverse of a matrix" at the Wikipedia for Gaussian elimiation. You can also check out the following videos to grasp the idea quickly:

Write a program to calculate the inverse of a given matrix A. (We shall denote the inverse as B.) The input format is shown next:

n ¡ö The number of rows (also the number of columns) of A a11 a12 . . . . . . a1n ¡ö the n numbers of row 1 of A a21 a22 . . . . . . a2n ¡ö the n numbers of row 2 of A . . . an1 an2 . . . . . . ann ¡ö the n numbers of row n of A The output format is shown next: error ¡ö the error of A*B b11 b12 . . . . . . b1n ¡ö the n numbers of row 1 of B b21 b22 . . . . . . b2n ¡ö the n numbers of row 2 of B . . . bn1 bn2 . . . . . . bnn ¡ö the n numbers of row n of B

The output format is the error (defined later) followed by the inverse matrix. See the test cases for the output examples.

Requirements & suggestions

  1. To keep high precision, use the data type "double" to store each element. All intermediate variables should be declared as "double" too.
  2. You can safely assume 0 < n < 201.
  3. You can safely assume the inverse matrix always exists. (So no exception handling for singular matrices is necessary.)
  4. Your program should take the input from the standard input and send the output to the standard output. Therefore you can redirect input and output files if necessary, such as "myProgram < input.txt > output.txt".
  5. The error in the output file is only for your own verification. Our judge system will compute the error based on the product of the original matrix and the computed inverse. The computed inverse is considered correct if the error is less than an error threshold of 1e-2. The error is defined as the maximum element of the absolute value of A*B-I, where I is an identity matrix of size n-by-n. (Check out the output of the test cases shown below.)
  6. Please make sure your output should have at least 6 digits below the decimal point to keep precision. (When you print out your error, usually it is less than 1e-5. Our error tolerance is much higher since we need to read the inverse from your output file, which introduces extra error due to the difference between the internal double data type and its printed version.)
  7. TAs will use 10 test cases (including the following ones) to test the accuracy of your program.

Test cases

  1. n=3: input, output
  2. n=10: input, output
  3. n=20: input, output
  4. n=121: input, output
  5. n=200: input, output

How I determined the error threshold

Just for your information, I've run my program to generate the following plots in order to determine the error threshold. The first plot shows the maximum error of 100 test cases for each of the matrix dimensions of 1x1, 2x2, ..., 200x200. Element of the matrices are drawn from a normal distribution with zero mean and unit variance. From the plot, it seems that 1e-5 is a pretty lenient threshold which is not likely to produce false rejection.

The following plot shows the errors vs normalized determinants for all 20000 test cases. (So there are actually 20000 dots on the plot!) In other words, the error becomes larger when the determinant is close to zero. This is a reasonable result since the inverse of a matrix is equal to its adjoint matrix divided by its determinant.