Harmonic quotients of regular graphs – examples

Posted on 2023/01/06 by wdjoyner

Caroline Melles and I have written a preprint that collects numerous examples of harmonic quotient morphisms $\phi : \Gamma_2 \to \Gamma_1$ , where $\Gamma_1=\Gamma_2/G$ is a quotient graph obtained from some subgroup $G \subset Aut(\Gamma_2)$ . The examples are for graphs having a small number of vertices (no more than 12). For the most part, we also focused on regular graphs with small degree (no more than 5). They were all computed using SageMath and a module of special purpose Python functions I’ve written (available on request). I’ve not counted, but the number of examples is relatively large, maybe over one hundred.

I’ll post it to the math arxiv at some point but if you are interested now, here’s a copy: click here for pdf.

A graph_id function in SageMath

Posted on 2022/09/07 by wdjoyner

While GAP has a group_id function which locates a “small” group in a small groups database (see the SageMath page or the GAP page for more info), AFAIK, SageMath doesn’t have something similar. I’ve written one (see below) based on the mountain of hard work done years ago by Emily Kirkman.

def graph_id_graph6(Gamma, verbose=False):
    """
    Returns the graph6 id of Gamma = (V,E).
    If verbose then it also displays the table of all graphs with
    |V| vertices and |E| edges.

    Assumes Gamma is a "small" graph.

    EXAMPLES:
    sage: Gamma = graphs.HouseGraph()
    sage: graph_id_graph6(Gamma, verbose=False)
    'Dbk'
    sage: graph_id_graph6(Gamma, verbose=True)

     graphs with 5 vertices and 6 edges:

    Graph6               Aut Grp Size         Degree Sequence     
    ------------------------------------------------------------
    DB{                  2                    [1, 2, 2, 3, 4]     
    DFw                  12                   [2, 2, 2, 3, 3]     
    DJ[                  24                   [0, 3, 3, 3, 3]     
    DJk                  2                    [1, 2, 3, 3, 3]     
    DK{                  8                    [2, 2, 2, 2, 4]     
    Dbk                  2                    [2, 2, 2, 3, 3]     


    'Dbk'

"""
n = len(Gamma.vertices())
m = len(Gamma.edges())
ds = Gamma.degree_sequence()
Q = GraphQuery(display_cols=['graph6', 'aut_grp_size', 'degree_sequence'], num_edges=['=', m], num_vertices=["=", n])
for g in Q:
    if g.is_isomorphic(Gamma):
        if verbose:
            print("\n graphs with %s vertices"%n+" and %s edges:\n"%m)
            Q.show()
            print("\n")
        return g.graph6_string()

Let’s do the Landau shuffle

Posted on 2021/10/23 by wdjoyner

Here’s a shuffle I’ve not seen before:

Take an ordinary deck of 52 cards and place them, face up, in the following pattern:
Going from the top of the deck to the bottom, placing cards down left-to-right, put 13 cards in the top row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
11 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 9 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 7 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 5 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\$
then 3 cards in the next row:
$\Box\ \Box\ \Box\$
and finally, the remaining 4 cards in the last row:
$\Box\ \Box\ \Box\ \Box\$
Now, take the left-most card in each row and move it to the right of the others (effectively, this is a cyclic shift of that row of cards to the left).
Finally, reassemble the deck by reversing the order of the placement.

In memory of the great German mathematician Edmund Landau (1877-1938, see also this bio), I call this the Landau shuffle. As with any card shuffle, this shuffle permutes the original ordering of the cards. To restore the deck to it’s original ordering you must perform this shuffle exactly 180180 times. (By the way, this is called the order of the shuffle.) Yes, one hundred eighty thousand, one hundred and eighty times. Moreover, no other shuffle than this Landau shuffle will require more repetitions to restore the deck. So, in some sense, the Landau shuffle is the shuffle that most effectively rearranges the cards.

Left to right: Oswald Veblen, Edmund Landau, Harald Bohr. Location, photographer, date unknown.

Now suppose we have a deck of $n$ (distictly labeled) cards, where $n>2$ is an integer. The collection of all possible shuffles, or permutations, of this deck is denoted $S_n$ and called the symmetric group. The above discussion leads naturally to the following question(s).

Question: What is the largest possible order of a shuffle of this deck (and how do you construct it)?

This requires a tiny bit of group theory. You only need to know that any permutation of $n$ symbols (such as the card deck above) can be decomposed into a composition or product) of disjoint cycles. To compute the order of an element $g \in S_n$ , write that element $g$ in disjoint cycle notation. Denote the lengths of the disjoint cycles occurring in $g$ as $k_1, k_2, \dots , k_m$ , where $k_i>0$ are integers forming a partition of $n$ : $n = k_1 + k_2 +\dots + k_m$ . Then the order of $g$ is known to be given by $order(g) = LCM(k_1, k_2, ...., k_m)$ , where LCM denotes the least common multiple.

The Landau function $g(n)$ is the function that returns the maximum possible order of an element $g \in S_n$ . Landau introduced this function in a 1903 paper where he also proved the asymptotic relation $\lim_{n\to \infty} \frac{\ln(g(n))}{\sqrt{n\ln(n)}}=1$ .

Example: If $n=52$ then note $52 = 13+11+9+7+5+3+4$ and that $LCM(13,11,9,77,5,3,4)=180180$ .

Oddly, my favorite mathematical software program SageMath does not have an implementation of the Landau function, so we end with some SageMath code.

def landau_function(n):
    L = Partitions(n).list()
    lcms = [lcm(P) for P in L]
    return max(lcms)

Here is an example (the time is included to show this took about 2 seconds on my rather old mac laptop):

sage: time landau_function(52) CPU times: user 1.91 s, sys: 56.1 ms, total: 1.97 s Wall time: 1.97 s 180180

Differential equations and SageMath

Posted on 2019/12/24 by wdjoyner

The files below were on my teaching page when I was a college teacher. Since I retired, they disappeared. Samuel Lelièvre found an archived copy on the web, so I’m posting them here.

The files are licensed under the Attribution-ShareAlike Creative Commons license.

Partial fractions handout, pdf
Introduction to matrix determinants handout, pdf
Impulse-response handout, pdf
Introduction to ODEs, pdf
Initial value problems, pdf
Existence and uniqueness, pdf
Euler’s method for numerically approximating solutions to DEs, pdf.
Includes both 1st order DE case (with Euler and improved Euler) and higher order DE and systems of DEs cases, without improved Euler.
Direction fields and isoclines, pdf
1st order ODEs, separable and linear cases, pdf
A falling body problem in Newtonian mechanics, pdf
A mixing problem, pdf
Linear ODEs, I, pdf
Linear ODEs, II, pdf
Undetermined coefficients for non-homogeneous 2nd order constant coefficient ODEs, pdf
Variation of parameters for non-homogeneous 2nd order constant coefficient ODEs, pdf.
Annihilator method for non-homogeneous 2nd order constant coefficient ODEs, pdf.
I found students preferred (the more-or-less equivalent) undetermined coefficient method, so didn’t put much effort into these notes.
Springs, I, pdf
Springs, II, pdf
Springs, III, pdf
LRC circuits, pdf
Power series methods, I, pdf
Power series methods, II, pdf
Introduction to Laplace transform methods, I, pdf
Introduction to Laplace transform methods, II, pdf
Lanchester’s equations modeling the battle between two armies, pdf
Row reduction/Gauss elimination method for systems of linear equations, pdf.
Eigenvalue method for homogeneous constant coefficient 2×2 systems of 1st order ODEs, pdf.
Variation of parameters for first order non-homogeneous linear constant coefficient systems of ODEs, pdf.
Electrical networks using Laplace transforms, pdf
Separation of variables and the Transport PDE, pdf
Fourier series, pdf.
one-dimensional heat equation using Fourier series, pdf.
one-dimensional wave equation using Fourier series, pdf.
one-dimensional Schroedinger’s wave equation for a “free particle in a box” using Fourier series, pdf.
All these lectures collected as one pdf (216 pages).
While licensed Attribution-ShareAlike CC, in the US this book is in the public domain, as it was written while I was a US federal government employee as part of my official duties. A warning – it has lots of typos. The latest version, written with Marshall Hampton, is a JHUP book, much more polished, available on amazon and the JHUP website. Google “Introduction to Differential Equations Using Sage”.

Course review: pdf

Love, War, and Zombies, pdf
This set of slides is of a lecture I would give if there was enough time towards the end of the semester

Mathematics of zombies

Posted on 2016/07/26 by wdjoyner

What do you do if there is a Zombie attack? Can mathematics help? This page is (humorously) dedicated to collecting links to papers or blog posted related to the mathematical models of Zombies.

George Romero’s 1968 Night of the Living Dead, now in the public domain, introduced reanimated ghouls, otherwise known as zombies, which craved live human flesh. Romero’s script was insired on Richard Matheson’s I Am Legend. In Romero’s version, the zombies could be killed by destroying the zombie’s brain. A dead human could, in some cases be “reanimated,” turning into a zombie. These conditions are modeled mathematically in several papers, given below.

When Zombies Attack! Mathematical Modelling of a Zombie Outbreak!, paper by Mathematicians at the University of Ottawa, Philip Munz, Ioan Hudea, Joe Imad and Robert J. Smith? (yes, his last name is spelled “Smith?”).
youtube video 28 Minutes Later – The Maths of Zombies , made by Dr James Grime (aka, “siningbanana”), which references the above paper.
Epidemics in the presence of social attraction and repulsion, Oct 2010 Zombie paper by Evelyn Sander and Chad M. Topaz.
Statistical Inference in a Zombie Outbreak Model, slides for a talk given by Des Higman, May 2010.
Mathematics kills zombies dead!, 08/17/2009 blog post by “Zombie Research Society Staff”.
The Mathematics of Zombies, August 18, 2009 blog post by Mike Elliot.
Love, War and Zombies – Systems of Differential Equations using Sage, April 2011 slides by David Joyner. Sage commands for Love, War and Zombies talk. This was given as a Project Mosaic/M-cast broadcast.
Public domain 1968 film Night of the Living Dead by George Romero.

Linear systems of graphs in Sage

Posted on 2015/05/22 by wdjoyner

Let $\Gamma$ be a graph. A divisor on $\Gamma$ is an element of the free group generated by the vertices $V$ , ${\mathbb{Z}}[V]$ .

We say that divisors $D$ and $D^\prime$ are linearly equivalent and write $D \sim D^\prime$ if $D^\prime-D$ is a principal divisor, i.e., if $D^\prime = D + \text{div}(f)$ for some function $f : V \rightarrow {\mathbb{Z}}$ . Note that if $D$ and $D^\prime$ are linearly equivalent, they must have the same degree, since the degree of every principal divisor is 0. Divisors of degree 0 are linearly equivalent if and only if they determine the same element of the Jacobian. If $D$ is a divisor of degree 0, we denote by $[D]$ the element of the Jacobian determined by $D$ . A divisor $D$ is said to be effective if $D(v) \geq 0$ for all vertices $v$ . We write $D \geq 0$ to mean that $D$ is effective. The linear system associated to a divisor $D$ is the set

$|D| = \{ D^\prime \in \text{Div}(\Gamma ) : D^\prime \geq 0 \text{ and } D^\prime \sim D\},$

i.e., $|D|$ is the set of all effective divisors linearly equivalent to $D$ . Note that if $D_1 \sim D_2$ , then $|D_1| = |D_2|$ . We note also that if $\text{deg}(D)<0$ , then $|D|$ must be empty.

Sage can be used to compute the linear system of any divisor on a graph.

def linear_system(D, Gamma):
    """
    Returns linear system attached to the divisor D.

    EXAMPLES:
        sage: Gamma2 = graphs.CubeGraph(2)
        sage: Gamma1 = Gamma2.subgraph(vertices = ['00', '01'], edges = [('00', '01')])
        sage: f = [['00', '01', '10', '11'], ['00', '01', '00', '01']]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: PhiV = matrix_of_graph_morphism_vertices(Gamma1, Gamma2, f); PhiV
        [1 0 1 0]
        [0 1 0 1]
        sage: D = vector([1,0,0,1])
        sage: PhiV*D
        (1, 1)
        sage: linear_system(PhiV*D, Gamma1)
        [(2, 0), (1, 1), (0, 2)]
        sage: linear_system(D, Gamma2)
        [(0, 2, 0, 0), (0, 0, 2, 0), (1, 0, 0, 1)]
        sage: [PhiV*x for x in linear_system(D, Gamma2)]
        [(0, 2), (2, 0), (1, 1)]

    """
    Q = Gamma.laplacian_matrix()
    CS = Q.column_space()
    N = len(D.list())
    d = sum(D.list())
    #print d
    lin_sys = []
    if d < 0:
        return lin_sys
    if (d == 0) and (D in CS):
        lin_sys = [CS(0)]
        return lin_sys
    elif (d == 0):
        return lin_sys
    S = IntegerModRing(d+1)^N
    V = QQ^N
    for v in S:
        v = V(v)
        #print D-v,v,D
        if D-v in CS:
            lin_sys.append(v)
    return lin_sys

Paley graphs in Sage

Posted on 2013/03/06 by wdjoyner

Let $q$ be a prime power such that $q\equiv 1 \pmod 4$ . Note that this implies that the unique finite field of order $q$ , $GF(q)$ , has a square root of $-1$ . Now let $V=GF(q)$ and

$E = \{(a,b)\in V\times V\ |\ a-b\in GF(q)^2\}.$
By hypothesis, $(a,b)\in E$ if and only if $(b,a)\in E$ . By definition $G = (V, E)$ is the Paley graph of order $q$ .

Paley was a brilliant mathematician who died tragically at the age of 26. Paley graphs are one of the many spin-offs of his work. The following facts are known about them.

The eigenvalues of Paley graphs are $\frac{q-1}{2}$ (with multiplicity $1$ ) and
$\frac{-1 \pm \sqrt{q}}{2}$ (both with multiplicity $\frac{q-1}{2}$ ).
It is known that a Paley graph is a Ramanujan graph.
It is known that the family of Paley graphs of prime order is a vertex expander graph family.
If $q=p^r$ , where $p$ is prime, then $Aut(G)$ has order $rq(q-1)/2$ .

Here is Sage code for the Paley graph (thanks to Chris Godsil, see [GB]):

def Paley(q):
    K = GF(q)
    return Graph([K, lambda i,j: i != j and (i-j).is_square()])

(Replace “K” by “ $K.\langle a\rangle$ ” above; I was having trouble rendering it in html.) Below is an example.

sage: X = Paley(13)
sage: X.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: X.is_vertex_transitive()
True
sage: X.degree_sequence()
[6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
sage: X.spectrum()
[6, 1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?]
sage: G = X.automorphism_group()
sage: G.cardinality()
78

We see that this Paley graph is regular of degree $6$ , it has only three distinct eigenvalues, and its automorphism group is order $13\cdot 12/2 = 78$ .

Here is an animation of this Paley graph:

The frames in this animation were constructed one-at-a-time by deleting an edge and plotting the new graph.

Here is an animation of the Paley graph of order $17$ :

The frames in this animation were constructed using a Python script:

X = Paley(17)
E = X.edges()
N = len(E)
EC = X.eulerian_circuit()
for i in range(N):
    X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%i))+".png")
    X.delete_edge(EC[i])
X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%N))+".png")

Instead of removing the frames “by hand” they are removed according to their occurrence in a Eulerian circuit of the graph.

Here is an animation of the Paley graph of order $29$ :

[GB] Chris Godsil and Rob Beezer, Explorations in Algebraic Graph Theory with Sage, 2012, in preparation.

Some remarks on monotone Boolean functions

Posted on 2012/09/01 by wdjoyner

This post summarizes some joint research with Charles Celerier, Caroline Melles, and David Phillips.

Let $f:GF(2)^n \to GF(2)$ be a Boolean function. (We identify $GF(2)$ with either the real numbers $\{0,1\}$ or the binary field ${\mathbb{Z}}/2{\mathbb{Z}}$ . Hopefully, the context makes it clear which one is used.)

Define a partial order $\leq$ on $GF(2)^n$ as follows: for each $v,w\in GF(2)^n$ , we say $v\leq w$ whenever we have $v_1 \leq w_1$ , $v_2 \leq w_2$ , …, $v_n \leq w_n$ . A Boolean function is called monotone (increasing) if whenever we have $v\leq w$ then we also have $f(v) \leq f(w)$ .

Note that if $f$ and $g$ are monotone then (a) $f+g+fg$ is also monotone, and (b) $\overline{\Omega_f}\cap \overline{\Omega_g}=\overline{\Omega_{fg}}$ . (Overline means bit-wise complement.)

Definition:
Let $f:GF(2)^n \to GF(2)$ be any monotone function. We say that $\Gamma\subset GF(2)^n$ is the least support of $f$ if $\Gamma$ consists of all vectors in $\Omega_f$ which are smallest in the partial ordering $\leq$ on $GF(2)^n$ . We say a subset $S$ of $GF(2)^n$ is admissible if for all $x,y\in S$ , ${\rm supp}(x)\not\subset {\rm supp}(y)$ and ${\rm supp}(y)\not\subset {\rm supp}(x)$

Monotone functions on $GF(2)^n$ are in a natural one-to-one correspondence with the collection of admissible sets.

Example:
Here is an example of a monotone function whose least support vectors are given by
$\Gamma =\{ (1,0,0,0), (0,1,1,0), (0,1,0,1), (0,0,1,1) \} \subset GF(2)^n,$
illustrated in the figure below.

The algebraic normal form is $x_0x_1x_2 + x_0x_1x_3 + x_0x_2x_3 + x_1x_2 + x_1x_3 + x_2x_3 + x_0$ .

The following result is due to Charles Celerier.

Theorem:
Let $f$ be a monotone function whose least support vectors are given by $\Gamma \subset GF(2)^n$ . Then
$f(x) = 1+\prod_{v\in\Gamma} (x^v+1).$

The following example is due to Caroline Melles.

Example:
Let $f$ be the monotone function whose least support is
$\Gamma = \{ (1,1,1,1,0,0),(1,1,0,0,1,1),(0,0,1,1,1,1)\}.$
Using the Theorem above, we obtain the compact algebraic form
$f(x_0,x_1,x_2,x_3,x_4,x_5) = x_0x_1x_2x_3 + x_0x_1x_4x_5 + x_2x_3x_4x_5 .$
This function is monotone yet has no vanishing Walsh-Hadamard transform values. To see this, we attach the file afsr.sage available from Celerier (https://github.com/celerier/oslo/), then run the following commands.

sage: V = GF(2)^(6)
sage: L = [V([1,1,0,0,1,1]),V([0,0,1,1,1,1]), V([1,1,1,1,0,0])]
sage: f = monotone_from_support(L)
sage: is_monotone(f)
True

These commands simply construct a Boolean function $f$ whose least support are the vectors in L. Next, we compute the Walsh-Hadamard transform of this using both the method built into Sage’s sage.crypto module, and the function in afsr.sage.

sage: f.walsh_hadamard_transform()
(-44, -12, -12, 12, -12, 4, 4, -4, -12, 4, 4, -4, 12, -4, -4, 4, -12, 4, 4, -4, 4, 4, 4, -4, 4, 4, 4, -4, -4, 
 -4, -4, 4, -12, 4, 4, -4, 4, 4, 4, -4, 4, 4, 4, -4, -4, -4, -4, 4, 12, -4, -4, 4, -4, -4, -4, 4, -4, -4, -4, 4, 4, 4, 4, -4)
sage: f.algebraic_normal_form()
x0*x1*x2*x3 + x0*x1*x4*x5 + x2*x3*x4*x5
sage: x0,x1,x2,x3,x4,x5 = var("x0,x1,x2,x3,x4,x5")
sage: g = x0*x1*x2*x3 + x0*x1*x4*x5 + x2*x3*x4*x5
sage: Omega = [v for v in V if g(x0=v[0], x1=v[1], x2=v[2], x3=v[3],
     x4=v[4], x5=v[5])0]
sage: len(Omega)
10
sage: g = lambda x: x[0]*x[1]*x[2]*x[3] + x[0]*x[1]*x[4]*x[5] + x[2]*x[3]*x[4]*x[5]
sage: [walsh_transform(g,a) for a in V]
[44, 12, 12, -12, 12, -4, -4, 4, 12, -4, -4, 4, -12, 4, 4, -4, 12, -4, -4, 4, -4, -4, -4, 4, -4, -4, -4, 4, 4, 
 4, 4, -4, 12, -4, -4, 4, -4, -4, -4, 4, -4, -4, -4, 4, 4, 4, 4, -4, -12, 4, 4, -4, 4, 4, 4, -4, 4, 4, 4, -4, -4, -4, -4, 4]

(Note: the Walsh transform method in the BooleanFunction class in Sage differs by a sign from the standard definition.) This verifies that there are no values of the Walsh-Hadamard transform which are $0$ .

More details can be found in the paper listed here. I end with two questions (which I think should be answered “no”).

Question: Are there any monotone functions $f$ of $n$ variables having no free variables of degree $\leq n/2$ ?

Question: Are there any monotone functions $f$ of most than two variables which are bent?

Review of R. Beezer’s “A first course in linear algebra”

Posted on 2012/08/01 by wdjoyner

The book this review will look at, A first course in linear algebra by Robert Beezer, is remarkable for several reasons. First, it is free and you can download it from its website. Second, if you have a somewhat different approach to teaching linear algebra and prefer a slightly modified version, you are in luck: Beezer’s book is open source, so you can download the LaTeX source, change it to suit your needs (delete some material and/or add some of your own), and then redistribute your revised version according to the stipulations of the GNU Free Documentation License. If are unsure how to do this, or have any book-related question, you’re in luck again – there is a googlegroups email list to help you out. Finally, it is huge. The version I will review (version 2.0) is not the most recent (at the time of this writing, version 3.0 is almost out) but still the book was about 750 pages (the most recent version is over 1000 pages!). There is plenty of material to fit almost any syllabus.

Cover of Beezer’s linear algebra book

Speaking of material, what does this book actually cover? The chapters are:

[SLE]
Systems of linear equations
[V]
Vectors
[M]
Matrices
[VS]
Vector spaces
[D]
Determinants
[E]
Eigenvalues
[LT]
Linear transformations
[R]
Representations

There are also several appendices (for example, one on Sage a free and open source mathematics software program with very strong linear algebra computational capabilities [S]).

Note the unusual labeling of the chapters – no numbering is used for the chapters, instead capital Roman letters are used (an acronym, E for Eigenvalues, for example). The same indexing method is used for the definitions, examples and theorems as well. How do you refer to a result with this method of labeling? The way cross-referencing works in this book is that each reference is followed by the page number that the reference can be found. For example the theorem that says the adjoint of a matrix respects matrix addition would be referred to as “Theorem AMA [175]” since it can be found on page 175 and is written there as

Theorem AMA (Adjoint and Matrix Addition):
Suppose $A$ and $B$ are matrices of the same size. Then $(A+B)^T = A^T + B^T$ .

One advantage to this method of indexing is that if, for example, replace the chapter on Vectors with your own chapter then recompile the LaTeX, the theorem on adjoint and matrix addition is still “Theorem AMA,” even though its page number has probably changed. Although this indexing method with the page numbers does make the various results pretty easy to find, all the labeled results are also conveniently listed in the index. Moreover, in the the electronic versions (PDF, XML, jsMath) of the book, all of this cross-referencing is available as hyperlinks.

Each chapter of course is composed of many sections. Each section not only has plentiful detailed examples and its own list of “reading questions” to see if you have understood the material, but also a list of exercises with solutions. More precisely, some exercises are marked as computational (e.g., solve the following system of linear equations), some as theoretical (e.g., prove that if a vector v is in the kernel of a matrix then any scalar times v is also in the kernel), and some as “mixed” (often of the form: find an example of a matrix with property X). As far as I could see, every computational exercise was accompanied by a more-or-less complete solution. However, the other types of problems usually (not always) either had no solution provided or only a sketch of one. A rough count would be about 500 exercises and 350 of them have solutions.

The book is very well-written and at a level similar to Anton’s popular book \cite{A}. What topics are actually covered by this book? There is a detailed table of contents of (a) the chapters, sections and subsections, (b) the definitions, (c) the theorems, (d) the examples, and (e) a 30 page index.

The first chapter on systems of linear equations discusses solving systems of linear equations, as well as classifying them (consistent, homogeneous, and so on), row reduction, and the matrix form of a system of linear equations. This chapter, in my opinion, approaches things in the right way by stressing the importance of the method of row reduction/Gauss elimination. Very detailed proofs are also presented. For most students, the more details the better, so this is also a strong plus.

The second chapter on vectors starts with the basics on vector operations. This is followed by four sections on linear spans and linear independence. This is a challenging topic for students but the book does a very though job. The final section discusses orthogonality, inner products and the Gram-Schmidt procedure.

The chapter on matrices comprises six sections. After several sections explaining the usual details on matrix operations (such as transposes and adjoints) and matrix arithmetic (such as addition and multiplication), the discussion turns to matrix inverses. Two sections are spent with this topic. The last two sections deal with row and column spaces and their basic properties.

The chapter on vector spaces begins with two sections on the basic definitions and properties of vector spaces and subspaces. The next two sections are on linear independence (again), spanning sets (again), and vector space bases. With the difficulty that linear independence and spanning sets present to many students, this reappearance of these topics provides excellent reinforcement. The last sections of the chapter are on the dimension properties of the row-span and column span of a matrix. For example, what Gilbert Strang calls the Fundamental Theorem of Linear Algebra, the so-called “rank plus nullity theorem,” is in one of these sections (see Theorem RPNC in section RNM on page 323).

After a relatively short 24-page chapter on the determinant and its properties, the book continues with the Eigenvalues chapter. This chapter discusses eigenvalues, eigenvectors, diagonalization, and similarity. Topics such as the Jordan canonical form are discussed in a later chapter.

The chapter on linear transformations has separate sections on injective maps, surjective maps, and invertible maps, resp.. This chapter has a wealth of examples to help guide the student through these relatively abstract concepts.

The final chapter is also the most difficult for the student. This is the chapter titled Representations, concerning topics such as the matrix representation of a linear transformation and the properties of this representation. Other topics, such as the Cayley-Hamilton Theorem, the Jordan canonical form, and diagonalization of orthogonal matrices appear in this chapter as well. In version 2.0, some sections of this chapter were less complete than those in other chapters.

Finally, I would also like to mention that the author has done a considerable amount of work on the use of Sage in the classroom. For example, he has added to the Sage code and documentation and has written the following “quick reference sheets” summarizing the most useful linear algebra commands in Sage. For more information, see his website http://linear.ups.edu/sage-fcla.html.

An excellent book written by an experienced teacher. Highly recommended.

Bibliography:

[A] H. Anton, Elementary linear algebra, 8th edition, Wiley, 2000.

[B] Robert Beezer’s Linear Algebra website, http://linear.ups.edu/.

[S] W. Stein, Sage: Open Source Mathematical Software (Version 5.2), The Sage~Group, 2012, http://www.sagemath.org

Sestinas and Sage

Posted on 2012/04/02 by wdjoyner

According to [1], a sestina is a highly structured poem consisting of six six-line stanzas followed by a tercet (called its envoy or tornada), for a total of thirty-nine lines. The same set of six words ends the lines of each of the six-line stanzas, but in a shuffled order each time. The shuffle used is very similar to the Mongean shuffle.

Define $f_n(k) = 2k$ , if k <= n/2 and $f_n(k) = 2n+1-2k$ , if $k > n/2.$ Let $p = (p_1,...,p_n) \in S_n$ , where $p_j = f_n(p_{j-1})$ and $S_n$ is the symmetric group of order $n$ . From [2], we have the following result.

Theorem: If p is an n-cycle then 2n+1 is a prime.

Call such a prime a “sestina prime”. Which primes are sestina primes?

Here is Python/Sage code for this permutation:


def sestina(n):
    """
    Computes the element of the symmetric group S_n associated to the shuffle above. 
  
    EXAMPLES: 
        sage: sestina(4)
        (1,2,4) 
        sage: sestina(6)
        (1,2,4,5,3,6)
        sage: sestina(8)
        (1,2,4,8)(3,6,5,7)
        sage: sestina(10)
        (1,2,4,8,5,10)(3,6,9)
        sage: sestina(12)
        (1,2,4,8,9,7,11,3,6,12)(5,10)
        sage: sestina(14)
        (1,2,4,8,13,3,6,12,5,10,9,11,7,14) 
        sage: sestina(16)
        (1,2,4,8,16)(3,6,12,9,15)(5,10,13,7,14)
        sage: sestina(18)
        (1,2,4,8,16,5,10,17,3,6,12,13,11,15,7,14,9,18)
        sage: sestina(20) (1,2,4,8,16,9,18,5,10,20)(3,6,12,17,7,14,13,15,11,19) 
        sage: sestina(22) (1,2,4,8,16,13,19,7,14,17,11,22)(3,6,12,21)(5,10,20)(9,18) 

    """ 
    def fcn(k, n):
        if k<=int(n/2): 
            return 2*k 
        else: 
            return 2*n+1-2*k 
    L = [fcn(k,n) for k in range(1,n+1)] 
    G = SymmetricGroup(n) 
    return G(L)

And here is an example due to Ezra Pound [3]:

                                  I

Damn it all! all this our South stinks peace.
You whoreson dog, Papiols, come! Let’s to music!
I have no life save when the swords clash.
But ah! when I see the standards gold, vair, purple, opposing
And the broad fields beneath them turn crimson,
Then howl I my heart nigh mad with rejoicing.

                                     II

In hot summer have I great rejoicing
When the tempests kill the earth’s foul peace,
And the light’nings from black heav’n flash crimson,
And the fierce thunders roar me their music
And the winds shriek through the clouds mad, opposing,
And through all the riven skies God’s swords clash.

                                     III

Hell grant soon we hear again the swords clash!
And the shrill neighs of destriers in battle rejoicing,
Spiked breast to spiked breast opposing!
Better one hour’s stour than a year’s peace
With fat boards, bawds, wine and frail music!
Bah! there’s no wine like the blood’s crimson!

                                     IV

And I love to see the sun rise blood-crimson.
And I watch his spears through the dark clash
And it fills all my heart with rejoicing
And prys wide my mouth with fast music
When I see him so scorn and defy peace,
His lone might ’gainst all darkness opposing.

                                     V

The man who fears war and squats opposing
My words for stour, hath no blood of crimson
But is fit only to rot in womanish peace
Far from where worth’s won and the swords clash
For the death of such sluts I go rejoicing;
Yea, I fill all the air with my music.

                                     VI

Papiols, Papiols, to the music!
There’s no sound like to swords swords opposing,
No cry like the battle’s rejoicing
When our elbows and swords drip the crimson
And our charges ’gainst “The Leopard’s” rush clash.
May God damn for ever all who cry “Peace!”

                                     VII

And let the music of the swords make them crimson
Hell grant soon we hear again the swords clash!
Hell blot black for always the thought “Peace”!

References:

[1] http://en.wikipedia.org/wiki/Sestina

[2] Richard Dore and Anton Geraschenko,”Sestinas and Primes” posted to http://stacky.net/wiki/index.php?title=Course_notes, and http://math.berkeley.edu/~anton/written/sestina.pdf

[3] Ezra Pound, “Sestina: Altaforte” (1909), (originally published int the English Review, 1909)

[4] John Bullitt, N. J. A. Sloane and J. H. Conway , http://oeis.org/A019567

Yet Another Mathblog

Tag Archives: sage