matrix determinant

Question

Calculate the determinant of a 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, 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 4

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 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

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.