Background: Rings

A ring is a set $R$ with a way of adding and multiplying the elements of $R$ (that satisfies certain axioms).

Examples:

The ring of integers (whole numbers): $\{\ldots, -3,-2,-1,0,1,2,3,\ldots\}$.
The ring of rational numbers (fractions): $2/3, -8/5, \ldots$
The real numbers (all decimals): 2.3333, $\pi$, $\sqrt{2}$ etc.
The complex numbers: $2 + 3i$, $\pi - \sqrt{2}i$, etc.
The Gaussian integers: all numbers of the form $a+b i$ with $a,b$ integers.
The ring of number modulo 12 (clock arithmetic): $\{0,1,2,3,4,5,6,7,8,9,10,11\}$ where $n + m$ is the result of adding, then taking the remainder upon dividing by $12$.

Remark: Rings are one of the absolutely most basic ideas in mathematics, and yet you might have never heard of them even as a junior undergrad math major (I certainly hadn't!). This is just weird. It is almost like taking chemistry courses, and never being told about the periodic table.

We create each of the above rings in Sage:

{{{id=226| ZZ /// Integer Ring }}} {{{id=225| QQ /// Rational Field }}} {{{id=224| RealField(200) /// Real Field with 200 bits of precision }}}

Real double precision:

{{{id=241| RDF /// Real Double Field }}} {{{id=229| CC /// Complex Field with 53 bits of precision }}} {{{id=236| ZZ[I] /// Order in Number Field in I with defining polynomial x^2 + 1 }}} {{{id=228| Integers(12) /// Ring of integers modulo 12 }}} {{{id=231| list(Integers(12)) /// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] }}}

Have a little fun:

{{{id=232| @interact def f(n=(10..1000)): i = 0 for x in QQ: print '%s,'%x, i += 1 if i > n: break /// }}} {{{id=227| /// }}}

Important Note: Computers are "finite" but many of the above rings are infinite. So really the above are merely "models" of the given rings. E.g., the real field in Sage is really a specific finite set of floating point numbers that are representable in a computer.

{{{id=222| /// }}}

Matrices in Sage

Sage has datatypes that represent $n\times m$ matrices in the mathematical sense of matrices. There are specialized optimized datatypes over certain base rings, and generic (possibly slow) matrices over absolutely any commutative ring in Sage. Sage also equally supports both sparse and dense representations of matrices.

You can create matrices using the matrix command, or by coercing into a space of matrices. Matrices act on vectors as well, and you can solve linear systems of equations using matrices.

Key points:

All Sage matrices are 2-dimensional
All entries of a Sage matrix must belong to the same ring
Sparse and dense is a property of the underlying representation of the matrix -- every entry of a sparsely represented matrix could be nonzero!

{{{id=194| /// }}}

1. Creating matrices

Use either the matrix command, or create a MatrixSpace and coerce elements in.

matrix(n, m, [list of $nm$ entries]) -- makes an $n\times m$ matrix with the given entries. Sage finds a ring into which all the entries canonically coerce, and coerces them into that common ring.
matrix(n) -- makes an $n\times n$ zero matrix
matrix(n, [list of $n^2$ entries]) -- makes an $n\times n$ matrix.
matrix(ring, ...) -- as above, but makes matrix with entries in the given ring
matrix([list of lists of entries]) -- makes matrix with given entries where size determined by list of lists structure

{{{id=0| matrix(2,3, [1,2, 3/4,5, 2/3,-7]) /// [ 1 2 3/4] [ 5 2/3 -7] }}} {{{id=209| matrix(4) /// [0 0 0 0] [0 0 0 0] [0 0 0 0] [0 0 0 0] }}} {{{id=210| A = matrix(CC, [[1,2,3], [4,5,6]]); A /// [1.00000000000000 2.00000000000000 3.00000000000000] [4.00000000000000 5.00000000000000 6.00000000000000] }}} {{{id=216| A.base_ring() /// Complex Field with 53 bits of precision }}} {{{id=212| matrix([[sqrt(2), sqrt(3)*x^pi], [I, pi^3]]) /// [ sqrt(2) sqrt(3)*x^pi] [ I pi^3] }}} {{{id=181| matrix? /// }}} {{{id=213| /// }}}

Problem: By far, the best way to learn the matrix command is simply to try it out.

Make a $3\times 3$ zero matrix.
Make a $2\times 4$ matrix with rational number entries with at least one having a big denominator.
Make a $5\times 5$ matrices whose entries are the integers from 1 to 25.

{{{id=220| /// }}} {{{id=219| /// }}} {{{id=218| /// }}} {{{id=238| /// }}} {{{id=237| /// }}} {{{id=217| /// }}}

You can also create a space of matrices. This is a Python object that you might view as "the set of all $n\times m$ matrices with entries in a specific ring". The primary use of matrix spaces is to create matrices in that matrix space.

MatrixSpace(ring, n, m) -- create the "space" of all $n\times m$ matrices with entries in the given ring.
MatrixSpace(ring, n) -- create the $n\times n$ matrices with entries in the given ring.

{{{id=130| M = MatrixSpace(QQ, 2, 3); M /// Full MatrixSpace of 2 by 3 dense matrices over Rational Field }}} {{{id=196| MatrixSpace? /// }}}

You can coerce (using call) lists (or lists of lists) into a matrix space to create a specific matrix in that space.

{{{id=131| M([1,2, 3/4,5, 2/3,-7]) /// [ 1 2 3/4] [ 5 2/3 -7] }}} {{{id=184| M([[1,2, 3/4], [5, 2/3,-7]]) /// [ 1 2 3/4] [ 5 2/3 -7] }}}

You can also create the zero matrix as follows:

{{{id=2| M(0) /// [0 0 0] [0 0 0] }}} {{{id=186| M.zero_matrix() /// [0 0 0] [0 0 0] }}} {{{id=235| /// }}} {{{id=234| /// }}}

Random Matrices

You can make random matrices over a ring $R$ using the random_matrix command. The inputs are similar to the inputs to the matrix command. Any ring $R$ has a random_element method, which sometimes takes parameters. You can control what parameters are used to make the random matrix, by passing in the same parameters that you would pass in to the random_element method of the ring.

{{{id=133| a = random_matrix(QQ, 3,10) show(a) ///

\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrrr} 2 & -1 & -\frac{1}{2} & -1 & -\frac{1}{2} & -1 & -1 & -\frac{1}{2} & -1 & -1 \\ -1 & -\frac{1}{2} & -\frac{1}{2} & 1 & -\frac{1}{2} & 1 & 2 & -1 & 2 & -2 \\ -2 & -2 & 2 & -1 & -2 & 1 & 1 & -\frac{1}{2} & -1 & -1 \end{array}\right)

}}} {{{id=179| QQ.random_element? /// }}} {{{id=178| show(random_matrix(QQ, 3,10, num_bound=10, den_bound=3)) ///

\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrrr} -\frac{9}{2} & 3 & -\frac{10}{3} & 2 & -1 & -\frac{9}{2} & -\frac{8}{3} & \frac{9}{2} & \frac{8}{3} & -\frac{5}{3} \\ 3 & 1 & -4 & -\frac{1}{3} & -4 & -\frac{8}{3} & -10 & -\frac{7}{2} & 3 & 10 \\ \frac{7}{3} & 10 & 5 & 1 & -\frac{7}{3} & -2 & -\frac{1}{3} & -6 & 1 & 1 \end{array}\right)

}}}

Matrix spaces also have a random_element method, which you can use to make a random matrix:

{{{id=189| M = MatrixSpace(QQ, 3,5) show(M.random_element()) ///

\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} 0 & \frac{1}{2} & -2 & 0 & 2 \\ 0 & 2 & \frac{1}{2} & 2 & 1 \\ -2 & 0 & 1 & -1 & 0 \end{array}\right)

}}} {{{id=191| show(M.random_element(num_bound=10, den_bound=20)) ///

\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} 1 & \frac{9}{14} & -\frac{4}{17} & \frac{6}{13} & -\frac{1}{2} \\ \frac{1}{6} & \frac{5}{14} & 3 & \frac{10}{3} & \frac{7}{12} \\ -\frac{1}{3} & \frac{5}{6} & \frac{5}{2} & -\frac{1}{10} & -1 \end{array}\right)

}}} {{{id=239| /// }}}

Here is an example of a random matrix with double precision real floating point entries.

{{{id=244| A = random_matrix(RDF, 4); A /// [-0.359993180633 -0.209099208458 -0.663802638468 -0.339228947421] [ 0.993580183935 -0.880517135658 0.770227435687 -0.974401864385] [ -0.44858409211 0.0335618570444 -0.926987566061 0.98029773631] [ 0.255177673673 0.893873775083 0.900989147539 0.49250385435] }}} {{{id=192| /// }}}

Sparse Matrices

As mentioned above, we can also represent matrices in Sage using a sparse data structure. This basically means that we only store the nonzero entries of the matrix, and certain algorithms take advantage of this. For some applications, this can be a huge win.

We can make a million by million matrix (with one nonzero entry). If you try this without putting "sparse=True", your computer or Sage will definitely and probably painfully crash as it runs out of memory.

{{{id=135| a = matrix(QQ, 10^6, 10^6, sparse=True) a[3,1039] = -4/5 /// }}} {{{id=138| a /// 1000000 x 1000000 sparse matrix over Rational Field (type 'print a.str()' to see all of the entries) }}} {{{id=136| a[3,1039] /// -4/5 }}} {{{id=249| /// }}} {{{id=140| /// }}} {{{id=197| /// }}}

2. Matrix arithmetic: addition, multiplication, etc.

One of the main points of matrices is that you can do arithmetic with them. As you know from a linear algebra class, you can often add and multiply matrices, at least if the number of rows and columns is compatible. Sage supports this arithmetic via + for add, and * for times.

NOTE: Matrix multiplication with * is really matrix multiplication, like you learned in your linear algebra class. It is not just componentwise multiplication of entries. Watch out, numpy is different.

{{{id=142| a = random_matrix(ZZ, 2,3); b = random_matrix(ZZ, 2,3) show((a,b)) ///

\newcommand{\Bold}[1]{\mathbf{#1}}\left(\left(\begin{array}{rrr} 1 & -4 & -2 \\ -2 & -2 & -2 \end{array}\right), \left(\begin{array}{rrr} -3 & -1 & -1 \\ 5 & 13 & -1 \end{array}\right)\right)

}}} {{{id=145| a*b.transpose() /// [ 3 -45] [ 10 -34] }}} {{{id=146| a+b /// [-2 -5 -3] [ 3 11 -3] }}} {{{id=251| /// }}} {{{id=147| /// }}}

Problem: Create two random 500x500 matrices with RDF (=real double precision floating point) entries, and multiply them. How long does this take? Impressed or not? What about 1000x1000?

{{{id=144| /// }}} {{{id=143| /// }}} {{{id=105| /// }}}

3. Canonical Forms

In a linear algebra class, you will likely spend a lot of time computing the reduced row echelon forms of matrices. This is an example of a "canonical form" of a matrix. It is one of the key building blocks on which many other algorithms are built.

In case you don't remember, this is the form you get a matrix into by doing elementary row operations. It's the form of the matrix from which invariants such as the "rank" and "nullity" are easy to read off, and it also helps in solving linear systems (Wednesday's lecture).

Reduced row echelon form

If M is a Sage matrix, compute the reduced row echelon form using either

M.echelon_form()
M.rref()

These two are synonyms -- the do exactly the same thing.

{{{id=151| M = random_matrix(QQ, 3, 5); M /// [-1/2 2 -1 1 1/2] [ -2 -1 2 -1/2 1] [ -1 -2 1/2 -1 1] }}} {{{id=153| M.echelon_form() /// [ 1 0 0 0 -23/27] [ 0 1 0 1/2 -5/27] [ 0 0 1 0 -4/9] }}} {{{id=205| M.rref() /// [ 1 0 0 0 -23/27] [ 0 1 0 1/2 -5/27] [ 0 0 1 0 -4/9] }}} {{{id=202| M = matrix(RDF, 4, [1..16]); M /// [ 1.0 2.0 3.0 4.0] [ 5.0 6.0 7.0 8.0] [ 9.0 10.0 11.0 12.0] [13.0 14.0 15.0 16.0] }}} {{{id=201| M.rref() /// [ 1.0 0.0 -1.0 -2.0] [ 0.0 1.0 2.0 3.0] [ 0.0 0.0 0.0 0.0] [ 0.0 0.0 0.0 0.0] }}} {{{id=200| /// }}}

Problem. Compute the reduced row echelon form of a random 20x25 matrix with rational number entries. Are the fractions scary looking? Aren't you glad you didn't do that by hand?

{{{id=253| /// }}} {{{id=199| /// }}} {{{id=255| /// }}} {{{id=257| /// }}}

Questions?

If time permits, show the students where the source code is for matrices, and give a quick tour.

It's in SAGE_ROOT/devel/sage/sage/matrix/

which in the notebook can be got via this link: /src/matrix/

{{{id=256| /// }}} {{{id=177| /// }}}