tg

tg
tgt

Monday, 25 March 2013

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}
Post a Comment