CoCalc Public FilesPackages.sagewsOpen with one click!
Author: Kaitlyn Phillipson
Views : 36

Part II of Sage Workshop:  Introduction to packages

Sage has a variety of packages.  In this section, feel free to try out different packages that may be useful for your research, class, or just to practice with Sage more.

A.  Polynomials and Symbolic Computation in Sage

Polynomials versus expressions

Warm-up (Example 1)

Define the expression f=x45x3+8x24xf=x^4-5x^3+8x^2-4x.  We know that ff is a polynomial with rational (in particular, integer) coefficients.

Plot the graph of this polynomial in sage.  Be sure that the plot displays all its (real) zeros.  Note that ff has at least one integer zero in particular, x=2).  Let's try to divide ff by g=x2g=x-2 by using the command quo_rem:

f.quo_rem(g)

Try out this command.  What happens?

#Example 1

Even though some of the expressions we have run into in examples previously look to us like polynomials, Sage would not recognize them that way. Sage makes a distinction between general symbolic expressions and polynomials. This means, for instance, that there are operations permitted on one type of object that are not defined on the other (for example, quo_rem does not work on an expression). This is somewhat annoying at times, but fortunately, there are ways to get Sage to display  what type of thing a given object is and to change that if necessary.

Defining the ring of polynomials with coefficients in a specific ring

Say we want to perform computations with polynomials in
the ring R=Q[x]R = {\bf Q}[x] (What does Q[x]\bf{Q}[x] mean?). Sage lets us define this structure
in several different ways. Here is the most direct:

R.<x> = PolynomialRing(QQ)

(Other possibilities for the coefficient ring would be ZZ -- the ring of integers, Integers(n) for the integers mod nn (fill in the specific integer nn, of course!), GF(p) for the finite field of order pp, and many, many others.)

Try it out! (Example 2)

Define the ring R=Q[x]R = {\bf Q}[x].

#Example 2

If you need to determine whether something (say f) is really a polynomial (for example, if it is causing an error message), you can enter a command like this:

f.parent()

Try it out!  (Example 3)

What is your ff that you defined before?

#Example 3

The output will indicate the ``parent structure'' in which  f is defined.  It should be something like Univariate Polynomial ring over x over Rational Field for some of the following commands to work. If the output is something like Symbolic Ring, then the object is not a polynomial; it is just a general symbolic expression.

All is not lost, though. If you have a symbolic polynomial expression that contains only the variable xx, you can ``force'' Sage to treat it as an element of the ring RR defined above with a command like this:

 fR = R(f)

(you could also use the same name if you wanted to).    

Try it out! (Example 4)

Use your newfound knowledge of defining polynomials to redefine ff as a polynomial.

#Example 4

Operations on polynomials

Sage has built-in commands:

  • factor to factor a polynomial. This gives the factorization over the specified coefficient ring. For instance, if we defined Q[x]{\bf Q}[x] as above, then the factor command does not know about radicals, complex numbers, etc.  Formats: factor(poly) or poly.factor(). This works on polynomials in any number of variables.

Try it out! (Example 5)

Factor ff over the rationals.

#Example 5

Example 6

Factor the following polynomials over the rationals:

a.)  p=x22x+1p=x^2-2x+1

b.)  s=x33x2+4s=x^3-3x^2+4

c.)  t=x22t=x^2-2.

#Example 6
  • quo_rem() to compute the quotient and remainder on division of one polynomial f(x)f(x) by another g(x)g(x). This has a slightly strange format: f.quo_rem(g) Note: the polynomial g in the parentheses is used as the divisor; the polynomial being acted on (the f) is the dividend. If ff or gg contain other variables besides xx, this will fail. The output from this is a Sage list -- the quotient is the first element and the remainder is the second element. If you want to assign names to the outputs, you can do something like this: (q,r) = f.quo_rem(g)

Try it out! (Example 7)

Compute the following:

a.) Divide x45x3+8x24xx^4-5x^3+8x^2-4x by x2x-2 (what do you expect to get?)

b.) Divide x2x-2 by x45x3+9x24xx^4-5x^3+9x^2-4x.

c.) Divide x34x5x^3-4x-5 by x22x4x^2-2x-4.

#Example 7
  • gcd to compute the greatest common divisor of two polynomials f(x)f(x) and g(x)g(x). Format: f.gcd(g). The greatest common divisor of a set of several polynomials can be computed by nested gcd's.  For example, gcd(f,g,h)\gcd(f,g,h) can be computed by f.gcd(g).gcd(h)

Try it out! (Example 8)

Compute the gcds of the following pairs of polynomials.  Given your results from Example 7, think critically about whether or not these answers make sense.

 a.) gcd(x52x44x3+8x22x+4,x2)\gcd(x^5-2x^4-4x^3+8x^2-2x+4, x-2)

b.) gcd(x34x5,x22x4)\gcd(x^3-4x-5, x^2-2x-4)

 
  • diff(f,x) computes the formal derivative of ff with respect to xx.

Example 9

Here is a sample sequence of Sage input lines illustrating some of these commands. Try entering and executing them in sequence. Look carefully at the output and make sure you understand what happened in each case:

R.<x> = PolynomialRing(QQ)

cube = (x**2 - 16)**3

print cube

s = (x**2-x+1)*(x - 4)

print s

(q,r) = cube.quo_rem(s)

print "q = ", q," , r = ", r

q*s + r == s 

#Example 9

B.  Graph Theory

Sage can be used to generate graphs.  

 

For example, you can use sage to create any complete graph with nn vertices using graphs.CompleteGraph(n)

Example 1

See below for the complete graph on 5 vertices.

G=graphs.CompleteGraph(5);show(G);
d3-based renderer not yet implemented
for n in

You can also figure out properties of graphs using commands:

  • is_connected() : Determines if a graph is connected or not
  • connected_components() : Gives you the connected components of the graph
  • is_hamiltonian() : Determines if a graph has a Hamiltonian cycle (circuit that passes through every vertex once)
  • hamiltonian_cycle() :Gives you a hamiltonian cycle
  • chromatic_number() : Tells you the minimum coloring needed for the vertices of this graph

Try it out! (Example 3)

Try out some of these commands on our previous graph GG.

#Example 3

How do you input graphs?

To create a graph, you can use one of the ready-made commands like CompleteGraph or Bipartite.  If your graph is a little more unusual, you could use the adjacency matrix instead:

M=(mij)M=(m_{ij}), where mij=1m_{ij}=1 if and only if there is an edge between vertex ii and vertex jj.

Then you would create the graph as:

Graph(M)

Try it out! (Example 4)

Try creating a graph using an adjacency matrix.  How would you create loops?

#Example 4

C. Game Theory

The game theory package has some options for creating common games, such as the Prisoners Dilemma.

g=game_theory.normal_form_games.PrisonersDilemma

Notice that the assumed matrices are

A=[RSTP]=[2504]A=\begin{bmatrix} R & S \\ T & P \end{bmatrix}=\begin{bmatrix} -2 & -5 \\ 0 & -4\end{bmatrix}

B=[RTSP]=[2054]B=\begin{bmatrix} R & T \\ S & P \end{bmatrix}=\begin{bmatrix} -2 & 0 \\ -5 & -4\end{bmatrix} 

You can obtain the Nash equilibrium for this via the command g.obtain_nash()

Try it out! (Example 1)

Find the Nash equilibrium for the above system.

#Example 1

If you'd like to change the values of R,P,S,TR, P, S, T, you can do so via the command

game_theory.normal_form_games.PrisonersDilemma(R=0, P=-1, S=-4, T=5)

Try it out! (Example 2)

Try out different values for the game, along with computing  the Nash equilbirium.  Which values are prohibited?

#Example 2

Some other games (look them up if interested)

  • Rock, paper, scissors, lizard, spock: game_theory.normal_form_games.RPSLS()
  • Stag Hunt: game_theory.normal_form_games.StagHunt()
  • Battle of the Sexes: game_theory.normal_form_games.BattleOfTheSexes()
  • Chicken: game_theory.normal_form_games.Chicken()
#Work space