Name: Anonymous 2009-04-09 10:07
I'M NOT THINKING WITH MATRICES
#/usr/bin/python
identity = lambda n: [[0]*a + [1] + [0]*(n - 1 - a) for a in xrange(n)]
augment = lambda m: [m[i] + identity(len(m))[i] for i in xrange(len(m))]
deaugment = lambda m: [row[len(m):] for row in m]
rowswitch = lambda m, i, j: \
m[:i] + [m[j]] + m[i+1:j] + [m[i]] + m[j+1:] if i < j else \
m[:j] + [m[i]] + m[j+1:i] + [m[j]] + m[i+1:] if i > j else m
rowmultiply = lambda m, r, i: \
m[:r] + [map(lambda n: n * i, m[r])] + m[r+1:]
rowadd = lambda m, r1, r2, i: \
m[:r2] + [map(sum, zip(map(lambda n: n * i, m[r1]), m[r2]))] + m[r2+1:]
def invert(m):
m = augment(m)
for i in xrange(len(m)):
k = i
try:
while m[k][i] == 0: k += 1
except:
raise "Cannot be inverted"
m = rowswitch(m, i, k)
m = rowmultiply(m, i, 1 / m[i][i])
for j in xrange(len(m)):
if j != i and m[j][i] != 0:
m = rowadd(m, i, j, -m[j][i])
return deaugment(m)