basis -- basis or generating set of all or part of a ring, ideal or module

Synopsis

Usage:

f = basis M

f = basis(deg, M)

f = basis(lo, hi, M)
Inputs:
- M, a module, a ring, an ideal, or a matrix,
- deg, an integer or a list, a degree or degree vector
- lo, an integer or an infinite number, or -infinity, the low degree
- hi, an integer or an infinite number, or infinity, the high degree
Optional inputs:
- Limit => an integer, default value infinity, an upper bound on the number of basis elements to collect
- Variables => a list, default value null, a list of variables, or variable indices (defaults to the generators of the ring of M)
- SourceRing => a ring, default value null, if not the ring (of) M, then returns a module map whose target and source have different rings
- Strategy => a thing, default value null, specifies the algorithm
- Degree => ..., default value null, an integer or a list, sets the degree of the resulting matrix. Default is 0. Seldom Used
- Truncate => a Boolean value, default value false, internal use only. Used to implement truncate(ZZ,Module)
Outputs:
- f, a matrix, a map from a free module over the ring of M (or by the ring specified with the SourceRing option, if given), to M which sends the basis elements of the free module to a basis (over the coefficient field) of the specified part of M

Description

The function basis finds a basis or generating set of a module over a coefficient ring, either for the full module, or for a degree range, or for a specific (multi-)degree. A ring or ideal may also be provided instead of a module. Partial multi-degrees may also be given, see below for the usage and meaning.

If $M$ is a matrix, then the matrix between the corresponding bases of the source and target of $M$ is returned. This feature should be considered experimental.

The following examples show the varied uses of this function.

Basis of the whole ring

If no degree or degree range is given, then a full basis is given. In the example below, the 12 entries generate $R$ over the base ring ${\mathbb Q}$. If the object is not finite, then an error is given.

i1 : R = QQ[a,b,c]/(a^2, b^3, a*c, c^3);

i2 : basis R

o2 = | 1 a ab ab2 b b2 b2c b2c2 bc bc2 c c2 |

             1      12
o2 : Matrix R  <-- R

i3 : sort basis R

o3 = | 1 c b a c2 bc b2 ab bc2 b2c ab2 b2c2 |

             1      12
o3 : Matrix R  <-- R

Basis in a degree or range of degrees

If a single degree or degree range is given, give a basis (or generating set) of that particular degree (or degree range) of $M$.

i4 : R = QQ[x,y,z]

o4 = R

o4 : PolynomialRing

i5 : basis(2,R)

o5 = | x2 xy xz y2 yz z2 |

             1      6
o5 : Matrix R  <-- R

i6 : I = ideal"x2,y3"

             2   3
o6 = ideal (x , y )

o6 : Ideal of R

i7 : phi = basis(3,I)

o7 = {2} | x y z 0 |
     {3} | 0 0 0 1 |

o7 : Matrix

i8 : super phi

o8 = | x3 x2y x2z y3 |

             1      4
o8 : Matrix R  <-- R

Notice that phi is a matrix whose source is a free module, and whose target is the ideal. super is used to get the actual elements of $I$.

Basis in a specific multi-degree

If a multidegree is given, then a range cannot be given. In this example, the dimension over QQ of this multigraded piece of R is 2.

i9 : R = QQ[a..c,Degrees=>{{1,0},{1,-1},{1,-2}}]

o9 = R

o9 : PolynomialRing

i10 : basis({4,-5},R)

o10 = | abc2 b3c |

              1      2
o10 : Matrix R  <-- R

Partially described multidegrees

A partial multidegree can be given. The given columns generate (form a basis in this case) the degree \{2,*\} part of R, over the subring QQ[d] generated by the variables which have degree \{0,*\}.

i11 : R = QQ[a..d,Degrees=>{{1,0},{1,-1},{1,-2},{0,1}}]

o11 = R

o11 : PolynomialRing

i12 : basis(2,R)

o12 = | a2 ab ac b2 bc c2 |

              1      6
o12 : Matrix R  <-- R

The base ring does not need to be a field. In these cases, the given image vectors might only generate over the base ring, not be a basis. For instance, in the following example, $B$ is generated over $A$ by 4 elements, but $B$ is not a free module.

i13 : A = ZZ/101[a..d];

i14 : B = A[x,y]/(a*x, x^2, y^2);

i15 : basis B

o15 = | 1 x xy y |

              1      4
o15 : Matrix B  <-- B

If $M$ is an ideal or module, the resulting map looks somewhat strange, since maps between modules are given from generators, in terms of the generators of the target module. Use super or cover to recover the actual elements.

i16 : R = QQ[a,b,c]/(a^2, b^3, a*c, c^3);

i17 : I = ideal(a,b^2,c)

                 2
o17 = ideal (a, b , c)

o17 : Ideal of R

i18 : F = basis I

o18 = {1} | 1 b 0 0 0 0  0 0 0  0 |
      {2} | 0 0 1 a c c2 0 0 0  0 |
      {1} | 0 0 0 0 0 0  1 b bc c |

o18 : Matrix

i19 : super F

o19 = | a ab b2 ab2 b2c b2c2 c bc bc2 c2 |

              1      10
o19 : Matrix R  <-- R

i20 : C = B[u,v]/(u^2,u*v,v^2)

o20 = C

o20 : QuotientRing

i21 : basis(C, Variables=>{u,v,x_C,y_C}, SourceRing => A)

o21 = | 1 u xu xyu yu v xv xyv yv x xy y |

              1      12
o21 : Matrix C  <-- A

If Variables is given as an optional argument, only monomial multiples of the generators which involve these variables will be considered. In this case, the resulting elements might not form a generating set over the coefficient ring. They do generate over the subring generated by the other variables.

i22 : D = QQ[a..d]/(a^2, b^2)

o22 = D

o22 : QuotientRing

i23 : basis(D, Variables => {a,b})

o23 = | 1 a ab b |

              1      4
o23 : Matrix D  <-- D

If the base ring has a local term order, then the generating set or basis will be over this ring.

i24 : E = QQ{a..d}

o24 = E

o24 : PolynomialRing

i25 : I = ideal(a+d^3-d^4, b^2 + d^3, c^2 + d^4, d^5)

                  3    4   2    3   2    4   5
o25 = ideal (a + d  - d , b  + d , c  + d , d )

o25 : Ideal of E

i26 : f = basis (E^1/I)

o26 = | 1 b bc bcd bcd2 bcd3 bcd4 bd bd2 bd3 bd4 c cd cd2 cd3 cd4 d d2 d3 d4
      -----------------------------------------------------------------------
      |

o26 : Matrix

i27 : cover f

o27 = | 1 b bc bcd bcd2 bcd3 bcd4 bd bd2 bd3 bd4 c cd cd2 cd3 cd4 d d2 d3 d4
      -----------------------------------------------------------------------
      |

              1      20
o27 : Matrix E  <-- E

Functoriality

basis is functorial, meaning that if $M : A \rightarrow B$ is a matrix between two modules, then the result is the induced matrix on the images of the result of basis applied to A and B.

i28 : R = ZZ/101[a..d]

o28 = R

o28 : PolynomialRing

i29 : M = koszul(2,vars R)

o29 = {1} | -b -c 0  -d 0  0  |
      {1} | a  0  -c 0  -d 0  |
      {1} | 0  a  b  0  0  -d |
      {1} | 0  0  0  a  b  c  |

              4      6
o29 : Matrix R  <-- R

i30 : f1 = basis(2, source M)

o30 = {2} | 1 0 0 0 0 0 |
      {2} | 0 1 0 0 0 0 |
      {2} | 0 0 1 0 0 0 |
      {2} | 0 0 0 1 0 0 |
      {2} | 0 0 0 0 1 0 |
      {2} | 0 0 0 0 0 1 |

              6      6
o30 : Matrix R  <-- R

i31 : f2 = basis(2, target M)

o31 = {1} | a b c d 0 0 0 0 0 0 0 0 0 0 0 0 |
      {1} | 0 0 0 0 a b c d 0 0 0 0 0 0 0 0 |
      {1} | 0 0 0 0 0 0 0 0 a b c d 0 0 0 0 |
      {1} | 0 0 0 0 0 0 0 0 0 0 0 0 a b c d |

              4      16
o31 : Matrix R  <-- R

i32 : f = basis(2,M)

o32 = {2} | 0  0  0  0  0  0  |
      {2} | -1 0  0  0  0  0  |
      {2} | 0  -1 0  0  0  0  |
      {2} | 0  0  0  -1 0  0  |
      {2} | 1  0  0  0  0  0  |
      {2} | 0  0  0  0  0  0  |
      {2} | 0  0  -1 0  0  0  |
      {2} | 0  0  0  0  -1 0  |
      {2} | 0  1  0  0  0  0  |
      {2} | 0  0  1  0  0  0  |
      {2} | 0  0  0  0  0  0  |
      {2} | 0  0  0  0  0  -1 |
      {2} | 0  0  0  1  0  0  |
      {2} | 0  0  0  0  1  0  |
      {2} | 0  0  0  0  0  1  |
      {2} | 0  0  0  0  0  0  |

o32 : Matrix

i33 : source f == image f1

o33 = true

i34 : target f == image f2

o34 = true

Obtain the map of free modules using matrix:

i35 : matrix f

o35 = {2} | 0  0  0  0  0  0  |
      {2} | -1 0  0  0  0  0  |
      {2} | 0  -1 0  0  0  0  |
      {2} | 0  0  0  -1 0  0  |
      {2} | 1  0  0  0  0  0  |
      {2} | 0  0  0  0  0  0  |
      {2} | 0  0  -1 0  0  0  |
      {2} | 0  0  0  0  -1 0  |
      {2} | 0  1  0  0  0  0  |
      {2} | 0  0  1  0  0  0  |
      {2} | 0  0  0  0  0  0  |
      {2} | 0  0  0  0  0  -1 |
      {2} | 0  0  0  1  0  0  |
      {2} | 0  0  0  0  1  0  |
      {2} | 0  0  0  0  0  1  |
      {2} | 0  0  0  0  0  0  |

              16      6
o35 : Matrix R   <-- R

Caveat

If the base ring is not a field, then the result is only a generating set. If the optional argument Variables is provided, then even this might not be correct.

Ways to use basis :

basis(Ideal)
basis(InfiniteNumber,InfiniteNumber,Ideal)
basis(InfiniteNumber,InfiniteNumber,Matrix)
basis(InfiniteNumber,InfiniteNumber,Module)
basis(InfiniteNumber,InfiniteNumber,Ring)
basis(InfiniteNumber,List,Ideal)
basis(InfiniteNumber,List,Matrix)
basis(InfiniteNumber,List,Module)
basis(InfiniteNumber,List,Ring)
basis(InfiniteNumber,ZZ,Ideal)
basis(InfiniteNumber,ZZ,Matrix)
basis(InfiniteNumber,ZZ,Module)
basis(InfiniteNumber,ZZ,Ring)
basis(List,Ideal)
basis(List,InfiniteNumber,Ideal)
basis(List,InfiniteNumber,Matrix)
basis(List,InfiniteNumber,Module)
basis(List,InfiniteNumber,Ring)
basis(List,List,Ideal)
basis(List,List,Matrix)
basis(List,List,Module)
basis(List,List,Ring)
basis(List,Matrix)
basis(List,Module)
basis(List,Ring)
basis(List,ZZ,Ideal)
basis(List,ZZ,Matrix)
basis(List,ZZ,Module)
basis(List,ZZ,Ring)
basis(Module)
basis(Ring)
basis(ZZ,Ideal)
basis(ZZ,InfiniteNumber,Ideal)
basis(ZZ,InfiniteNumber,Matrix)
basis(ZZ,InfiniteNumber,Module)
basis(ZZ,InfiniteNumber,Ring)
basis(ZZ,List,Ideal)
basis(ZZ,List,Matrix)
basis(ZZ,List,Module)
basis(ZZ,List,Ring)
basis(ZZ,Matrix)
basis(ZZ,Module)
basis(ZZ,Ring)
basis(ZZ,ZZ,Ideal)
basis(ZZ,ZZ,Matrix)
basis(ZZ,ZZ,Module)
basis(ZZ,ZZ,Ring)

For the programmer

The object basis is a method function with options.