Determinant of an Integer Matrix Given a square integer matrix as input, output the determinant of the matrix.

Rules


You may assume that all elements in the matrix, the determinant of the matrix, and the total number of elements in the matrix are within the representable range of integers for your language.
Outputting a decimal/float value with a fractional part of 0 is allowed (e.g. 42.0 instead of 42).
Builtins are allowed, but you are encouraged to include a solution that does not use builtins.


Test Cases

[[42]] -&gt; 42
[[2, 3], [1, 4]] -&gt; 5
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -&gt; 0
[[13, 17, 24], [19, 1, 3], [-5, 4, 0]] -&gt; 1533
[[372, -152, 244], [-97, -191, 185], [-53, -397, -126]] -&gt; 46548380
[[100, -200, 58, 4], [1, -90, -55, -165], [-67, -83, 239, 182], [238, -283, 384, 392]] -&gt; 571026450
[[432, 45, 330, 284, 276], [-492, 497, 133, -289, -28], [-443, -400, 56, 150, -316], [-344, 316, 92, 205, 104], [277, 307, -464, 244, -422]] -&gt; -51446016699154
[[416, 66, 340, 250, -436, -146], [-464, 68, 104, 471, -335, -442], [159, -407, 310, -489, -248, 370], [62, 277, 446, -325, 47, -193], [460, 460, -418, -28, 234, -374], [249, 375, 489, 172, -423, 125]] -&gt; 39153009069988024
[[-246, -142, 378, -156, -373, 444], [186, 186, -23, 50, 349, -413], [216, 1, -418, 38, 47, -192], [109, 345, -356, -296, -47, -498], [-283, 91, 258, 66, -127, 79], [218, 465, -420, -326, -445, 19]] -&gt; -925012040475554
[[-192, 141, -349, 447, -403, -21, 34], [260, -307, -333, -373, -324, 144, -190], [301, 277, 25, 8, -177, 180, 405], [-406, -9, -318, 337, -118, 44, -123], [-207, 33, -189, -229, -196, 58, -491], [-426, 48, -24, 72, -250, 160, 359], [-208, 120, -385, 251, 322, -349, -448]] -&gt; -4248003140052269106
[[80, 159, 362, -30, -24, -493, 410, 249, -11, -109], [-110, -123, -461, -34, -266, 199, -437, 445, 498, 96], [175, -405, 432, -7, 157, 169, 336, -276, 337, -200], [-106, -379, -157, -199, 123, -172, 141, 329, 158, 309], [-316, -239, 327, -29, -482, 294, -86, -326, 490, -295], [64, -201, -155, 238, 131, 182, -487, -462, -312, 196], [-297, -75, -206, 471, -94, -46, -378, 334, 407, -97], [-140, -137, 297, -372, 228, 318, 251, -93, 117, 286], [-95, -300, -419, 41, -140, -205, 29, -481, -372, -49], [-140, -281, -88, -13, -128, -264, 165, 261, -469, -62]] -&gt; 297434936630444226910432057
Jelly, 15 bytes

LŒ!ðŒcIṠ;ị"Pð€S


Try it online!

How it works

LŒ!ðŒcIṠ;ị"Pð€S   input
L                 length
 Œ!               all_permutations
   ð        ð€    for each permutation:
    Œc                take all unordered pairs
      I               calculate the difference between
                      the two integers of each pair
       Ṡ              signum of each difference
                      (positive -&gt; 1, negative -&gt; -1)
        ;             append:
         ị"             the list of elements generated by taking
                        each row according to the index specified
                        by each entry of the permutation
           P          product of everything
              S   sum


Why it works -- mathy version

The operator det takes a matrix and returns a scalar. An n-by-n matrix can be thought of as a collection of n vectors of length n, so det is really a function that takes n vectors from ℤn and returns a scalar.

Therefore, I write det(v1, v2, v3, ..., vn) for det [v1 v2 v3 ... vn].

Notice that det is linear in each argument, i.e. det(v1 + λw1, v2, v3, ..., vn) = det(v1, v2, v3, ..., vn) + λ det(w1, v2, v3, ..., vn). Therefore, it is a linear map from (ℤn)⊗n to ℤ.

It suffices to determine the image of the basis under the linear map. The basis of (ℤn)⊗n consists of n-fold tensor products of the basis elements of ℤn, i.e. e.g. e5 ⊗ e3 ⊗ e1 ⊗ e5 ⊗ e1. Tensor products that include identical tensors must be sent to zero, since the determinant of a matrix in which two columns are identical is zero. It remains to check what the tensor products of distinct basis elements are sent to. The indices of the vectors in the tensor product form a bijection, i.e. a permutation, in which even permutations are sent to 1 and odd permutations are sent to -1.

For example, to find the determinant of [[1, 2], [3, 4]]: note that the columns are [1, 3] and [2, 4]. We decompose [1, 3] to give (1 e1 + 3 e2) and (2 e1 + 4 e2). The corresponding element in the tensor product is (1 e1 ⊗ 2 e1 + 1 e1 ⊗ 4 e2 + 3 e2 ⊗ 2 e1 + 3 e2 ⊗ 4 e2), which we simplify to (2 e1 ⊗ e1 + 4 e1 ⊗ e2 + 6 e2 ⊗ e1 + 12 e2 ⊗ e2). Therefore:

det [[1, 2], [3, 4]] 
= det(1 e1 + 3 e2, 2 e1 + 4 e2) 
= det(2 e1 ⊗ e1 + 4 e1 ⊗ e2 + 6 e2 ⊗ e1 + 12 e2 ⊗ e2) 
= det(2 e1 ⊗ e1) + det(4 e1 ⊗ e2) + det(6 e2 ⊗ e1) + det(12 e2 ⊗ e2) 
= 2 det(e1 ⊗ e1) + 4 det(e1 ⊗ e2) + 6 det(e2 ⊗ e1) + 12 det( e2 ⊗ e2) 
= 2 (0) + 4 (1) + 6 (-1) + 12 (0) 
= 4 - 6 
= -2

Now it remains to prove that the formula for finding the parity of the permutation is valid. What my code does is essentially find the number of inversions, i.e. the places where an element on the left is bigger than an element on the right (not necessarily consecutively).

For example, in the permutation 3614572, there are 9 inversions (31, 32, 61, 64, 65, 62, 42, 52, 72), so the permutation is odd.

The justification is that each transposition (swapping two elements) either adds one inversion or takes away one inversion, swapping the parity of the number of inversions, and the parity of the permutation is the parity of the number of transpositions needed to achieve the permutation.

Therefore, in conclusion, our formula is given by:

Why it works -- non-mathy version



where σ is a permutation of n the group of all permutations on n letters, and sgn is the sign of the permutation, AKA (-1) raised to the parity of the permutation, and aij is the (ij)th entry in the matrix (i down, j across).