Lecture 1: Introduction

References:

• Introduction to Symbolic Computation, Lectures 1,2,3

Summary:
In today's lecture we'll motivate why computer algebra systems are helpful, followed by an overview of SageMath (the system we'll use in this course). Then we get started with using SageMath, learn some elementary functions and how to get help. In the appendix, there is some advice on how to install SageMath on your local computer, and an exercise for the lecturer.

Motivation

In practical mathematics, one often has to do concrete computations. As an example, one might need to compute the determinant of the following matrix: $$M = \begin{pmatrix} 17 & 2 & -4 & 9\\ -13 & 2 & 8 & 3\\ 6 & 1 & -1 & 4\\ 5 & 5 & -2 & 2 \end{pmatrix}$$ Doing this by hand can be rather exhausting (and prone to producing errors). For the above $4 \times 4$-matrix, the typical recipes for computing determinants take a lot of operations:

Luckily, instead of using our brains (or pen and paper) we can ask a computer to do the calculation for us.

In the input cell below, we enter the matrix from above, and store it in a variable M in the first line. Then we ask the computer to print out the value of the variable M in the second line. Click into the grey box below and press Shift+Enter to execute it.

Then we can compute the determinant of M as follows:

For the calculation above, we used SageMath. This is a free, open-source mathematical software system, which allows us to do computations in many different areas of mathematics. In particular, it is an example of a Computer Algebra System (CAS) and we can use it for manipulations of symbolic objects, like polynomials:

In the course, we will learn how to

• use the functions of SageMath

• apply them to concrete problems

• program new functions and software packages for SageMath

On the other hand, we will not treat in so much detail

• theoretical descriptions of algorithms

• extensive introduction to Python (we'll have a crash course)

Plan of the course

The following is a preliminary plan of the topics covered in the lectures this semester:

Part 1 : Introduction to computer algebra

1. Introduction

2. Linear Algebra

3. Numbers and symbolic expressions

4. Calculus and power series

5. Algebra

6. Combinatorics and graph theory

7. Convex geometry

8. External packages and software

Part 2: Mathematical programming

9. Classes and algebraic structures

10. Tools for debugging and optimization

11. Python packaging

12. Documentation and testing frameworks

The total number of lectures in the semester is 13, so we have a bit of wiggle-room in case a topic needs longer than one lecture.

To get credit for the lecture, you should either

• hand in a short software project (from list of topics or chosen yourself)
  Example: PlaneTriangle (with functions for area, circumference, center of mass, $\ldots$)

• or have an oral exam

SageMath

History

SageMath (or Sage, "Software for Algebra and Geometry Experimentation") was originally developed by a team around William Stein at the University of Washington. The first version was released in 2005 and since then it has been steadily updated and developed. For more information you can have a look at the SageMath wikipedia page or watch this video from 2010 describing the motivation behind and the beginnings of SageMath.

Features, strengths and weaknesses

Useful links

• Official website

• Ask.SageMath forum

Getting started

In an Appendix below you find a guide how to get access to SageMath. Please tell me if you encounter any problems, and I will do my best to help. For quick access to the present document (only requiring a web browser and internet access) click on the following link and select

Edit -> Use CoCalc Anonymously -> Create Project -> Copy * to ** -> Open your copy of **

There are two main ways to use SageMath. One is to run it in a command line (or console/shell/prompt/terminal/...). For this, open the console (on Linux or MacOS) and type sage+Enter, or start the program SageMath 9.X (on Windows). You will see something like the following: Then you can enter commands one after the other, pressing Enter to execute them.

Instead of the command line, we are going to use a so-called Jupyter notebook running SageMath as a kernel. This is the format you see before you - in particular, it allows mixing text (with formulas and pictures) and cells with code that can be executed.
To run the notebook of this lecture on your computer, you should type sage -n jupyter+Enter in your console (on Linux or MacOS) or start the program SageMath 9.X Notebook (on Windows). This opens a page in your webbrowser where you see files on your computer. Click your way to the folder where you saved the file 01_Introduction.ipynb and click on it to start.

For the rest of the lecture, we are going to play around a bit with SageMath, make some computations and see some of the basic features that help us using it.

SageMath as a calculator

One of the most elementary ways to use SageMath is as a calculator: you can type numbers and combine them using + for addition, * for multiplication and ^ (or **) for raising to a power. To structure the calculation, you can also use parentheses ( and ).

Exercise

Calculate the numbers $$17+3\cdot(8-9),\quad 9^{12 \cdot 12},\quad \frac{24}{33}$$ in the three code cells below. Remember that you can execute a cell by clicking into it and pressing Shift+Enter.

Solution (uncomment to see)

A priori, SageMath tries to do exact computations, and thus the division of two integers is in general displayed as a fraction instead of a decimal number. To get the decimal digits, you can use the function n:

Or, if we need it to a precision of 30 digits (not that this is very interesting in this case ...):

It also knows a lot of standard functions, like exp, sin or cos and universal constants like e, pi and i.

Exercise

Verify that SageMath is smart enough to know the following identities: $$\sin\left(\frac{\pi}{2}\right)=1, \quad e^{\pi i}=-1.$$

Solution (uncomment to see)

But what about the logarithm? Here we could get ourselves into trouble, since there are different conventions: some people write $\log$ for the natural logarithm, some people use it for the logarithm to base $10$. To find out which convention SageMath uses, we can look at the documentation of the function log by typing log?:

So this tells us that log(x) computes the natural logarithm of x, whereas log(x,b) computes the logarithm to base b.

Exercise

On a big lake, the number of water lilies doubles every three days. Starting with one water lily, how many days does it take before their number exceeds 10000?

Solution (uncomment to see)

Before moving on to more interesting mathematical objects, let's see another useful feature: tab completion. If you start typing the name of a function and press Tab, you can see a list of all functions starting with the letters you already typed:

Exercise

Mmh, I'm sure that SageMath has some way to compute the binomial coefficient $$\binom{n}{k} = \frac{n!}{k! (n-k)!}$$ but was the corresponding function binom (like in LaTeX) or maybe binomial_coefficient? Find it out using Tab-completion and compute $\binom{20}{10}$.

Solution (uncomment to see)

Interlude : getting to know the Jupyter notebook

Since we are going to use SageMath within a notebook like the present one, it's a good idea to learn a bit about how to use it.

As you have already seen, there are two types of cells in Jupyter:

• code cells where you can perform computations with SageMath

• Markdown cells containing text, formulas, or pictures

Clicking on a Markdown cell and pressing Enter allows you to see its source code. You can execute it and see the nicely formatted text again by pressing Shift+Enter.

Exercise

Play around with the notebook a bit (in particular with the various options in the menu above). Some things you can try:

• Insert two new code cells below.

• Convert one of them into markdown and write a bit of text.

• Delete the code cell again.

• (if you know LaTeX) Insert an equation between two $$-symbols, e.g. giving the value of the integral of $x^2$ from $0$ to $1$.

• Find a picture of a cat on google and insert it into one of the markdown cells.

• Save the notebook so you don't loose the picture of the cat!

Solution (uncomment to see)

Some first computations with matrices

As we saw before, SageMath can also handle more complicated mathematical objects, such as matrices. As we saw above, you can create a matrix M using the function matrix. Then you can compute information about this matrix (such as its determinant) by using the internal functions (or methods) of the matrix M such as M.determinant(). SageMath also supports addition, scalar multiplication and matrix multiplication using +,* as before.

Exercise

• Enter the matrix N given by $$N = \begin{pmatrix} 1 & 4 & 9\\16&25&36\\49&64&81 \end{pmatrix}.$$

• Compute the determinant and trace of N.
  Hint: Given a matrix N, you still have access to Tab completion by typing for example N.+Tab or N.de+Tab.

• Compute the matrix $3 \cdot (N + N^\top) - N \cdot N^\top$, where $N^\top$ denotes the transpose of the matrix $N$.

When solving this exercise, you should keep in mind the

Solution (uncomment to see)

Let's finish up by seeing a first toy example of how SageMath can be used to solve "real" mathematics problems. Consider the following question, which might appear on a Linear Algebra problem sheet:

Question For the matrix $$M(n) = \begin{pmatrix} 1 & 2 & \ldots & n\\ n+1 & n+2 & \ldots & 2n\\ \vdots & & & \vdots\\ n^2-n+1 & n^2-n+2 & \ldots & n^2 \end{pmatrix} \in \mathbb{R}^{n \times n},$$ what is the rank of $M(n)$ in dependence of $n \in \mathbb{Z}_{>0}$?

Exercise

Let's compute the rank of $M(n)$ in some examples, to see if we spot a pattern. However, instead of entering the matrix by hand, we can write a function M(n) taking as input the number n and returning the matrix.

• We will recall the details about how to define a Python functions in a later lecture. Below, I have an almost finished version of the function M(n). Replace the ???? part by a formula for the $(i,j)$-entry of $M(n)$, where $i,j$ run from $0$ to $n-1$.
  Here we use that a different way to create a matrix $M$ is to call matrix(n,m,f) where n is the number of rows, m is the number of columns and f is a function $(i,j) \mapsto M_{i,j}$.

• Check that for some values of $n$, your function above computes the correct matrix.

• Compute the rank of $M(n)$ for several examples of $n$ and guess the pattern.

• (optional) Can you see how to prove the formula that you guessed?

Solution (uncomment to see)

Two take-aways from that last example:

• Knowing the answer of a problem in some examples is often really helpful in finding a general proof, and computers can help us with those examples!

• Learning a bit about programming (such as Python functions above) can help in doing computations, even if one is not primarily interested in pursuing a big programming project.

I hope you enjoyed this little introduction to SageMath. Starting from next week, we'll go into more details for specific areas of mathematics (beginning with Linear Algebra) and also recall more systematically some Python concepts like functions, lists, etc.

Appendix: Getting your hands on SageMath

Here are three ways of getting access to SageMath:

SageMathCell

If you have internet access and want to perform a short computation, you can go to https://sagecell.sagemath.org/, enter the code you want to run and click a button to see the result.

Cocalc

For longer computations and projects, you can got to https://cocalc.com/ and create a free account. Then you can create a new project, and add a Jupyter notebook (a file ending on .ipynb). Select a SageMath kernel to get an environment like the current file.

Local SageMath installation

The most convenient way to work with SageMath is to install it on your computer. On the university computers, it is already installed. For your personal computers, see https://doc.sagemath.org/html/en/installation/binary.html for the official installation guide. Here is the short version for the most important operating systems:

• Linux: follow the section of the installation guide above

• Windows: go to https://github.com/sagemath/sage-windows/releases to download the latest SageMath-XX-Installer-YY.exe and run it

• MacOS: installing SageMath here can be slightly tricky, but many people had good experiences with this inofficial guide: https://github.com/3-manifolds/Sage_macOS/releases/

If you still have some older version of SageMath installed on your computer, note that you should use Version 9.0 or newer for this course, since the version of Python changed starting from SageMath 9.0 and some of our code will not work on the older versions.

Appendix: Strengths and weaknesses of SageMath and an exercise for the lecturer

As an illustration of some of the points in the tabular overview of Pros and Cons about SageMath: originally I wanted to demonstrate a slightly different computation in the "Motivation" section above. There we had the characteristic polynomial P of the matrix M:

What we can do in SageMath is to compute the quotient ring $$S = \mathbb{Z}[x]/(P).$$

Then I had planned to demonstrate that SageMath can decide cool properties about this ring, such as whether $S$ is an integral domain.
Recall: A ring $S$ is an integral domain if $S \neq 0$ and for $a,b \in S$ with $a \cdot b = 0$ we must have $a=0$ or $b=0$.
However, I was disappointed:

On the other hand, since SageMath is open-source, we can immediately check what goes wrong here, by looking at the code of the function is_integral_domain:

Now we have seen that SageMath knows that P is not irreducible:

But the quotient $S=\mathbb{Z}[x]/(P)$ can never be an integral domain if $P$ is not irreducible: for $P=P_1 \cdot P_2$ with $P_1, P_2$ not units, we have $$\overline{P_1} \cdot \overline{P_2} = \overline{P} = 0 \in S$$ but $\overline{P_1} \neq 0, \overline{P_2} \neq 0 \in S$.

Exercise (for the lecturer):
Implement a better function is_integral_domain for quotient rings like $S$ and get it added to SageMath.

Assignments

Exercise (not so relevant for course, but fun anyway)

• Understand where the numbers of multiplications and additions for computing the determinant of $M$ in the first section come from.
  Fun fact: I actually used SageMath to compute them!

• For the two algorithms from the table, show that one needs at least $n!$ multiplications to compute the determinant of a $n \times n$-matrix.

• Can you think of an algorithm where this number grows only polynomially in $n$?