Author: Ken Levasseur
Description: Worksheets related to Applied Discrete Structures



# Algebraic Structures using SageMath

Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial -  No Derivative Works 3.0 United States License.

import sage.monoids.monoid



M=Monoids().free(['a','b'])

x=M('ab')

x

Error in lines 1-1 Traceback (most recent call last): File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals File "", line 1, in <module> File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_salvus.py", line 3601, in displayhook _system_sys_displayhook(obj) File "sage/structure/sage_object.pyx", line 244, in sage.structure.sage_object.SageObject.__repr__ (build/cythonized/sage/structure/sage_object.c:2904) result = reprfunc() File "/ext/sage/sage-8.2_1604/local/lib/python2.7/site-packages/sage/monoids/indexed_free_monoid.py", line 117, in _repr_ return scalar_mult.join(P._repr_generator(g) + exp(v) for g,v in monomial) File "/ext/sage/sage-8.2_1604/local/lib/python2.7/site-packages/sage/monoids/indexed_free_monoid.py", line 117, in <genexpr> return scalar_mult.join(P._repr_generator(g) + exp(v) for g,v in monomial) ValueError: need more than 1 value to unpack

Monoids().axioms()

frozenset(['Associative', 'Unital'])

## Abelian Groups

%html
<p>
Most standard algebraic stuctures are built into SageMath.  Some do require importing a packages such <c>abelian_grps</c>.
</p>


Most standard algebraic stuctures are built into SageMath. Some do require importing a packages such Group.

from sage.groups.group import Group

import sage.groups.abelian_gps


G=AbelianGroup([2,4])
G

Multiplicative Abelian group isomorphic to C2 x C4
G

Multiplicative Abelian group isomorphic to C2 x C4
G.is_cyclic()

False
G.cayley_table(names='elements')

* 1 f1 f1^2 f1^3 f0 f0*f1 f0*f1^2 f0*f1^3 +---------------------------------------------------------------- 1| 1 f1 f1^2 f1^3 f0 f0*f1 f0*f1^2 f0*f1^3 f1| f1 f1^2 f1^3 1 f0*f1 f0*f1^2 f0*f1^3 f0 f1^2| f1^2 f1^3 1 f1 f0*f1^2 f0*f1^3 f0 f0*f1 f1^3| f1^3 1 f1 f1^2 f0*f1^3 f0 f0*f1 f0*f1^2 f0| f0 f0*f1 f0*f1^2 f0*f1^3 1 f1 f1^2 f1^3 f0*f1| f0*f1 f0*f1^2 f0*f1^3 f0 f1 f1^2 f1^3 1 f0*f1^2| f0*f1^2 f0*f1^3 f0 f0*f1 f1^2 f1^3 1 f1 f0*f1^3| f0*f1^3 f0 f0*f1 f0*f1^2 f1^3 1 f1 f1^2
sage.groups.abelian_gps.abelian_group?

File: /ext/sage/sage-8.2_1604/local/lib/python2.7/site-packages/sage/groups/abelian_gps/abelian_group.py
Docstring :
Multiplicative Abelian Groups

This module lets you compute with finitely generated Abelian groups of
the form

G = ZZ^r oplus ZZ_{k_1} oplus ... oplus ZZ_{k_t}

It is customary to denote the infinite cyclic group ZZ as having
order 0, so the data defining the Abelian group can be written as an
integer vector

vec{k} = (0, ..., 0, k_1, ..., k_t)

where there are r zeroes and t non-zero values. To construct this
Abelian group in Sage, you can either specify all entries of vec{k}
or only the non-zero entries together with the total number of
generators:

sage: AbelianGroup([0,0,0,2,3])
Multiplicative Abelian group isomorphic to Z x Z x Z x C2 x C3
sage: AbelianGroup(5, [2,3])
Multiplicative Abelian group isomorphic to Z x Z x Z x C2 x C3

It is also legal to specify 1 as the order. The corresponding
generator will be the neutral element, but it will still take up an
index in the labelling of the generators:

sage: G = AbelianGroup([2,1,3], names='g')
sage: G.gens()
(g0, 1, g2)

Note that this presentation is not unique, for example ZZ_6 = ZZ_2
x ZZ_3. The orders of the generators
vec{k}=(0,...,0,k_1,..., k_t) has previously been called
invariants in Sage, even though they are not necessarily the (unique)
invariant factors of the group. You should now use "gens_orders()"
instead:

sage: J = AbelianGroup([2,0,3,2,4]);  J
Multiplicative Abelian group isomorphic to C2 x Z x C3 x C2 x C4
sage: J.gens_orders()            # use this instead
(2, 0, 3, 2, 4)
sage: J.invariants()             # deprecated
(2, 0, 3, 2, 4)
sage: J.elementary_divisors()    # these are the "invariant factors"
(2, 2, 12, 0)
sage: for i in range(J.ngens()):
....:     print((i, J.gen(i), J.gen(i).order()))     # or use this form
(0, f0, 2)
(1, f1, +Infinity)
(2, f2, 3)
(3, f3, 2)
(4, f4, 4)

Background on invariant factors and the Smith normal form (according
to section 4.1 of [C1]): An abelian group is a group A for which there
exists an exact sequence ZZ^k rightarrow ZZ^ell rightarrow A
rightarrow 1, for some positive integers k,ell with k<= ell. For
example, a finite abelian group has a decomposition

A = langle a_1rangle x ... x  langle a_ellrangle ,

where ord(a_i)=p_i^{c_i}, for some primes p_i and some positive
integers c_i, i=1,...,ell. GAP calls the list (ordered by size) of
the p_i^{c_i} the *abelian invariants*. In Sage they will be called
*invariants*. In this situation, k=ell and phi:  ZZ^ell
rightarrow A is the map phi(x_1,...,x_ell) =
a_1^{x_1}...a_ell^{x_ell}, for (x_1,...,x_ell)in ZZ^ell. The
matrix of relations M:ZZ^k rightarrow ZZ^ell is the matrix whose
rows generate the kernel of phi as a ZZ-module. In other words,
M=(M_{ij}) is a ell x ell diagonal matrix with M_{ii}=p_i^{c_i}.
Consider now the subgroup Bsubset A generated by b_1 =
a_1^{f_{1,1}}...a_ell^{f_{ell,1}}, ..., b_m =
a_1^{f_{1,m}}...a_ell^{f_{ell,m}}. The kernel of the map phi_B:
ZZ^m rightarrow B defined by phi_B(y_1,...,y_m) =
b_1^{y_1}...b_m^{y_m}, for (y_1,...,y_m)in ZZ^m, is the kernel of
the matrix

F= ( begin{array}{cccc} f_{11} & f_{12} & ... & f_{1m}
f_{21} & f_{22} & ... & f_{2m} vdots &        & ddots &
vdots  f_{ell,1} & f_{ell,2} & ... & f_{ell,m} end{array}
),

regarded as a map ZZ^mrightarrow (ZZ/p_1^{c_1}ZZ) x ... x
(ZZ/p_ell^{c_ell}ZZ). In particular, Bcong ZZ^m/ker(F). If B=A
then the Smith normal form (SNF) of a generator matrix of ker(F) and
the SNF of M are the same. The diagonal entries s_i of the SNF S =
diag[s_1,s_2,s_3, ... s_r,0,0,...0], are called *determinantal
divisors* of F. where r is the rank. The {it invariant factors} of  A
are:

s_1, s_2/s_1, s_3/s_2, ... s_r/s_{r-1}.

Sage supports multiplicative abelian groups on any prescribed finite
number n >= 0 of generators.  Use the "AbelianGroup()" function to
create an abelian group, and the "gen()" and "gens()" methods to
obtain the corresponding generators.  You can print the generators as
arbitrary strings using the optional "names" argument to the
"AbelianGroup()" function.

EXAMPLE 1:

We create an abelian group in zero or more variables; the syntax T(1)
creates the identity element even in the rank zero case:

sage: T = AbelianGroup(0,[])
sage: T
Trivial Abelian group
sage: T.gens()
()
sage: T(1)
1

EXAMPLE 2:

An Abelian group uses a multiplicative representation of elements, but
the underlying representation is lists of integer exponents:

sage: F = AbelianGroup(5,[3,4,5,5,7],names = list("abcde"))
sage: F
Multiplicative Abelian group isomorphic to C3 x C4 x C5 x C5 x C7
sage: (a,b,c,d,e) = F.gens()
sage: a*b^2*e*d
a*b^2*d*e
sage: x = b^2*e*d*a^7
sage: x
a*b^2*d*e
sage: x.list()
[1, 2, 0, 1, 1]

REFERENCES:

* [C1] H. Cohen Advanced topics in computational number theory,
Springer, 2000.

* [C2] ----, A course in computational algebraic number theory,
Springer, 1996.

* [R] J. Rotman, An introduction to the theory of groups, 4th ed,
Springer, 1995.

Warning: Many basic properties for infinite abelian groups are not
implemented.

AUTHORS:

* William Stein, David Joyner (2008-12): added (user requested)
is_cyclic, fixed elementary_divisors.

* David Joyner (2006-03): (based on free abelian monoids by David
Kohel)

* David Joyner (2006-05) several significant bug fixes

* David Joyner (2006-08) trivial changes to docs, added random,
fixed bug in how invariants are recorded

* David Joyner (2006-10) added dual_group method

* David Joyner (2008-02) fixed serious bug in word_problem

* David Joyner (2008-03) fixed bug in trivial group case

* David Loeffler (2009-05) added subgroups method

* Volker Braun (2012-11) port to new Parent base. Use tuples for
immutables. Rename invariants to gens_orders.


%html
<h2>
Modular Arithmetic
</h2>


## Modular Arithmetic

Integers(5)

Ring of integers modulo 5
a=2017
b=561
[q,r]=[a//b,a%b]
[q,r]

[3, 334]
a=2017
b=561
print gcd(a,b)
print xgcd(a,b)

1 (1, -173, 622)


G=AbelianGroup(1,)
G.list()


(1, f, f^2, f^3, f^4, f^5, f^6, f^7, f^8, f^9, f^10, f^11, f^12, f^13)

for g in G:
print str(g)+" has order "+str(g.order())

1 has order 1 f has order 14 f^2 has order 7 f^3 has order 14 f^4 has order 7 f^5 has order 14 f^6 has order 7 f^7 has order 2 f^8 has order 7 f^9 has order 14 f^10 has order 7 f^11 has order 14 f^12 has order 7 f^13 has order 14
G= AdditiveAbelianGroup([2,2,2])
G.list()

[(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 0), (0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 1, 1)]


G.is_cyclic()

False
 G= AdditiveAbelianGroup(); G

Additive abelian group isomorphic to Z/23
G2=AdditiveAbelianGroup([2,4]);G2

Additive abelian group isomorphic to Z/2 + Z/4

G2.addition_table(names='elements')

+ (0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 1) (1, 2) (1, 3) +-------------------------------------------------------- (0, 0)| (0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 1) (1, 2) (1, 3) (0, 1)| (0, 1) (0, 2) (0, 3) (0, 0) (1, 1) (1, 2) (1, 3) (1, 0) (0, 2)| (0, 2) (0, 3) (0, 0) (0, 1) (1, 2) (1, 3) (1, 0) (1, 1) (0, 3)| (0, 3) (0, 0) (0, 1) (0, 2) (1, 3) (1, 0) (1, 1) (1, 2) (1, 0)| (1, 0) (1, 1) (1, 2) (1, 3) (0, 0) (0, 1) (0, 2) (0, 3) (1, 1)| (1, 1) (1, 2) (1, 3) (1, 0) (0, 1) (0, 2) (0, 3) (0, 0) (1, 2)| (1, 2) (1, 3) (1, 0) (1, 1) (0, 2) (0, 3) (0, 0) (0, 1) (1, 3)| (1, 3) (1, 0) (1, 1) (1, 2) (0, 3) (0, 0) (0, 1) (0, 2)


G2.is_cyclic()


False
a=[1878,1384,84,2021,784,1509,1740,1201,2363,1774,1865,33,1477,894,690,520,198,1349,1278,650]
s =0
for t in a:
s+=t
s

23692


G=cartesian_product([Integers(32),Integers(27),Integers(25)])
def theta(x):
return G((x%32,x%27,x%25))

theta(1000)

(8, 1, 0)
[theta(1878)+theta(1384),theta(1878+1384)]

[(30, 22, 12), (30, 22, 12)]
sum=G((0,0,0))
for t in a:
sum+=theta(t)
sum

(12, 13, 17)
l=list(sum)

(7425*12 + 6400*13+ 7776* 17)%21600

2092
isum=crt([12,13,17],[32,27,25])
[isum,(s-isum)%(32*27*25)]


[2092, 0]
32*27*25

21600
s =0
for t in a:
s+=t
s

(s-isum)%21600

0
u=[crt([1,0,0],[32,27,25]),crt([0,1,0],[32,27,25]),crt([0,0,1],[32,27,25])]
u


[7425, 6400, 7776]
G=DihedralGroup(5)
gr=G.cayley_graph(simple="True")
gr.plot(vertex_size=2)  g=DiGraph({2:,1:[2,3]})
g.plot() triangle = SymmetricGroup(3)
triangle.list()

[(), (1,2), (1,2,3), (1,3,2), (2,3), (1,3)]
triangle.cayley_graph(generators=[(1,2),(1,2,3)]).show() triangle.cayley_graph(generators=[(1,2),(1,3)]).show() 