Lecture 2 : Linear Algebra

References:

• Introduction to Symbolic Computation, Lecture 29

• Linear Algebra tutorial in SageMath

• Sage Quickstart for Linear Algebra

Summary:
We start with a reminder on lists in Python, and functions for creating and manipulating them. Then we discuss matrices in SageMath: how to construct them, how to solve linear systems of equations, computer kernels and eigenvalues etc. Finally, we discuss linear spaces and how to intersect or add them.

Python warmup : lists

Recall that in Python, a list L is an ordered collection of objects. They can be created by hand, using square brackets [,]:

You can access element number i in the list (with count starting from 0) using L[i]:

This can also be used to change an element of the list:

Lists have many useful functions:

• you can get the number of elements in L using len(L)

• given a second list M you can compute the concatenation of L and M by L+M

• you can check if a is contained in L by the expression a in L

Exercise

• Create a list M with 3 elements of your choice.

• Define N to be the list obtained by concatenating L (from above) and M.

• Check that the length of N is now equal to 7.

Solution (uncomment to see)

A list L also has many useful methods, like L.pop(i) which returns L[i] and removes this entry from the list. As we saw last week, you can see all these methods by typing L.+Tab to access the Tab completion.

Exercise

Consider the following list:

• What is the number i such that L[i] equals 9?
  Hint: Use Tab completion and the documentation to find the right function.

• Remove the corresponding entry from the list.

Solution (uncomment to see)

Finally, a nice way to create bigger lists is using list comprehension involving the for constructor. We will learn more about this and for-loops later, but for now we just mention that

[f(i) for i in range(n)]

creates the list [f(0), f(1), ..., f(n-1)], and similarly

[f(i) for i in range(a,b)]

creates the list [f(a), f(1), ..., f(b-1)].

Exercise

You get an email from a local school, asking for help since they misplaced some of their math education materials. In particular, they request whether you can send them:

• a list of the square numbers 1^2, ..., 20^2

• a multiplication table for the numbers from 1 to 10

Solution (uncomment to see)

Matrices

At the center of linear algebra are matrices, which describe linear maps between finite-dimensional vector spaces.

Constructing matrices

From last time, we recall that we can create matrices using the function matrix. We saw that it can handle at least two different types of input:

• matrix([v1, v2, ..., vm]) takes a list of vectors, forming the rows of the desired matrix,

• matrix(m,n,f) takes the numbers m,n of rows and columns of the matrix $M$, and a function f sending pairs $(i,j)$ to the desired entry $M_{i,j}$ of the matrix

Exercise

The Vandermonde matrix associated to a vector $a=(a_1, \ldots, a_n)$ of numbers is the matrix $$V(a_1, \ldots, a_n)= \begin{pmatrix} 1 & a_1 & \ldots & a_1^{n-1}\\ 1 & a_2 & \ldots & a_2^{n-1}\\ \vdots & & & \vdots\\ 1 & a_n & \ldots & a_n^{n-1} \end{pmatrix}\,.$$ Below is the beginning of an implementation of the function taking a list a of numbers and returning the corresponding Vandermonde matrix. Complete the program and test it in some examples.

Solution (uncomment to see)

One further possibility to construct a matrix by hand is to call matrix with a dictionary. We are going to discuss these later in more detail, but below is a hopefully self-explaining example:

For many standard types of matrices, there are also pre-defined functions:

On the other hand, if someone hands you a matrix M, you can find out its number of rows and columns using M.nrows() and M.ncols():

You can access the entry $M_{i,j}$ using M[i,j]:

Sometimes it can be useful to explicitly specify that a matrix should have entries in a certain ring. This ring can then be given as the first argument to the matrix function.

Some common rings:

• ZZ the integers

• QQ the rational numbers

• RR the real numbers (floating point operations!)

• CC the complex numbers (floating point operations!)

• GF(q) the finite field $\mathbb{F}_q$ with $q$ elements

Example

The matrix $$M = \begin{pmatrix} 1 & 1 \\ 3 & 5 \end{pmatrix}$$ has rank $2$ seen as a matrix of rational numbers.

But over the finite field $\mathbb{F}_2 = \mathbb{Z}/2\mathbb{Z}$ we have $$M = \begin{pmatrix} 1 & 1 \\ 3 & 5 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$$ and so the matrix only has rank $1$.

Exercise

Find a formula for the determinant $\det(V(a_1, \ldots, a_n))$ of the Vandermonde matrix. Bonus points if you can get the sign correct ...
Hint: Another useful ring is a polynomial ring, which you can construct as follows:

Solution (uncomment to see)

Linear algebra with matrices

Now that we can input matrices, we can start doing more interesting computations.

Matrix arithmetic and vector products

We already saw that we can perform matrix arithmetic with +,*,^:

In particular, when M is invertible, we can compute its inverse by M^(-1) (or M.inverse()):

Note that you can also compute the expression $M^x$ for a formal variable $x$. Below we use that in SageMath x is by default a variable in the symbolic ring, which we will see later.

We can also create vectors and multiply them with matrices.

Row echelon form

Another interesting computation for a matrix $M$ is its row echelon form (German: Zeilenstufenform), which is the simplified form of $M$ obtained by row-operations.

Note that if we work over the integers ZZ, the algorithm only does integer operations on the rows (it is not allowed to divide a row by a number), so the output will be slightly different:

We can also get the matrix $U$ describing the row-operations to bring $M$ into echelon form $E$, so that $U \cdot M = E$:

Exercise

Does there exist a subset of the vectors $$v_1 = \begin{pmatrix}-2\\ 5\\ 3 \end{pmatrix}, v_2 = \begin{pmatrix}4\\ -10\\ -6 \end{pmatrix}, v_3 = \begin{pmatrix}1 \\0 \\ -7 \end{pmatrix}, v_4 = \begin{pmatrix} -1\\ 5\\ -4 \end{pmatrix}, v_5 = \begin{pmatrix} -5\\ 10\\ 13 \end{pmatrix}, v_6 = \begin{pmatrix} 5\\ -2\\ -11 \end{pmatrix}, v_7 = \begin{pmatrix} 9\\ -15\\ -30 \end{pmatrix} \in \mathbb{R}^3$$ which forms a basis of $\mathbb{R}^3$? If so, specify such a subset.
Hint: To save you time, here is the list of the vectors above:

Solution (uncomment to see)

Solving linear equations

Of course, we can also solve linear systems of equations using SageMath: given a matrix M and a vector b the solution of the linear system $$M \cdot x = b$$ is computed using M.solve_right(b).

As the name suggests, there is also the methods M.solve_left(b), which solves the equation $$x^T \cdot M = b^T,$$ where $x^T, b^T$ are the transposed (or row) vectors of $x,b$.

Exercise

Find out what M.solve_right(b) does when the system has

• more than one solution, or

• no solution,

either by reading the documentation or by experimenting.

Solution (uncomment to see)

Further matrix functions

As you can imagine, there are many more things that SageMath can compute about matrices. Instead of going through all of them, let's have an exercise where you can practice finding out about some of these functions yourself. In this regard, the following advice has proven useful in the past:

Exercise Consider the following matrix:

• What are the eigenvalues of M?

• Compute a matrix $S$ such that $S M S^{-1}$ is a diagonal matrix.

• Compute a permutation matrix $P$, a lower-triangular matrix $L$ and an upper triangular matrix $U$ such that $A = PLU$.
  (Hint: This is often called a LU-decomposition)

• Is $M$ a normal matrix, i.e. does it satisfy $M \cdot M^\top = M^\top \cdot M$?

Solution (uncomment to see)

Linear spaces

In SageMath we can also directly create vector spaces and perform computations with subspaces (like direct sums, intersections etc.).

Then we can create subspaces of V:

Here degree 3 means that the ambient space V has is of rank 3, and dimension 2 means that W1 itself is of dimension 2.

Now we can check if a vector is contained in one of those subspaces, or compute their intersection or sum in V.

An alternative way to create subspaces is using the function span:

Exercise

Consider the following vectors in $\mathbb{Q}^4$:

Use the methods for linear spaces we saw above, to answer the following questions:

• Are $w_1, w_2, w_3$ linearly independent?

• Is $v$ contained in the subspace of $\mathbb{Q}^4$ generated by $w_1, w_2, w_3$?

Solution (uncomment to see)

Of course one could also find the answer to these questions using matrices, and in the background this is what SageMath does. Given a space like W1, you can get access to the matrix whose rows form a basis of W1 using W1.basis_matrix():

Exercise

Let's apply the concepts from above to write a nice function ourselves, which computes orthogonal projections. Recall that given a sub-vector space $V \subseteq \mathbb{R}^n$ and a point $p \in \mathbb{R}^n$, the orthogonal projection of $p$ onto $V$ is the unique point $p_0 \in V$ such that the vector $p-p_0$ is orthogonal to $V$.

• Complete the definition of the function orthogonal_projection below, which takes as input the vector space V and the vector p and returns the orthogonal projection p_0 as above.

Hint: If $v_1, \ldots, v_m \in V$ is a basis of $V$, then there exist numbers $x_1, \ldots, x_m$ such that $p_0 = x_1 v_1 + \ldots + x_m v_m$. Reformulate the condition that $p - p_0$ is orthogonal to $V$ as a linear system $A \cdot x = b$.

• Test your function in some non-trivial example.

Solution (uncomment to see)

Assignments

Exercise

For which values of $x \in \mathbb{Q}$ is the matrix $$M(x) = \begin{pmatrix} -2 & 3 & x \\ -5 & x & 6 \\ 1 & -1 & 0 \end{pmatrix}$$ invertible?

Solution (uncomment to see)

Exercise

Write a function jordan_form(blocks) taking as input a list blocks of the form [[e1,m1], ..., [en,mn]] of pairs [ei,mi] of eigenvalues and multiplicities, and producing the corresponding Jordan block diagonal matrix. Here is an example how it would work:

jordan_form([[3,2],[4,1],[-1,3]])
>
[ 3  1  0  0  0  0]
[ 0  3  0  0  0  0]
[ 0  0  4  0  0  0]
[ 0  0  0 -1  1  0]
[ 0  0  0  0 -1  1]
[ 0  0  0  0  0 -1]

For an easier variant of the exercise: try to create the particular $6 \times 6$-matrix above with as little code as possible.

Solution (uncomment to see)

Exercise

Consider the following matrix:

Compute its characteristic polynomial and minimal polynomial. Why are they different?
Bonus: See the solution for an explanation how the hell I came up with this matrix.

Solution (uncomment to see)

Exercise

Inside $\mathbb{R}^3$ with coordinates $x_1, x_2, x_3$ consider the subspace $$V = \{(x_1, x_2, x_3) : 2 x_1 - x_2 + 3 x_3 = 0\}\,.$$

• Compute a basis $\mathcal{B}$ of $V$.

• For the linear map $f:\mathbb{R}^3 \to \mathbb{R}^3$ induced by the matrix $$A = \begin{pmatrix} 3 & 5 & 0 \\ -2 & 6 & 8 \\ -1 & 1 & 7 \end{pmatrix}$$ compute the matrix $A_V$ for the restriction $f|_V : V \to \mathbb{R}^3$ with respect to your chosen basis $\mathcal{B}$ of $V$ and the standard basis of $\mathbb{R}^3$.

Solution (uncomment to see)