Matrix Determinant

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 0.1s
Java 0.2s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

FatalEagle recently stumbled upon a manga that teaches linear algebra. A particularly interesting topic was matrix determinants. Your task is simple: given A, an N \times N matrix, find its determinant! Since this number can be really big, we want to find its value \bmod 1\,000\,000\,007 (10^9+7).

Input Specification

The first line of input will have N.

The next N lines will have N integers each. The j^{th} integer of the i^{th} line will contain A_{i,j} (-10^9 \le A_{i,j} \le 10^9).

For cases worth 30% of the total marks, 1 \le N \le 8.

For cases worth another 30% of the total marks, 1 \le N \le 20.

For all test cases, 1 \le N \le 500.

Output Specification

The output should be a single integer in the range [0, 1\,000\,000\,007), the determinant of the matrix A.

Sample Input 1

2
-1 3
-5 7

Sample Output 1

8

Sample Input 2

6
1 3 5 2 4 6
2 5 4 3 1 6
6 1 2 3 4 5
2 5 1 3 6 4
4 5 1 2 3 6
5 4 3 6 1 2

Sample Output 2

2457

Comments


  • -27
    harry7557558  commented on April 18, 2020, 8:43 p.m. edit 249

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 14
      ManchurioX  commented on April 20, 2020, 12:02 a.m.

      Hey! Spamming the "view previous" button on the comment above (the one with many edits) will get you captcha'd so be warned!!!


    • 0
      Moana  commented on April 19, 2020, 7:06 p.m. edit 6

      Comment by harry7557558: original edit 2 edit 6 edit 12 edit 13+; Account kicked out for spam requesting and is currently inaccessible.

      Python hard-coding AC submission; First proper Python AC solution; PyPy 2 AC'd with 0.2s TL;

      The proper Python submission has an average complexity of O(N^3); Current fastest submission uses O(1/3 N^3) addition/multiplication/modulo operations (++ inside for loop doesn't count) and O(N) modular multiplicative inverse operations, when N is large; This C++ submission works without #pragma and uses a "proper" IO. (typo in header comment: "peering" -> "peeping")

      Some facts about matrix determinant:

      • The determinant of an upper-triangular matrix is the product of all diagonal elements;
      • Add the multiple of one row to another row (element-wise) does not change the determinant of a matrix;
      • When two rows of a matrix are swapped, the determinant of the matrix changes sign;

      Some facts related to the comment with many edits:

      Edited Oct.13, 2020. \mathsf{\color{#FFFFFF00}{\text{Downvote or upvote you decide.}}}

      \mathsf{\tiny{\color{#80808080}{\text{If you think these comments are polluting the comment area, don't hesitate to delete them. @admins}}}}


  • 9
    FatalEagle  commented on Jan. 20, 2015, 3:32 p.m.

    There are a large number of test cases with increasing size. This problem is to test the efficiency of your matrix determinant algorithm -- in other words, the constant matters in this question!


    • -1
      bobhob314  commented on Jan. 26, 2015, 2:25 p.m.

      Wait Fatal so you mean e.g. for T(n) = O(f(n)), if f(n) were to be 2(n^3) or something, then the 2 coefficient would matter?


      • -2
        bobhob314  commented on Jan. 26, 2015, 2:25 p.m.

        Or sorry, I goofed. What do you mean by constant?