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
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
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
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
First we keep the first row and add it to the second as well as to the third
rows. We obtain
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
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
Back to our original problem. Consider the message
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
Now we rearrange these numbers into a matrix B. For example, we have
Then we perform the product AB, where A is the matrix found above.
We get
The encrypted message to be sent is
|
