Application of Invertible Matrices: Coding

There are many ways to encrypt a message. And the use of coding has become particularly significant in recent years (due to the explosion of the internet for example). One way to encrypt or code a message uses matrices and their inverse. Indeed, consider a fixed invertible matrix A. Convert the message into a matrix B such that AB is possible to perform. Send the message generated by AB. At the other end, they will need to know A^-1 in order to decrypt or decode the message sent. Indeed, we have

$$A^{-1} \Big(AB\Big) = B$$

which is the original message. Keep in mind that whenever an undesired intruder finds A, we must be able to change it. So we should have a mechanical way of generating simple matrices A which are invertible and have simple inverse matrices. Note that, in general, the inverse of a matrix involves fractions which are not easy to send in an electronic form. The best is to have both A and its inverse with integers as their entries. In fact, we can use our previous knowledge to generate such class of matrices. Indeed, if A is a matrix such that its determinant is $\pm 1$ and all its entries are integers, then A^-1 will have entries which are integers. So how do we generate such class of matrices? One practical way is to start with an upper triangular matrix with $\pm 1$ on the diagonal and integer-entries. Then we use the elementary row operations to change the matrix while keeping the determinant unchanged. Do not multiply rows with non-integers while doing elementary row operations. Let us illustrate this on an example.

Example. Consider the matrix

$$\left(\begin{array}{rrr} -1&5&-1\\ 0&1&8\\ 0&0&1\\ \end{array}\right).$$

First we keep the first row and add it to the second as well as to the third rows. We obtain

$$\left(\begin{array}{rrr} -1&5&-1\\ -1&6&7\\ -1&5&0\\ \end{array}\right).$$

Next we keep the first row again, we add the second to the third, and finally add the last one to the first multiplied by -2. We obtain

$$\left(\begin{array}{rrr} -1&5&-1\\ -2&11&7\\ 1&-5&2\\ \end{array}\right).$$

This is our matrix A. Easy calculations will give det(A) = -1, which we knew since the above elementary operations did not change the determinant from the original triangular matrix which obviously has -1 as its determinant. We leave the details of the calculations to the reader. The inverse of A is

$$\left(\begin{array}{rrr} 57&-5&46\\ 11&-1&9\\ -1&0&-1\\ \end{array}\right).$$

Back to our original problem. Consider the message

$$\mbox{I LOVE MONICA }$$

To every letter we will associate a number. The easiest way to do that is to associate 0 to a blank or space, 1 to A, 2 to B, etc... Another way is to associate 0 to a blank or space, 1 to A, -1 to B, 2 to C, -2 to D, etc... Let us use the second choice. So our message is given by the string

$$\begin{array}{rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr} I& &L&O&V&E&&M&O&N&I&C&A\\ 5&0&-6&8&-11&3&0&7&8&-7&5&2&1\end{array}$$

Now we rearrange these numbers into a matrix B. For example, we have

$$B = \left(\begin{array}{rrrrrr} 5&8&0&-7&1\\ 0&-11&7&5&0\\ -6&3&8&2&0 \end{array}\right).$$

Then we perform the product AB, where A is the matrix found above. We get

$$AB = \left(\begin{array}{rrr} -1&5&-1\\ -2&11&7\\ 1&-5&2\\ ... ...-1\\ -52&-116&133&83&-2\\ -7&69&-19&-28&1 \end{array}\right).$$

The encrypted message to be sent is

$$1,\; -52,\; -7,\; -66,\; \cdots,\; -1,\; -2,\; 1$$

[Geometry] [Algebra] [Trigonometry ] [Calculus] [Differential Equations] [Matrix Algebra]

S.O.S MATH: Home Page

Do you need more help? Please post your question on our S.O.S. Mathematics CyberBoard.

Author: M.A. Khamsi

Copyright © 1999-2024 MathMedics, LLC. All rights reserved.
Contact us
Math Medics, LLC. - P.O. Box 12395 - El Paso TX 79913 - USA
users online during the last hour