The first part of class is a continuation of the discussion of techniques for making effective oral mathematical presentations.
Today you are going to implement a simple cipher in Maple. This exercise gives practice with matrices, string handling, and programming 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.
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''?
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)
MessageToList that takes one
argument named Message.
local cntr,MessageList;
cntr is going to be a counter for a loop, and
the variable MessageList is going to hold the
comma-separated list.
MessageList := NULL;
MessageList to
be an empty string.
for cntr to length(Message) do
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);
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;
do backwards: it signals the
end of the statements that are included in the
do loop.
MessageList := [MessageList];
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;
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.
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.
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.