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