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 +_ 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 + or -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

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

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

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

www.sosmath.com/matrix/coding/coding.htm

Using Matrices for Incryption and Decryption

In the early days of satellite television, the video signals weren't encrypted and anyone with a satellite dish could watch whatever was being shown. Well, this didn't work because all of the networks using satellites didn't want the satellite dish owners to be able to receive their satellite feed for no cost while cable subscribers had to pay for the channel, they were losing money. So, they started encrypting the video signal with a system called Videocipher (later replaced by Videocipher II).

What the Videocipher encryption system did was to convert the signal into digital form, encrypt it, and send the data over the satellite. If the satellite dish owner had a Videocipher box, and paid for the channel, then the box would descramble (unencrypt) the signal and return it to its original, useful form.

This was done by using a key that was invertible. It was very important that they key be invertible, or there would be no way to return the encrypted data to its original form.

The same thing can be done using matrices.

Encryption Process

1. Convert the text of the message into a stream of numerical values.
2. Place the data into a matrix.
3. Multiply the data by the encoding matrix.
4. Convert the matrix into a stream of numerical values that contains the encrypted message.

Example

Consider the message "Red Rum"

A message is converted into numeric form according to some scheme. The easiest scheme is to let space=0, A=1, B=2, ..., Y=25, and Z=26. For example, the message "Red Rum" would become 18, 5, 4, 0, 18, 21, 13.

This data was placed into matrix form. The size of the matrix depends on the size of the encryption key. Let's say that our encryption matrix (encoding matrix) is a 2x2 matrix. Since I have seven pieces of data, I would place that into a 4x2 matrix and fill the last spot with a space to make the matrix complete. Let's call the original, unencrypted data matrix A.

		18										5
A =		4										0
		18										21
		13										0

There is an invertible matrix which is called the encryption matrix or the encoding matrix. We'll call it matrix B. Since this matrix needs to be invertible, it must be square.

This could really be anything, it's up to the person encrypting the matrix. I'll use this matrix.

B =		4								-2
		-1								3

The unencrypted data is then multiplied by our encoding matrix. The result of this multiplication is the matrix containing the encrypted data. We'll call it matrix X.

		67									-21
X = A B =		16									-8
		51									27
		52									-26

The message that you would pass on to the other person is the the stream of numbers 67, -21, 16, -8, 51, 27, 52, -26.

Decryption Process

1. Place the encrypted stream of numbers that represents an encrypted message into a matrix.
2. Multiply by the decoding matrix. The decoding matrix is the inverse of the encoding matrix.
3. Convert the matrix into a stream of numbers.
4. Conver the numbers into the text of the original message.

Example

The message you need to decipher is in the encrypted data stream 67, -21, 16, -8, 51, 27, 52, -26.

The encryption matrix is not transmitted. It is known by the receiving party so that they can decrypt the message. Other times, the inverse is known by the receiving party. The encryption matrix can not be sent with the data, otherwise anyone could grab the data and decode the information. Also, by not having the decoding matrix, someone intercepting the message doesn't know what size of matrix to use.

The receiving end gets the encrypted message and places it into matrix form.

		67								-21
X =		16								-8
		51								27
		52								-26

The receiver must calculate the inverse of the encryption matrix. This would be the decryption matrix or the decoding matrix.

B-1 =		0.3						0.2
		0.1						0.4

The receiver then multiplies the encrypted data by the inverse of the encryption matrix. The result is the original unencrypted matrix.

		18								5
A = X B-1 =		4								0
		18								21
		13								0

The receiver then takes the matrix and breaks it apart into values 18, 5, 4, 0, 18, 21, 13, 0 and converts each of those into a character according to the numbering scheme. 18=R, 5=E, 4=D, 0=space, 18=R, 21=U, 13=M, 0=space.

Trailing spaces will be discarded and the message is received as intended: "RED RUM"

Cryptology

To encode a short message a number can be assigned to each letter of the alphabet according
to a given table. The text as a sequence of numbers will be organized into a square matrix A;
in the case that the number of letters is lower than the number of elements of the matrix A,
the rest of the matrix can be filled with zero elements. Let a nonsingular square matrix C be
given. To encode the text the matrix A can be multiplied by the matrix C for example on the
left. Let the following table and the matrix C be given:

A B C D E F G H I J K L M N O P Q R S T U V W X y Z
8 7 5 13 9 16 18 22 4 23 11 3 21 1 6 15 12 19 2 14 17 20 25 24 10 26

C =

2 0 1
1 0 1
0 1 0

We put the text ”BILA KOCKA” (a white cat) into the matrix A:
A =

7 4 3
8 11 6
5 11 8

and encode the text:
Z = CA =

19 19 14
12 15 11
8 11 6

.
To decode the message we have to multiply the matrix Z by the matrix C−1 on the left:
C−1Z =

1 −1 0
0 0 1
−1 2 0


19 19 14
12 15 11
8 11 6

= A.
Since the matrix multiplication is not commutative, it is necessary to keep the order of
the matrices in the product. If we multiply the matrices C−1 and Z in the opposite order, we
obtain

ZC−1=

19 19 14
12 15 11
8 11 6



1 −1 0
0 0 1
−1 2 0

=

5 9 19
1 10 15
2 4 11

and it means ”CERNY PSIK”(a black dog).

FIRAS ABDEL DAYEM
http://www.mff.cuni.cz/veda/konference/wds/contents/pdf06/WDS06_106_m8_Ulrychova.pdf

Encrypting Text Using Linear Algebra

Each letter is first encoded as a number. Often the simplest scheme is used: A = 0, B =1, ..., Z=25, but this is not an essential feature of the cipher. A block of n letters is then considered as a vector of n dimensions, and multiplied by a n × n matrix, modulo 26. (If one uses a larger number than 26 for the modular base, then a different number scheme can be used to encode the letters, and spaces or punctuation can also be used.) The whole matrix is considered the cipher key, and should be random provided that the matrix is invertible in (to ensure decryption is possible).
Consider the message 'ACT', and the key below (or GYBNQKURP in letters):

Since 'A' is 0, 'C' is 2 and 'T' is 19, the message is the vector:

Thus the enciphered vector is given by:

which corresponds to a ciphertext of 'POH'. Now, suppose that our message is instead 'CAT', or:

This time, the enciphered vector is given by:

which corresponds to a ciphertext of 'FIN'. Every letter has changed. The Hill cipher has achieved Shannon's diffusion, and an n-dimensional Hill cipher can diffuse fully across n symbols at once.
Article found at http://en.wikipedia.org/wiki/Hill_cipher
Alexander Abi Chaker 20091978

Using Inverse Matrices in Real Life

i think this is very interesting!!
we can use matrices to create a cryptogram
cryptogram is a message written according to a secret code.
From greek word kryptos meaning hidden and gramma meaning letter.
steps 2 create a cryptogram:
. Assign a number to each letter in the alphabet with out a blank space.
. Convert the message to numbers partitioned into 1*2 uncoded row matrices.
. To encode a message choose a 2*2 matrix A that has an inverse and multiply the uncoded row matrices by A on the right to obtain coded row matrices.
for example:
convert : GET HELP
. 7 5 20 0 8 5 12 16
. [7 5] [20 0] [8 5] [12 16]
. encode use A= 2 3
-1 -2
to see the answer just download the following:
http://www.google.com/url?sa=t&source=web&ct=res&cd=11&ved=0CAcQFjAAOAo&url=http%3A%2F%2Fguilford.rps205.com%2Fdepartments%2Fmath%2FLinks%2FAlgebra%2520II%2520-%2520College%2520Alg%2F4.4%2520Cryptograms%2520Using%2520Inverse%2520Matrices%2520in%2520Real%2520Life.ppt&ei=4bJDS7q6Nc7X4gap5sTGDA&usg=AFQjCNER0oUlU2FsTOVJ0Nuam0xTfjPIeg&sig2=UYWzPn9H0M5WADqSk0NopA

we can encode and decode!!!



Claudia Abdel-Sater

thank you.

i was doing my math revision in this holiday and while reading this blog i really got important informations about many things i didnt know especially about determinants. thank you!!

MATRICES IN CODING MESSAGES

http://www.sosmath.com/matrix/coding/coding.html
This link contains the most important application of matrices in the coding pattern!!!!
after viewing this link really we can say that matrices are related in our real life.they are used for sending text messages which is so important.
In this post: to encrypt a message we convert the msg to a matrix BUT to decrypt the msg we need to know the inverse of the matrix !
All what we learned in class including row operations,determinants,upper triangular matrix are applied to be able to sent the message finally!
hope u enjoyed these nice information that teach us how to solve a problem through matrices!
MOHAMMAD JAWISH ;)

When you click on it, it opens in a larger FONT

writing short messages using numbers and matrices

To encode a short message a number can be assigned to each letter of the alphabet according
to a given table. The text as a sequence of numbers will be organized into a square matrix A;
in the case that the number of letters is lower than the number of elements of the matrix A,
the rest of the matrix can be filled with zero elements. Let a nonsingular square matrix C be
given. To encode the text the matrix A can be multiplied by the matrix C for example on the
left. Let the following table and the matrix C be given:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
8 7 5 13 9 16 18 22 4 23 11 3 21 1 6 15 12 19 2 14 17 20 25 24 10
C =  2 0 1/ 1 0 1/ 0 1 0 
We put the text ”BILA KOCKA” (a white cat) into the matrix A:
A =  7 4 3 8 /11 6 5/ 11 8 
and encode the text:
Z = CA =  19 19 14/ 12 15 11 /8 11 6/ 
To decode the message we have to multiply the matrix Z by the matrix C−1 on the left:
C−1Z =  1 1 0/ 0 0 1 /1 2 0   19 19 14/ 12 15 11 /8 11 6 / = A.
Since the matrix multiplication is not commutative, it is necessary to keep the order of
the matrices in the product. If we multiply the matrices C−1 and Z in the opposite order, we
obtain
ZC−1 =  19 19 14 /12 15 11/ 8 11 6   1 1 0/ 0 0 1 /1 2 0  = 
5 919 /1 10 15/ 2 4 11 
and it means ”CERNY PSIK”(a black
dog). Source:http://www.mff.cuni.cz/veda/konference/wds/contents/pdf06/WDS06_106_m8_Ulrychova.pdf
what did i learn: i chose this article because its very simple and useful.It helps me text message others in a simpler way and in a fast way.I liked it and i can use it on daily bases.

BY JOHN Michel HItti

Matrices & Cryptography

Cryptopgraphy is extremely benifical to people, enabling them to keep certain information private, it has been a very imporatant matter all throughout history and till this very day.
You Probably Wonder how can matrices possibly be used Cryptography!
Well it is quite simple to say that due to the existence of matrices their multiplication and their inverse, The idea of cryptoghraphy was made possible.
Here is an example I found demonstrating how cryptography can be use to hide certain information using matrices multiplyong them and then finding their inverses, if you are intrested enough check this link to expand your understanding on how the following example was made Possible.

EXAMPLE:
Consider the Following Matrix Reffered to as the Encoding Matrix:
{-3,-3,-4;0,1,1;4,3,4} ( the comma seperates the entries in the rows and the semicolon seperates the columns)
Let the message we want to send be: Prepare to negotiate.
Assing every letter of the alphabet to a number ex: A-1 B-2 C-3 etc...
By Decoding the Matrix above and finding its inverse relate every entery in the Inverse matrix to the approtpriate letter and you will find your message.
Check out the Link To Deepen your understanding of Cryptography using matrices and their inverses. http://aix1.uottawa.ca/~jkhoury/cryptography.htm

Thank You,
Oliver Chlela