1####################################################################### 2## 3#O UnitForm( <B> ) 4## 5## A unitform is identitied with a symmetric square matrix, where the 6## entries along the diagonal are all 2. The bilinear form associated 7## to the unitform given by a matrix B is defined for two vectors 8## x and y as: 9## x*B*y^T 10## The quadratic form associated to the unitform given by a matrix B 11## is defined for a vector x as: 12## (1/2)*x*B*x^T 13## The bilinear and the quadratic forms associated to a unitform B are 14## attributes of the unitform and they are given by 15## BilinearFormOfUnitForm(B) 16## and 17## QuadraticFormOfUnitForm(B). 18## The matrix of a unitform is also given as an attribute by 19## SymmetricMatrixOfUnitForm(B). 20## 21InstallMethod( UnitForm, 22 "for a matrix", 23 [ IsMatrix ], 24 25 function( B ) 26 local dimB, bilinearform, quadraticform, unitform; 27 28 # 29 # Checking the input. 30 # 31 dimB := DimensionsMat(B); 32 if dimB[1] <> dimB[2] then 33 Error("the entered matrix is not a square matrix,\n"); 34 fi; 35 if not ForAll(Flat(B), IS_INT) then 36 Error("the entered matrix is not an integer matrix,\n"); 37 fi; 38 if not ForAll([1..dimB[1]], x -> B[x][x] = 2) then 39 Error("the matrix doesn't have 2's along the diagonal,\n"); 40 fi; 41 if not B = TransposedMat(B) then 42 Error("the entered matrix is not a symmetric matrix,\n"); 43 else 44 # 45 # if the input is OK, define the bilinear and quadratic form, 46 # and set the associated symmetric matrix. 47 # 48 bilinearform := function( x, y ); 49 50 if not ( IsVector(x) or IsVector(y) ) then 51 Error("the arguments of the bilinear form must be in the category IsVector,\n"); 52 fi; 53 if Length(x) <> Length(y) then 54 Error("the arguments are not vectors of the same length,\n"); 55 fi; 56 if Length(x) <> Length(B[1]) then 57 Error("the arguments don't have correct size,\n"); 58 fi; 59 60 return x*B*y; 61 end; 62 quadraticform := function( x ) 63 if not IsVector(x) then 64 Error("the argument of the quadratic form must be in the category IsVector,\n"); 65 fi; 66 if Length(x) <> Length(B[1]) then 67 Error("the argument doesn't have the correct size,\n"); 68 fi; 69 70 return (1/2)*x*B*x; 71 end; 72 73 unitform := Objectify( NewType( ElementsFamily( FamilyObj( B ) ), 74 IsUnitForm and IsUnitFormRep ), rec( type := "undetermined" )); 75 SetSymmetricMatrixOfUnitForm(unitform, B); 76 SetBilinearFormOfUnitForm(unitform, bilinearform); 77 SetQuadraticFormOfUnitForm(unitform, quadraticform); 78 return unitform; 79 fi; 80end 81); 82 83####################################################################### 84## 85#M ViewObj( <B> ) 86## 87## This function defines how View prints a UnitForm <B>. 88## 89InstallMethod( ViewObj, 90 "for a UnitForm", 91 true, 92 [ IsUnitForm ], NICE_FLAGS+1, 93 function ( B ); 94 95 View(SymmetricMatrixOfUnitForm(B)); 96end 97); 98 99####################################################################### 100## 101#O TitsUnitFormOfAlgebra( <A> ) 102## 103## This function returns the Tits unitform associated to a finite 104## dimensional quotient of a path algebra given that the underlying 105## quiver has no loops or minimal relations that starts and ends in 106## the same vertex. That is, then it returns a symmetric matrix B 107## such that for x = (x_1,...,x_n) 108## (1/2)*(x_1,...,x_n)B(x_1,...,x_n)^T = 109## \sum_{i=1}^n x_i^2 - \sum_{i,j} dim_k Ext^1(S_i,S_j)x_ix_j 110## + \sum_{i,j} dim_k Ext^2(S_i,S_j)x_ix_j 111## where n is the number of vertices in Q. 112## 113InstallMethod( TitsUnitFormOfAlgebra, 114 "for a QuotientOfPathAlgebra", 115 [ IsAdmissibleQuotientOfPathAlgebra ], 116 117 function( A ) 118 local fam, I, KQ, Q, arrows, gens, JI, IJ, JI_IJ, Aprime, IAprime, 119 famAprime, gb, ImodJI_IJ, gensforImodJI_IJ, ext2matrix, pids, 120 i, j, temp; 121 122 if not IsFiniteDimensional(A) then 123 Error("the entered algebra is not finite dimensional,\n"); 124 fi; 125 # 126 # Checking if the quiver has any loops. 127 # 128 KQ := OriginalPathAlgebra(A); 129 Q := QuiverOfPathAlgebra(A); 130 if not ForAll([1..NumberOfVertices(Q)], i -> AdjacencyMatrixOfQuiver(Q)[i][i] = 0) then 131 Error("the quiver of the algebra has at least one loop,\n"); 132 fi; 133 # 134 # Finding elements generating the ideal JI + IJ and primitive orthogonal 135 # idempotents which sum is the identity. 136 # 137 fam := ElementsFamily(FamilyObj(A)); 138 I := fam!.ideal; 139 arrows := ArrowsOfQuiver(Q); 140 gens := GeneratorsOfTwoSidedIdeal(I); 141 JI := Filtered(Flat(List(gens, g -> List(arrows, a -> a*g))), x -> x <> Zero(x)); 142 IJ := Filtered(Flat(List(gens, g -> List(arrows, a -> g*a))), x -> x <> Zero(x)); 143 JI_IJ := Concatenation(JI,IJ); 144 if Length(JI_IJ) = 0 then 145 Aprime := KQ; 146 ImodJI_IJ := gens; 147 pids := List(VerticesOfQuiver(Q), v -> v*One(KQ)); 148 else 149 Aprime := KQ/JI_IJ; 150 famAprime := ElementsFamily(FamilyObj(Aprime)); 151 IAprime := famAprime!.ideal; 152 gb := GroebnerBasisOfIdeal(IAprime); 153 ImodJI_IJ := Unique(List(gens, x -> 154 ElementOfQuotientOfPathAlgebra(famAprime, CompletelyReduce(gb,x),true))); 155 pids := List(VerticesOfQuiver(Q), v -> 156 ElementOfQuotientOfPathAlgebra(famAprime,CompletelyReduce(gb,v*One(KQ)),true)); 157 fi; 158 gensforImodJI_IJ := List([1..Length(pids)], x -> List([1..Length(pids)], y -> [])); 159 ext2matrix := NullMat(Length(pids),Length(pids)); 160 for i in [1..Length(pids)] do 161 for j in [1..Length(pids)] do 162 gensforImodJI_IJ[i][j] := Filtered(pids[i]*ImodJI_IJ*pids[j], y -> y <> Zero(y)); 163 gensforImodJI_IJ[i][j] := BasisVectors(Basis(Subspace(Aprime,gensforImodJI_IJ[i][j]))); 164 ext2matrix[i][j] := Length(gensforImodJI_IJ[i][j]); 165 od; 166 od; 167 if not ForAll([1..Length(pids)], i -> ext2matrix[i][i] = 0) then 168 Error("the algebra has at least one minimal relation starting and ending in the same vertex,\n"); 169 fi; 170 temp := IdentityMat(NumberOfVertices(Q)) - AdjacencyMatrixOfQuiver(Q) + ext2matrix; 171 172 return UnitForm(temp + TransposedMat(temp)); 173end 174); 175 176InstallMethod( TitsUnitFormOfAlgebra, 177 "for a PathAlgebra", 178 [ IsPathAlgebra ], 179 180 function( A ) 181 local Q, temp; 182 183 Q := QuiverOfPathAlgebra(A); 184 temp := IdentityMat(NumberOfVertices(Q)) - AdjacencyMatrixOfQuiver(Q); 185 return UnitForm(temp + TransposedMat(temp)); 186end 187); 188 189####################################################################### 190## 191#O ReflectionByBilinearForm( <B>, <i>, <z> ) 192## 193## Computing the reflection of a vector z with respect to a bilinear form 194## given by a matrix B in the coordinate i. 195## 196InstallMethod( ReflectionByBilinearForm, 197 "for bilinear form, integer and a vector", 198 [ IsUnitForm, IS_INT, IsVector ], 199 200 function( B, i, z ) 201 local q, n, e_i; 202 203 q := BilinearFormOfUnitForm(B); 204 n := DimensionsMat(SymmetricMatrixOfUnitForm(B))[1]; 205 e_i := ShallowCopy(Zero(SymmetricMatrixOfUnitForm(B)[1])); 206 e_i[i] := 1; 207 if Length(z) = n then 208 return z - q(z,e_i)*e_i; 209 else 210 Error("the entered vector for reflection was not of correct size,\n"); 211 fi; 212end 213); 214 215####################################################################### 216## 217#O IsWeaklyNonnegativeUnitForm( <B> ) 218## 219## This function returns true if the unit form is weakly non-negative and false 220## otherwise. It is based on the algorithm given by A. Dean and J. A. de la 221## Pena in "Algorithms for quadratic forms", Linear algebra and its 222## applications, 235 (1996) 35-46. Comments in the code are using the same 223## notation as in this paper. 224## 225InstallMethod( IsWeaklyNonnegativeUnitForm, 226 "for sets", 227 [ IsUnitForm ], 228 229 function( B ) 230 local q, A, Bmatrix, n, simples, i, temp, C, flag, test_one, test_two, v, R, r, j; 231 232 q := BilinearFormOfUnitForm(B); 233 A := SymmetricMatrixOfUnitForm(B); 234 n := DimensionsMat(A)[1]; 235 simples := IdentityMat(n); 236 C := ShallowCopy(simples); # this is C_1. 237 flag := true; 238 while flag do 239 for v in C do # performing the test in (2) (a) 240 if ForAny(simples, e -> q(v,e) <= -3) then 241 return false; 242 fi; 243 od; 244 for v in C do # performing the test in (2) (b) 245 if ForAny(simples, e -> ( q(v,e) = -2 ) and not ForAll((v+e)*A, x -> x >= 0 ) ) then 246 return false; 247 fi; 248 od; 249 # 250 # Now we know that the procedure didn't fail. 251 # Construct R_s, i.e. step (3) in the algorithm. 252 # 253 R := Filtered(C, v -> ( ForAll(v, y -> y <= 6) and ForAny(simples, e -> q(v,e) = -1 ) ) ); 254 if Length(R) = 0 then # step (4) 255 flag := false; 256 return true; # C_{s+1} is empty, return "successful". 257 else 258 C := []; 259 for r in R do # construct C_{s+1}, i.e. step (5) in the algorithm. 260 j := Position(simples, First(simples, s -> q(r,s) = -1 )); 261 Add(C,ReflectionByBilinearForm(B,j,r)); 262 od; 263 fi; 264 od; 265end 266); 267 268####################################################################### 269## 270#O IsWeaklyPositiveUnitForm( <B> ) 271## 272## This function returns true if the unit form is weakly positive and false 273## otherwise. It is based on the algorithm given by Hans-Joachim von Hoehne 274## "Edge reduction for unit forms", Arch. Math. vol. 65 (1995) 300-302. 275## Comments in the code are using the same notation as in this paper. In addition 276## the function computes the roots of the unit form when true is returned. 277## 278InstallMethod( IsWeaklyPositiveUnitForm, 279 "for a UnitForm", 280 [ IsUnitForm ], 281 282 function( B ) 283 local q, n, flag, reductionpairs, m, testI, roots, temp, testII, 284 breakflag, j, i, reductionnumber, lastcolumn, lastrow, qq, s; 285 286 q := ShallowCopy(SymmetricMatrixOfUnitForm(B)); 287 flag := false; 288 reductionpairs := []; 289 m := DimensionsMat(q)[1]; 290 while not flag do 291 n := DimensionsMat(q)[1]; 292 # 293 # Performing test I) from the paper. 294 # 295 testI := ForAll(Flat(List([1..n], j -> List([1..j-1], i -> q[i][j]))), x -> x >= 0); 296 if testI then 297 roots := ShallowCopy(IdentityMat(m)); 298 for i in [Length(reductionpairs), Length(reductionpairs) - 1..1] do 299 temp := roots[reductionpairs[i][1]]{[1..m + i - Length(reductionpairs) - 1]} + 300 roots[reductionpairs[i][2]]{[1..m + i - Length(reductionpairs) - 1]}; 301 for j in [1..Length(roots)] do 302 roots[j] := roots[j]{[1..m + i - Length(reductionpairs) - 1]} + 303 roots[j][m + i - Length(reductionpairs)]*temp; 304 od; 305 od; 306 SetPositiveRootsOfUnitForm(B,roots); 307 B!.type := "weakly_positive"; 308 return true; 309 fi; 310 # 311 # Performing test II) from the paper. 312 # 313 testII := ForAny(Flat(List([1..n], j -> List([1..j-1], i -> q[i][j]))), x -> x <= -2); 314 if testII then 315 return false; 316 fi; 317 breakflag := false; 318 for j in [1..n] do 319 for i in [1..j] do 320 if q[i][j] = -1 then 321 Add(reductionpairs, [i,j]); 322 m := m + 1; 323 breakflag := true; 324 break; 325 fi; 326 od; 327 if breakflag then 328 break; 329 fi; 330 od; 331 # 332 # Preforming reduction of unit form. 333 # 334 if breakflag then 335 reductionnumber := Length(reductionpairs); 336 i := reductionpairs[reductionnumber][1]; 337 j := reductionpairs[reductionnumber][2]; 338 lastcolumn := TransposedMat(q)[i] + TransposedMat(q)[j]; 339 lastrow := ShallowCopy(q[i] + q[j]); 340 qq := List(q, r -> ShallowCopy(r)); 341 for s in [1..n] do 342 Add(qq[s],lastcolumn[s]); 343 od; 344 Add(lastrow,2); 345 Add(qq,lastrow); 346 qq[i][j] := 0; 347 qq[j][i] := 0; 348 q := qq; 349 fi; 350 od; 351 352 return false; 353end 354); 355 356 357 358 359####################################################################### 360## 361#O EulerBilinearFormOfAlgebra( <A> ) 362## 363## This function returns the Euler (non-symmetric) bilinear form 364## associated to a finite dimensional (basic) quotient of a path algebra <A>. 365## That is, it returns a bilinear form (function) defined by 366## <x,y> = x*CartanMatrix^(-1)y 367## It makes sense only in case <A> is of finite global dimension. 368## (Recall that in QPA the rows of the CartanMatrix are the dimension 369## vectors of projectives). 370## 371InstallMethod( EulerBilinearFormOfAlgebra, 372 "for a PathAlgebra or a QuotientOfPathAlgebra", 373 [ IsQuiverAlgebra ], 374 375 function( A ) 376 local C, bilinearform; 377 378 C := CartanMatrix(A); 379 # Operation CartanMatrix checks if A is: 380 # FiniteDimensional and (PathAlgebra or AdmissibleQuotientOfPathAlgebra) 381 # in particular, if A is basic 382 if C = fail then 383 Print("Unable to determine the Cartan matrix!\n"); 384 return fail; 385 fi; 386 387 if not Determinant(C) in [-1,1] then 388 Print("The Cartan matrix is not invertible over Z!\n"); 389 return fail; 390 fi; 391 392 bilinearform := function( x, y ); 393 394 if not ( IsVector(x) or IsVector(y) ) then 395 Error("the arguments of the bilinear form must be in the category IsVector,\n"); 396 fi; 397 if Length(x) <> Length(y) then 398 Error("the arguments are not vectors of the same length,\n"); 399 fi; 400 if Length(x) <> Length(C[1]) then 401 Error("the arguments don't have correct size,\n"); 402 fi; 403 404 return x*Inverse(C)*y; 405 end; 406 407 return bilinearform; 408end 409); # EulerBilinearFormOfAlgebra