Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Matrix Encoder and Decoder

Date: 07/22/2003 at 20:24:56
From: Jai
Subject: Matrix encoder and decoder

If the encoder is 2  5  I know that the decoder would be 3 -5
                  1  3                                  -1  2

Why do the 3 and 2 swap diagonally and why do the 1 and 5 stay the 
same but change to a negative?


Date: 07/23/2003 at 01:05:57
From: Doctor Barrus
Subject: Re: Matrix encoder and decoder

Hey, Jai!

Let's suppose that you take ANY matrix that you want to encode, with 
entries like this:

[p q]
[r s]

When we multiply this matrix by the encoder (I don't know whether 
you're multiplying on the left or on the right. The decoder works 
either way, so I'll just assume you're multiplying on the right), we 
get the following matrix:

[p q][2 5] = [2p+q 5p+3q]
[r s][1 3]   [2r+s 5r+3s]

This is the encoded matrix. Now if we apply the decoding matrix, 
we'll get the following:

[2p+q 5p+3q][3 -5] = [(6p+3q)-(5p+3q) (-10p-5q)+(10p+6q)]
[2r+s 5r+3s][-1 2]   [(6r+3s)-(5r+3s) (-10r-5s)+(10r+6s)]

                   = [p q]
                     [r s]

So you see that the decoder matrix ALWAYS returns the original matrix, 
no matter what the entries are.

Why does this happen? Well, basically, we're multiplying the original 
matrix (I'll call it M) by an encoding matrix E and a decoding matrix 
D:

M*E*D

Now since we carry out the multiplication in steps, this is how the 
grouping goes:

(M*E)*D

i.e., we're multiplying first by the encoder matrix, and then (second) 
by the decoder matrix. However, matrix multiplication is associative. 
You can't change the order in which the matrices appear on the line, 
but you can change how you group them (you can change where the 
parentheses are). So what we're doing is the same as finding the 
matrix

M*(E*D)

Now try multiplying the encoder and the decoder matrices together, 
all by themselves. You should get the following:

[1 0]
[0 1]

This is called the identity matrix, because (as you've seen), when 
you multiply any matrix by it, you get the original matrix back (try 
it!). It acts for matrices the way the number 1 does for real numbers.

So when you're multiplying by the encoder matrix and then the decoder 
matrix, the net product is pretty much just multiplying your original 
matrix by 1 - it's going to the same as it was originally.

So how do we find pairs of matrices that have this pattern - that when 
you multiply them together, you get an identity matrix out? What we 
do is called finding the "inverse" of a matrix. We say that the 
decoder matrix is the inverse of the encoder matrix. In any book on 
matrix algebra or linear algebra you can learn a lot more about the 
properties of inverses, but for right now, let's stick to 2-by-2 
matrices. Say your encoder matrix is

[a b]
[c d]

One important thing is that we cannot allow ad-bc=0. If that's true, 
then there will be no decoder matrix for the encoder matrix. But if 
ad-bc is not equal to zero, we form the decoder by doing pretty much 
what you said:

1. Switch a and d.
2. Change the sign on both b and c.
3. Divide each entry in this changed matrix by the quantity ad-bc. 
(This is why it's not allowed to be 0. Notice that in the original 
matrix you gave, ad-bc = 2*3-1*5 = 1, so the division we had to do to 
get the decoder matrix is invisible.)

For example, say our encoder matrix is 

[5 3]
[1 2]

Then the decoder matrix is

[ 2/7  -3/7]
[-1/7   5/7]

Try it out and see that it, too, works.

I hope this helps. Good luck!

- Doctor Barrus, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Linear Algebra

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/