Up: Class 10, Math 696
Next: Homework
Previous: Goals

Activities for Class 10

Classroom discussion

The first part of class is a continuation of the discussion of techniques for making effective oral mathematical presentations.

Computer activities

Today you are going to implement a simple cipher in Maple. This exercise gives practice with matrices, string handling, and programming in Maple.

Matrix operations in Maple

You all know and love systems of simultaneous linear equations. We have seen that one way to solve linear systems is via Maple's solve command. For example, if you set

eqns := {u+v+w=1, 3*u+v=3, u-2*v-w=0};

then you can solve(eqns); to get numerical values for the variables u, v, and w.

Matrices are often an efficient way to handle linear systems. In the previous class, we used matrices in a casual way, and you learned that Maple has a linear algebra package that can be loaded via the with(linalg): command. (Do not be concerned if loading this package produces a message from Maple about new definitions for norm and trace. This message is normal.)

Maple views a matrix as a list of lists. Therefore you can define a matrix with the name A via A:=matrix([[9,13,17],[14,18,22]]);. Alternatively, you can specify the number of rows and the number of columns and give a single list (which Maple will then break up into the appropriate rows). Thus, another way to specify the above matrix is A:=matrix(2,3,[9,13,17,14,18,22]);. Still another way to define a matrix is to specify a formula for the entries in terms of the row and column indices. For example, the above matrix can be generated via A:=matrix(2,3,(i,j)->5*i+4*j);.

After you have defined the above matrix A, what happens if you ask Maple for the value A;? If you want to see the entries displayed, you must ask Maple for matrix evaluation via evalm(A);.

Maple knows the standard matrix operations of addition, subtraction, multiplication, scalar multiplication, forming inverses, and exponentiation. For the 2x3 matrix A that you defined above, try evalm(A+A); and evalm(4*A); for example.

Maple uses the asterisk * for scalar multiplication and the symbol &* for matrix multiplication. Since A is a 2x3 matrix, it is not possible to multiply A by itself. Does Maple complain if you ask it for A^2;? Try it. Now try evalm(A^2);.

The above matrix A is a 2x3 matrix, so its transpose is a 3x2 matrix. Therefore you can multiply A by its transpose (in either order). Try evalm(A&*transpose(A)); to evaluate this product. An alternate syntax that computes the same result is multiply(A, transpose(A));. Do you get the same answer if you form the product in the other order via multiply(transpose(A), A);?

Define B:=evalm(A&*transpose(A));. What does Maple do if you ask for 1/B;? How about B^(-1);? What about evalm(1/B);?

You can also use inverse(B); to display the inverse of a matrix. What happens if you ask for inverse(transpose(A)&*A);? Can you now predict what det(transpose(A)&*A); will return?

Maple can perform operations on the individual entries of a matrix. Try map(sin,A); map(evalf,"); for example. You can also refer to individual entries of a matrix. For example, A[2,3]; picks out the entry of A that is in the second row and the third column.

Exercise

Try the following Maple commands.

Digits:=3;
C:=hilbert(4):
inverse(map(evalf,C));
inverse(C);

These commands compute (a) the inverse of a three-digit numerical approximation to the 4x4 Hilbert matrix and (b) the exact inverse of the 4x4 Hilbert matrix. Do you see any resemblance between the two inverses? Does this explain the terminology ``ill-conditioned''?

A simple cipher

As an application of matrices, let's implement a simple cipher. In doing this, we will also see an example of a Maple program.

At this point, it would be a good idea to reinitialize your Maple session by executing the command restart;. (Then reload the linear algebra package via with(linalg):.) We are going to be using the alphabetic characters as names for themselves, so if you have A and B defined as matrices, it may cause problems.

The idea behind the cipher is first to translate letters into numbers via A->1, B->2, and so on. After translating a message into a string of numbers, encode the message in the following way. Break the string of numbers into blocks of five, view these blocks as the rows of a matrix, and multiply this matrix on the right by a specified 5x5 matrix. Then translate the numbers back into letters. The message is now unintelligible, but if the recipient of the message knows the matrix (and hence the inverse matrix), then the recipient can recover the original plain text.

To make the procedure a little more sophisticated, we will include some punctuation marks as well as both uppercase and lowercase letters, and we will do the arithmetic modulo 59.

Here is the 5x5 matrix we will use.

     [ 49  19  17  13  19 ]
     [                    ]
     [ 33  32  30  21  13 ]
     [                    ]
     [  7  30  27   6  40 ]
     [                    ]
     [ 12   9  46  31  20 ]
     [                    ]
     [ 43  52   6  57  36 ]

I generated this random matrix via map(x->modp(x,59), randmatrix(5,5));.

Here is a format for the matrix that you can cut and paste into your Maple session.

Mtrx:=matrix([[49, 19, 17, 13, 19], [33, 32, 30, 21, 13], [7, 30, 27, 6, 40], [12, 9, 46, 31, 20], [43, 52, 6, 57, 36]]);

I generated this list format for the matrix via convert(",listlist);.

Your task is to follow the hints to decode this message:

kUByDQ?PGVsKkkKUEWu.prt?FG:KROKhtC. sK;QImDhdV;VDIDlRpFeRR::wZYinVkqJrEhDH!;,EUwSmfczSdxqbUXaD;D,EgLArQN 

Caution. There happen to be exactly two spaces in the message: one space in the middle, and one space at the end. When you cut and paste the cipher text into your Maple session, be careful not to lose the two spaces, and be careful to avoid introducing spurious newline characters. The matrix form of the message looks like this:

[k    U    B    y    D]
[                     ]
[Q    ?    P    G    V]
[                     ]
[s    K    k    k    K]
[                     ]
[U    E    W    u    .]
[                     ]
[p    r    t    ?    F]
[                     ]
[G    :    K    R    O]
[                     ]
[K    h    t    C    .]
[                     ]
[     s    K    ;    Q]
[                     ]
[I    m    D    h    d]
[                     ]
[V    ;    V    D    I]
[                     ]
[D    l    R    p    F]
[                     ]
[e    R    R    :    :]
[                     ]
[w    Z    Y    i    n]
[                     ]
[V    k    q    J    r]
[                     ]
[E    h    D    H    !]
[                     ]
[;    ,    E    U    w]
[                     ]
[S    m    f    c    z]
[                     ]
[S    d    x    q    b]
[                     ]
[U    X    a    D    ;]
[                     ]
[D    ,    E    g    L]
[                     ]
[A    r    Q    N     ]

To create the secret message, I first defined a list of the alphabetic characters. This requires a little care. First of all, Maple thinks that I represents the square root of minus one, so I had to undo this convention by aliasing I to itself. Also, I gave punctuation characters symbolic names to avoid confusion (since Maple uses some punctuation characters---such as the semicolon---for special purposes). Here are my definitions, which you will need to copy into your Maple session.

space:=` `: period:=`.`: comma:=`,`: semicolon:=`;`: colon:=`:`: bang:=`!`: query:=`?`: alias(I=I);
Alphabet:=[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z, space, period, comma, semicolon, colon, bang, query];

Now if you ask Maple for Alphabet[28];, for example, you should get the 28th element of the list Alphabet, which is the lower case letter b.

To convert numbers into letters, define a function NumToAlph as follows.

NumToAlph := Number -> Alphabet[ modp(Number-1,59) +1 ];

The reason for adding and subtracting 1 in this definition is that modp returns values between 0 and 58, while the index parameter for the list Alphabet runs from 1 to 59. Test this definition by checking NumToAlph(5); and NumToAlph(50); for example.

You can define an inverse function AlphToNum that converts letters into numbers by executing the following do loop.

for counter from 1 to 59 do
AlphToNum(Alphabet[counter]):=counter:
od:

Notice that there is no semicolon after the do. (Usually one writes a do loop in the form ``for i from 1 to n do,'' but in our situation single letters are reserved as names of alphabetic characters, so I named the counter in the loop ``counter'' instead of ``i.'')

Try AlphToNum(a); and AlphToNum(` `); to confirm that the function is defined correctly.

If you have a message written as a list of alphabetic characters, you can convert it into a list of numbers via map(AlphToNum,CharacterList);. Try converting the list [H,e,l,l,o,space,w,o,r,l,d] for example.

Conversely, if you have a list of numbers, you can convert it into a list of letters via map(NumToAlph,NumberList);. Try converting the list [22, 31, 44, 51, 53, 33, 41, 41, 30, 58] for example. You should get a list of letters inside square brackets. To convert this list into words, try cat(op(")); to concatenate the letters in the list.

One problem I had to solve before putting my secret message into numeric form was how to change a string of characters into a comma-separated list. (Of course, I could have typed in all the commas, but that would have been tedious.) I wrote the following little Maple procedure.

MessageToList:=proc(Message)
 local cntr,MessageList;
   MessageList := NULL;
   for cntr to length(Message) do
     MessageList := MessageList,substring(Message,cntr .. cntr);
   od;
 MessageList := [MessageList];
end;

Here is a line-by-line explanation of this procedure.

MessageToList:=proc(Message)
This defines a procedure (a function) named MessageToList that takes one argument named Message.
local cntr,MessageList;
The procedure uses two internal variables, which are declared to be local to the procedure. The variable cntr is going to be a counter for a loop, and the variable MessageList is going to hold the comma-separated list.
MessageList := NULL;
This initializes the variable MessageList to be an empty string.
for cntr to length(Message) do
This starts a loop. By default, the counter cntr starts at 1, and it is incremented by one unit each time through the loop. The loop terminates when the counter reaches the length of the string Message (the string that is the input to the procedure).
MessageList := MessageList,substring(Message,cntr .. cntr);
Here the substring function picks out of Message the part starting at the position of the counter and ending at the position of the counter. In other words, it picks out a single character at the position of the counter. Then MessageList is replaced by itself with a comma and this character appended.
od;
This is the word do backwards: it signals the end of the statements that are included in the do loop.
MessageList := [MessageList];
This redefines MessageList to be itself enclosed in brackets, so that it is now a Maple list structure. This list is the output of the procedure.
end;
This marks the end of the procedure.

In summary, this procedure takes one argument Message and runs a loop that picks out each one-character substring at position cntr and appends it to a comma-separated list. The procedure returns that list. The procedure uses two local variables: cntr is the counter for the loop, and MessageList holds the current value of the comma-separated list of characters.

Now executing the Maple command

MessageToList(`Three can keep a secret, if two of them are dead. Benjamin Franklin`);

produces the output

[T, h, r, e, e, , c, a, n, , k, e, e, p, , a, , s, e, c, r, e, t, ,, , i, f, , t, w, o, , o, f, , t, h, e, m, , a, r, e, , d, e, a, d, ., , B, e, n, j, a, m, i, n, , F, r, a, n, k , l, i, n]

Notice the backquotes ` that I used to convert the text into a Maple string.

Now see if you can decode the secret message. You need to convert the message into numeric form, change the list of numbers into a matrix, multiply the matrix on the right by the inverse of Mtrx, and then convert back to a string of alphabetic characters.

Exercise

If you succeeded in decoding the message, then try using Mtrx to encipher your own message. Send your message by e-mail to your neighbor for decoding.


Up: Class 10, Math 696
Next: Homework
Previous: Goals

Created Oct 13, 1996. Last modified Nov 6, 1996 by boas@tamu.edu.
URL: /~harold.boas/courses/696-96c/class10/activities.html
Copyright © 1996 by Harold P. Boas. All rights reserved.