matrix determinant

Question

Calculate the determinant of an n x n matrix.

Rules

• read matrix from standard input
• write to standard output
• do not use ready solutions from library or language
• input: columns separated by any space char
• input: lines separated by cr and/or lf

Winner

• The shortest code :)

Answer 1

GolfScript, 58 chars

n%{~]}%{[.!{(.,,0\{:^2$=-1^?*3${.^<\^)>+}%d*+}/}or])\;}:d~

A straightforward recursive algorithm using Laplace expansion.

Example input (random 5 × 5 matrix):

-562   40   43 -586  347
-229  177  305 -367   50
-434  343  241 -365  -86
-3   -384 -351   61 -214
-400   96 -339   25 -116

Output: 282416596900 (Online demo; Verify with Wolfram Alpha)

The code consists of three parts:

• n%{~]}% parses the input,
• {[.!{(.,,0\{:^2$=-1^?*3${.^<\^)>+}%d*+}/}or])\;}:d defines a recursive subroutine to calculate the determinant, and
• the final ~ applies the subroutine to the input.

I'm sure there's room for improvement in this code, but at least I beat Gareth by three chars. Also, {:^2$= is a pretty nice GS smiley. :)

Answer 2

Haskell, 139 131

(a:r)%0=r;(a:r)%n=a:r%(n-1)
d[]=1;d(f:r)=foldr(\(j,x)->(x*d(map(%j)r)-))0$zip[0..]f
main=interact$show.d.map(map read.words).lines

Answer 3

Python 233

def d(x):
 l=len(x)
 if l<2:return x[0][0]
 return sum([(-1)**i*x[i][0]*d(m(x,i))for i in range(l)])
def m(x,i):y=x[:];del(y[i]);y=zip(*y);del(y[0]);return zip(*y)
x=[input()]
for i in (len(x[0])-1)*[1]:x+=[input()]
print d(x)

Ungolfed:

def det(x):
    l = len(x)
    if l == 1:
        return x[0][0]
    return sum([(-1)**i*x[i][0]*det(minor(x,i+1,1)) for i in range(l)])

def minor(x,i,j):
    y = x[:]
    del(y[i-1])
    y=zip(*y)
    del(y[j-1])
    return zip(*y)

def main():
    x = [input()]
    for i in range(len(x[0])-1):
        x += [input()]
    print det(x)

if __name__ == '__main__':
    main()

Usage

As requested, input is on stdin and output is to stdout.

I interpreted columns separated by any space char to mean that I can use comma delimited numbers. If this is not the case, I will rework my solution.

This could be about 30 characters shorter if I could specify my input matrix in the form [[a,b,c],[d,e,f],[g,h,i]].

./det.py
1,-4,9
-6,7,3
1,2,3

Result

-240

The determinant is found using Laplace Expansion

Answer 4

Python, 369

This is ridiculously long, but I thought I'd provide a solution that implements the Leibniz formula.

def f(l):
    if len(l)==1:return [l]
    a=[]
    for s in l:
        for p in f(list(set(l)-set([s]))):a+=[[s]+p]
    return a
def s(a):
    n=1
    for i in range(len(a)):n*=(-1)**(a[i]>i);a[a.index(i)]=a[i];a[i]=i
    return n
m=[map(int,w.split(','))for w in raw_input().split(' ')]
r=range(len(m))
print sum([reduce(lambda x,y:x*y,[m[p[i]][i] for i in r],1)*s(p) for p in f(r)])

Values are read from stdin in a format like 1,2,-3 7,0,4 -1,-3,0 with a single space between columns. I wouldn't have posted this, but it was fun to write and contains a couple interesting sub-problems. The function f generates all permutations of n elements, and the function s determines the parity of those permutations.

Answer 5

Python, 198

This also uses the Liebniz formula. I'm using a heavily-modified version of ugoren's permutation solution to generate permutations and their inversion counts simultaneously. (edit: now correct!)

t=input()
e=enumerate
p=lambda t:t and((b+[a],j+i)for i,a in e(t)for b,j in p(t[:i]+t[i+1:]))or[([],0)]
print sum(reduce(lambda t,(i,r):t*r[i],e(p),1-i%2*2)for p,i in p([t]+[input()for x in t[1:]]))

Answer 6

Dyalog APL, 53 58 59 characters

{1=≢⍵:⊃⍵⋄-/⍵[1;]×∇¨{w[f~1;f~⍵]}¨f←⍳⊃⍴w←⍵}U⍪↑{⎕}¨1↓⍳⍴U←⎕

I'm pretty late to the party here. Please, alert me if there are any issues with this code! Takes negatives as input via ¯ (the APL negative sign). I think values by default go to STDOUT in APL, but I may be wrong.

Uses Laplace expansion to find the determinant of the matrix.

This program is separated into three main parts: an input section, and the case of a 1x1 matrix, and the actual recursive function.

Input program:

U⍪↑{⎕}¨1↓⍳⍴U←⎕
             ⎕ - Takes evaluated input, space separated numbers are vectors in APL.
           U←  - Stores the input into variable `U`.
         ⍳⍴    - The array of integers from 1 to the length of `U` (inclusive).
       1↓      - Drops the first element of the result.
   {⎕}¨        - Receives a new input for each element in the vector. (Result is a vector of vectors)
  ↑            - Transforms the vector vector into a 2D-array.
U⍪             - The original line was stored then used for its length, so we stick it on top of the new array.

1x1 case:

{1=≢⍵:⊃⍵⋄...}
       ⍵      - The input
      ⊃       - The first element of the input
     :        - Return that if and only if ...
   ≢⍵         - The largest dimension of the input matrix
 1=           - Has equality with 1.
        ⋄     - Statement separator
{           } - Function enclosure brackets.

Actual determinant program:

{...-/⍵[1;]×∇¨{w[f~1;f~⍵]}¨f←⍳⊃⍴w←⍵}
                                w←⍵  - The input stored in `w`
                               ⍴     - The dimensions of `w`
                              ⊃      - The first dimension
                             ⍳       - 1 to the result of last operation
                           f←        - Store the result in `f`
              {          }¨          - Do what is inside the brackets to each member of `f`
               w[f~1;f~⍵]            - Return the minor matrix.
            ∇¨                       - Find determinant of each element (recursive)
      ⍵[1;]×                         - Multiply elementwise by the first row of the input matrix
    -/                               - Reduction using subtraction, since APL evaluates right to left, it comes out to be + - + - ...

Answer 7

J, 61 characters

-/>([:+/#(([{.<:@[}.])[:*//._2,\2#])])&.>(|.;])".];._2[1!:1[3

A big ugly bit of code that takes its input from stdin (if you're running this on Windows you may need to change ".];._2[1!:1[3 to ".}:@];._2[1!:1[3 to ensure both character return and line feed are removed).

   -/>([:+/#(([{.<:@[}.])[:*//._2,\2#])])&.>(|.;])".];._2[1!:1[3
1 8 5
2 7 3
9 9 4
_72
   -/>([:+/#(([{.<:@[}.])[:*//._2,\2#])])&.>(|.;])".];._2[1!:1[3
_2 2 3
_1 1 3
2 0 _1
6

Of course, no-one using J would ever bother to do this. They'd just use:

(-/ .*)".];._2[1!:1[3

making use of the . determinant verb.

Answer 8

Jq 1.5, 171 bytes

This is a golf-ed version of det from rosettacode Matrix arithmetic - jq.

def d:if[paths]==[[0],[0,0]]then.[0][0]else. as$m|reduce range(length)as$i(0;.+({"0":1}["\($i%2)"]//-1)*$m[0][$i]*($m|reduce del(.[0])[]as$r([];.+[$r|del(.[$i])])|d))end;d

Original

def except(i;j):
  reduce del(.[i])[] as $row ([]; . + [$row | del(.[j]) ] );

def det:
  def parity(i): if i % 2 == 0 then 1 else -1 end;
  if length == 1 and (.[0] | length) == 1 then .[0][0]
  else . as $m
    | reduce range(0; length) as $i
        (0; . + parity($i) * $m[0][$i] * ( $m | except(0;$i) | det) )
  end ;

Alterations:

• replace base case condition with [paths]==[[0],[0,0]]
• replace parity($i) with ({"0":1}["\($i%2)"]//-1)
• replace except(0;$i) with inline definition
• replace det,row with d,r and remove whitespace

Try it online!

Answer 9

Python, 181 characters

Late to the party, but here's a simple 181 character implementation of Laplace:

l,r=len,range
d=lambda A:sum((-1)**i*A[0][i]*d([[A[x][y]for x in r(1,l(A))]for y in r(i)+r(1+i,l(A))])for i in r(l(A)))if len(A)>1 else A[0][0]
print d(map(eval,iter(raw_input,'')))

This meets the specs if "any space character" includes commas, which seems to be the norm here. Otherwise,

l,r=len,range
d=lambda A:sum((-1)**i*A[0][i]*d([[A[x][y]for x in r(1,l(A))]for y in r(i)+r(1+i,l(A))])for i in r(l(A)))if len(A)>1 else A[0][0]
print d(map(lambda x:map(int,x.split(' ')),iter(raw_input,'')))

is 207 characters.

Input is terminated by entering a blank line.