Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download

Worksheets related to Applied Discrete Structures

Views: 15734
Image: ubuntu2004

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/python3.8/site-packages/smc_sagews/sage_server.py", line 1230, in execute exec( File "", line 1, in <module> File "/cocalc/lib/python3.8/site-packages/smc_sagews/sage_salvus.py", line 4013, in displayhook _system_sys_displayhook(obj) File "sage/structure/sage_object.pyx", line 194, in sage.structure.sage_object.SageObject.__repr__ (build/cythonized/sage/structure/sage_object.c:2460) result = reprfunc() File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/monoids/indexed_free_monoid.py", line 115, in _repr_ return scalar_mult.join(P._repr_generator(g) + exp(v) for g,v in monomial) File "/ext/sage/sage-9.2/local/lib/python3.8/site-packages/sage/monoids/indexed_free_monoid.py", line 115, in <genexpr> return scalar_mult.join(P._repr_generator(g) + exp(v) for g,v in monomial) ValueError: not enough values to unpack (expected 2, got 1)
Monoids().axioms()
frozenset({'Unital', 'Associative'})

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 .

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.order?
File: /ext/sage/9.5/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/groups/abelian_gps/abelian_group.py Signature : G.order(self) Docstring : Return the order of this group. EXAMPLES: sage: G = AbelianGroup(2,[2,3]) sage: G.order() 6 sage: G = AbelianGroup(3,[2,3,0]) sage: G.order() +Infinity
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?
%html <h2> Modular Arithmetic </h2>

Modular Arithmetic

def U_table(n): if n.parent()!=2.parent() or n<2 or n>64: return "input error/out of range" R=Integers(n) els=[] for k in filter(lambda k:gcd(n,k)==1,range(n)): els=els+[str(k)] return R.multiplication_table(elements=els,names="elements")
U_table(19)
* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 +------------------------------------------------------ 1| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2| 2 4 6 8 10 12 14 16 18 1 3 5 7 9 11 13 15 17 3| 3 6 9 12 15 18 2 5 8 11 14 17 1 4 7 10 13 16 4| 4 8 12 16 1 5 9 13 17 2 6 10 14 18 3 7 11 15 5| 5 10 15 1 6 11 16 2 7 12 17 3 8 13 18 4 9 14 6| 6 12 18 5 11 17 4 10 16 3 9 15 2 8 14 1 7 13 7| 7 14 2 9 16 4 11 18 6 13 1 8 15 3 10 17 5 12 8| 8 16 5 13 2 10 18 7 15 4 12 1 9 17 6 14 3 11 9| 9 18 8 17 7 16 6 15 5 14 4 13 3 12 2 11 1 10 10| 10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 11| 11 3 14 6 17 9 1 12 4 15 7 18 10 2 13 5 16 8 12| 12 5 17 10 3 15 8 1 13 6 18 11 4 16 9 2 14 7 13| 13 7 1 14 8 2 15 9 3 16 10 4 17 11 5 18 12 6 14| 14 9 4 18 13 8 3 17 12 7 2 16 11 6 1 15 10 5 15| 15 11 7 3 18 14 10 6 2 17 13 9 5 1 16 12 8 4 16| 16 13 10 7 4 1 17 14 11 8 5 2 18 15 12 9 6 3 17| 17 15 13 11 9 7 5 3 1 18 16 14 12 10 8 6 4 2 18| 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
els=[] for k in filter(lambda k:gcd(12,k)==1,range(12)): els=els+[str(k)] els
['1', '5', '7', '11']
Z5.multiplication_table?
Z5.multiplication_table(elements=els,names="elements")
* 1 5 7 11 +------------ 1| 1 5 7 11 5| 5 1 11 7 7| 7 11 1 5 11| 11 7 5 1
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,[14]) 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([23]); 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],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()
G=DihedralGroup(4)
G.cayley_table()
* a b c d e f g h +---------------- a| a b c d e f g h b| b a d c f e h g c| c g a e d h b f d| d h b f c g a e e| e f g h a b c d f| f e h g b a d c g| g c e a h d f b h| h d f b g c e a
G.list()
[(), (1,5,4,3,2), (1,4,2,5,3), (1,3,5,2,4), (1,2,3,4,5), (2,5)(3,4), (1,5)(2,4), (1,4)(2,3), (1,3)(4,5), (1,2)(3,5)]
22