Wednesday, 10 February 2010

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
\begin{displaymath}A^{-1} \Big(AB\Big) = B\end{displaymath}

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
\begin{displaymath}\left(\begin{array}{rrr}
-1&5&-1\\
0&1&8\\
0&0&1\\
\end{array}\right).\end{displaymath}

First we keep the first row and add it to the second as well as to the third rows. We obtain
\begin{displaymath}\left(\begin{array}{rrr}
-1&5&-1\\
-1&6&7\\
-1&5&0\\
\end{array}\right).\end{displaymath}

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
\begin{displaymath}\left(\begin{array}{rrr}
-1&5&-1\\
-2&11&7\\
1&-5&2\\
\end{array}\right).\end{displaymath}

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
\begin{displaymath}\left(\begin{array}{rrr}
57&-5&46\\
11&-1&9\\
-1&0&-1\\
\end{array}\right).\end{displaymath}

Back to our original problem. Consider the message
\begin{displaymath}\mbox{I LOVE MONICA }\end{displaymath}

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{displaymath}\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}\end{displaymath}

Now we rearrange these numbers into a matrix B. For example, we have
\begin{displaymath}B = \left(\begin{array}{rrrrrr}
5&8&0&-7&1\\
0&-11&7&5&0\\
-6&3&8&2&0
\end{array}\right).\end{displaymath}

Then we perform the product AB, where A is the matrix found above. We get
\begin{displaymath}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).\end{displaymath}

The encrypted message to be sent is
\begin{displaymath}1,\; -52,\; -7,\; -66,\; \cdots,\; -1,\; -2,\; 1\end{displaymath}

0 comments:

 

Everything About Science In Nepal Copyright © to scientific nepal team