vac2009

1036 days ago by pub

Doing algebra in Sage

Alex Ghitza (The University of Melbourne)

Twenty-Seventh Annual Victorian Algebra Conference

5 November 2009

 

Sage:

The goal of this short talk is to whet your appetite by giving you a quick overview of some algebra-related functionality in Sage.

(This is neither a Sage tutorial nor a Python tutorial.)
BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]]) 
       
BD 
        
Incidence structure with 7 points and 7 blocks
Incidence structure with 7 points and 7 blocks

Python is an object-oriented language, and most of the functionality in Sage is centred around objects, such as our block design BD.  To do something interesting with an object, we must access its methods:
BD.dual_design() 
        
Incidence structure with 7 points and 7 blocks
Incidence structure with 7 points and 7 blocks

To see what are the various methods implemented for block designs, one can read the corresponding chapter of the reference manual.  A quicker way is to use tab-completion (press Tab after the . below):
BD. 
        
Syntax Error:
    BD.                           # press Tab after the .
Syntax Error:
    BD.                           # press Tab after the .

We can visualise this design by looking at its incidence matrix:
M = BD.incidence_matrix() M 
        
[1 1 1 0 0 0 0]
[1 0 0 1 1 0 0]
[1 0 0 0 0 1 1]
[0 1 0 1 0 1 0]
[0 1 0 0 1 0 1]
[0 0 1 1 0 0 1]
[0 0 1 0 1 1 0]
[1 1 1 0 0 0 0]
[1 0 0 1 1 0 0]
[1 0 0 0 0 1 1]
[0 1 0 1 0 1 0]
[0 1 0 0 1 0 1]
[0 0 1 1 0 0 1]
[0 0 1 0 1 1 0]
M.plot(cmap='Oranges') 
       

Or we can look at the incidence graph:
G = BD.incidence_graph() G.plot(graph_border=1) 
       

What else can we do with the graph G?
G. 
        
Syntax Error:
    G.                                     # press Tab after .
Syntax Error:
    G.                                     # press Tab after .
A = G.automorphism_group() A.order() 
        
336
336
A 
        
Permutation Group with generators [(3,5)(4,6)(8,9)(12,13),
(3,6)(4,5)(8,9)(10,11), (1,2)(5,6)(10,12)(11,13),
(1,3)(2,4)(7,8)(11,12), (1,8)(2,9)(3,10)(4,11)(5,12)(6,13)(7,14),
(1,14)(4,5)(8,10)(9,11)]
Permutation Group with generators [(3,5)(4,6)(8,9)(12,13), (3,6)(4,5)(8,9)(10,11), (1,2)(5,6)(10,12)(11,13), (1,3)(2,4)(7,8)(11,12), (1,8)(2,9)(3,10)(4,11)(5,12)(6,13)(7,14), (1,14)(4,5)(8,10)(9,11)]

The automorphism group A is represented as a group of permutations of the graph's vertices.  Six generators might seem like a lot, so we wonder whether automorphism_group returns a minimal set of generators.  We could look up the method in the reference manual; but there's an easier way:
G.automorphism_group? 
       

One question mark gives us access to the method's docstring - which is very informative but doesn't answer the question we had about generators.  This is where the fun begins:
G.automorphism_group?? 
       

Two question marks give us the source code of the method.  Without getting more familiar with the algorithm, we still notice that some generators are computed and then the constructor PermutationGroup is called on them.
PermutationGroup? 
       

In a somewhat roundabout way, the description of the argument canonicalize suggests that no nontrivial work is done to obtain a minimal set of generators (which is a good thing because it is a potentially expensive operation that shouldn't be performed by default).  Some more tab-completion allows us to discover:
A.gens_small? 
       
A.gens_small() # in this case, easy to check that this is a minimal set of generators 
        
[(1,8)(2,9)(3,11)(4,10)(5,13)(6,12)(7,14),
(1,14,5,3,4,2,6)(7,9,10,8,13,12,11)]
[(1,8)(2,9)(3,11)(4,10)(5,13)(6,12)(7,14), (1,14,5,3,4,2,6)(7,9,10,8,13,12,11)]

Compare this to the original 6 generators:
A.gens() 
        
[(3,5)(4,6)(8,9)(12,13), (3,6)(4,5)(8,9)(10,11),
(1,2)(5,6)(10,12)(11,13), (1,3)(2,4)(7,8)(11,12),
(1,8)(2,9)(3,10)(4,11)(5,12)(6,13)(7,14), (1,14)(4,5)(8,10)(9,11)]
[(3,5)(4,6)(8,9)(12,13), (3,6)(4,5)(8,9)(10,11), (1,2)(5,6)(10,12)(11,13), (1,3)(2,4)(7,8)(11,12), (1,8)(2,9)(3,10)(4,11)(5,12)(6,13)(7,14), (1,14)(4,5)(8,10)(9,11)]
A = PermutationGroup(A.gens_small()) 
       
A.normal_subgroups() len(_) 
        
[Permutation Group with generators [()], Permutation Group with
generators [(3,5)(4,6)(8,9)(12,13), (3,6)(4,5)(8,9)(10,11),
(2,6,3)(4,5,14)(7,11,10)(8,13,9), (1,5,4,6,14,3,2)(7,10,13,11,9,8,12)],
Permutation Group with generators
[(1,8)(2,9)(3,11)(4,10)(5,13)(6,12)(7,14),
(1,14,5,3,4,2,6)(7,9,10,8,13,12,11)]]
3
[Permutation Group with generators [()], Permutation Group with generators [(3,5)(4,6)(8,9)(12,13), (3,6)(4,5)(8,9)(10,11), (2,6,3)(4,5,14)(7,11,10)(8,13,9), (1,5,4,6,14,3,2)(7,10,13,11,9,8,12)], Permutation Group with generators [(1,8)(2,9)(3,11)(4,10)(5,13)(6,12)(7,14), (1,14,5,3,4,2,6)(7,9,10,8,13,12,11)]]
3
N = A.normal_subgroups()[1] 
       
A.quotient(N) 
        
Permutation Group with generators [(), (1,2)]
Permutation Group with generators [(), (1,2)]
N.is_simple() N.order() 
        
True
168
True
168
PSL(2, 7) 
        
Permutation Group with generators [(3,7,5)(4,8,6), (1,2,6)(3,4,8)]
Permutation Group with generators [(3,7,5)(4,8,6), (1,2,6)(3,4,8)]
N.is_isomorphic(PSL(2, 7)) 
        
True
True

Note that projective linear groups are implemented as permutation groups, however:
type(SL(2, 7)) 
        
<class
'sage.groups.matrix_gps.special_linear.SpecialLinearGroup_finite_field'&\
gt;
<class 'sage.groups.matrix_gps.special_linear.SpecialLinearGroup_finite_field'>
N.cohomology(2, 0) 
        
Trivial Abelian Group
Trivial Abelian Group
N.cohomology(2, 2) 
        
Multiplicative Abelian Group isomorphic to C2
Multiplicative Abelian Group isomorphic to C2

We mentioned already that Sage glues together many specialised mathematical libraries.  For instance, most of the group theory functionality in Sage uses GAP behind the scenes.  Sometimes GAP packages are used, e.g. Graham Ellis' HAP for computing the cohomology groups given above.

There is a package for doing computations with the mod p cohomology rings of p-groups, due to Simon King and David Green.  It can compute Poincaré series, Massey products, and more.

Let's leave groups aside for now, and see what else Sage knows about.
R.<x,y,z> = QQ[]; R 
        
Multivariate Polynomial Ring in x, y, z over Rational Field
Multivariate Polynomial Ring in x, y, z over Rational Field
R. # tab-complete 
        
Syntax Error:
    R.                           # tab-complete
Syntax Error:
    R.                           # tab-complete
R.krull_dimension() 
        
3
3
I = R.ideal([x^2-y, x*z]) 
       
I. # tab-complete 
        
Syntax Error:
    I.                            # tab-complete
Syntax Error:
    I.                            # tab-complete

Of course, whenever we speak of computations with polynomial rings, we have:
I.groebner_basis() 
        
[x^2 - y, x*z, y*z]
[x^2 - y, x*z, y*z]

A method that brings us closer to geometry:
I.primary_decomposition() 
        
[Ideal (y, x) of Multivariate Polynomial Ring in x, y, z over Rational
Field, Ideal (z, x^2 - y) of Multivariate Polynomial Ring in x, y, z
over Rational Field]
[Ideal (y, x) of Multivariate Polynomial Ring in x, y, z over Rational Field, Ideal (z, x^2 - y) of Multivariate Polynomial Ring in x, y, z over Rational Field]
S = R.quotient(I) S 
        
Quotient of Multivariate Polynomial Ring in x, y, z over Rational Field
by the ideal (x^2 - y, x*z)
Quotient of Multivariate Polynomial Ring in x, y, z over Rational Field by the ideal (x^2 - y, x*z)
S.gens() 
        
(xbar, ybar, zbar)
(xbar, ybar, zbar)

Most of the multivariate polynomial functionality in Sage is based on Singular.

Sage has implementations for a lot of rings:

  • \ZZ (arbitrary size), uses MPIR
  • \QQ (arbitrary size), uses MPIR
  • \RR (arbitrary fixed precision), uses MPFR
  • \CC (arbitrary fixed precision), uses MPFR and native code
  • finite fields, use Givaro, NTL, PARI
  • number fields, rings of integers, use PARI and native code
  • quaternion algebras, native
  • p-adic integers, p-adic numbers, finite extensions of these, native

Most of these can be used as coefficients to construct univariate and multivariate polynomial rings, power series rings, rings of Laurent series and Laurent polynomials.  There is also a way to construct the fraction field of an integral domain (but more general localisations are not yet implemented).
M = FreeModule(ZZ, 2) M 
        
Ambient free module of rank 2 over the principal ideal domain Integer
Ring
Ambient free module of rank 2 over the principal ideal domain Integer Ring
B = M.basis() B 
        
[
(1, 0),
(0, 1)
]
[
(1, 0),
(0, 1)
]
N = M.submodule([B[0]-5*B[1]]) N.basis() 
        
[
(1, -5)
]
[
(1, -5)
]

Sage also knows about morphisms, not just objects:
H = M.Hom(N) H 
        
Set of Morphisms from Ambient free module of rank 2 over the principal
ideal domain Integer Ring to Free module of degree 2 and rank 1 over
Integer Ring
Echelon basis matrix:
[ 1 -5] in Category of free modules over Integer Ring
Set of Morphisms from Ambient free module of rank 2 over the principal ideal domain Integer Ring to Free module of degree 2 and rank 1 over Integer Ring
Echelon basis matrix:
[ 1 -5] in Category of free modules over Integer Ring
f = H([(1,-5),(0,0)]) f 
        
Free module morphism defined by the matrix
[1]
[0]
Domain: Ambient free module of rank 2 over the principal ideal domain
...
Codomain: Free module of degree 2 and rank 1 over Integer Ring
Echelon ...
Free module morphism defined by the matrix
[1]
[0]
Domain: Ambient free module of rank 2 over the principal ideal domain ...
Codomain: Free module of degree 2 and rank 1 over Integer Ring
Echelon ...
f((3, 2)) 
        
(3, -15)
(3, -15)

Say a few words about

  • linear algebra libraries used
  • representation theory (root systems, etc.)
  • homological algebra (chain complexes)

The End