Page 155 - 35Linear Algebra

7.6 Review Problems 155

Notice that −1 = 1, since 1+1 = 0. Therefore, we can apply all of the linear
algebra we have learned thus far to matrices with Z 2 entries. A matrix with
entries in Z 2 is sometimes called a bit matrix.
 
1 0 1
Example 95  0 1 1  is an invertible matrix over Z 2 ;
1 1 1
−1
   
1 0 1 0 1 1
 0 1 1  =  1 0 1  .
1 1 1 1 1 1
This can be easily verified by multiplying:
     
1 0 1 0 1 1 1 0 0
0 1 1 1 0 1 = 0 1 0
     
1 1 1 1 1 1 0 0 1

Application: Cryptography A very simple way to hide information is to use a sub-
stitution cipher, in which the alphabet is permuted and each letter in a message is
systematically exchanged for another. For example, the ROT-13 cypher just exchanges
a letter with the letter thirteen places before or after it in the alphabet. For example,
HELLO becomes URYYB. Applying the algorithm again decodes the message, turning
URYYB back into HELLO. Substitution ciphers are easy to break, but the basic idea
can be extended to create cryptographic systems that are practically uncrackable. For
example, a one-time pad is a system that uses a different substitution for each letter
in the message. So long as a particular set of substitutions is not used on more than
one message, the one-time pad is unbreakable.
English characters are often stored in computers in the ASCII format. In ASCII,
a single character is represented by a string of eight bits, which we can consider as a
8
8
vector in Z (which is like vectors in R , where the entries are zeros and ones). One
2
way to create a substitution cipher, then, is to choose an 8 × 8 invertible bit matrix
M, and multiply each letter of the message by M. Then to decode the message, each
string of eight characters would be multiplied by M −1 .
To make the message a bit tougher to decode, one could consider pairs (or longer
16
sequences) of letters as a single vector in Z 2 (or a higher-dimensional space), and
then use an appropriately-sized invertible matrix. For more on cryptography, see “The
Code Book,” by Simon Singh (1999, Doubleday).

7.6 Review Problems

Webwork: Reading Problems 6 , 7

155