#########################################################
# Programme GAP4 pour calculer la dimension             #
# de l'algebre de Lie engendree par la liste            #
# de matrices Z, sur un corps non specifie.             #
# Debut : 11/11/05                                      #
#########################################################
# modif provisoire 13/11/05, qui ne prend pas en compte celle du 12/11...
# (test)

# procedures auxiliaires

# on suppose que MM est une matrice triangulaire, avec
# possiblement des lignes de 0 *a la fin*, on enleve ces lignes.
# 	
# NB1 : il faut qu'il n'y ait pas de ligne remplie de zeros au milieu,
# sinon cela creerait une liste avec des trous
# NB2 : si on voulait creer une nouvelle liste, Filtered suffirait

EnleveZeros := function(MM)
	local n,i,j,lc;
	n := Length(MM);
	for i in [1..n] do
		j := n-i+1;
		lc := SSortedList(MM[j]);
		if Length(lc)=1 and IsZero(lc[1]) then Unbind(MM[j]); fi;
	od;
end;
	
	
# Explication des variables locales/parametres :
#
# Z : liste des matrices des generateurs (au moins 1)
#
# d : taille des matrices
# n : nombre de generateurs
# M : liste des matrices deja obtenues, eventuellement triangularisees
# m : dimension obtenue
# NM : nouvelles matrices

# Algorithme :
#
# 1) On recopie Z dans M et NM
# 2) 


dimension := function(Z)
	local d,n,M,NM,m,NM2,i,j,x;
	d := Length(Z[1]);
	n := Length(Z);
	M := Z;
	NM := M;
	M := List(M,Concatenation);
	TriangulizeMat(M);
	EnleveZeros(M);
	m := Length(M);
	NM2 := [1];
	while Length(NM2)>0 do
		# Print(m); Print("\n");
		NM2 := [];
		for i in [1..n] do
			for j in [1..Length(NM)] do
				x := Z[i]*NM[j] - NM[j]*Z[i];
				Add(M,Concatenation(x));
				TriangulizeMat(M);
				EnleveZeros(M);
				if Length(M)>m then
					m := Length(M);
					Add(NM2,x);
				fi;
			od;
		od;
		NM := NM2;
	od;
	return Length(M);
end;
	

	

# Pour une liste de matrices a coefficients dans Q, trouve
# le plus petit multiple a coefficients entiers (multiplie
# par le ppcm des denominateurs) et le retourne.

viredenom := function(Z)
	local LC;
	LC := Lcm(List(Concatenation(Concatenation(Z)),DenominatorRat));
	return LC*Z;
end;