34
\$\begingroup\$

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]] -> 42
[[2, 3], [1, 4]] -> 5
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 0
[[13, 17, 24], [19, 1, 3], [-5, 4, 0]] -> 1533
[[372, -152, 244], [-97, -191, 185], [-53, -397, -126]] -> 46548380
[[100, -200, 58, 4], [1, -90, -55, -165], [-67, -83, 239, 182], [238, -283, 384, 392]] -> 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]] -> -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]] -> 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]] -> -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]] -> -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]] -> 297434936630444226910432057
\$\endgroup\$
  • \$\begingroup\$ Sandbox, relevant meta post \$\endgroup\$ – Mego Nov 10 '17 at 13:50
  • \$\begingroup\$ is there a maximum size of matrix that needs to be supported or is it arbitrary? \$\endgroup\$ – Taylor Scott Nov 10 '17 at 14:59
  • 1
    \$\begingroup\$ @TaylorScott First rule listed: 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. \$\endgroup\$ – Mego Nov 10 '17 at 15:00
  • 4
    \$\begingroup\$ You know you have an interesting challenge when you have 4 Jelly answers consecutively out-golfing each other... \$\endgroup\$ – totallyhuman Nov 10 '17 at 18:21

37 Answers 37

0
\$\begingroup\$

Jelly, 2 bytes

ÆḊ

Try it online!

Currently only built-in solution. :( Looks like others have managed to find out interesting non-built-in solutions.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 3 bytes

Det

Try it online!

Per the meta consensus, mainly upvote nontrivial solutions that take effort to write.

\$\endgroup\$
11
\$\begingroup\$

R, 3 bytes

Trivial Solution

det

Try it online!

R, 94 92 bytes

re-implemented solution

outgolfed by Jarko Dubbeldam

d=function(m)"if"(x<-nrow(m),m[,1]%*%sapply(1:x,function(y)(-1)^(y-1)*d(m[-y,-1,drop=F])),1)

Try it online!

Recursively uses expansion by minors down the first column of the matrix.

f <- function(m){
 x <- nrow(m)                 # number of rows of the matrix
 if(sum(x) > 1){              # when the recursion reaches a 1x1, it has 0 rows
                              # b/c [] drops attributes
  minor <- function(y){
   m[y] * (-1)^(y-1) *
   d(m[-y,-1])                # recurse with the yth row and first column dropped
   }
  minors <- sapply(1:x,minor) # call on each row
  sum(minors)                 # return the sum
 } else {
  m                           # return the 1x1 matrix
 }
}

\$\endgroup\$
  • \$\begingroup\$ 32 bytes \$\endgroup\$ – JAD Nov 11 '17 at 9:22
6
\$\begingroup\$

Proton, 99 bytes

f=m=>(l=len(m))==1?m[0][0]:sum((-1)**i*m[0][i]*f([[m[k][j]for k:1..l]for j:0..l if j-i])for i:0..l)

Try it online!

-3 bytes thanks to Mr. Xcoder
-3 bytes thanks to Erik the Outgolfer

Expansion over the first row

\$\endgroup\$
  • \$\begingroup\$ Just because Proton doesn't have builtin for determinant. \$\endgroup\$ – user202729 Nov 10 '17 at 14:05
  • \$\begingroup\$ 103 Bytes. ((~i%2)*2-1) -> ((-i%2)|1) \$\endgroup\$ – Mr. Xcoder Nov 10 '17 at 14:18
  • \$\begingroup\$ Also 102 bytes by replacing j!=i with j-i or i-j. \$\endgroup\$ – Mr. Xcoder Nov 10 '17 at 14:20
  • \$\begingroup\$ 99 bytes \$\endgroup\$ – Erik the Outgolfer Nov 10 '17 at 15:09
  • \$\begingroup\$ @EriktheOutgolfer Ah yes, thanks! \$\endgroup\$ – HyperNeutrino Nov 10 '17 at 15:28
1
\$\begingroup\$

Python 2 + numpy, 29 bytes

from numpy.linalg import*
det

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Julia, 3 bytes

det

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 3, 238 bytes, 227 bytes, 224 bytes, 216 bytes

from functools import*
from itertools import*
r=range;n=len;s=sum
f=lambda l:s(reduce(lambda p,m:p*m,[l[a][b]for a,b in zip(r(n(l)),j)])*(-1)**s(s(y<j[x]for y in j[x:])for x in r(n(l)))for j in permutations(r(n(l))))

Try it online!

My solution uses the definition of a determinant for calculations. Unfortunately, the complexity of this algorithm is n! and I can not show the passage of the last test, but in theory this is possible.

\$\endgroup\$
3
\$\begingroup\$

Octave, 30 bytes

@(x)-prod(diag([~,l,~]=lu(x)))

Try it online!

or, the boring 4 byte solution (saved 6 bytes thanks to Luis Mendo (forgot the rules regaring builtin functions)):

@det

Explanation:

Coming up! :)

\$\endgroup\$
5
\$\begingroup\$

C,  176  125 bytes

Thanks to @ceilingcat for golfing 42 bytes, and thanks to both @Lynn and @Jonathan Frech for saving a byte each!

d(M,n)int*M;{int i=n--,s=*M*!n,c,T[n*n];for(;i--;s+=M[i]*(1-i%2*2)*d(T,n))for(c=n*n;c--;T[c]=M[n-~c+c/n+(c%n>=i)]);return s;}

Calculates the determinant using the Laplace expansion along the first row.

Try it online!

Unrolled:

d(M, n)int*M;
{
    int i=n--, s=*M*!n, c, T[n*n];
    for (; i--; s+=M[i]*(1-i%2*2)*d(T,n))
        for (c=n*n; c--;)
            T[c] = M[n-~c+c/n+(c%n>=i)];
    return s;
}
\$\endgroup\$
  • \$\begingroup\$ (i%2*-2+1)(1-i%2*2) saves one more byte. \$\endgroup\$ – Lynn Nov 11 '17 at 13:34
  • \$\begingroup\$ n+1+c can be n-~c. \$\endgroup\$ – Jonathan Frech Nov 11 '17 at 22:52
  • \$\begingroup\$ Suggest i=s instead of return s \$\endgroup\$ – ceilingcat Nov 25 '17 at 0:49
5
\$\begingroup\$

Jelly, 43 bytes

Finally I've done writing my non-builtin solution in a golfing language!

ḣ⁹’’¤;ṫḊ€Ç×⁸ị@⁹’¤¤ḷ/¤
çЀ⁸J‘¤µJ-*×NS
ÇḢḢ$Ṗ?

Thanks to HyperNeutrino for saving a byte!

Try it online! (spaced code for clarity)

terribly long way to remove n'th elements from a list, will improve later


This answer had been outgolfed by answers of HyperNeutrino, Dennis and Leaky Nun. Jelly is very popular as a golfing language.

Quick explanation:

ÇḢḢ$Ṗ?    Main link.
     ?    If
    Ṗ     after remove the last element, the value is not empty (truthy)
Ç         then execute the last link
 ḢḢ$      else get the element at index [1, 1].

çЀ⁸J‘¤µJ-*×NS     Helper link 1, take input as a matrix.
çЀ                Apply the previous link, thread right argument to
   ⁸J‘¤            the range [2, 3, ..., n+1]
       µ           With the result,
        J-*        generate the range [-1, 1, -1, 1, ...] with that length
           ×N      Multiply by negative
             S     Sum

ḣ⁹’’¤;ṫḊ€Ç×⁸ị@⁹’¤¤ḷ/¤    Helper link 2, take left input as a matrix, right input as a number in range [2..n+1]
ḣ
 ⁹’’¤                    Take head ρ-2 of the matrix
     ;                   concatenate with 
      ṫ                  tail ρ (that is, remove item ρ-1)
       Ḋ€                Remove first column
         Ç               Calculate determinant of remaining matrix
          ×         ¤    multiply by
                  ḷ/     the first column,
            ị@           row #
              ⁹’¤        ρ-1 (just removed in determinant calculation routine) of
           ⁸     ¤       the matrix.
\$\endgroup\$
3
\$\begingroup\$

TI-Basic, 2 bytes

det(Ans

Ah, well.

Please don't upvote trivial answers.

As a high school student (who's forced to own one of these calculators), this function is hella useful so...

\$\endgroup\$
  • 8
    \$\begingroup\$ It's still hella useful in college - linear algebra does not go away \$\endgroup\$ – Taylor Scott Nov 10 '17 at 14:57
  • 5
    \$\begingroup\$ @TaylorScott In fact, it comes back with a vengeance in differential equations. \$\endgroup\$ – Mego Nov 10 '17 at 16:05
  • \$\begingroup\$ @Mego - you are right on that; though for some reason they let me take all of calc and that before linear :/ \$\endgroup\$ – Taylor Scott Nov 11 '17 at 1:23
  • 1
    \$\begingroup\$ @TaylorScott Due to an oversight by my university's math department, linalg was not a prerequisite for diffeq when I took it. When my professor realized that, he quickly gave us a 3-day crash course in linalg. \$\endgroup\$ – Mego Nov 11 '17 at 19:41
0
\$\begingroup\$

Excel VBA, 58 50 Bytes

Returns the determinant of the matrix entered into the the upper left corner of the default Sheet1 object.

?Evaluate("MDeterm("+Sheet1.UsedRange.Address+")")

-8 Bytes thanks to Greedo

\$\endgroup\$
  • \$\begingroup\$ Save 7 with ?Evaluate("MDeterm("&Sheet1.UsedRange.Address &")") \$\endgroup\$ – Greedo Nov 12 '17 at 12:43
4
\$\begingroup\$

MATL, 3 bytes / 5 bytes

With built-in function

&0|

Try it online!

Without built-in

Thanks to Misha Lavrov for pointing out a mistake, now corrected

YvpYo

Try it online!

This computes the determinant as the product of the eigenvalues, rounded to the closest integer to avoid floating-point inaccuracies.

Yv       % Implicit input. Push vector containing the eigenvalues
p        % Product
Yo       % Round. Implicit display
\$\endgroup\$
  • \$\begingroup\$ Wouldn't the product of the singular values only tell you the absolute value of the determinant? \$\endgroup\$ – Misha Lavrov Nov 10 '17 at 22:02
  • \$\begingroup\$ @MishaLavrov You're totally right! Thanks for noticing. I corrected it by using eigenvalues instead of singular values... and that saved 4 bytes \o/ \$\endgroup\$ – Luis Mendo Nov 10 '17 at 22:12
4
\$\begingroup\$

Jelly, 24 bytes

œcL’$ṚÑ€
J-*×Ḣ€×ÇSµḢḢ$Ṗ?

Try it online!

Explanation

œcL’$ṚÑ€         Helper Link; get the next level of subdeterminants (for Laplace Expansion)
œc               Combinations without replacement of length:
  L’$            Length of input - 1 (this will get all submatrices, except it's reversed)
     Ṛ           Reverse the whole thing
      р         Get the determinant of each of these
J-*×Ḣ€×ÇSµḢḢ$Ṗ?  Main Link
              ?  If the next value is truthy
             Ṗ   Remove the last element (truthy if the matrix was at least size 2)
J-*×Ḣ€×ÇSµ       Then expand
          ḢḢ$    Otherwise, get the first element of the first element (m[0][0] in Python)
J                [1, 2, ..., len(z)]
 -*              (-1 ** z) for each z in the length range
   ×             Vectorizing multiply with
    Ḣ€           The first element of each (this gets the first column); modifies each row (makes it golfier yay)
      ×Ç         Vectorizing multiply with the subdeterminants
        S        Sum

-2 bytes thanks to user202729's solution

\$\endgroup\$
0
\$\begingroup\$

J, 5 bytes

-/ .*

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Octave, 28 bytes

@(x)round(prod(diag(qr(x))))

Try it online!

This uses the QR decomposition of a matrix X into an orthgonal matrix Q and an upper triangular matrix R. The determinant of X is the product of those of Q and R. An orthogonal matrix has unit determinant, and for a triangular matrix the determinant is the product of its diagonal entries. Octave's qr function called with a single output gives R.

The result is rounded to the closest integer. For large input matrices, floating-point inaccuracies may produce an error exceeding 0.5 and thus produce a wrong result.

\$\endgroup\$
  • 1
    \$\begingroup\$ That's an interesting way to evade the det builtin. ;) \$\endgroup\$ – tomsmeding Nov 10 '17 at 23:49
  • 1
    \$\begingroup\$ @tomsmeding :-) Also, it had already been "used" in Stewie's answer \$\endgroup\$ – Luis Mendo Nov 10 '17 at 23:53
0
\$\begingroup\$

MY, 3 (4?) bytes

ω∥↵

Try it online!

Precision is a little weird (the second test case is 5.000000000000001), this can be fixed at a cost of one byte: ω∥⌊↵

\$\endgroup\$
  • \$\begingroup\$ Right argument, parallel, return... what? \$\endgroup\$ – totallyhuman Nov 10 '17 at 16:14
  • \$\begingroup\$ Right argument, determinant, output with new line. \$\endgroup\$ – Zacharý Nov 10 '17 at 16:45
8
\$\begingroup\$

Haskell, 71 bytes

-3 bytes thanks to Lynn. Another one bytes the dust thanks to Craig Roy.

f[]=1
f(h:t)=foldr1(-)[v*f[take i l++drop(i+1)l|l<-t]|(i,v)<-zip[0..]h]

Try it online! Added -O flag for optimization purposes. It is not necessary.

Explanation (outdated)

f recursively implements cofactor expansion.

f[[x]]=x

This line covers the base case of a 1 × 1 matrix, in which case the determinant is mat[0, 0].

f(h:t)=

This uses Haskell's pattern matching to break the matrix into a head (the first row) and a tail (the rest of the matrix).

          [                                     |(i,v)<-zip[0..]h]

Enumerate the head of the matrix (by zipping the infinite list of whole numbers and the head) and iterate over it.

           (-1)*i*v

Negate the result based on whether its index is even since the calculation of the determinant involves alternating addition and subtraction.

                     [take i l++drop(i+1)l|l<-t]

This essentially removes the ith column of the tail by taking i elements and concatenating it with the row with the first (i + 1)th elements dropped for every row in the tail.

                   *f

Calculate the determinant of the result above and multiply it with the result of (-1)*i*v.

       sum

Sum the result of the list above and return it.

\$\endgroup\$
  • 2
    \$\begingroup\$ you could save 1 byte if you replace the sum[(-1)^i*... with foldr(-)0[... \$\endgroup\$ – Craig Roy Nov 12 '17 at 23:07
9
\$\begingroup\$

Jelly, 16 15 12 10 bytes

Ḣ×Zß-Ƥ$Ṛḅ-

Uses Laplace expansion. Thanks to @miles for golfing off 3 5 bytes!

Try it online!

How it works

Ḣ×Zß-Ƥ$Ṛḅ-  Main link. Argument: M (matrix / 2D array)

Ḣ           Head; pop and yield the first row of M.
      $     Combine the two links to the left into a monadic chain.
  Z         Zip/transpose the matrix (M without its first row).
   ß-Ƥ      Recursively map the main link over all outfixes of length 1, i.e., over
            the transpose without each of its rows.
            This yields an empty array if M = [[x]].
 ×          Take the elementwise product of the first row and the result on the
            right hand. Due to Jelly's vectorizer, [x] × [] yields [x].
       Ṛ    Reverse the order of the products.
        ḅ-  Convert from base -1 to integer.
                [a]          -> (-1)**0*a
                [a, b]       -> (-1)**1*a + (-1)**0*b = b - a
                [a, b, c]    -> (-1)**2*a + (-1)**1*b + (-1)**0*c = c - b + a
                etc.
\$\endgroup\$
3
\$\begingroup\$

Python 2, 95 bytes

-12 bytes thanks to Lynn.

Port of my Haskell answer.

f=lambda m:sum((-1)**i*v*f([j[:i]+j[i+1:]for j in m[1:]])for i,v in enumerate(m[0]))if m else 1

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Here, too, you can use [] as a base case: f=lambda m:sum((-1)**i*v*f([j[:i]+j[i+1:]for j in m[1:]])for i,v in enumerate(m[0]))if m else 1 for 95 bytes! \$\endgroup\$ – Lynn Nov 11 '17 at 13:31
  • \$\begingroup\$ m==[]or sum(...) gives 92 bytes. \$\endgroup\$ – Bubbler Oct 22 '18 at 1:18
2
\$\begingroup\$

Java 8, 266 261 259 258 bytes

long d(int[][]m){long r=0;int i=0,j,k,l=m.length,t[][]=new int[l-1][l-1],q=m[0][0];if(l<3)return l<2?q:q*m[1][1]-m[0][1]*m[1][0];for(;i<l;r+=m[0][i]*(1-i++%2*2)*d(t))for(j=0;++j<l;)for(k=l;k-->0;){q=m[j][k];if(k<i)t[j-1][k]=q;if(k>i)t[j-1][k-1]=q;}return r;}

Look mom, no build-ins.. because Java has none.. >.>

-7 bytes thanks to @ceilingcat.

Explanation:

Try it here. (Only the last test case is too big to fit in a long of size 263-1.)

long d(int[][]m){             // Method with integer-matrix parameter and long return-type
  long r=0;                   //  Return-long, starting at 0
  int i=0,j,k,                //  Index-integers
      l=m.length,             //  Dimensions of the square matrix
      t[][]=new int[l-1][l-1],//  Temp-matrix, one size smaller than `m`
      q=m[0][0];              //  The first value in the matrix (to reduce bytes)
  if(l<3)                     //  If the dimensions are 1 or 2:
    return l<2?               //   If the dimensions are 1:
      q                       //    Simply return the only item in it
     :                        //   Else (the dimensions are 2):
      q*m[1][1]-m[0][1]*m[1][0];
                              //    Calculate the determinant of the 2x2 matrix
                              //  If the dimensions are 3 or larger: 
  for(;i<l;                   //  Loop (1) from 0 to `l` (exclusive)
      r+=                     //    After every iteration: add the following to the result:
         m[0][i]              //     The item in the first row and `i`'th column,
         *(1-i++%2*2)         //     multiplied by 1 if `i` is even; -1 if odd,
         *d(t))               //     multiplied by a recursive call with the temp-matrix
    for(j=0;                  //   Reset index `j` to 0
        ++j<l;)               //   Inner loop (2) from 0 to `l` (exclusive)
      for(k=l;k-->0;){        //    Inner loop (3) from `l-1` to 0 (inclusive)
        q=m[j][k];            //     Set the integer at location `j,k` to reduce bytes
        if(k<i)               //     If `k` is smaller than `i`:
          t[j-1][k]=q;        //      Set this integer at location `j-1,k`
        if(k>i)               //     Else-if `k` is larger than `i`:
          t[j-1][k-1]=q;      //      Set this integer at location `j-1,k-1`
                              //     Else: `k` and `i` are equals: do nothing (implicit)
      }                       //    End of inner loop (3)
                              //   End of inner loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
  return r;                   //  Return the result-long
}                             // End of method
\$\endgroup\$
25
+200
\$\begingroup\$

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 -> 1, negative -> -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).

\$\endgroup\$
  • 17
    \$\begingroup\$ That "non-mathy version" is pretty damn mathy. \$\endgroup\$ – MD XF Nov 10 '17 at 19:01
  • 6
    \$\begingroup\$ @MDXF formulas and symbols and numbers hardly constitute maths. Mathematics is the abstraction and the generalization and the logic behind the formal manipulations of the symbols. \$\endgroup\$ – Leaky Nun Nov 10 '17 at 19:02
  • 7
    \$\begingroup\$ @JAB Jelly implements its own custom code page. (One of these days, TIO will include a link to the code page...) \$\endgroup\$ – totallyhuman Nov 10 '17 at 23:16
  • 1
    \$\begingroup\$ @Mego the "sum-of-diagonal-products" only work for 1x1, 2x2, and 3x3 matrices. For bigger matrices, you need to consider all permutations and their parity. \$\endgroup\$ – Leaky Nun Nov 12 '17 at 7:31
  • 3
    \$\begingroup\$ +1 for actually include the proof in the post instead of saying "because this formula is listed on the page abcxyz it must be true". \$\endgroup\$ – user202729 Nov 13 '17 at 5:51
3
\$\begingroup\$

Wolfram Language (Mathematica), 53 52 bytes

1##&@@@(t=Tuples)@#.Signature/@t[Range@Tr[1^#]&/@#]&

Try it online!

Unfortunately, computing the determinant of an n by n matrix this way uses O(nn) memory, which puts large test cases out of reach.

How it works

The first part, 1##&@@@(t=Tuples)@#, computes all possible products of a term from each row of the given matrix. t[Range@Tr[1^#]&/@#] gives a list of the same length whose elements are things like {3,2,1} or {2,2,3} saying which entry of each row we picked out for the corresponding product.

We apply Signature to the second list, which maps even permutations to 1, odd permutations to -1, and non-permutations to 0. This is precisely the coefficient with which the corresponding product appears in the determinant.

Finally, we take the dot product of the two lists.


If even Signature is too much of a built-in, at 73 bytes we can take

1##&@@@(t=Tuples)@#.(1##&@@Order@@@#~Subsets~{2}&/@t[Range@Tr[1^#]&/@#])&

replacing it by 1##&@@Order@@@#~Subsets~{2}&. This computes Signature of a possibly-permutation by taking the product of Order applied to all pairs of elements of the permutation. Order will give 1 if the pair is in ascending order, -1 if it's in descending order, and 0 if they're equal.


-1 byte thanks to @user202729

\$\endgroup\$
  • 1
    \$\begingroup\$ 52 bytes (in case you didn't know this Mathematica golfing tip) \$\endgroup\$ – user202729 Nov 11 '17 at 14:09
  • \$\begingroup\$ I did, but somehow forgot about it here. Thanks! \$\endgroup\$ – Misha Lavrov Nov 11 '17 at 16:07
8
\$\begingroup\$

Wolfram Language (Mathematica), between 14 and 42 bytes

We've had a 3-byte built-in and a 53-byte solution that completely avoids built-ins, so here are some weirder solutions somewhere in between.

The Wolfram Language has a lot of very intense functions for decomposing matrices into products of other matrices with simpler structure. One of the simpler ones (meaning I've heard of it before) is Jordan decomposition. Every matrix is similar to a (possibly complex-valued) upper triangular matrix made of diagonal blocks with a specific structure, called the Jordan decomposition of that matrix. Similarity preserves determinants, and the determinant of a triangular matrix is the product of the diagonal elements, so we can compute the determinant with the following 42 bytes:

1##&@@Diagonal@Last@JordanDecomposition@#&

The determinant is also equal to the product of the eigenvalues of a matrix, with multiplicity. Luckily, Wolfram's eigenvalue function keeps track of multiplicity (even for non-diagonalisable matrices), so we get the following 20 byte solution:

1##&@@Eigenvalues@#&

The next solution is kind of cheating and I'm not really sure why it works. The Wronskian of a list of n functions is the determinant of the matrix of the first n-1 derivatives of the functions. If we give the Wronskian function a matrix of integers and say that the variable of differentiation is 1, somehow it spits out the determinant of the matrix. It's weird, but it doesn't involve the letters "Det" and it's only 14 bytes

#~Wronskian~1&

(The Casoratian determinant works as well, for 1 more byte: #~Casoratian~1&)

In the realm of abstract algebra, the determinant of an n x n matrix (thought of as the map k → k that is multiplication by the determinant) is the nth exterior power of the matrix (after picking an isomorphism k → ⋀n kn). In Wolfram language, we can do this with the following 26 bytes:

HodgeDual[TensorWedge@@#]&

And here's a solution that works for positive determinants only. If we take an n-dimensional unit hypercube and apply a linear transformation to it, the n-dimensional "volume" of the resulting region is the absolute value of the determinant of the transformation. Applying a linear transformation to a cube gives a parallelepiped, and we can take its volume with the following 39 bytes of code:

RegionMeasure@Parallelepiped[Last@#,#]&
\$\endgroup\$
  • 1
    \$\begingroup\$ The solution I had along these lines was Exp@*Tr@*MatrixLog, but unfortunately this doesn't work for singular matrices. \$\endgroup\$ – Misha Lavrov Nov 10 '17 at 23:29
  • 1
    \$\begingroup\$ @MishaLavrov Ooh, that's clever! I think you can fix it with Check[E^Tr@MatrixLog@#,0]&. \$\endgroup\$ – Not a tree Nov 10 '17 at 23:39
  • \$\begingroup\$ That's great! I hadn't been aware of Check before. \$\endgroup\$ – Misha Lavrov Nov 10 '17 at 23:45
  • 1
    \$\begingroup\$ I created a challenge for Jordan Decomposition a while ago. You might be interested in it, too. What a great answer! \$\endgroup\$ – Mego Nov 11 '17 at 19:39
0
\$\begingroup\$

TI-Basic (83 series), 137 133 bytes

Ans→[A]
For(N,max(dim(Ans)),2,-1
 Matr▶list(Ans,N,C
 1+sum(not(cumSum(not(not(∟C→R
 If R>N
 Then
  0[A]→[A]
 Else
  rowSwap([A],R,N
  *row(cos(π(R≠N))Ans(N,N),Ans,1
  *row(-Ans(N,N)⁻¹,Ans,N
  For(I,1,N
   *row+(Ans(I,N),Ans,N,I→[A]
  End
 End
End
Ans(1,1

(Indentation is purely decorative and doesn't appear on the calculator.)

Instead of the built-in det(, does row reduction by hand. The pivots are built backwards, starting at the (n,n)th entry and going back to the (1,1)th (or is that (1,1)st?).

Every time we need to divide by a number to set the pivot to 1, we multiply the first row by the same number (possibly negated, if we needed to swap rows), so that the determinant of the matrix stays the same. (If we didn't find a pivot, we zero out the entire matrix.) As a result, at the end, the (1,1)th (1,1)st top left entry holds the determinant.

\$\endgroup\$
4
\$\begingroup\$

R, 32 bytes

function(m)Re(prod(eigen(m)$va))

Uses Not a Tree's algorithm of taking the eigenvalues of the matrix and taking the real part of their product.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Very elegant! +1. \$\endgroup\$ – Giuseppe Nov 11 '17 at 19:36
3
\$\begingroup\$

Haskell, 62 bytes

a#((b:c):r)=b*d(a++map tail r)-(a++[c])#r
_#_=0
d[]=1
d l=[]#l

Try it online! (Footer with test cases taken from @totallyhuman's solution.)

d computes the determinant using a Laplace expansion along the first column. Needs three bytes more than the permanent.

\$\endgroup\$
5
\$\begingroup\$

Haskell, 59 bytes

p%(l:r)=l!!0*f(tail<$>p++r)-(p++[l])%r
[]%_=1
p%_=0
f=([]%)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 75 bytes

f=lambda m,p=[]:m[0][0]*f(zip(*p+m[1:])[1:])-f(m[1:],p+m[:1])if m else[]==p

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 6 bytes

matdet

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.