# matrici.py
import copy,geom

def cramer2 (A,c):
  (a1,b1)=A[0]; (a2,b2)=A[1]; pc=[a1,a2]; sc=[b1,b2]
  D=float(det2(A))
  x=det2([c,sc])/D; y=det2([pc,c])/D; return [x,y]

def det (A):
  A=triangolare(A)
  if A==None: return 0
  n=len(A); p=1
  for i in xrange(0,n): p*=A[i][i]
  return p

def det2 (A): (a,b)=A[0]; (c,d)=A[1]; return a*d-b*c

def det3 (A):
  u=A[0]; v=A[1]; w=A[2]
  return geom.prodottoscalare(u,prodottovettoriale(v,w))

def gauss (A):
  n=len(A); A=triangolare(A)
  if A==None: return None
  A=risolvitriangolare(A)
  A=trasposta(A); m=len(A); A=A[n:]; A=trasposta(A); return(A)

def identica (n):
  A=range(n)
  for i in xrange(n): A[i]=range(n)
  for i in xrange(n):
    for j in xrange(n):
      if i==j: A[i][j]=1
      else: A[i][j]=0
  return A

def inversa (A):
  B=trasposta(A)
  B.extend(identica(len(A)))
  B=trasposta(B); return gauss(B)

def mul (A,B):
  C=[]; Bt=trasposta(B)
  for r in A:
    rigaC=[]
    for c in Bt: rigaC.append(geom.prodottoscalare(r,c))
    C.append(rigaC)
  return C

def mulmatvet (A,x):
  y=[]
  for r in A: y.append(geom.prodottoscalare(r,x))
  return y

def mulvetmat (x,A):
  y=[]; At=trasposta(A)
  for c in At: y.append(geom.prodottoscalare(x,c))
  return y

def perno (A,j):
  B=A[j:]; A=A[0:j]
  B.sort(key=lambda r: abs(r[j]),reverse=1)
  A.extend(B); return A

def prodottovettoriale (v,w):
  (v1,v2,v3)=v; (w1,w2,w3)=w
  return [v2*w3-v3*w2,v3*w1-v1*w3,v1*w2-v2*w1]

# I coefficienti nella diagonale principale
# devono essere diversi da 0.
def risolvitriangolare (A):
  A=copy.deepcopy(A); n=len(A)
  for i in xrange(0,n): A[i]=geom.mul(1/float(A[i][i]),A[i])
  for j in xrange(n-1,-1,-1):
    Aj=A[j]
    for i in xrange(0,j):
      A[i]=geom.diff(A[i],geom.mul(A[i][j],Aj))
  return A

def trasposta (A):
  return map(list,apply(zip,A))

def triangolare (A):
  A=copy.deepcopy(A); n=len(A)
  for j in xrange(0,n):
    A=perno(A,j)
    Aj=A[j]; ajj=float(Aj[j])
    if ajj==0: return None
    for i in xrange(j+1,n):
      A[i]=geom.diff(A[i],geom.mul(A[i][j]/ajj,Aj))
  return A