Matrix Cryptography

[Orillion]

Im not sure how many people have had experience doing this by hand, but Im attempting to decrypt a matrix. The type of encryption may have a name, but I'm not aware of it by hand. It is formed from giving each letter its corresponding number (ie A = 1, B = 2, Space = 27).

From that the message is put into a matrix where it reads down the columns, and then left to right.  This matrix, say A, is then multiplied by a completely randomly chosen matrix B, and Matrix C is produced. Im having to work my way back from Matrix C. What matrix operations am I looking at having to do?

[Arta]

I know nothing about matrices, but couldn't you yield matrix A by dividing C by B?

[Raven]

No Arta, it doesn't really work that way, since when you multiply matrices, different numbers interact than when you divide them. Could you maybe post the matrices so we could see exactly what you're dealing with (and perhaps be better able to help you)?

[Yoni]

Linear algebra classes paid off:

How completely randomly chosen is matrix B? Is it a square matrix? Is it a nonsingular matrix?

If B is not a square, you have more or less no way to get A back.
If B is square but singular, then C is singular as well, and there is probably an infinite number of choices for the matrix A.

If both A and B are square and nonsingular, then C is nonsingular as well, so given the matrix B, you can get A back.

Remember that with matrices, AB != BA.

If: C = AB
Then: A = C(B^-1)

If: C = BA
Then: A = (B^-1)C

Edit: Grammar.

[Adron]

Which matrices do you know? Any? Or are you supposed to figure out A from C without having any other knowledge than that it's a message in English so you can do some kind of statistic/probabilistic assumptions?

[Orillion]

Sorry for not giving all the information. Thankfully its made easier by the fact A isnt necessarly random. It is

-3  -3  -4
0   1    1
4   3    4

in this particular problem.

Yes the message is in English, knowing my lecturer, its some completely cheesy statement (The Example involved 'Lets Eat' as the statement to be encrypted).


And the equation from what Ive gathered is AB = C. A being the random matrix mentioned earlier, and B being the matrix composed of the message and C being the final encrypted message.

The matrix I have to decyrpt is

-122  -123 -176  -130  -124  -150
  23     19     47     28     21      38
138    139   181   145   144   153    

[Camel]

You need to find the inverse of Matrix B, and multiply Matrix C by that. The result will be Matrix A.

Here's the idea:
A * B = C

Because there is no such thing as matrix division, in order to move B on to the other side of the equals sign above, B must be inverted (see next post).

So what we get is:
A = B^-1 * C

* Camel searches for his graphing calculator

The inverse of:
-3  -3  -4
0  1    1
4  3    4

is:
1 0 1
4 4 3
-4 -3 -3
When multiplied by:
-122  -123 -176  -130  -124  -150
 23    19    47    28    21      38
138    139  181  145  144  153


WARNING: Spoiler!!


the result I recieved was:
16 16 5 15 20 3
18 1 27 27 20 11
5 18 20 1 1 27
"prepare to attack "

[edit]added spoiler message

PS, I love these kinds of puzzles, +1 for providing it.

[Camel]

BTW, if you want to know how to find the inverse matrix, the basic idea is to augment the origional with an identity matrix of equal size and then try to get the leftmost (in this case) 3 columns to the identity using matrix operations.

So this matrix:
-3  -3  -4 : 1 0 0
0  1    1 : 0 1 0
4  3    4 : 0 0 1

Will become this one:
1 0 1 : 1 0 1
0 1 0 : 4 4 3
0 0 1 : -4 -3 -3

[edit] I am going to assume you know what matrix operations are as you probably wouldn't be asked this problem if you didn't. For that reason, I have omitted all of the steps between the previous two augmented matricies. Well, I actually just punched the numbers into my calculator and had it do the inverse, but I do know how to do it out on paper. [/edit]

Which in actuality is like trying to solve for A, B, and C given:
-3A + -3B + -4C = 1X + 0Y + 0Z
0A + 1B + 1C = 0X + 1Y + 0Z
4A + 3B + 4C = 0X + 0Y + 1Z
or
-3A - 3B - 4C = X
B + C = Y
4A + 3B + 4C = Z

So,
1A + 0B + 0C = 1X + 0Y + 1Z
0A + 1B + 0C = 4X + 4Y + 3Z
0A + 0B + 1C = -4X + -3Y + -3Z
or
A = X + Z
B = 4X + 4Y + 3Z
C = -4X - 3Y - 3Z

[Orillion]

Thanks Camel.

I was already aware of the Gauss-Jordan Technique for finding inverse, but thanks . And your answer was the same as what I got. Knew it was going to be some cheesy statement.