Learning Objectives
In this section, we will learn to find the inverse of a matrix, if it exists. Later, we will use matrix inverses to solve linear systems. In this section you will learn to
- encode a message using matrix multiplication.
- decode a coded message using the matrix inverse and matrix multiplication
Encryption dates back approximately 4000 years. Historical accounts indicate that the Chinese, Egyptians, Indian, and Greek encrypted messages in some way for various purposes. One famous encryption scheme is called the Caesar cipher, also called a substitution cipher, used by Julius Caesar, involved shifting letters in the alphabet, such as replacing A by C, B by D, C by E, etc, to encode a message. Substitution ciphers are too simple in design to be considered secure today.
In the middle ages, European nations began to use encryption. A variety of encryption methods were used in the US from the Revolutionary War, through the Civil War, and on into to modern times.
Applications of mathematical theory and methods to encryption became widespread in military usage in the 20th century. The military would encode messages before sending and the recipient would decode the message, in order to send information about military operations in a manner that kept the information safe if the message was intercepted. In World War II, encryption played an important role, as both Allied and Axis powers sent encrypted messages and devoted significant resources to strengthening their own encryption while also trying to break the opposition’s encryption.
In this section we will examine a method of encryption that uses matrix multiplication and matrix inverses. This method, known as the Hill Algorithm, was created by Lester Hill, a mathematics professor who taught at several US colleges and also was involved with military encryption. The Hill algorithm marks the introduction of modern mathematical theory and methods to the field of cryptography.
These days, the Hill Algorithm is not considered a secure encryption method; it is relatively easy to break with modern technology. However, in 1929 when it was developed, modern computing technology did not exist. This method, which we can handle easily with today’s technology, was too cumbersome to use with hand calculations. Hill devised a mechanical encryption machine to help with the mathematics; his machine relied on gears and levers, but never gained widespread use. Hill’s method was considered sophisticated and powerful in its time and is one of many methods influencing techniques in use today. Other encryption methods at that time also utilized special coding machines. Alan Turing, a computer scientist pioneer in the field of artificial intelligence, invented a machine that was able to decrypt messages encrypted by the German Enigma machine, helping to turn the tide of World War II.
With the advent of the computer age and internet communication, the use of encryption has become widespread in communication and in keeping private data secure; it is no longer limited to military uses. Modern encryption methods are more complicated, often combining several steps or methods to encrypt data to keep it more secure and harder to break. Some modern methods make use of matrices as part of the encryption and decryption process; other fields of mathematics such as number theory play a large role in modern cryptography.
To use matrices in encoding and decoding secret messages, our procedure is as follows.
We first convert the secret message into a string of numbers by arbitrarily assigning a number to each letter of the message. Next we convert this string of numbers into a new set of numbers by multiplying the string by a square matrix of our choice that has an inverse. This new set of numbers represents the coded message.
To decode the message, we take the string of coded numbers and multiply it by the inverse of the matrix to get the original string of numbers. Finally, by associating the numbers with their corresponding letters, we obtain the original message.
In this section, we will use the correspondence shown below where letters A to Z correspond to the numbers 1 to 26, a space is represented by the number 27, and punctuation is ignored.
\[\begin{array}{cccccccccccccc}
\mathrm{A} & \mathrm{B} & \mathrm{C} & \mathrm{D} & \mathrm{E} & \mathrm{F} & \mathrm{G} & \mathrm{H} & \mathrm{I} & \mathrm{J} & \mathrm{K} & \mathrm{L} & \mathrm{M} \\
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\
\hline \mathrm{N} & \mathrm{O} & \mathrm{P} & \mathrm{Q} & \mathrm{R} & \mathrm{S} & \mathrm{T} & \mathrm{U} & \mathrm{V} & \mathrm{W} & \mathrm{X} & \mathrm{Y} & \mathrm{Z} \\
14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26
\end{array} \nonumber \]
Example \(\PageIndex{1}\)
Use matrix \(A=\left[\begin{array}{ll}
1 & 2 \\
1 & 3
\end{array}\right]\) to encode the message: ATTACK NOW!
Solution
We divide the letters of the message into groups of two.
\[\begin{array}{lllll}\text { AT } & \text { TA } & \text { CK } & \text { -N } & \text { OW }\end{array} \nonumber \]
We assign the numbers to these letters from the above table, and convert each pair of numbers into \(2 \times 1\) matrices. In the case where a single letter is left over on the end, a space is added to make it into a pair.
\[\left[\begin{array}{c}
\mathrm{A} \\
\mathrm{T}
\end{array}\right]=\left[\begin{array}{c}
1 \\
20
\end{array}\right] \quad\left[\begin{array}{l}
\mathrm{T} \\
\mathrm{A}
\end{array}\right]=\left[\begin{array}{c}
20 \\
1
\end{array}\right] \quad\left[\begin{array}{l}
\mathrm{C} \\
\mathrm{K}
\end{array}\right]=\left[\begin{array}{l}
3 \\
11
\end{array}\right] \nonumber \]
\[\left[\begin{array}{c}
- \\
\mathrm{N}
\end{array}\right]=\left[\begin{array}{l}
27 \\
14
\end{array}\right] \quad\left[\begin{array}{l}
\mathrm{O} \\
\mathrm{W}
\end{array}\right]=\left[\begin{array}{l}
15 \\
23
\end{array}\right] \nonumber \]
So at this stage, our message expressed as \(2 \times 1\) matrices is as follows.
\[\left[\begin{array}{c}
1 \\
20
\end{array}\right]\left[\begin{array}{c}
20 \\
1
\end{array}\right]\left[\begin{array}{c}
3 \\
11
\end{array}\right]\left[\begin{array}{c}
27 \\
14
\end{array}\right]\left[\begin{array}{c}
15 \\
23
\end{array}\right] \quad \bf{(I)} \nonumber \]
Now to encode, we multiply, on the left, each matrix of our message by the matrix \(A\). For example, the product of \(A\) with our first matrix is: \(\left[\begin{array}{ll}
1 & 2 \\
1 & 3
\end{array}\right]\left[\begin{array}{c}
1 \\
20
\end{array}\right]=\left[\begin{array}{l}
41 \\
61
\end{array}\right]\)
And the product of \(A\) with our second matrix is: \(\left[\begin{array}{ll}
1 & 2 \\
1 & 3
\end{array}\right]\left[\begin{array}{l}
20 \\
1
\end{array}\right]=\left[\begin{array}{l}
22 \\
23
\end{array}\right]\)
Multiplying each matrix in \(\bf{(I)}\) by matrix \(A\), in turn, gives the desired coded message:
\[\left[\begin{array}{l}
41 \\
61
\end{array}\right]\left[\begin{array}{l}
22 \\
23
\end{array}\right]\left[\begin{array}{l}
25 \\
36
\end{array}\right]\left[\begin{array}{l}
55 \\
69
\end{array}\right]\left[\begin{array}{l}
61 \\
84
\end{array}\right] \nonumber \]
Example \(\PageIndex{2}\)
Decode the following message that was encoded using matrix \(A=\left[\begin{array}{ll}
1 & 2 \\
1 & 3
\end{array}\right]\).
\[\left[\begin{array}{l}
21 \\
26
\end{array}\right]\left[\begin{array}{l}
37 \\
53
\end{array}\right]\left[\begin{array}{l}
45 \\
54
\end{array}\right]\left[\begin{array}{c}
74 \\
101
\end{array}\right]\left[\begin{array}{l}
53 \\
69
\end{array}\right] \quad(\bf { II }) \nonumber \]
Solution
Since this message was encoded by multiplying by the matrix \(A\) in Example \(\PageIndex{1}\), we decode this message by first multiplying each matrix, on the left, by the inverse of matrix \(A\) given below.
\[A^{-1}=\left[\begin{array}{cc}
3 & -2 \\
-1 & 1
\end{array}\right] \nonumber \]
For example: \(\left[\begin{array}{cc}
3 & -2 \\
-1 & 1
\end{array}\right]\left[\begin{array}{c}
21 \\
26
\end{array}\right]=\left[\begin{array}{c}
11 \\
5
\end{array}\right]\)
By multiplying each of the matrices in \(\bf{(II)}\) by the matrix \(A^{-1}\), we get the following.
\[\left[\begin{array}{c}
11 \\
5
\end{array}\right]\left[\begin{array}{c}
5 \\
16
\end{array}\right]\left[\begin{array}{c}
27 \\
9
\end{array}\right]\left[\begin{array}{c}
20 \\
27
\end{array}\right]\left[\begin{array}{c}
21 \\
16
\end{array}\right] \nonumber \]
Finally, by associating the numbers with their corresponding letters, we obtain:
\[\left[\begin{array}{l}
\mathrm{K} \\
\mathrm{E}
\end{array}\right]\left[\begin{array}{l}
\mathrm{E} \\
\mathrm{P}
\end{array}\right]\left[\begin{array}{l}
- \\
\mathrm{I}
\end{array}\right]\left[\begin{array}{l}
\mathrm{T} \\
-
\end{array}\right]\left[\begin{array}{l}
\mathrm{U} \\
\mathrm{P}
\end{array}\right] \nonumber \]
And the message reads: KEEP IT UP.
Now suppose we wanted to use a \(3 \times 3\) matrix to encode a message, then instead of dividing the letters into groups of two, we would divide them into groups of three.
Example \(\PageIndex{3}\)
Using the matrix \(B=\left[\begin{array}{ccc}
1 & 1 & -1 \\
1 & 0 & 1 \\
2 & 1 & 1
\end{array}\right] \nonumber\), encode the message: ATTACK NOW!
Solution
We divide the letters of the message into groups of three.
ATT ACK -NO W- -
Note that since the single letter "W" was left over on the end, we added two spaces to make it into a triplet.
Now we assign the numbers their corresponding letters from the table, and convert each triplet of numbers into \(3 \times 1\) matrices. We get
\[\left[\begin{array}{l}
\mathrm{A} \\
\mathrm{T} \\
\mathrm{T}
\end{array}\right]=\left[\begin{array}{c}
1 \\
20 \\
20
\end{array}\right]\left[\begin{array}{l}
\mathrm{A} \\
\mathrm{C} \\
\mathrm{K}
\end{array}\right]=\left[\begin{array}{l}
1 \\
3 \\
11
\end{array}\right]\left[\begin{array}{l}
- \\
\mathrm{N} \\
\mathrm{O}
\end{array}\right]=\left[\begin{array}{l}
27 \\
14 \\
15
\end{array}\right]\left[\begin{array}{l}
\mathrm{W} \\
- \\
-
\end{array}\right]=\left[\begin{array}{l}
23 \\
27 \\
27
\end{array}\right] \nonumber \]
So far we have,
\[\left[\begin{array}{c}
1 \\
20 \\
20
\end{array}\right]\left[\begin{array}{c}
1 \\
3 \\
11
\end{array}\right]\left[\begin{array}{c}
27 \\
14 \\
15
\end{array}\right]\left[\begin{array}{c}
23 \\
27 \\
27
\end{array}\right] \quad \bf{(III)} \nonumber \]
We multiply, on the left, each matrix of our message by the matrix \(B\). For example,
\[\left[\begin{array}{ccc}
1 & 1 & -1 \\
1 & 0 & 1 \\
2 & 1 & 1
\end{array}\right]\left[\begin{array}{c}
1 \\
20 \\
20
\end{array}\right]=\left[\begin{array}{c}
1 \\
21 \\
42
\end{array}\right] \nonumber \]
By multiplying each of the matrices in \(\bf{(III)}\) by the matrix \(B\), we get the desired coded message as follows:
\[\left[\begin{array}{c}
1 \\
21 \\
42
\end{array}\right]\left[\begin{array}{c}
-7 \\
12 \\
16
\end{array}\right]\left[\begin{array}{c}
26 \\
42 \\
83
\end{array}\right]\left[\begin{array}{c}
23 \\
50 \\
100
\end{array}\right] \nonumber \]
If we need to decode this message, we simply multiply the coded message by \(B^{-1}\), and associate the numbers with the corresponding letters of the alphabet.
In Example \(\PageIndex{4}\) we will demonstrate how to use matrix \(B^{-1}\) to decode an encrypted message.
Example \(\PageIndex{4}\)
Decode the following message that was encoded using matrix \(B=\left[\begin{array}{lll}
1 & 1 & -1 \\
1 & 0 & 1 \\
2 & 1 & 1
\end{array}\right] \).
\[\left[\begin{array}{l}
11 \\
20 \\
43
\end{array}\right]\left[\begin{array}{l}
25 \\
10 \\
41
\end{array}\right]\left[\begin{array}{l}
22 \\
14 \\
41
\end{array}\right] \quad \bf{(IV)} \nonumber \]
Solution
Since this message was encoded by multiplying by the matrix \(B\). We first determine inverse of \(B\).
\[\mathrm{B}^{-1}=\left[\begin{array}{ccc}
1 & 2 & -1 \\
-1 & -3 & 2 \\
-1 & -1 & 1
\end{array}\right] \nonumber \]
To decode the message, we multiply each matrix, on the left, by \(B^{-1}\). For example,
\[\left[\begin{array}{ccc}
1 & 2 & -1 \\
-1 & -3 & 2 \\
-1 & -1 & 1
\end{array}\right]\left[\begin{array}{c}
11 \\
20 \\
43
\end{array}\right]=\left[\begin{array}{c}
8 \\
15 \\
12
\end{array}\right] \nonumber \]
Multiplying each of the matrices in \(\bf{(IV)}\) by the matrix \(B^{-1}\) gives the following.
\[\left[\begin{array}{c}
8 \\
15 \\
12
\end{array}\right]\left[\begin{array}{c}
4 \\
27 \\
6
\end{array}\right]\left[\begin{array}{c}
9 \\
18 \\
5
\end{array}\right] \nonumber \]
Finally, by associating the numbers with their corresponding letters, we obtain
\[\left[\begin{array}{l}
\mathrm{H} \\
\mathrm{O} \\
\mathrm{L}
\end{array}\right]\left[\begin{array}{l}
\mathrm{D} \\
- \\
\mathrm{F}
\end{array}\right]\left[\begin{array}{l}
\mathrm{I} \\
\mathrm{R} \\
\mathrm{E}
\end{array}\right] \quad \text { The message reads: } \mathrm{HOLD} \text { FIRE } \nonumber \]
The message reads: HOLD FIRE.
We summarize:
TO ENCODE A MESSAGE
1. Divide the letters of the message into groups of two or three.
2. Convert each group into a string of numbers by assigning a number to each letter of the message. Remember to assign letters to blank spaces.
3. Convert each group of numbers into column matrices.
3. Convert these column matrices into a new set of column matrices by multiplying them with a compatible square matrix of your choice that has an inverse. This new set of numbers or matrices represents the coded message.
TO DECODE A MESSAGE
1. Take the string of coded numbers and multiply it by the inverse of the matrix that was used to encode the message.
2. Associate the numbers with their corresponding letters.
