Mathematical Structures¶

The individual chapters in this part of the tutorial are relatively independent of one another. You should be familiar with the chapter sage_objects before reading material here. The section List Comprehensions (Loops in Lists) is also useful. Eventually, when you are ready for some real experimentation, you will want to read much of the chapter Programming Tools. Many sections in this part are incomplete, and we welcome contributions and additions!

Integers and Modular Arithmetic¶

Integers Modulo $n$ ¶

You should be familiar with Universes and Coercion and Variables

In this section we cover how to construct $\mathbb{Z}_{n}$ , the ring of integers modulo $n$ , and do some basic computations.

To construct $\mathbb{Z}_{n}$ you use the Integers command.

sage: Integers(7)
Ring of integers modulo 7
sage: Integers(100)
Ring of integers modulo 100

We could do computations modulo an integer by repeatedly using the % operator in all of our expressions, but by constructing the ring explicitly we have access to a more natural method for doing arithmetic.

sage: R=Integers(13)
sage: a=R(6)
sage: b=R(5)
sage: a + b
11
sage: a*b
4

And by explicitly coercing our numbers into the ring $\mathbb{Z}_{n}$ we can compute some of the mathematical properties of the elements. Like their order, both multiplicative and additive, and whether or not the element is a unit.

sage: a.additive_order()
13
sage: a.multiplicative_order()
12
sage: a.is_unit()
True

The additive inverse of $a$ is computed using -a and, if $a$ is a unit, the multiplicative inverse is computed using a^(-1) or 1/a.

sage: (-a)
7
sage: (a^(-1))
11

These inverses can be checked easily.

sage: a + (-a)
0
sage: a*(a^(-1))
1

Recall that division in $\mathbb{Z}_{n}$ is really multiplication by an inverse.

sage: R=Integers(24)
sage: R(4)/R(5)
20
sage: R(4)*R(5)^-1
20
sage: R(4/5)
20

Not all elements have an inverse, of course. If we try an invalid division, SageMath will complain

sage: R(5/4)
...
ZeroDivisionError: Inverse does not exist.

We have to be a little bit careful when we are doing this since we are asking SageMath to coerce a rational number into the $\mathbb{Z}_{24}$ This may cause some unexpected consequences since some reduction is done on rational numbers before the coercion. For an example, consider the following:

sage: R(20).is_unit()
False
sage: R(16/20)
20

In $\mathbb{Z}_{24}$ , $20$ is not a unit, yet at first glance it would seem we divided by it. However, note the order of operations. First sage reduces $16/20$ to $4/5$ , and then coerces $4/5$ into $\mathbb{Z}_{24}$ . Since $5$ is a unit in $\mathbb{Z}_{24}$ , everything works out ok.

We can also compute some properties of the ring itself.

sage: R
Ring of integers modulo 24
sage: R.order()
24
sage: R.is_ring()
True
sage: R.is_integral_domain()
False
sage: R.is_field()
False

Since this ring is finite then we can have SageMath list all of its elements.

sage: R = Integers(13)
sage: R.list()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

R in this example is a field, since $13$ is a prime number. If our ring is not a field then the units in $\mathbb{Z}_{n}$ form a group under multiplication. SageMath can compute a list of generators of the group of units using its unit_gens() method.

sage: R = Integers(12)
sage: R.uni
R.unit_gens            R.unit_group_order
R.unit_group_exponent  R.unit_ideal
sage: R.unit_gens()
[7, 5]

We can also compute the order of this subgroup.

sage: R.unit_group_order()
4

Unfortunately, SageMath doesn’t seem to have a function which directly returns the units in $\mathbb{Z}_{n}$ as a group. We can list the elements in a couple of different ways using the information above.

sage: (a,b) = R.unit_gens()
sage: a
7
sage: b
5
sage: [ (a^i)*(b^j) for i in range(2) for j in range(2) ]
[1, 5, 7, 11]

We can also compute the list of units by using a list comprehension.

sage: [ x for x in R if x.is_unit()]
[1, 5, 7, 11]

Exercises:

Construct the ring of integers modulo $16$ and answer the following:

Compute the multiplicative orders of $2,4,5,6,13$ and $15$ ?

Which of the elements listed above is a unit?

What are the generators for the group of units?

Compute a list of all of the elements in the group of units.

Do all of the steps above again, but with the ring of integers modulo $17$ .

Use an exhaustive search method to write a function which determines if a is a unit modulo n.

For $n = 13, 15$ and $21$ determine which of $3,4$ and $5$ are units in $\mathbb{Z}_{n}$ . When you find a unit, determine its inverse and compare this to the output of $xgcd(a,n)$ . Try to explain this relationship.

Use SageMath to determine whether the following Rings are fields. For each example, describe the unit group using generators and relations.

$\mathbb{Z}_{1091}$

$\mathbb{Z}_{1047}$

$\mathbb{Z}_{1037}$

$\mathbb{Z}_{1087}$

Solving Congruences¶

You should be familiar with Integers Modulo and List Comprehensions (Loops in Lists)

A linear congruence is an equation of the form $ax=b$ in $\mathbb{Z}_{n}$ . One way to see if there is a solution to such a problem is an exhaustive search. For example, to determine if there exists a solution to $9x = 6$ we can do the following:

sage: R=Integers(21)
sage: a=R(9)
sage: 6 in [ a*x for x in R ]
True

Notice that the above tells us only that there exists at least one solution to the equation $9x= 6$ in $\mathbb{Z}_{21}$ . We can construct the list of these solutions by using the following list comprehension.

sage: [ x for x in R if R(9)*x == R(6)]
[3, 10, 17]

We can determine when a solution does not exist in a similar fashion.

sage: [ x for x in R if R(9)*x == R(2) ]
[]

We can also use the solve_mod() function to compute the same results.

sage: solve_mod( 9*x == 6, 21)
[(3,), (10,), (17,)]
sage: solve_mod( 9*x == 2, 21)
[]

solve_mod() can handle linear congruences of more than one variable.

sage: solve_mod( 9*x + 7*y == 2, 21)
[(15, 14), (15, 8), (15, 2), (15, 17), (15, 11), (15, 5), (15, 20), (1, 14), (1, 8), (1, 2), (1, 17), (1, 11), (1, 5), (1, 20), (8, 14), (8, 8), (8, 2), (8, 17), (8, 11), (8, 5), (8, 20)]

The solutions are in the form $\left(x,y\right)$ , where the variables are listed in the order in which they appear in the equations.

solve_mod() can solve systems of linear congruences.

sage: solve_mod( [9*x + 2*y == 2, 3*x + 2*y == 11   ], 21)
[(9, 13), (16, 13), (2, 13)]

As with the solve() command, computations can be slow when working with systems that have a lot of variables and/or equations. For these systems the linear algebra capabilities are recommended.

We can also compute the solutions for non-linear congruences using solve_mod().

sage: solve_mod(x^2 + y^2 == 1, 7)
[(0, 1), (0, 6), (1, 0), (2, 2), (2, 5), (5, 2), (5, 5), (6, 0)]
sage: solve_mod([x^2 + y^2 == 1, x^2 - y == 2], 7)
[(2, 2), (5, 2)]

Finally, SageMath can compute the simulatenous solution of linear congruences with different modulii under certain circumstances. This is done using the Chineses Remainder Theorem, and is implemented in the crt() command. For example, the following computes the smallest nonnegative integer, $x$ that is congruent to $3 \bmod 8$ , $4 \bmod 9$ , and $5 \bmod 25$ .

sage: crt([3,4,5],[8,9,25])
355

We can check the validity of this solution using the mod() command.

sage: mod(355,8)
3
sage: mod(355,9)
4
sage: mod(355,25)
5

The set of all integer solutions is those integers congruent to $355$ modulo $8*9*25=1800$ .

Exercises:

Find all solutions to the following congruences over $\mathbb{Z}_{42}$ .

$41x = 2$

$5x = 13$

$6x = 0$

$6x = 12$

$6x = 18$

$37x = 21$

Above you computed the solution sets for the congruences $6x =0$ , $6x = 12$ and $6x = 18$ . What are the similarities? What are the differences? Can you use these results to say something in general about the structure of the set ${\left\{ 6x \mid x \in \mathbb{Z}_{42} \right\} }$ ?

Use the solve_mod() command find all of the solutions to the following congruences modulo $36$ .

$3x = 21$

$7x = 13$

$23x = 32$

$8x = 14$

Mini-Topic: Euclidean Algorithm¶

You should be familiar with Integer Division and Factoring, Variables, External Files and Sessions, and While loops

Recall that for $a,b \in \mathbb{Z}$ with $b \neq 0$ , there always exists unique $q,r \in \mathbb{Z}$ such that $a=bq+r$ with $0 \leq r< b$ . With that in mind, we will use SageMath to calculate the gcd of two integers using the Euclidean Algorithm. The following code is an implementation of the Euclidean Algorithm in SageMath.

# Begin euclid.sage
r=a%b
print (a,b,r)
while r != 0:
        a=b; b=r
        r=a%b
        print (a,b,r)
# End euclid.sage

If you create a file euclid.sage containing the text above, then the output after loading the file is:

sage: a=15; b=4
sage: load euclid.sage
(15, 4, 3) (4, 3, 1) (3, 1, 0)
sage: a=15; b=5
sage: load euclid.sage
(15, 5, 0)

In the first case, we see that the gcd was $1$ , while in the second the gcd was $5$ .

Exercises:

Revise the loop in the euclid.sage so that only the gcd and the total number of divisions (i.e. the number of steps through the algorithm) are printed. Compare the speed of this version of the algorithm with the built-in SageMath function gcd() by using both functions on large integers.

Write your own Extended Euclidean Algorithm by revising the loop in euclid.sage.

Groups¶

There are three major types of groups implemented in sage, PermutationGroup(), MatrixGroup() and AbelianGroup(). We will work with permutation groups first and cover most of the methods that are applied to them. Many of these methods are applicable to arbitrary groups, so the other sections will be somewhat briefer and will focus on methods particular to those structures.

Symmetric Groups¶

The Symmetric Group $S_n$ is the group of all permutations on $n$ elements. First we will construct the symmetric group on $\{ 1, 2, 3, 4 ,5 \}$ which is done by using the SymmetricGroup command.

sage: S5 = SymmetricGroup(5)
S5 Symmetric group of order 5! as a permutation group

Once the group has been constructed we can check the number of elements, which is $5!$ , and list them all.

sage: S5.cardinality()
 120
sage: S5.list()
 [(), (4,5), (3,4), (3,4,5), (3,5,4), (3,5), (2,3), (2,3)(4,5), (2,3,4), (2,3,4,5), (2,3,5,4), (2,3,5), (2,4,3), (2,4,5,3), (2,4), (2,4,5), (2,4)(3,5), (2,4,3,5), (2,5,4,3), (2,5,3), (2,5,4), (2,5), (2,5,3,4), (2,5)(3,4), (1,2), (1,2)(4,5), (1,2)(3,4), (1,2)(3,4,5), (1,2)(3,5,4), (1,2)(3,5), (1,2,3), (1,2,3)(4,5), (1,2,3,4), (1,2,3,4,5), (1,2,3,5,4), (1,2,3,5), (1,2,4,3), (1,2,4,5,3), (1,2,4), (1,2,4,5), (1,2,4)(3,5), (1,2,4,3,5), (1,2,5,4,3), (1,2,5,3), (1,2,5,4), (1,2,5), (1,2,5,3,4), (1,2,5)(3,4), (1,3,2), (1,3,2)(4,5), (1,3,4,2), (1,3,4,5,2), (1,3,5,4,2), (1,3,5,2), (1,3), (1,3)(4,5), (1,3,4), (1,3,4,5), (1,3,5,4), (1,3,5), (1,3)(2,4), (1,3)(2,4,5), (1,3,2,4), (1,3,2,4,5), (1,3,5,2,4), (1,3,5)(2,4), (1,3)(2,5,4), (1,3)(2,5), (1,3,2,5,4), (1,3,2,5), (1,3,4)(2,5), (1,3,4,2,5), (1,4,3,2), (1,4,5,3,2), (1,4,2), (1,4,5,2), (1,4,2)(3,5), (1,4,3,5,2), (1,4,3), (1,4,5,3), (1,4), (1,4,5), (1,4)(3,5), (1,4,3,5), (1,4,2,3), (1,4,5,2,3), (1,4)(2,3), (1,4,5)(2,3), (1,4)(2,3,5), (1,4,2,3,5), (1,4,2,5,3), (1,4,3)(2,5), (1,4)(2,5,3), (1,4,3,2,5), (1,4)(2,5), (1,4,2,5), (1,5,4,3,2), (1,5,3,2), (1,5,4,2), (1,5,2), (1,5,3,4,2), (1,5,2)(3,4), (1,5,4,3), (1,5,3), (1,5,4), (1,5), (1,5,3,4), (1,5)(3,4), (1,5,4,2,3), (1,5,2,3), (1,5,4)(2,3), (1,5)(2,3), (1,5,2,3,4), (1,5)(2,3,4), (1,5,3)(2,4), (1,5,2,4,3), (1,5,3,2,4), (1,5)(2,4,3), (1,5,2,4), (1,5)(2,4)]

As you can see from the list, in SageMath a permutation is written in cycle notation. Note that the empty parenthesis () is used to represent the identity permutation. We create the identity permutation and a randomly chosen element as follows.

sage: id = S5.identity()
()
sage: S5.random_element()
(1,2)(3,4)
sage: r=  S5.random_element(), r
(1,3,4)(2,5)

As you can see, subsequent calls for a random element give a new element each time. We can also express the element $r$ as a function by listing the images of $1,2,3,4,5$ in order.

sage: r.list()
[3,5,4,1,2]

We can construct a specific element in $S_5$ by coercing a permutation, written in cycle notation, into $S5$ . We must enclose the product of cycles in quotations for SageMath to parse the input correctly.

sage:  r = S5('(1,3)(2,4)'); r
(1,3)(2,4)
sage:  s = S5('(1,4,3,2)'); s
(1,4,3,2)

We may also construct an element $t$ using the list of images that it has as a function.

sage:  t = S5([1,5,4,3,2]); t
(2,5)(3,4)

The product of cycles is taken from left-to-right and is, of course, not commutative.

sage: s*t
(1,4,2,3)
sage: t*s
(1,2,4,3)
sage: id*s

Let’s compute the order of an element by using the object’s order() method and check this directly.

sage: r.order()
2
sage: r*r
()
sage: s.order()
4
sage: s*s
(1,3)(2,4)
sage: s*s*s*s
()

The exponent of a group is the least common multiple of the orders of the elements.

sage: S5.exponent()
  60

The sign() method is used to compute the sign of a permutation, indicating whether it can be written as the product of an even or an odd number of permutations.

sage: S5('(2,3,4)').sign()
1
sage: S5('(4,5)').sign()
-1

Each symmetric group $S_n$ is a subgroup of $S_{n+1}$ .

sage: S4 = SymmetricGroup(4)
sage: S4.is_subgroup(S5)
True

You can construct the subgroup generated by a list of elements by using the subgroup() method.

sage: H = S5.subgroup([r,s])
sage: H
Subgroup of SymmetricGroup(5) generated by [(1,3)(2,4), (1,4,3,2)]
sage: H.list()
[(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)]

We can test to see if the subgroup that we have just created has certain properties by using the appropriate methods. typing H.is() <tab> will give a list of several properties to test.

sage: H.is_abelian()
True
sage: H.is_cyclic()
True

The elements originally used to generate a subgroup are obtained with the gens() method. SageMath can’t guarantee a minimal generating set, but gens_small() makes an attempt.

sage: H.gens()
[(1,3)(2,4), (1,4,3,2)]
sage: H.gens_small()
[(1,4,3,2)]

A useful tool for examining the structure of a group is the multiplication table, often called the Cayley Table. Invoke the group’s cayley_table() method (also called multiplication_table()). The default uses letters to represent the group elements (in the order they appear using list()).

sage: S3 = SymmetricGroup(3)
sage: S3.cayley_table()
*  a b c d e f
+-----------
a| a b c d e f
b| b a d c f e
c| c e a f b d
d| d f b e a c
e| e c f a d b
f| f d e b c a
sage: S3.list()
[(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]

We can also use the elements themselves, or give them names. Here we assign name based on the symmetries of a triangle: u_i() for reflections through the axis containing vertex i() and r^1, r^2() for the rotations.

sage: S3.cayley_table(names='elements')
*       |      ()   (2,3)   (1,2) (1,2,3) (1,3,2)   (1,3)
-------------------------------------------------
()      |      ()   (2,3)   (1,2) (1,2,3) (1,3,2)   (1,3)
(2,3)   |   (2,3)      () (1,2,3)   (1,2)   (1,3) (1,3,2)
(1,2)   |   (1,2) (1,3,2)      ()   (1,3)   (2,3) (1,2,3)
(1,2,3) | (1,2,3)   (1,3)   (2,3) (1,3,2)      ()   (1,2)
(1,3,2) | (1,3,2)   (1,2)   (1,3)      () (1,2,3)   (2,3)
(1,3)   |   (1,3) (1,2,3) (1,3,2)   (2,3)   (1,2)      ()


sage: S3.cayley_table(names=['id','u1','u3','r1','r2','u2'])
*  id u1 u3 r1 r2 u2
+------------------
id| id u1 u3 r1 r2 u2
u1| u1 id r1 u3 u2 r2
u3| u3 r2 id u2 u1 r1
r1| r1 u2 u1 r2 id u3
r2| r2 u3 u2 id r1 u1
u2| u2 r1 r2 u1 u3 id

General Permutation Groups¶

A permutation group is a subgroup of some symmetric group. We can construct a permutation group directly, without constructing the whole symmetric group, by giving a list of permutations to the PermutationGroup command.

sage: r = '(1,3)(2,4)(5)'
sage: s = '(1,3,2)'
sage: K = PermutationGroup([r,s])
sage: K
Permutation Group with generators [(1,3,2), (1,3)(2,4)]
sage: K.order()
12

Several important permutation groups can also be constructed directly. Here are the simplest.

sage: K= KleinFourGroup(); K
The Klein 4 group of order 4, as a permutation group
sage: K.list()
[(), (3,4), (1,2), (1,2)(3,4)]
sage: Q= QuaternionGroup(); Q.list()
[(), (1,2,3,4)(5,6,7,8), (1,3)(2,4)(5,7)(6,8),
(1,4,3,2)(5,8,7,6), (1,5,3,7)(2,8,4,6), (1,6,3,8)(2,5,4,7),
(1,7,3,5)(2,6,4,8), (1,8,3,6)(2,7,4,5)]
sage: [x.order() for x in Q]
[1, 4, 2, 4, 4, 4, 4, 4]

There are several families of permutation groups. The CyclicPermutationGroup in $S_n$ is generated by the cycle $(1,2,\dots,n)$ . The DihedralGroup is $S_n$ is the symmetries of a regular $n$ -gon with the vertices enumerated clockwise from 1 to $n$ . It is generated by the rotation $(1,2,\dots,n)$ and a reflection. Use the gens() to see which reflection is used. The collection of all even permutations—permutations with positive sign—is a subgroup of $S_5$ obtained by the command AlternatingGroup.

sage: C = CyclicPermutationGroup(4); C
Cyclic group of order 4 as a permutation group
sage: C.list()
[(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)]
sage: D = DihedralGroup(4); D
Dihedral group of order 8 as a permutation group
sage: D.list()
[(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3), (1,3)(2,4), (1,4,3,2),
(1,4)(2,3)]
sage: D.gens()
[(1,2,3,4), (1,4)(2,3)]
sage: A = AlternatingGroup(4); A
Alternating group of order 4!/2 as a permutation group
sage: A.cardinality()
12

Another builtin group is the DiCyclicGroup (see the Group Properties article). Let’s check that the $A_4$ is not isomorphic to the dicyclic group with the same number of elements.

sage: B = DiCyclicGroup(3); B
Diyclic group of order 12 as a permutation group
sage: B.list()
[(), (5,6,7), (5,7,6), (1,2)(3,4), (1,2)(3,4)(5,6,7), (1,2)(3,4)(5,7,6), (1,3,2,4)(6,7), (1,3,2,4)(5,6), (1,3,2,4)(5,7), (1,4,2,3)(6,7), (1,4,2,3)(5,6), (1,4,2,3)(5,7)]
sage: A.is_isomorphic(B)
False

With any permutation group we may compute its cardinality, list its elements, compute the order of elements, etc. By using python’s list comprehensions (see Lists) we can create a list of elements with certain properties. In this case we can construct the list of all elements or order 2.

sage: S5 = SymmetricGroup(5)
sage: T = [s for s in S5  if s.order() == 2 ];  T
 [(4,5), (3,4), (3,5), (2,3), (2,3)(4,5), (2,4), (2,4)(3,5), (2,5), (2,5)(3,4), (1,2), (1,2)(4,5), (1,2)(3,4), (1,2)(3,5), (1,3), (1,3)(4,5), (1,3)(2,4), (1,3)(2,5), (1,4), (1,4)(3,5), (1,4)(2,3), (1,4)(2,5), (1,5), (1,5)(3,4), (1,5)(2,3), (1,5)(2,4)]

Next we will construct a permutation group $H$ and list its members. This group $H$ has different elements from DihedralGroup(5), but is isomorphic to it.

sage: H= PermutationGroup(['(1,5),(3,4)', '(1,2,5,4,3)']); H
Subgroup of SymmetricGroup(5) generated by [(1,2,5,4,3), (1,5)(3,4)]
sage: H.list()
[(), (2,3)(4,5), (1,2)(3,5), (1,2,5,4,3), (1,3,4,5,2), (1,3)(2,4), (1,4,2,3,5), (1,4)(2,5), (1,5)(3,4), (1,5,3,2,4)]
sage: H.order()
10
sage: D = DihedralGroup(5)
sage: D
Dihedral group of order 10 as a permutation group
sage: D.list()
[(), (2,5)(3,4), (1,2)(3,5), (1,2,3,4,5), (1,3)(4,5), (1,3,5,2,4), (1,4)(2,3), (1,4,2,5,3), (1,5,4,3,2), (1,5)(2,4)]
sage: H == D
False
sage: H.is_isomorphic(D)
True

As with the symmetric group, we can pass a list of group elements to the method subgroup() to create a subgroup of any permutation group.

The list of all subgroups of a permutation group is obtained by the subgroups() method. It returns a list whose 0th element is the trivial subgroup.

sage: D = DihedralGroup(4)
sage: L = D.subgroups(); L
[Permutation Group with generators [()], Permutation Group with generators [(1,3)(2,4)], Permutation Group with generators [(2,4)], Permutation Group with generators [(1,3)], Permutation Group with generators [(1,2)(3,4)], Permutation Group with generators [(1,4)(2,3)], Permutation Group with generators [(2,4), (1,3)(2,4)], Permutation Group with generators [(1,2,3,4), (1,3)(2,4)], Permutation Group with generators [(1,2)(3,4), (1,3)(2,4)], Permutation Group with generators [(2,4), (1,2,3,4), (1,3)(2,4)]]

The join of two subgroups $C$ and $K$ , is the group generated by the union of the two subgroups. We get the union of $C$ and $K$ by “adding” the respective lists. In the example below, we see that the cyclic permutation group generated by $(1,2,3,4,5)$ and the Klein four group generate the whole symmetric group $S_5$ . Notice that the Klein four group is a subgroup of $S_4$ , which itself is a subgroup of $S_5$ .

sage: K = KleinFourGroup(); K.list()
[(), (3,4), (1,2), (1,2)(3,4)]
sage: C = CyclicPermutationGroup(5)
sage: CjK = PermutationGroup(C.list()+K.list() )
Permutation Group with generators [(), (3,4), (1,2), (1,2)(3,4), (1,2,3,4,5), (1,3,5,2,4), (1,4,2,5,3), (1,5,4,3,2)]
sage: CjK.gens_small(); CjK.cardinality()
[(1,2)(3,5,4), (1,4,5,3)]
120
sage: CjK == SymmetricGroup(5)
True

The centralizer of an element $a$ (the subgroup of elements that commute with $a$ ) and the center of a group are constructed in the way you’d expect.

sage: D.center()
Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,3)(2,4)]
sage: D.centralizer(D('(1,3)(2,4)'))
Subgroup of (Dihedral group of order 8 as a permutation group) generated by [(1,2,3,4), (1,4)(2,3)]

Quotients of Permutation Groups¶

In this section we explore normal subgroups and the quotient of a group by a normal subgroup. First we consider cosets and conjugation.

The alternating group $A_4$ has a subgroup isomorphic to the Klein four group that is normal.

sage: A4 = AlternatingGroup(4)
sage: g1 = A4('(1,4)(3,2)') ; g2 = A4('(2,4)(1,3)')
sage: H = A4.subgroup([g1,g2]);
sage: H.is_normal(A4); H.is_isomorphic(KleinFourGroup())
True
True

Let’s compare the right and left cosets of $H$ in $A_4$ .

sage: Hr = A4.cosets(H, side = 'right')
sage: Hl = A4.cosets(H, side = 'left')
sage: Hr; Hl
[[(), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3)], [(2,3,4), (1,3,2), (1,4,3), (1,2,4)], [(2,4,3), (1,4,2), (1,2,3), (1,3,4)]]
[[(), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3)], [(2,3,4), (1,2,4), (1,3,2), (1,4,3)], [(2,4,3), (1,2,3), (1,3,4), (1,4,2)]]
sage: Hr == Hl
False

We can see they are equal, but sage is comparing each coset as lists, and notes that the elements of the last two cosets are not listed in the same order. To rectify this, use sorted() to remind sage to order each coset. We are fortunate with this example that the cosets themselves are listed in the same order. Otherwise we would have to apply sorted() to the two lists of cosets.

sage: Hr_sorted = [sorted(S) for S in Hr]
sage: Hl_sorted = [sorted(S) for S in Hl]
sage: Hr_sorted == Hl_sorted
True

The conjugate by $a$ of an element $g$ is the element $a^{-1}ga$ . The set of all conjugates of $g$ as $a$ varies is the conjugacy class of $g$ . Below, we create a 3-cycle and compute its conjugacy class in $S_4$ and then in $A_4$ . This shows that two elements may be conjugate in $S_4$ but not in $A_4$ .

sage: S4 = SymmetricGroup(4)
sage: A4 = AlternatingGroup(4)
sage: g = S4('(1,3,4)')
sage: Set([a^(-1)*g*a for a in A4])
{(1,3,4), (1,4,2), (1,2,3), (2,4,3)}
sage: Set([a^(-1)*g*a for a in S4])
{(1,2,3), (1,3,4), (2,3,4), (2,4,3), (1,4,3), (1,2,4), (1,3,2), (1,4,2)}

The method conjugacy_class_representatives() chooses one element from each conjugacy class. Notice that there are two classes for 3-cycles in $A_4$ , but only one in $S_4$ .

sage: S4.conjugacy_classes_representatives()
[(), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4)]
sage: A4.conjugacy_classes_representatives()
[(), (1,2)(3,4), (1,2,3), (1,2,4)]

The conjugate by $a$ of a subgroup $H$ is the group $a^{-1}Ha$ (recall that multiplication is left-to right). The group encompassing $a$ and $H$ need not be specified; sage just considers them inside the symmetric group containing all the integers that appear.

sage: H = CyclicPermutationGroup(4)
sage: K = H.conjugate(PermutationGroupElement('(3,5)'));  K
Permutation Group with generators [(1,2,5,4)]

The normalizer of $H$ in $S_4$ is the subgroup of elements of $a \in S_4$ such that $a^{-1}Ha = H$ .

sage: S4.normalizer(H)
Permutation Group with generators [(2,4), (1,2,3,4), (1,3)(2,4)]
sage: H1 = H.conjugate(PermutationGroupElement('(2,4)'));  H1
Permutation Group with generators [(1,4,3,2)]
sage: H1 ==H
True

SageMath can compute all normal subgroups of a group $G$ . Let’s verify that $S_4$ has 2 non-trivial normal subgroups, the alternating group, and a group isomorphic to the Klein four group (but not equal to sage’s standard Klein four group).

sage: S4 = SymmetricGroup(4)
sage: S4norms = S4.normal_subgroups(); S4norms
[Permutation Group with generators [()], Permutation Group with generators [(1,3)(2,4), (1,4)(2,3)], Permutation Group with generators [(2,4,3), (1,3)(2,4), (1,4)(2,3)], Permutation Group with generators [(1,2), (1,2,3,4)]]
sage: K = S4norms[1];  K==KleiFourGroup()
False
sage: K.is_isomorphic(KleinFourGroup())
True
sage: A = S4norms[2]; A == AlternatingGroup(4)
True

We may now compute the quotient of $G$ by the normal subgroups $K$ and $A$ in the previous example. As expected $G/A$ is isomorphic to $S_2$ . Since $G$ has 24 elements and $K$ has 4 elements, the quotient has 6 elements. We can check that it is isomorphic to $S_3$ .

sage: G.quotient(A)
Permutation Group with generators [(1,2)]
sage: H = G.quotient(K); H
Permutation Group with generators [(1,2)(3,6)(4,5), (1,3,5)(2,4,6)]
sage: H.is_isomorphic(SymmetricGroup(3))
True

SageMath can also compute the normalizer of a subgroup $H$ of $G$ , which is the largest subgroup of $G$ containing $H$ in which $H$ is normal. Here we compute the normalizer of the cyclic permutation group $H$ created above inside of $S_4$ . We get the dihedral group $D_4$ . If we had used a different 4-cycle the resulting group may have been isomorphic to $D_4$ but not equal to it.

sage: G.normalizer(H).cardinality()
8
sage: HK.normalizer(H)== DihedralGroup(4)
True

For some groups the list of all subgroups may be large. To better understand the subgroups of $G$ we may compute one group from each conjugacy class. The following computations show that there are 30 subgroups of $S_4$ but only 11 up to conjugacy. Every other subgroup is not only isomorphic to one of the 11, given by conjugacy_classes_subgroups(), but is also isomorphic via conjugation by some element of $G$ .

sage: G
Symmetric group of order 4! as a permutation group
sage: G.subgroups()
[Permutation Group with generators [()], Permutation Group with generators [(1,2)(3,4)], Permutation Group with generators [(1,3)(2,4)], Permutation Group with generators [(1,4)(2,3)], Permutation Group with generators [(3,4)], Permutation Group with generators [(2,3)], Permutation Group with generators [(2,4)], Permutation Group with generators [(1,2)], Permutation Group with generators [(1,3)], Permutation Group with generators [(1,4)], Permutation Group with generators [(2,4,3)], Permutation Group with generators [(1,2,3)], Permutation Group with generators [(1,4,2)], Permutation Group with generators [(1,3,4)], Permutation Group with generators [(1,4)(2,3), (1,3)(2,4)], Permutation Group with generators [(1,2)(3,4), (3,4)], Permutation Group with generators [(1,4)(2,3), (2,3)], Permutation Group with generators [(1,3)(2,4), (2,4)], Permutation Group with generators [(1,2)(3,4), (1,3,2,4)], Permutation Group with generators [(1,3)(2,4), (1,4,3,2)], Permutation Group with generators [(1,4)(2,3), (1,2,4,3)], Permutation Group with generators [(3,4), (2,4,3)], Permutation Group with generators [(3,4), (1,3,4)], Permutation Group with generators [(1,2), (1,2,3)], Permutation Group with generators [(1,2), (1,4,2)], Permutation Group with generators [(1,3)(2,4), (1,4)(2,3), (1,2)], Permutation Group with generators [(1,2)(3,4), (1,3)(2,4), (1,4)], Permutation Group with generators [(1,4)(2,3), (1,2)(3,4), (1,3)], Permutation Group with generators [(1,3)(2,4), (1,4)(2,3), (2,4,3)], Permutation Group with generators [(1,3)(2,4), (1,4)(2,3), (2,4,3), (1,2)]]
sage: len(G.subgroups())
30
sage: G.conjugacy_classes_subgroups()
[Permutation Group with generators [()], Permutation Group with generators [(1,3)(2,4)], Permutation Group with generators [(3,4)], Permutation Group with generators [(2,4,3)], Permutation Group with generators [(1,4)(2,3), (1,3)(2,4)], Permutation Group with generators [(1,2)(3,4), (3,4)], Permutation Group with generators [(1,2)(3,4), (1,3,2,4)], Permutation Group with generators [(3,4), (2,4,3)], Permutation Group with generators [(1,3)(2,4), (1,4)(2,3), (1,2)], Permutation Group with generators [(1,3)(2,4), (1,4)(2,3), (2,4,3)], Permutation Group with generators [(1,3)(2,4), (1,4)(2,3), (2,4,3), (1,2)]]
sage: len(G.conjugacy_classes_subgroups())
11

Exercises:

Find two subgroups of $A_4$ that are conjugate in $S_4$ but are not conjugate in $A_4$ .

Permutation Group Homomorphisms¶

To construct a homomorphism between two permutation groups we use the PermutationGroupMorphism() command. For an example let us use the two isomorphic groups that we constructed earlier.

sage: G = SymmetricGroup(5)
sage: r = G('(1,2,5,4,3)')
sage: s = G('(1,5),(3,4)')
sage: H = G.subgroup([r,s])
sage: H
Subgroup of SymmetricGroup(5) generated by [(1,2,5,4,3), (1,5)(3,4)]
sage: D = DihedralGroup(5)
sage: D
Dihedral group of order 10 as a permutation group

A homomorphism between these is constructed by listing an association between the generators of one group to the generators of the other. To see these we will use the gens() method provided by our groups

sage: H.gens()
[(1,2,5,4,3), (1,5)(3,4)]
sage: D.gens()
[(1,2,3,4,5), (1,5)(2,4)]

We construct the homomorphism $\phi: H \rightarrow D$ that sends $(1,2,5,4,3) \rightarrow (1,2,3,4,5)$ and $(1,5)(3,4) \rightarrow (1,5)(2,4)$ as follows:

sage: phi = PermutationGroupMorphism(H,D,H.gens(), D.gens())
sage: phi
Homomorphism : Permutation Group with generators [(1,2,5,4,3), (1,5)(3,4)] --> Dihedral group of order 10 as a permutation group

We can apply this homomorphism as we would any function, by calling it.

sage: phi( '(2,3)(4,5)')
(1,3)(4,5)
sage: phi( '(1,5,3,2,4)')
(1,3,5,2,4)
sage: phi('(1,5)')
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
...
AttributeError: 'str' object has no attribute '_gap_init_'

Note that we get an AttributeError because the permutation $(1,5)$ is not in the domain of phi().

The homomorphism also comes equipped with a few useful methods, the most useful is the kernel() method, which yields the kernel of the homomorphism. Since this homomorphism is an injection, the kernel is just the trivial group.

sage: phi.kernel()
Permutation Group with generators [()]

The direct product of two PermutationGroups produces another PermutationGroup, but in a larger symmetric group. The output is a list of length five consisting of the direct product followed by four homomorphisms. The first two homomorphism are the natural ones from each factor into the product. The second two homomorphisms are the natural projections from the product on to each factor.

sage: C4 = CyclicPermutationGroup(4)
sage: C3 = CyclicPermutationGroup(3)
sage: C4xC3 = C4.direct_product(C3);  C4xC3
(Permutation Group with generators [(5,6,7), (1,2,3,4)], Permutation group morphism:
From: Cyclic group of order 4 as a permutation group
To:   Permutation Group with generators [(5,6,7), (1,2,3,4)]
Defn: Embedding( Group( [ (1,2,3,4), (5,6,7) ] ), 1 ), Permutation group morphism:
From: Cyclic group of order 3 as a permutation group
To:   Permutation Group with generators [(5,6,7), (1,2,3,4)]
Defn: Embedding( Group( [ (1,2,3,4), (5,6,7) ] ), 2 ), Permutation group morphism:
From: Permutation Group with generators [(5,6,7), (1,2,3,4)]
To:   Cyclic group of order 4 as a permutation group
Defn: Projection( Group( [ (1,2,3,4), (5,6,7) ] ), 1 ), Permutation group morphism:
From: Permutation Group with generators [(5,6,7), (1,2,3,4)]
To:   Cyclic group of order 3 as a permutation group
Defn: Projection( Group( [ (1,2,3,4), (5,6,7) ] ), 2 ))

If we just want the direct product group, we must select the 0th element of the direct product.

sage: C4xC3[0]
Permutation Group with generators [(1,2,3,4), (5,6,7)]

Exercises:

There is a homomorphism from the dicyclic group of index $n$ to the dihedral group of index $n$ . Construct it and find the kernel.

Matrix Groups¶

Please contribute!

Abelian Groups¶

Please contribute!

Linear Algebra¶

Vectors and Matrices¶

To create a vector, use the vector() command with a list of entries. Scalar multiples and the dot product are straightforward to compute. As with lists, vectors are indexed starting from $0$ .

sage: v= vector([1,2,3,4])
sage: v[0]
1
sage: v[4]
ERROR: An unexpected error occurred while tokenizing input

Arithmetic on vectors is what one would expect. SageMath will produce an error message if you add two vectors of different lengths.

sage: 7*v
(7, 14, 21, 28)
sage: v + vector([2,1,4,5])
(3, 3, 7, 9)
sage: v*v
sage: v + vector([2,1,4])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/Users/mosullivan/Work/SageMath/Tutorial/sdsu-sage-tutorial/<ipython console> in <module>()

/Applications/sage/local/lib/python2.6/site-packages/sage/structure/element.so in sage.structure.element.ModuleElement.__add__ (sage/structure/element.c:7627)()

/Applications/sage/local/lib/python2.6/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6995)()

TypeError: unsupported operand parent(s) for '+': 'Ambient free module of rank 4 over the principal ideal domain Integer Ring' and 'Ambient free module of rank 3 over the principal ideal domain Integer Ring'

We use the matrix() command to construct a matrix with a list of the rows of the matrix as the argument.

sage: matrix([[1,2],[3,4]])
[1 2]
[3 4]

We can also construct a matrix by specifying all of the coordinates in a single matrix while specifying the dimensions of the matrix. The following command creates a matrix with $4$ rows and $2$ columns.

sage: matrix(4,2, [1,2,3,4,5,6,7,8])
[1 2]
[3 4]
[5 6]
[7 8]

If the matrix that we want to construct is square we can omit the number of columns from the argument.

sage: matrix(2,[1,2,3,4])
[1 2]
[3 4]

By default, SageMath constructs the matrix over the smallest universe which contains the coordinates.

sage: parent(matrix(2,[1,2,3,4]))
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
sage: parent(matrix(2,[1,2/1,3,4]))
Full MatrixSpace of 2 by 2 dense matrices over Rational Field
sage: parent(matrix(2,[x,x^2,x-1,x^3])
Full MatrixSpace of 2 by 2 dense matrices over Symbolic Ring

We can specify the universe for the coordinates of a matrix or vector by giving it as an optional argument.

sage: matrix(QQ,2,[1.1,1.2,1.3,1.4])
[11/10   6/5]
[13/10   7/5]

There are shortcuts in SageMath to construct some of the more commonly used matrices. To construct the identity matrix we use the identity_matrix() function.

sage: identity_matrix(3)
[1 0 0]
[0 1 0]
[0 0 1]

To construct the zero matrix we may use zero_matrix() or the regular matrix function with no list input.

sage: zero_matrix(2,2)
[0 0]
[0 0]
sage: matrix(2)
[0 0]
[0 0]
sage: matrix(2,3)
[0 0 0]
[0 0 0]

Note that if we use zero_matrix() we must input two integers.

Exercises:

Use SageMath to construct the vector $v = \left(4, 10, 17, 28, 2 \right)$

Construct the following matrix over the rational numbers in SageMath.

$\left(\begin{array}{ccc} 5 & 3 & 2 \\ 4 & 7 & 10 \\ 2 & 11 & 1 \end{array}\right)$

Construct a 10x10 identity matrix.

Construct a 20x10 zero matrix.

Matrix Arithmetic¶

You should be familiar with Vectors and Matrices.

We may use +, -, * and ^ for matrix addition, subtraction, multiplication and exponents.

sage: A=matrix(2,[1,1,0,1])
sage: B=matrix(2,[1,0,1,1])
sage: A+B
[2 1]
[1 2]
sage: A*B
[2 1]
[1 1]
sage: B*A
[1 1]
[1 2]
sage: A-B
[ 0  1]
[-1  0]
sage: A^3
[1 3]
[0 1]

We can compute the inverse of a matrix by raising it to the $-1$ -th power.

sage: A^-1
[ 1 -1]
[ 0  1]

If the matrix is not invertible SageMath will complain about a ZeroDivisionError.

sage: A = matrix([[4,2],[8,4]])
sage: A^-1
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)
... (Long error message)
ZeroDivisionError: input matrix must be nonsingular

When multiplying vectors and matrices; vectors can be considered both as rows or as columns, so you can multiply a 3-vector by a 3×n matrix on the right, or by a n×3 matrix on the left.

sage: x = vector([12,3,3])
sage: x
(12, 3, 3)
sage: A
[1 2 3]
[4 5 6]
sage: A*x
(27, 81)
sage: B = transpose(A)
sage: B
[1 4]
[2 5]
[3 6]
sage: x*B
(27, 81)

We use the det() method to calculate the determinant of a square matrix.

sage: A = matrix([[-1/2,0,-1],[0,-2,2],[1,0,-1/2]]); A
[-1/2    0   -1]
[   0   -2    2]
[   1    0 -1/2]
sage: A.det()
-5/2

We use the trace() method to compute the *trace*of a square (or any) matrix.

sage: A = matrix([[-1/2,0,-1],[0,-2,2],[1,0,-1/2]]); A.trace()
-3

This was a trivial case that could have been easily done by hand, but there will be circumstances when knowing the trace() method will turn out to be useful.

To check if a matrix is invertible we use the is_invertible() method.

sage: A=matrix(2,[1,1,0,1])
sage: A.is_invertible()
True
sage: A.det()
1

The invertibility of a matrix depends on the ring or field it is defined over. For example:

sage: B=matrix(2,[1,2,3,4])
sage: B.is_invertible()
False

In this example, SageMath assumes that the matrix B is defined over the integers and not the rationals, where it does not have an inverse. But if we define B as a matrix over the rationals, we obtain different results.

sage: B = matrix(QQ, 2,[1,2,3,4])
sage: B
[1 2]
[3 4]
sage: B.is_invertible()
True

If we ask SageMath to compute the inverse of a matrix over the integers it will automatically coerce B into a matrix over the rationals if necessary.

sage: B = matrix(2,[1,2,3,4])
sage: parent(B)
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
sage: B^-1
[  -2    1]
[ 3/2 -1/2]
sage: parent(B^-1)
Full MatrixSpace of 2 by 2 dense matrices over Rational Field

Exercises:

Consider the matrices:

$A = \left(\begin{array}{cc} 1 & 3 \\ 7 & 8 \end{array} \right) \quad \textrm{and} \quad B = \left(\begin{array}{cc} 4 & 8 \\ 9 & 15 \end{array} \right) Compute the following: a) :math:`A + B` b) :math:`AB` c) :math:`B^{-1}` d) :math:`B^{-1} A B`$

Which of the following matrices is invertable over $\mathbb{Z}$ ? What about $\mathbb{Q}$ ?

$A = \left(\begin{array}{cc} 2 & 8 \\ 4 & 16 \end{array} \right) \qquad B = \left(\begin{array}{cc} 2 & 7 \\ 13 & 24 \end{array} \right) \qquad C = \left(\begin{array}{cc} 1 & 4 \\ 2 & 7 \end{array} \right) \qquad D = \left(\begin{array}{cc} 4 & 6 \\ 8 & -2 \end{array} \right)$

Matrix Manipulation¶

You should be familiar with Vectors and Matrices and Matrix Arithmetic.

In this section we will cover some of the commands that we can use to manipulate matrices. Let’s begin by defining a matrix over the rational numbers.

sage: M = matrix(QQ, [[1,2,3],[4,5,6],[7,8,9]]); M
[1 2 3]
[4 5 6]
[7 8 9]

To get a list of row and column vectors, we use the rows() and columns() methods.

sage: M.rows()
[(1, 2, 3), (4, 5, 6), (7, 8, 9)]
sage: M.columns()
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

The following examples show how to get a particular row or column vector. Remember that SageMath follows Python’s convention that all of the indexes begin with zero.

sage: M.row(0)
(1, 2, 3)
sage: M.row(2)
(7, 8, 9)
sage: M.column(1)
(2, 5, 8)
sage: M.column(2)
(3, 6, 9)

You can even get a list of the diagonal entries, by calling the diagonal() method.

sage: M.diagonal()
[1, 5, 9]

SageMath also allows us to construct new matrices from the row and/or column vectors.

sage: M.matrix_from_columns([0,2])
[1 3]
[4 6]
[7 9]
sage: M.matrix_from_rows([0,2])
[1 2 3]
[7 8 9]
sage: M.matrix_from_rows_and_columns([0,2],[0,2])
[1 3]
[7 9]

It should be noted that the matrix_from_rows_and_columns() returns the intersection of the rows and columns specified. In the above example we are selecting the matrix that consists of the four ‘corners’ of our $3\times3$ matrix.

Next we will discuss some of the elementary row operations. To multiply a row or column by a number we use the rescale_row() or rescale_column() methods. Note that these commands change the matrix itself.

sage: M.rescale_row(1,-1/4); M
[   1    2    3]
[  -1 -5/4 -3/2]
[   7    8    9]
sage: M.rescale_col(2,-1/3); M
[   1    2   -1]
[  -1 -5/4  1/2]
[   7    8   -3]
sage: M.rescale_row(1,-4); M
[ 1  2 -1]
[ 4  5 -2]
[ 7  8 -3]

We can add a multiple of a row or column to another row or column by using the add_multiple_of_row() method. The first command takes $-4$ times the row $0$ and adds it to row $1$ .

sage: M.add_multiple_of_row(1,0,-4); M
[ 1  2 -1]
[ 0 -3  2]
[ 7  8 -3]
sage: M.add_multiple_of_row(2,0,-7); M
[ 1  2 -1]
[ 0 -3  2]
[ 0 -6  4]

The same can be done with the column vectors, which are also zero indexed.

sage: M.add_multiple_of_column(1,0,-2);M
[ 1  0 -1]
[ 0 -3  2]
[ 0 -6  4]
sage: M.add_multiple_of_column(2,0,1);M
[ 1  0  0]
[ 0 -3  2]
[ 0 -6  4]

If we don’t like the ordering of our rows or columns we can swap them in place.

sage: M.swap_rows(1,0); M
[ 0 -3  2]
[ 1  0  0]
[ 0 -6  4]
sage: M.swap_columns(0,2); M
[ 2 -3  0]
[ 0  0  1]
[ 4 -6  0]

If we want to change a row or column of M then we use the set_column() or set_row() methods.

sage: M.set_column(0,[1,2,3]);M
[ 1 -3  0]
[ 2  0  1]
[ 3 -6  0]
sage: M.set_row(0,[1,2,5]);M
[ 1  2  5]
[ 2  0  1]
[ 3 -6  0]

And finally if we want to change a whole “block” of a matrix, we use the set_block() method with the coordinates of where we want the upper left corner of the block to begin.

sage: B = matrix(QQ,[ [1,0 ],[0,1]]); B
[1 0]
[0 1]
sage: M.set_block(1,1,B); M
[1 2 5]
[2 1 0]
[3 0 1]

Of course, if all we want is the echelon form of the matrix we can use either the echelon_form() or echelonize() methods. The difference between the two is the former returns a copy of the matrix in echelon form without changing the original matrix and the latter alters the matrix itself.

sage: M.echelon_form()
[1 0 0]
[0 1 0]
[0 0 1]

sage: M.echelonize(); M
[ 1  0  0]
[ 0  1  0]
[ 0  0  1]

Next we use the augmented matrix and the echelon form to solve a $3\times 4$ system of the form $Mx = b$ . First we define the matrix M and the vector b

sage: M = matrix(QQ,   [[2,4,6,2,4],[1,2,3,1,1],[2,4,8,0,0],[3,6,7,5,9]]); M
[2 4 6 2 4]
[1 2 3 1 1]
[2 4 8 0 0]
[3 6 7 5 9]
sage: b = vector(QQ, [56, 23, 34, 101])

Then we construct the augmented matrix $\left( M\ \vert b \right)$ , store it in the variable M_aug and compute its echelon form.

sage: M_aug = M.augment(b); M_aug
[  2   4   6   2   4  56]
[  1   2   3   1   1  23]
[  2   4   8   0   0  34]
[  3   6   7   5   9 101]
sage: M_aug.echelon_form()
[ 1  2  0  4  0 21]
[ 0  0  1 -1  0 -1]
[ 0  0  0  0  1  5]
[ 0  0  0  0  0  0]

This tells us that we have a one dimensional solution space that consists of vectors of the form ${v = c \left(-2,1,0,0,0 \right) + \left(21,0,1,0,5\right)}$ .

sage: M*vector([21,0,-1,0,5])
(56, 23, 34, 101)
sage  M*vector([-2,1,0,0,0])
(0, 0, 0, 0)

If all we need is a single solution to this system, we can use the solve_right() method.

sage: M.solve_right(b)
(21, 0, -1, 0, 5)

Exercises:

Consider the matrix.

$A = \left(\begin{array}{ccc} 4 & 17 & 23 \\ 1/32 & 2 & 17 \\ 16 & -23 & 27 \end{array} \right)$

Use only the elementary row operations discussed to put $A$ into echelon form.

Using the commands discussed in this section, transform the matrix on the left into the matrix on the right.

$\left(\begin{array}{rrrrr} -7 & -1 & 1 & 4 & 0 \\ -8 & -2 & 4 & 2 & 6 \\ 1 & 1 & -3 & 3 & 0 \\ 0 & 8 & 13 & -2 & 0 \\ 1 & 4 & 0 & -1 & 4 \end{array}\right) \quad \quad \left(\begin{array}{rrrrr} -7 & -8 & 1 & 0 & 1 \\ -1 & -2 & 1 & 8 & 4 \\ 1 & 4 & -3 & 13 & 0 \\ 4 & 2 & 3 & -2 & -1 \\ 0 & 6 & 0 & 0 & 4 \end{array}\right)$

$\left(\begin{array}{rrrr} -1 & -2 & 1 & -13 \\ -3 & -1 & 1 & 1 \\ 1 & 1 & -1 & 1 \\ -2 & -1 & -9 & 1 \end{array}\right) \quad \quad \left(\begin{array}{rrrr} 1 & 0 & 0 & 100 \\ 0 & 1 & 0 & 12 \\ 0 & 0 & 1 & 111 \\ 0 & 0 & 0 & 202 \end{array}\right)$

$\left(\begin{array}{rrr} 0 & -1 & 1 \\ -2 & 1 & -1 \\ 1 & 0 & 1 \end{array}\right) \quad \quad \left(\begin{array}{rrrr} 0 & -1 & 1 & -4 \\ -2 & 1 & -1 & -1 \\ 1 & 0 & 1 & 1 \end{array}\right)$

Vector and Matrix Spaces¶

It is sometimes useful to create the space of all matrices of particular dimension, for which we use the MatrixSpace() function. We must specify the field (or indeed any ring) where the entries live.

sage: MatrixSpace(QQ,2,3)
Full MatrixSpace of 2 by 3 dense matrices over Rational Field

If we input a ring $R$ and an integer $n$ we get the matrix ring of $n\times n$ matrices over $R$ . Coercion can be used to construct the zero matrix, the indentity matrix, or a matrix with specified entries as shown.

sage: Mat = MatrixSpace(ZZ,2); Mat
Full MatrixSpace of 2 by 2 dense matrices over Integer Ring
sage: Mat(1)
[1 0]
[0 1]
sage: Mat(0)
[0 0]
[0 0]
sage: Mat([1,2,3,4])
[1 2]
[3 4]

We may compute various spaces associated to a matrix.

sage: Mat = MatrixSpace(QQ, 3,4)
sage: A = Mat([[1,2,3,4], [1,3,4,4],[2,5,7,8]])
sage: A
[1 2 3 4]
[1 3 4 4]
[2 5 7 8]
sage: A.rank()
2
sage: A.right_kernel()
Vector space of degree 4 and dimension 2 over Rational Field
Basis matrix:
[   1    0    0 -1/4]
[   0    1   -1  1/4]
sage: A.left_kernel()
Vector space of degree 3 and dimension 1 over Rational Field
Basis matrix:
[ 1  1 -1]
sage: A.row_space()
Vector space of degree 4 and dimension 2 over Rational Field
Basis matrix:
[1 0 1 4]
[0 1 1 0]

Exercises:

For the following 5x3 matrix:

$\left(\begin{array}{rrr} 1 & -1 & -1 \\ 0 & 1 & -3 \\ 1 & 1 & 1 \\ 0 & -6 & -20 \\ 0 & 0 & 0 \end{array}\right)$

Use SageMath to compute the bases for the following spaces:
1. The right and left kernel.
2. The row space.
3. The column space.

Mini-Topic: The Jordan Canonical Form¶

For every linear transformation $\mathrm{T}:\mathbb{R}^n \longrightarrow \mathbb{R}^{n}$ there is a basis of $\mathbb{R}^n$ such that the matrix $\left[m\right]_{\mathcal{B}}$ is in an almost diagonal form. This unique matrix is called the Jordan Canonical Form of $\mathrm{T}$ . For more information on this please refer to this article on Wikipedia. To demonstrate some common tools that we use in SageMath we will compute this basis for the linear transformation

$\mathrm{T}\left(x,y,z,t \right) = \left(2x+y, 2y+1, 3z, y-z+3t \right).$

We will begin by defining $\mathrm{T}$ in SageMath.

sage: T(x,y,z,t) = (2*x+y, 2*y+1, 3*z, y - z + 3*t)

Now, let’s use the standard ordered basis of $\mathbb{R}^3$ to find the matrix form of $\mathrm{T}$ .

sage: T(1,0,0,0), T(0,1,0,0), T(0,0,1,0), T(0,0,0,1)
((2, 1, 0, 0), (1, 3, 0, 1), (0, 1, 3, -1), (0, 1, 0, 3))

Note that since SageMath uses rows to construct a matrix we must use the transpose() function to get the matrix we expect.

sage: M = transpose(matrix([[2,1,0,0],[0,2,1,0],  [0,0,3,0],[0,1,-1,3]]));  M
[ 2  1  0  0]
[ 0  2  1  0]
[ 0  0  3  0]
[ 0  1 -1  3]

Once we have the matrix we will compute its characteristic polynomial and then factor it in order to fine its eigenvalues.

sage: f = M.characteristic_polynomial(); f
x^4 - 10*x^3 + 37*x^2 - 60*x + 36
sage: f.factor()
(x - 3)^2 * (x - 2)^2

Alternatively, you can compute the eigenvalues directly.

sage: eval_M = M.eigenvalues(); eval_M;
[3, 3, 2, 2]

Above we have two eigenvalues $\lambda_1 = 3$ and $\lambda_2 = 2$ and both are of algebraic multiplicity $2$ . Now we need to look at the associated eigenvectors. To do so we will use the eigenvectors_right() method.

sage: evec_M = M.eigenvectors_right(); evec_M
[(3, [
(1, 1, 1, 0),
(0, 0, 0, 1)
], 2), (2, [
(1, 0, 0, 0)
], 2)]
sage: evec_M[1][1][0]
(1, 0, 0, 0)

What is returned is a list() of ordered triples. Each triple is consists of an eigenvalue followed by a list with a basis for the associated eigenspace followed by the dimension of the associated eigenspace. Note that the eigenvalue $2$ has algebraic multiplicity of $2$ but geometric multiplicity only $1$ . This means that we will have to compute a generalized eigenvector for this eigenvalue. We will do this by solving the system $\left(M - 2\mathrm{I}\right) v = x$ , where $x$ is the eigenvector $\left(1,0,0,0\right)$ . We will use the echelon_form() of the augmented matrix to solve the system.

sage: (M - 2*identity_matrix(4)).augment(evec_M[1][1][0])
[ 0  1  0  0  1]
[ 0  0  1  0  0]
[ 0  0  1  0  0]
[ 0  1 -1  1  0]
sage: _.echelon_form()
[ 0  1  0  0  1]
[ 0  0  1  0  0]
[ 0  0  0  1 -1]
[ 0  0  0  0  0]
sage: gv = vector([1,1,0,-1]); gv
(1, 1, 0, -1)

With the generalized eigenvector gv, we now have the right number of linearly independent vectors to form a basis for our Jordan Form matrix. We will next form the change of basis matrix that consists of these vectors as columns.

sage: S = transpose( matrix( [[1,1,1,0],[0,0,0,1],[1,0,0,0],gv])); S
[ 1  0  1  1]
[ 1  0  0  1]
[ 1  0  0  0]
[ 0  1  0 -1]

Now we will compute the matrix representation of $\mathrm{T}$ with respect to this basis.

sage: S.inverse()*M*S
[3 0 0 0]
[0 3 0 0]
[0 0 2 1]
[0 0 0 2]

And there it is, the Jordan Canonical Form of the linear transformation $\mathrm{T}$ . Of course we could have just used SageMath’s built in jordan_form() method to compute this directly.

sage: M.jordan_form()
[3|0|0 0]
[-+-+---]
[0|3|0 0]
[-+-+---]
[0|0|2 1]
[0|0|0 2]

But that wouldn’t be any fun!

Exercises:

Compute a jordan basis for the following matrix using the steps outlined in this section.

$\left(\begin{array}{rrrr} 1 & 2 & 0 & 2 \\ 0 & 2 & 0 & 0 \\ -1 & 2 & -\frac{1}{2} & -2 \\ 0 & 2 & 0 & 2 \end{array}\right)$

Rings¶

Polynomial Rings¶

Constructing polynomial rings in SageMath is fairly straightforward. We just specify the name of the “indeterminate” variable as well as the coefficient ring.

sage: R.<x>=PolynomialRing(ZZ)
sage: R
Univariate Polynomial Ring in x over Integer Ring

Once the polynomial ring has been defined we can construct a polynomial without any special coercions.

sage: p = 2*x^2 + (1/2)*x + (3/5)
sage: parent(p)
Univariate Polynomial Ring in x over Rational Field

Though $x$ is the most common choice for a variable, we could have chosen any letter for the indeterminate.

sage: R.<Y>=PolynomialRing(QQ)
sage: R
Univariate Polynomial Ring in Y over Rational Field

Polynomials with rational coefficients in Y are now valid objects in SageMath.

sage: q = Y^4 + (1/2)*Y^3 + (1/3)*Y + (1/4)
sage: q
Y^4 + 1/2*Y^3 + 1/3*Y + 1/4
sage: parent(q)
Univariate Polynomial Ring in Y over Rational Field

We can define polynomial rings over any ring or field.

sage: Z7=Integers(7)
sage: R.<x>=PolynomialRing(Z7); R
Univariate Polynomial Ring in x over Ring of integers modulo 7

When entering a polynomial into SageMath the coefficients are automatically coerced into the ring or field specified.

sage: p = 18*x^2 + 7*x + 16; p
4*x^2 + 2
sage: parent(p)
Univariate Polynomial Ring in x over Ring of integers modulo 7

Of course this coercion has to be well defined.

sage: q  = x^4 + (1/2)*x^3 + (1/3)*x^2 + (1/4)*x + (1/5)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)  ...
TypeError: unsupported operand parent(s) for '*': 'Rational Field' and 'Univariate Polynomial Ring in x over Ring of integers modulo 7'

When prudent, SageMath will extend the universe of definition to fit the polynomial entered. For example, if we ask for a rational coefficient in a polynomial ring over $\mathbb{Z}$ , SageMath will naturally coerce this polynomial into a ring over $\mathbb{Q}$

sage: S.<y>=PolynomialRing(ZZ)
sage: 1/2*y
1/2*y
sage: parent(1/2*y)
Univariate Polynomial Ring in y over Rational Field

It should be noted that the ring S hasn’t been changed at all. Nor is (1/2)*y` in the universe ``S. This can be easily verified.

sage: S
Univariate Polynomial Ring in y over Integer Ring
sage: (1/2)*y in S
False

Once constructed, the basic arithmetic with polynomials is straightforward.

sage: R.<x>=PolynomialRing(QQ)
sage: f=x+1
sage: g=x^2+x-1
sage: h=1/2*x+3/4
sage: f+g
x^2 + 2*x
sage: g-h
x^2 + 1/2*x - 7/4
sage: f*g
x^3 + 2*x^2 - 1
sage: h^3
1/8*x^3 + 9/16*x^2 + 27/32*x + 27/64

We can also divide elements of the polynomial ring, but this changes the parent.

sage: f/g
(x + 1)/(x^2 + x - 1)
sage: parent(f/g)
Fraction Field of Univariate Polynomial Ring in x over Rational Field

A fundamental attribute of a polynomial is its degree. We use the degree() method to calculate this.

sage: R.<x>=PolynomialRing(QQ)
sage: (x^3+3).degree()
3
sage: R(0).degree()
-1

Notice that by convention SageMath sets the degree of 0 to be -1.

The polynomial ring over a field has a division algorithm. As with the integers, we may use the // operator to determine the quotient and the % operator to determine the remainder of a division.

sage: R.<x>=PolynomialRing(Integers(7))
sage: f=x^6+x^2+1
sage: g=x^3+x+1
sage: f // g
x^3 + 6*x + 6
sage: f % g
2*x^2 + 2*x + 2

Additionally, if the coefficients of the polynomial are in $\mathbb{Z}$ or $\mathbb{Q}$ , we may use the divmod() command to compute both at the same time.

sage: S.<y>=PolynomialRing(QQ)
sage: a=(y+1)*(y^2+1)
sage: b=(y+1)*(y+5)
sage: a // b
y - 5
sage: a % b
26*y + 26
sage: divmod(a,b)
(y - 5, 26*y + 26)

For a field $F$ , the polynomial ring $F[x]$ has a division algorithm, so we have a unique greatest common divisor (gcd) of polynomials. This can be computed using the gcd() command.

sage: R.<x> = PolynomialRing(QQ)
sage: p = x^4 + 2*x^3 + 2*x^2 + 2*x + 1
sage: q = x^4 - 1
sage: gcd(p,q)
x^3 + x^2 + x + 1

The greatest common divisor of two integers can be represented as a linear combination of the two integers, and the extended Euclidean algorithm is used to determine one such linear combination. Similarly, the greatest common divisor of polynomials $a(x)$ and $b(x)$ may be written in the form $a(x)f(x) + b(x)g(x)$ for some polynomials $f(x)$ and $g(x)$ . We may use the xgcd() function to compute the multipliers $f(x)$ and $g(x)$ .

sage: R.<x>=PolynomialRing(ZZ)
sage: a=x^4-1
sage: b=(x+1)*x
sage: xgcd(a,b)
(x + 1, -1, x^2 - x + 1)
sage: d,u,v=xgcd(a,b)
sage: a*u+b*v
x + 1

To check whether a polynomial is irreducible, we use its is_irreducible() method.

sage: R.<x>=PolynomialRing(Integers(5))
sage: (x^3+x+1).is_irreducible()
True
sage: (x^3+1).is_irreducible()
False

This method is only suitable for polynomial rings that are defined over a field, as polynomials defined more generally may not posses a unique factorization.

To compute the factorization of a polynomial, where defined, we use the factor() command.

sage: R.<x>=PolynomialRing(Integers(5))
sage: factor(x^3+x+1)
x^3 + x + 1
sage: factor(x^3+1)
(x + 1) * (x^2 + 4*x + 1)

In the example above, we see a confirmation that $x^3+x+1$ is irreducible in $\mathbb{Z}_{5}[x]$ whereas $x^3+1$ may be factored, hence is reducible.

We can also consider polynomials in $R[x]$ as functions from $R$ to $R$ by evaluation, that is by substituting the indeterminate variable with a member of the coefficient ring. Evaluation of polynomials in SageMath works as expected, by calling the polynomial like a function.

sage: R.<x>=PolynomialRing(Integers(3))
sage: f=2*x+1
sage: f(0)
1
sage: f(1)
0
sage: f(2)
2

Calculating the roots, or zeros, of a polynomial can be done by using the roots() method.

sage: ((x-1)^2*(x-2)*x^3).roots()
[(2, 1), (1, 2), (0, 3)]

SageMath returns a list of pairs $(r,m)$ where r is the root and m is its multiplicity. Of course, a polynomial need not have any roots and in this case the empty list is returned.

sage: (x^2+1).roots()
[]

Multivariate Polynomial Rings¶

Defining a polynomial ring with more that one variable can be done easily by supplying an extra argument to PolynomialRing() which specifies the number of variables desired.

sage: R.<x,y,z> = PolynomialRing(QQ, 3)
sage: p = -1/2*x - y*z - y + 8*z^2; p
-y*z + 8*z^2 - 1/2*x - y

Unlike with univariate polynomials, there is not a single way that we can order the terms of a polynomial. So to specify things like the degree and the leading term of a polynomial we must first fix a rule for deciding when one term is larger than another. If no argument is specified, SageMath defaults to the graded reverse lexicographic ordering, sometimes referred to as grevlex, to make these decisions. To read more about Monomial Orderings, see this page on Wikipedia.

To access a list of the monomials with nonzero coefficients in $p$ , you use the monomials() method.

sage: p.monomials()
[y*z, z^2, x, y]

These monomials are listed in descending order using the term ordering specified when the ring was constructed.

To access a list of coefficients we use the coefficients() method.

sage: p.coefficients()
[-1, 8, -1/2, -1]

The list of coefficients is provided in the same order as the monomial listing computed earlier. This means that we can create a list of terms of our polynomial by zip()-ing up the two lists.

sage: [ a*b for a,b in zip(p.coefficients(),p.monomials())]
[-y*z, 8*z^2, -1/2*x, -y]

Often you want to compute information pertaining to the largest, or leading, term. We can compute the lead coefficient, leading monomial, and the lead term as follows:

sage: p.lc()
-1
sage:
sage: p.lm()
y*z
sage: p.lt()
-y*z

We can also compute the polynomial’s total degree using the total_degree() method.

sage: p.total_degree()
2

The exponents of each variable in each term, once again specified in descending order, is computed using the exponents() method.

sage: p.exponents()
[(0, 1, 1), (0, 0, 2), (1, 0, 0), (0, 1, 0)]

and the exponent of the lead term is computed by chaining together two of the methods just presented.

sage: p.lm().exponents()
[(0, 1, 1)]

To change the term ordering we must reconstruct both the ring itself and all of the polynomials with which we were working. The following code constructs a multivariate polynomial ring in $x,y,$ and $z$ using the lexicographic monomial ordering.

sage: R.<x,y,z> = PolynomialRing(QQ,3,order='lex')
sage: p = -1/2*x - y*z - y + 8*z^2; p
-1/2*x - y*z - y + 8*z^2

Once the term order changes, all of the methods discussed earlier, even how SageMath displays the polynomial, take this into account.

sage: p.lm()
x
sage: p.lc()
-1/2
sage: p.lt()
-1/2*x
sage: p.monomials()
[x, y*z, y, z^2]

Note that the order in which the indeterminates are listed affects the monomial ordering. In the example above we have the lexicographic ordering, with $x>y>z$ . We may redefine the ring to use the lexicographic order $z>y>x$ .

sage: R.<z,y,x> = PolynomialRing(QQ,3,order='lex')
sage:  p = -1/2*x - y*z - y + 8*z^2
sage: p
8*z^2 - z*y - y - 1/2*x
sage: p.lm()
z^2
sage: p.lc()
8
sage: p.lt()
8*z^2

Note again how all of the methods automatically take the new ordering into account.

Finally we can reduce a polynomial modulo a list of polynomials using the mod() method.

sage: r = -x^2 + 1/58*x*y - y + 1/2*z^2
sage: r.mod([p,q])
-238657765/29696*y^2 + 83193/14848*y*z^2 + 68345/14848*y - 1/1024*z^4 + 255/512*z^2 - 1/1024

Exercises:

Use SageMath to find out which of the following polynomials with rational coefficients are irreducible.

$3 y^{4} - \frac{1}{2} y^{2} - \frac{1}{2} y - \frac{1}{2}$

$2 y^{4} - y^{2} - y$

$\frac{1}{5} y^{5} - \frac{1}{3} y^{4} + y^{3} - \frac{17}{2} y^{2} - 21 y$

$y^{3} + \frac{1}{4} y^{2} - 6 y + \frac{1}{8}$

$3 y^{7} + y^{6} + \frac{9}{2} y^{4} - y^{3} + y^{2} - \frac{1}{2} y$

Factor all of the polynomials over $\mathbb{Z}[x]$ .

$-x^{10} + 4x^{9} - x^{8} + x^{7} - x^{6} + 2x^{3} + x^{2} - 1$

$x^{5} + 2x^{4} + x^{3} + 3x^{2} - 3$

$x^{4} + x^{3} - x^{2} - x$

$2x^{8} - 5x^{7} - 3x^{6} + 15x^{5} - 3x^{4} - 15x^{3} + 7x^{2} + 5x - 3$

$6x^{6} - x^{5} - 8x^{4} - x^{3} + 3x^{2} + x$

Compute all of the roots and of the following polynomials defined over $\mathbb{Z}_7$ . Compare this list to their factorizations.

$2 x^{7} + 3 x^{6} + 6 x^{5} + 4 x^{4} + x^{3} + 5 x^{2} + 2 x + 5$

$3 x^{3} + x^{2} + 2 x + 1$

$3 x^{8} + 5 x^{7} + 5 x^{5} + x^{3} + 2 x^{2} + 6 x$

$x^{5} + 2 x^{4} + x^{3} + 2 x^{2} + 2 x + 1$

$2 x^{10} + 2 x^{8} + 5 x^{6} + x^{5} + 3 x^{4} + 5 x^{3} + 2 x^{2} + 6 x + 5$

Ideals and Quotients¶

In this section we will construct and do common computations with ideals and quotient rings.

Ideals¶

Once a ring is constructed and a list of generating elements have been selected, the ideal generated by this list is constructed by using the * operator.

sage: R.<x> = PolynomialRing(QQ)
sage: I = [2*x^2 + 8*x - 10, 10*x - 10]*R; I
Principal ideal (x - 1) of Univariate Polynomial Ring in x over Rational Field
sage: J = [ x^2 + 1, x^3 + x ]*R; J
Principal ideal (x^2 + 1) of Univariate Polynomial Ring in x over Rational Field
sage: K = [ x^2 + 1, x - 2]*R; K
Principal ideal (1) of Univariate Polynomial Ring in x over Rational Field

SageMath automatically reduces the set of generators. This can be seen by using the gens() method which returns the list of the ideal’s generating elements.

sage: I.gens()
(x - 1,)
sage: J.gens()
(x^2 + 1,)
sage: K.gens()
(1,)

Ideal membership can be determined by using the in conditional.

sage: R(x-1) in I
True
sage: R(x) in I
False
sage: R(2) in J
False
sage: R(2) in K
True

You can determine some properties of the ideal by using the corresponding is_ methods. For example, to determine weather the ideals are prime, principal, or idempotent we enter the following:

sage: J.is_prime()
True
sage: K.is_prime()
False
sage: I.is_idempotent()
False
sage: K.is_principal()
True

Ideals in Multivarate Polynomial Rings¶

To construct an ideal within a multivariate polynomial ring, we must first construct the Polynomial ring with a term ordering and a collection of polynomials that will generate the ideal.

sage: R.<x,y,z> = PolynomialRing(QQ,3,order='lex')
sage: p = -1/2*x - y*z - y + 8*z^2
sage: q = -32*x + 2869*y - z^2 - 1

The ideal is constructed in the same manner as before.

sage: I = [p,q]*R
sage: I
Ideal (-1/2*x - y*z - y + 8*z^2, -32*x + 2869*y - z^2 - 1) of Multivariate Polynomial Ring in x, y, z over Rational Field

When the ring is a multivariate polynomial, we can compute a special list of generators for I, called a groebner_basis.

sage: I.groebner_basis()
[x - 2869/32*y + 1/32*z^2 + 1/32, y*z + 2933/64*y - 513/64*z^2 - 1/64]

There are different algorithms for computing a Groebner basis. We can change the algorithm by supplying an optional argument to the groebner_basis() command. The following commands compute a Groebner basis using the Buchberger algorithm while showing the intermediate results. Very useful for teaching!

sage: set_verbose(3)
sage: I.groebner_basis('toy:buchberger')
(-32*x + 2869*y - z^2 - 1, -1/2*x - y*z - y + 8*z^2) => -2*y*z - 2933/32*y + 513/32*z^2 + 1/32
G: set([-2*y*z - 2933/32*y + 513/32*z^2 + 1/32, -1/2*x - y*z - y + 8*z^2, -32*x + 2869*y - z^2 - 1])
(-1/2*x - y*z - y + 8*z^2, -32*x + 2869*y - z^2 - 1) => 0
G: set([-2*y*z - 2933/32*y + 513/32*z^2 + 1/32, -1/2*x - y*z - y + 8*z^2, -32*x + 2869*y - z^2 - 1])
(-1/2*x - y*z - y + 8*z^2, -2*y*z - 2933/32*y + 513/32*z^2 + 1/32) => 0
G: set([-2*y*z - 2933/32*y + 513/32*z^2 + 1/32, -1/2*x - y*z - y + 8*z^2, -32*x + 2869*y - z^2 - 1])
(-32*x + 2869*y - z^2 - 1, -2*y*z - 2933/32*y + 513/32*z^2 + 1/32) => 0
G: set([-2*y*z - 2933/32*y + 513/32*z^2 + 1/32, -1/2*x - y*z - y + 8*z^2, -32*x + 2869*y - z^2 - 1])
3 reductions to zero.
[x + 2*y*z + 2*y - 16*z^2, x - 2869/32*y + 1/32*z^2 + 1/32, y*z + 2933/64*y - 513/64*z^2 - 1/64]

We can compute the various elimination ideals by using the elimination_ideal() method.

sage: I.elimination_ideal([x])
Ideal (64*y*z + 2933*y - 513*z^2 - 1) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: I.elimination_ideal([x,y])
Ideal (0) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: I.elimination_ideal([x,z])
Ideal (0) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: I.elimination_ideal([x])
Ideal (64*y*z + 2933*y - 513*z^2 - 1) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: I.elimination_ideal([y])
Ideal (64*x*z + 2933*x + 2*z^3 - 45902*z^2 + 2*z + 2) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: I.elimination_ideal([z])
Ideal (263169*x^2 + 128*x*y^2 - 47095452*x*y + 16416*x - 11476*y^3 + 2106993608*y^2 - 1468864*y + 256) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: I.elimination_ideal([x,y])
Ideal (0) of Multivariate Polynomial Ring in x, y, z over Rational Field

Quotient Rings¶

To construct the quotient ring of a ring with an ideal we use the quotient() method.

sage: R = ZZ
sage: I = R*[5]
sage: I
Principal ideal (5) of Integer Ring
sage: Q = R.quotient(I)
sage: Q
Ring of integers modulo 5

To preform arithmetic in the quotient ring, we must first coerce elements into this universe. For more on why we do this see Universes and Coercion.

sage: Q(10)
0
sage: Q(12)
2
sage: Q(10) + Q(12)
2
sage: Q(10 + 12)
2

When working with quotients of polynomial rings it is a good idea to give the indeterminate a new name.

sage: R.<x> = PolynomialRing(ZZ)
sage: parent(x)
Univariate Polynomial Ring in x over Integer Ring
sage: I = R.ideal(x^2 + 1)
sage: Q.<a> = R.quotient(I)
sage: parent(a)
Univariate Quotient Polynomial Ring in a over Integer Ring with modulus x^2 + 1
sage: a^2
-1
sage: x^2
x^2

Then we can do arithmetic in this quotient ring without having to explicitly coerce all of our elements.

sage: 15*a^2 + 20*a + 1
20*a - 14
sage: (15 + a)*(14 - a)
-a + 211

Properties of Rings¶

You can check some of the properties of the rings which have been constructed. For example, to check whether a ring is an integral domain or a field we use the is_integral_domain() or is_field() methods.

sage: QQ.is_field()
True
sage: ZZ.is_integral_domain()
True
sage: ZZ.is_field()
False
sage: R=Integers(15)
sage: R.is_integral_domain()
False
sage: S=Integers(17)
sage: S.is_field()
True

These properties are often determined instantaneously since they are built into the definitions of the rings and not calculated on the fly.

For a complete listing of properties that are built into a ring, you can use SageMath’s built in tab-completion. For example, to see all of the properties which can be determined for the rational numbers we type QQ.is then the tab key. What we get is a list of all of the properties that we can compute.

sage: QQ.is[TAB]
QQ.is_absolute           QQ.is_finite             QQ.is_ring
QQ.is_atomic_repr        QQ.is_integral_domain    QQ.is_subring
QQ.is_commutative        QQ.is_integrally_closed  QQ.is_zero
QQ.is_exact              QQ.is_noetherian
QQ.is_field              QQ.is_prime_field

The characteristic of the ring can be computed using the ring’s characteristic() method.

sage: QQ.characteristic()
0
sage: R=Integers(43)
sage: R.characteristic()
43
sage: F.<a> = FiniteField(9)
sage: F.characteristic()
3
sage: ZZ.characteristic()
0

Mini-Topic: Multivariate Polynomial Division Algorithm¶

In this section we will use SageMath to construct a division algorithm for multivariate polynomials. Specifically, for a given polynomial $f$ (the dividend) and a sequence of polynomials $f_1, f_2, \ldots, f_k$ (the divisors) we want to compute a sequence of quotients $a_1, a_2,\ldots, a_k$ and a remainder polynomial $r$ so that

$f = \sum_{i=1}^{i=k} a_i \cdot f_i + r$

where no terms of $r$ are divisible by any of the leading terms of $f_i$ .

The first thing that we will do is to construct the base field for the polynomial ring and determine how many variables we want for the polynomial ring. In this case, lets define a two variable polynomial ring over the finite field $\mathbb{F}_{2}$ .

sage: K = GF(2)
sage: n = 2

Next we will construct the polynomial ring.

sage: P.<x,y> = PolynomialRing(F,2,order="lex")

Since we are working with more than one variable we must tell SageMath how to order the terms, in this case we selected a lexicographic ordering. The default term ordering is degree reverse lexicographic, where the total degree is used first to determine the order of the monomials, then a reverse lexicographic order is used to break ties. Other options for monomial orderings are deglex (degree lexicographic) or you can define a block ordering by using the TermOrder() command. You can read more on monomial orderings on-line on Wikipedia and on MathWorld, or the book [Cox2007] .

[Cox2007]

Cox, David and Little, John and O’Shea, Donald, Ideals, varieties, and algorithms. Springer 2007

Now we will begin our division algorithm. The first thing we will do is define a function which determines whether two monomial divide each other.

def does_divide(m1,m2):
    for c in (vector(ZZ, m1.degrees()) - vector(ZZ,m2.degrees())):
        if c < 0:
           return False
return True

Then we will define a sequence of polynomials which we will use to reduce our dividend.

sage: F  = [x^2 + x,  y^2 + y]

Next we will define the polynomial which will be reduced.

sage: f = x^3* y^2

Now we will define the list of quotients and the remainder and initialize them to $0$ .

sage: A =  [P(0) for  i in range(0,len(F)) ]
sage: r  = P(0)

Now because we alter f through the algorithm we will create a copy of it so that we can keep the value of $f$ for later to verify the algorithm.

sage: p = f

Now we are ready to define the main loop of our algorithm.

while p != P(0):
    i = 0
    div_occurred = False
    while (i < len(F) and div_occurred == False):
        print A,p,r
        if does_divide(p.lm(), F[i]):
            q = P(p.lm()/F[i].lm())
            A[i] = A[i] + q
            p = p - q*F[i]
            div_occurred = True
        else:
            i = i + 1
    if div_occurred == False:
        r = r + p.lm()
        p = p - p.lm()

print A, p, r

Fields¶

Number Fields¶

We create a number field by specifying an irreducible polynomial and a name for the root of that polynomial. We may use the indeterminate $x$ , which is already defined in sage. We can also create a polynomial ring over the rationals and use the indeterminate for that polynomial ring.

sage: P.<t> = PolynomialRing(QQ)
sage: K.<a> = NumberField(t^3-2)
sage: K
Number Field in a with defining polynomial t^3 - 2
sage: K.polynomial()
t^3 - 2

A “random element” may be constructed producing an element with degree at most 2 (one less than the degree of the defining polynomial). The options num_bound() or dem_bound() may be used to bound the numerator or denominator.

sage: K.random_element()
-5/14*a^2 + a - 3
sage: K.random_element()
-2*a
sage: K.random_element(num_bound= 2)
-a^2 + 1

Every irrational element will have a minimal polynomial of degree 3.

sage: a.minpoly()
 x^3 - 2
 sage: (a^2-3*a).minpoly()
 x^3 + 18*x + 50

We can test isomorphism of fields.

sage: K.<a>= NumberField(t^3-2)
sage: L.<b> = NumberField(t^3-6*t-6)
sage: K.is_isomorphic(L)
True

The number of real embeddings and the number of pairs of complex embeddings are given by the signature of the field. The embeddings into the real field, RR() , or complex field CC() may also be constructed.

sage: K.signature()
(1, 1)
sage: K.real_embeddings()
[
Ring morphism:
  From: Number Field in a with defining polynomial t^3 - 2
  To:   Real Field with 53 bits of precision
  Defn: a |--> 1.25992104989487
]
sage: K.complex_embeddings()
[
Ring morphism:
  From: Number Field in a with defining polynomial t^3 - 2
  To:   Complex Field with 53 bits of precision
  Defn: a |--> -0.629960524947437 - 1.09112363597172*I,
Ring morphism:
  From: Number Field in a with defining polynomial t^3 - 2
  To:   Complex Field with 53 bits of precision
  Defn: a |--> -0.629960524947437 + 1.09112363597172*I,
Ring morphism:
  From: Number Field in a with defining polynomial t^3 - 2
  To:   Complex Field with 53 bits of precision
  Defn: a |--> 1.25992104989487
]
sage: phi1, phi2, phi3 = K.complex_embeddings()
sage: phi1(a)
-0.629960524947437 - 1.09112363597172*I
sage: phi2(a)
-0.629960524947437 + 1.09112363597172*I
sage: phi3(a^2+3*a+5)
10.3671642016528

The Galois group() method computes the Galois group of the Galois closure, not of the field itself. When the Galois group is not cyclic, as in the second example, you need to name one of the generators. The generators may also be accessed as shown below.

sage: G = L.galois_group()
sage: G.gens()
[(1,2,3)]
sage: H.<g>= K.galois_group()
sage: H.gens()
[(1,2)(3,4)(5,6), (1,4,6)(2,5,3)]
sage: H.0
(1,2)(3,4)(5,6)
sage: H.1
(1,4,6)(2,5,3)

The Galois closure of K.

sage: L.<b> = K.galois_closure()
sage: L
Number Field in b with defining polynomial t^6 + 40*t^3 + 1372

Field Extensions¶

Now let’s construct field extensions, which may be done in a few different ways. The methods absolute_() refer to the prime field $\mathbb{Q}$ , while the methods relative_() refer to a field extension as constructed, which may be relative to some intermediate field.

sage: P.<t> = PolynomialRing(QQ)
sage: K.<a> = NumberField(t^3-2)
sage: L.<b> = NumberField(t^3-a)
sage: L.relative_degree(); L.relative_polynomial()
3
t^3 - a
sage: L.base_field()
Number Field in a with defining polynomial t^3 - 2
sage: L.absolute_degree(); L.absolute_polynomial()
9
x^9 - 2
sage: L.gens()
(b, a)

We may also create the compositum of several fields defined by a list of polynomials over the rationals. We must specify a root for each polynomial. SageMath creates a sequence of 3 fields in the following example, starting at the far right in the list.

sage: M.<a,b,c> = NumberField([t^3-2, t^2-3, t^3-5])
sage: M
Number Field in a with defining polynomial t^3 - 2 over its base field
sage: M.relative_degree()
3
sage: M.absolute_degree()
18
sage: d = M.absolute_generator(); d
a - b + c
sage: d.minpoly()
x^3 + (3*b - 3*c)*x^2 + (-6*c*b + 3*c^2 + 9)*x + (3*c^2 + 3)*b - 9*c - 7
sage: d.absolute_minpoly()
x^18 - 27*x^16 - 42*x^15 + 324*x^14 + 378*x^13 - 2073*x^12 + 1134*x^11 - 6588*x^10 - 23870*x^9 + 88695*x^8 + 79002*x^7 - 147369*x^6 - 1454922*x^5 + 431190*x^4 + 164892*x^3 + 2486700*x^2 - 1271592*x + 579268

The next example computes the Galois closure of K() and asks for the roots of unity. The generator for L() is something that sage computes, so it may have a complicated minimum polynomial, as we see. We know that L() contains cube roots of unity, so let’s verify it.

sage: K.<a> = NumberField(t^3-2)
sage: L.<b> = K.galois_closure()
sage: b.minpoly()
x^6 + 40*x^3 + 1372
sage: units= L.roots_of_unity(); units
[1/36*b^3 + 19/18, 1/36*b^3 + 1/18, -1, -1/36*b^3 - 19/18, -1/36*b^3 - 1/18, 1]
sage: len(units)
6
sage: [u^3 for u in units]
[-1, 1, -1, 1, -1, 1]

Special Number Fields¶

There are two classes of number fields with special properties that you can construct directly. For a quadratic field extension simply specify a square free integer.

sage: F.<a> = QuadraticField(17)
sage: a^2
17
sage: (7*a-3).minpoly()
x^2 + 6*x - 824

A cyclotomic field is created by indentifying its primitive root of unity.

CyclotomicField()

QuadraticField()

Finite Fields¶

In a prior section we constructed rings of integers modulo $n$ . We know that when $n$ is a prime number the ring $\mathbb{Z}_{n}$ is actually a field. SageMath will allow us to construct this same object as either a ring or a field.

sage: R = Integers(7)
sage: F7 = GF(7)
sage: R, F7
(Ring of integers modulo 7, Finite Field of size 7)

To take advantage of the extra stucture it is best to use the command GF() (or equivalently, FiniteField()) to construct this object. As with modular rings we have to coerece integers into the field in order to do arithemetic in the field.

sage: F7(4 + 3)
0
sage: F7(2*3)
6
sage: F7(3*7)
0
sage: F7(3/2)
5

We can use SageMath to construct any finite field. Recall that a finite field is always of order $n = p^k$ where $p$ is a prime number. To construct the field of order $25 = 5^2$ we input the following command.

sage: F25.<a> = GF(25)

Recall that the finite field of order $5^2$ can be thought of a an extension of $\mathbb{Z}_{5}$ using a root of a polynomial of degree $2$ . The a that you specified is a root of this polynomial. There are different polynomials that can be used to construct this extension and SageMath chooses one for you. You can see the polynomial chosen by using the, aptly named, polynomial() method.

sage: p = F25.polynomial();
sage: p
a^2 + 4*a + 2

We can verify that a satisfies this polynomial.

sage: a^2 + 4*a + 2
0

It should be noted that a already lives in the field and no special coercion is necessary to do arithmetic using a.

sage: parent(a)
Finite Field in a of size 5^2
sage: a^2
a + 3
sage: a*(a^2 + 1)
3

But if we are using only integers we must coerce the arithmetic into the field.

sage: 3+4
7
sage: parent(3+4)
Integer Ring
sage: F25(3 + 4)
2
sage: parent(F25(3+4))
Finite Field in a of size 5^2

Sometimes we would like to specify the polynomial used to construct out extension. to do so we just need to add the modulus option to our field constructor.

sage: F25.<a> = GF(25, modulus=x^2 + x + 1)
sage: a^2 + a + 1
0
sage: a^2
4*a + 4

Remember that the modulus must be a polynomial which is irreducible over $\mathbb{F}_{5}[x]$ . Many times we would like for the modulus to not just be irreducible, but to be primitive. Next we will construct all of the primitive polynomials of degree $2$ . The following example uses Polynomial Rings and List Comprehensions (Loops in Lists). First thing that we will do is construct a list of all monic polynomials over $\mathrm{GF}(5)$

sage: F5 = GF(5)
sage: P.<x> = PolynomialRing(F, 'x')
sage: AP = [ a0 + a1*x + a2*x^2 for (a0,a1) in F^3]
sage: AP
[x^2, x^2 + 1, x^2 + 2, x^2 + 3, x^2 + 4, x^2 + x, x^2 + x + 1, x^2 + x + 2, x^2 + x + 3, x^2 + x + 4, x^2 + 2*x, x^2 + 2*x + 1, x^2 + 2*x + 2, x^2 + 2*x + 3, x^2 + 2*x + 4, x^2 + 3*x, x^2 + 3*x + 1, x^2 + 3*x + 2, x^2 + 3*x + 3, x^2 + 3*x + 4, x^2 + 4*x, x^2 + 4*x + 1, x^2 + 4*x + 2, x^2 + 4*x + 3, x^2 + 4*x + 4]

Next we will filter out the primitive polynomials out of this list.

sage: PR = [ p for p in AP if p.is_primitive() ]
sage: PR
[x^2 + x + 2, x^2 + 2*x + 3, x^2 + 3*x + 3, x^2 + 4*x + 2]

If we wanted all of the irreducible polynomials we would only change the last command slightly.

sage: IR = [ p for p in AP if p.is_irreducible() ]
sage: IR
[x^2 + 2, x^2 + 3, x^2 + x + 1, x^2 + x + 2, x^2 + 2*x + 3, x^2 + 2*x + 4, x^2 + 3*x + 3, x^2 + 3*x + 4, x^2 + 4*x + 1, x^2 + 4*x + 2]

It should be noted that the above code will only work if the polynomials are over finite rings or fields.

Exercises:

Compute the list of all primitive polynomials of degree 3 over $GF(5)$ .
Compute the number of primitive elements in $GF(125)$ .
Explain the relationship between the number of primitive polynomials and the number of primitive elemens in the previous exercises.

Function Fields¶

Coding Theory¶

Linear Codes¶

A linear code is just a finite-dimensional vector space commonly defined over a finite field. To construct a linear code in SageMath we first define a finite field and a matrix over this field whose range will define this vector space.

sage: F = GF(2)
sage: G = matrix(F, [(0,1,0,1,0),(0,1,1,1,0),(0,0,1,0,1),(0,1,0,0,1)]); G
[0 1 0 1 0]
[0 1 1 1 0]
[0 0 1 0 1]
[0 1 0 0 1]

The code itself is constructed by the LinearCode() command.

sage: C = LinearCode(G); C
Linear code of length 5, dimension 4 over Finite Field of size 2

While the length and dimension of the code are displayed in the object’s description, you can also obtain these properties at anytime using the code’s length() and dimension() methods.

sage: C.length()
5
sage: C.dimension()
4

Given two code words, we can compute their Hamming Weight and Distance both by using the hamming_weight() function.

sage: w1 = vector(F, (0,1,0,1,0)); w1
(0, 1, 0, 1, 0)
sage: hamming_weight(w1)
2
sage: w2 = vector(F, (0,1,1,0,1)); w2
(0, 1, 1, 0, 1)
sage: hamming_weight(w2)
3
sage: hamming_weight(w1 - w2)
3

The minimum distance of C can be computed by using the minimum_distance() method.

sage: C.minimum_distance()
1

SageMath can also compute the distribution of weights for the code.

sage: C.weight_distribution()
[1, 4, 6, 4, 1, 0]

Where the value listed at index i of the list, starting with zero and ending with the length of the code, is the number of codewords with that weight.

Related to the weight distribution is the weight enumerator polynomial, which you compute using the code’s weight_enumerator() method.

sage: C.weight_enumerator()
x^5 + 4*x^4*y + 6*x^3*y^2 + 4*x^2*y^3 + x*y^4

The generating and check matrices are computed using the gen_mat() and check_mat() methods.

sage: C.gen_mat()
[0 1 0 1 0]
[0 1 1 1 0]
[0 0 1 0 1]
[0 1 0 0 1]
sage: C.check_mat()
[1 0 0 0 0]

The systematic form of the generating matrix is computed using gen_mat_systematic().

sage: C.gen_mat_systematic()
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]

SageMath can both extend and puncture our code. The extended code is computed as follows:

sage: Cx = C.extended_code(); Cx
Linear code of length 6, dimension 4 over Finite Field of size 2
sage: Cx.gen_mat()
[0 1 0 1 0 0]
[0 1 1 1 0 1]
[0 0 1 0 1 0]
[0 1 0 0 1 0]
sage: Cx.check_mat()
[1 0 0 0 0 0]
[0 1 1 1 1 1]

The punctured code is computed by supplying the code’s punctured() method a list of coordinates in which to delete. The following commands construct the code that results when the 1st and 3rd coordinate from every code word in C are deleted. Note that unlike vectors, lists and matrices the 1st column is indexed by 1 and not 0 when puncturing a code.

sage: Cp = C.punctured([1,3]); Cp
Linear code of length 3, dimension 2 over Finite Field of size 2
sage: Cp.gen_mat()
[0 1 0]
[0 0 1]
sage: Cp.check_mat()
[1 0 0]

SageMath can also compute the dual of C.

sage: Cd = C.dual_code(); Cd
Linear code of length 5, dimension 1 over Finite Field of size 2
sage: Cd.gen_mat()
[1 0 0 0 0]
sage: Cd.check_mat()
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]

And finally SageMath can decode a received vector. The following simulates a communications channel; We begin with a code word, introduce an error and then correct this error by decoding the received message.

sage: wrd = vector(F,(0,0,0,0,1))
sage: err = vector(F,(0,0,1,0,0))
sage: msg = wrd + err; msg
(0, 0, 1, 0, 1)
sage: C.decode(msg)
(0, 0, 0, 0, 1)
sage: C.decode(msg) == wrd
True

It should be noted that since the above code has a minimum distance of only 1 that decoding will not always produce the code word that you may have expected.

These are only some of the commands that SageMath offers for computing and working with linear codes. There is much more information on the following web sites:

See also

Cyclic Codes¶

To construct a cyclic code of length $3$ over $\mathbb{F}_2$ we first need a generating polynomial, which can be any irreducible factor of $x^{3} - 1$ . A list of irreducible factors is computed using the factor() command.

sage: P.<x> = PolynomialRing(GF(2),'x')
sage: factor(x^3 -1 )
(x + 1) * (x^2 + x + 1)

The output above tells you that there are 2 choices for non-trivial generating polynomials. The following commands will construct the code generated by $g(x) = x + 1$ .

sage: g = x + 1
sage: C = CyclicCode(3,g)
sage: C.list()
[(0, 0, 0), (1, 0, 1), (0, 1, 1), (1, 1, 0)]

Cyclic codes are a special type of linear code. So the commands that you worked with in the prior section all work in the same way. For example, the generating matrix is computed, in the usual and systematic forms, as follows:

sage: G = C.gen_mat(); G
[1 1 0]
[0 1 1]
sage: Gs = C.gen_mat_systematic(); Gs
[1 0 1]
[0 1 1]

Just to verify that this is the generating matrix, and to practice working with matrices and vectors, we will see if the image of $G$ spans the code.

sage: vector(GF(2),[0,0])*G
(0,0,0)
sage: vector(GF(2),[1,0])*G
(1, 1, 0)
sage: vector(GF(2),[1,1])*G
(1, 0, 1)
sage: vector(GF(2),[0,1])*G
(0, 1, 1)

SageMath can also compute a parity check matrix of $C$ using the code’s check_mat() method.

sage: H = C.check_mat()
[1 1 1]

Verifying that H is a check matrix for $C$ is straightforward.

sage: H*vector(GF(2),[0,1,1])
(0)
sage: H*vector(GF(2),[1,0,1])
(0)
sage: H*vector(GF(2),[1,0,0])
(1)

You can also compute the dual code and its generating and parity check matrices.

sage: Cp = C.dual_code()
sage: Cp.gen_mat()
[1 1 1]
sage: Cp.check_mat()
[1 0 1]
[0 1 1]

Mini-Topic: Factoring $x^n -1$ ¶

The smallest field containing $\mathbb{F}_{q}$ and containing the roots of $x^n - 1$ is $GF(q^t)$ where $t$ is the order of $q$ in $\mathbb{Z} \bmod{n}$ .

The factors of $x^n - 1$ over $\mathbb{F}_{q}$ must all have degree dividing $t$ .

Let us begin by first defining $n$ and $q$ and constructing the ambient rings.

sage: n = 19
sage: q = 2
sage: F = GF(2)
sage: P.<x> = PolynomialRing(F, 'x')

Remembering that since we are constructing a finite field that $q$ has to either be prime or a prime power. Now let us compute all of the irreducable factors of $x^{n} -1$ over $\mathbb{F}_{q}$ .

sage: A = factor(x^n-1); A

Now to verify the facts about the degrees of the factors computed that was stated ealier. Compare the list above with the order of $2$ in $\mathbb{Z}_{n}$ .

sage: Integers(19)(2).multiplicative_order()

Remembering that since $\mathbb{Z}_{n}$ is a ring, we have to specify which type of order we want to compute, either additive or multiplicative.

Now let us repeat what we just did, but this time letting $q=2^2$ . Changing q alone will not change the base field nor the polynomial ring. So we will have to re-construct everything using our new parameter.

sage: q = 4
sage: F.<a> = GF(4,'a')
sage: P.<x> = PolynomialRing(F,'x')

Now let us factor $x^n - 1$ again. This time over a non-prime field.

sage: A = factor(x^n-1); A
(x + 1) * (x^9 + a*x^8 + a*x^6 + a*x^5 + (a + 1)*x^4 + (a + 1)*x^3 + (a + 1)*x + 1) * (x^9 + (a + 1)*x^8 + (a + 1)*x^6 + (a + 1)*x^5 + a*x^4 + a*x^3 + a*x + 1)

Exercises:

Try repeating the above for $F= \mathbb{F}_{8}$ .

Compute the order of 2, 4, 8 mod 19. What are your observations?

Try other values of n and other fields.

Mini-Topic: Idempotent Polynomials¶

We’ll find the idempotent which is 1 modulo the ith factor of $x^n -1$ . Continuing with $\mathbb{F}_{4}$ .

sage: F.<a> = GF(4, 'a')
sage: P.<x> = PolynomialRing(F, 'x')

Then we will create the quotient ring.

sage: R.<y> = P.quotient(x^19 - 1)
sage: A = factor(x^19 - 1); A
(x + 1) * (x^9 + a*x^8 + a*x^6 + a*x^5 + (a + 1)*x^4 + (a + 1)*x^3 + (a + 1)*x + 1) * (x^9 + (a + 1)*x^8 + (a + 1)*x^6 + (a + 1)*x^5 + a*x^4 + a*x^3 + a*x + 1)

Since the factor() command returns a list of polynomial factors and their multiplicities, which we do not need, we will strip those out.

sage: A = [p[0] for p in A]

Now we will just select one of these factors. The reader should also try different factors for themselves.

sage: p0 = A[2]

Now we take the product of all of the other factors.

sage: ap = prod( [p for p in A if p != a])
x^10 + (a + 1)*x^9 + a*x^8 + a*x^7 + x^5 + (a + 1)*x^3 + (a + 1)*x^2 + a*x + 1

Then compute the xgcd() of p0 and ap.

sage: d, s, t = xgcd(p0, ap)

You should recall that $d = s \cdot p_0 + t* ap$ is the extended gcd. You should check that $s\cdot p_0 \equiv 1 \bmod{p}$ for all $p \neq p_0$ and $s\cdot p_0 \equiv 0 \bmod{p_0}$

sage: s*p0 % A[1]
1
sage: s*p0 % A[2]
0
sage: s*p0 % A[0]
1

Now check that $t\cdot ap \equiv 0 \bmod{p}$ for $p \neq p_0$ and $t \cdot ap \equiv 1 \bmod{p_0}$ .

sage: t*ap % A[0]
0
sage: t*ap % A[1]
0
sage: t*ap % A[2]
1

Now we will check that the polynomial that we computed is an idempotent in $F\left[x\right]/\left<x^n - 1 \right>$ .

sage: f = R(bp*ap)
sage: f^2 == f
True

Check the generating polynomial.

sage: gcd(b*p0, x^19-1)
x^9 + (a + 1)*x^8 + (a + 1)*x^6 + (a + 1)*x^5 + a*x^4 + a*x^3 + a*x + 1
sage: p0
x^9 + (a + 1)*x^8 + (a + 1)*x^6 + (a + 1)*x^5 + a*x^4 + a*x^3 + a*x + 1

Exercises:

Find the idempoent element of $F\left[x\right]/\left<x^n -1\right>$ For $q = 4$ and $n =3, 5, 11$ and $17$ .

For the reciprocal polynomials of idempotents, see Theorem 5 [MacWilliams1977] p. 219

[MacWilliams1977]

MacWilliams, F. J. and Sloane, N. J. A., The theory of error-correcting codes. North-Holland Publishing Co. 1977

Other Codes¶

Hamming Codes¶

A Hamming Code is a simple linear code which has the capability to detect up to 2 contiguous errors and correct for any single error.

We will begin by constructing a binary Hamming code with 3 parity checks.

sage: F = GF(2)
sage: C = HammingCode(3,F); C
Linear code of length 7, dimension 4 over Finite Field of size 2

Hamming codes always have a length, $\vert \mathbb{F} \vert^r - 1$ where $r$ is the number of parity checks and $\mathbb{F}$ is the finite-field over which the code is defined. This is because the columns of its parity check matrix consists of all non-zero elements of $\mathbb{F}^r$ .

sage: C.check_mat()
[1 0 1 0 1 0 1]
[0 1 1 0 0 1 1]
[0 0 0 1 1 1 1]

A Ternary Hamming Code is constructed by supplying a non-binary finite field as the base field. Here we will construct the ternary Hamming code over $GF(2^3)$ also with 3 parity checks.

sage: C = HammingCode(3, F); C
Linear code of length 73, dimension 70 over Finite Field in a of size 2^3

BCH Codes¶

BCH codes, or Bose-Chaudhuri-Hockenghem codes, are a special class of the cyclic codes with 3 required parameters, $n, \delta, F$ and one optional one $b$ . Here $n$ is the length of the code words, $\delta$ is a parameter called the designed distance and $F$ is a finite field of order $q^{n}$ where $gcd(n, q) = 1$ .

If $b$ is not provided then a default value of zero is used. For example, you construct construct a BCH code of length $n = 13$ with $\delta = 5$ over $F = \mathrm{GF}(9)$ .

sage: F.<a> = GF(3^2,'a')
sage: C = BCHCode(13, 5, F)
sage: C
Linear code of length 13, dimension 6 over Finite Field in a of size 3^2

We can compute the code’s minimum distance using its minimum_distance() method.

sage: C.minimum_distance()
6

Since BCH codes are also linear, you can use SageMath to compute the code’s generating and check matrices.

sage: C.gen_mat()
[2 2 1 2 0 0 1 1 0 0 0 0 0]
[0 2 2 1 2 0 0 1 1 0 0 0 0]
[0 0 2 2 1 2 0 0 1 1 0 0 0]
[0 0 0 2 2 1 2 0 0 1 1 0 0]
[0 0 0 0 2 2 1 2 0 0 1 1 0]
[0 0 0 0 0 2 2 1 2 0 0 1 1]
sage: C.check_mat()
[1 0 0 0 0 0 0 1 2 1 2 2 2]
[0 1 0 0 0 0 0 1 0 0 0 1 1]
[0 0 1 0 0 0 0 2 2 2 1 1 2]
[0 0 0 1 0 0 0 1 1 0 1 0 0]
[0 0 0 0 1 0 0 0 1 1 0 1 0]
[0 0 0 0 0 1 0 0 0 1 1 0 1]
[0 0 0 0 0 0 1 2 1 2 2 2 1]

We can also compute its dual code.

sage: Cp = C.dual_code(); Cp
Linear code of length 13, dimension 7 over Finite Field in a of size 3^2
sage: Cp.gen_mat()
[1 0 0 0 0 0 0 1 2 1 2 2 2]
[0 1 0 0 0 0 0 1 0 0 0 1 1]
[0 0 1 0 0 0 0 2 2 2 1 1 2]
[0 0 0 1 0 0 0 1 1 0 1 0 0]
[0 0 0 0 1 0 0 0 1 1 0 1 0]
[0 0 0 0 0 1 0 0 0 1 1 0 1]
[0 0 0 0 0 0 1 2 1 2 2 2 1]
sage: Cp.check_mat()
[1 0 0 0 0 0 2 2 1 2 0 0 1]
[0 1 0 0 0 0 1 0 1 2 2 0 2]
[0 0 1 0 0 0 2 0 1 0 2 2 1]
[0 0 0 1 0 0 1 0 2 2 0 2 1]
[0 0 0 0 1 0 1 2 2 0 2 0 1]
[0 0 0 0 0 1 1 2 1 0 0 2 2]

See also

http://en.wikipedia.org/wiki/BCH_code

Mathematical Structures¶

Integers and Modular Arithmetic¶

Integers Modulo ¶

Solving Congruences¶

Mini-Topic: Euclidean Algorithm¶

Groups¶

Symmetric Groups¶

General Permutation Groups¶

Quotients of Permutation Groups¶

Permutation Group Homomorphisms¶

Matrix Groups¶

Abelian Groups¶

Linear Algebra¶

Vectors and Matrices¶

Matrix Arithmetic¶

Matrix Manipulation¶

Vector and Matrix Spaces¶

Mini-Topic: The Jordan Canonical Form¶

Rings¶

Polynomial Rings¶

Multivariate Polynomial Rings¶

Ideals and Quotients¶

Ideals¶

Ideals in Multivarate Polynomial Rings¶

Quotient Rings¶

Properties of Rings¶

Mini-Topic: Multivariate Polynomial Division Algorithm¶

Fields¶

Number Fields¶

Field Extensions¶

Special Number Fields¶

Finite Fields¶

Function Fields¶

Coding Theory¶

Linear Codes¶

Cyclic Codes¶

Mini-Topic: Factoring ¶

Mini-Topic: Idempotent Polynomials¶

Other Codes¶

Hamming Codes¶

BCH Codes¶

Topics

This Page

Quick search

Integers Modulo $n$ ¶

Mini-Topic: Factoring $x^n -1$ ¶