Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$H$ is an $n \times n$ matrix with elements in $ \{ -1,0,1 \}$

$G$ is an $n \times k$ matrix with elements in $GF(2)$ and also upper triangular, invertable

$m$ is an $k \times 1$ vector with elements in $GF(2)$

How can we perceive the output of $HGm$ where $Gm$ multiplication is in $GF(2)$ and $H$ multiplication is a normal real multiplication. Actually I want to combine $HG$ transformation into one $P$ transformation. How can I multiply two matrices while elements in one are in $GF(2)$ and other is in $R$ ? (We can also restrict the entries in $H$ to be one of $-1$ and $1$ but the output can be in $R$).

Motivation: It is a digital communication problem. $Gm$ is output codeword with 1 being mapped to -1 and 0 bit being mapped to +1. This codeword is multiplied to a channel convolution matrix $H$ e.g.

write in MATLAB

H = [1 -1 0 0 0;0 1 -1 0 0; 0 0 1 -1 0; 0 0 0 1 -1; 0 0 0 0 1]'

Now I have the following questions?

  1. I want to know whether the whole transformation P = H(G) can be represented by an equivalent transformation P' in GF(2) ? In other words, does there exist a $M \in [GF(2)]^{n \times n}$ such that $P'=G; P=H(MG)$

  2. If above is not generally possible, do there exist sufficient conditions for $H$ such that above is even possible?

  3. Which branch of mathematics deals with the interaction of real matrices with matrices on finite fields?

share|cite|improve this question
$HGm$ makes little sense when $H$ is a real matrix and each entry of $Gm$ is an element of $\mathbb F_2$, that is, a residue class of $\mathbb Z$ modulo 2. Each of these residue classes is unchanged under multiplication by $1$ or $-1$. – Henning Makholm Nov 10 '11 at 20:16
Is $H$ a matrix with entries in $\{+1,-1\}$ or in $\{0,+1,-1\}$? You state the former while describing the set-up but your example uses the latter alphabet. Also, $Gm$ is a vector over $\mathbb F_2$. Are you mapping it to the alphabet $\{+1,-1\}$ using $x \to (-1)^x$? – Dilip Sarwate Nov 10 '11 at 20:32
I believe you simply take the matrix G and map its entries one by one: 0→−1 and 1→1. I've only seen 0→0 and 1→1, which is a very simple embedding used in decoding algorithms. Neither of these is a homomorphism, but they still end up being helpful in decoding. – Jack Schmidt Nov 10 '11 at 21:15
Also posted to MO,… – Gerry Myerson Nov 10 '11 at 21:31
you are right $H \in \{-1,0,+1\}^{n \times n}$ and No I am not mapping it to ${+1, -1}$. Instead, I am mapping it to $\{+1, 0\}$. – ubaabd Nov 10 '11 at 21:34

The vector ${\mathbf x} = Gm \in \mathbb F_2^n$ is transformed into a vector $\mathbf y$ over the alphabet $\{-1, +1\}$ by mapping each component $x_i$ via $x_i\to (-1)^{x_i}$ since the OP says "output codeword with $1$ being mapped to $-1$ and $0$ bit being mapped to $+1$." But the product ${\mathbf z} = H{\mathbf y}$ is a $n$-tuple of real numbers from the set $\{-n, -n+1, \ldots, n-1, n\}$. So I suppose that the question is how to describe the map from $m \in \mathbb F_2^k$ to $\mathbf z$. One way would be to treat the elements of $\mathbb F_2$ as elements of $\mathbb Z$ and replace all additions $a\oplus b$ in $\mathbb F_2$ with $a + b - 2ab$ while computing the product $Gm$, map $\mathbf x$ to $\mathbf y$ as described above, and finally write the matrix multiplication.

All this might be describable purely in terms of operations in $\mathbb F_2$ with a final map from some $\mathbb F_2^N$ to $\{-n, -n+1, \ldots, n-1, n\}^n$, but I don't see the point of doing so.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.