MathOverflow is a question and answer site for professional mathematicians. 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,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 want to impose a restriction on the complete transformation $P=HG$ and want to know if it is upper triangular or not ?

share|cite|improve this question
The result will generally not be a linear transformation. If you provide some motivation, I may have a good idea for you. Right now, it looks to me like a lookup table of column sums. Gerhard "Ask Me About System Design" Paseman, 2011.10.28 – Gerhard Paseman Oct 28 '11 at 20:45
As long as your entries are integers (or rationals with odd denominators) you can reduce mod 2. You should tell us what you want to do with this information, so we can help you better. – S. Carnahan Oct 28 '11 at 21:04
I added the description Carnahan. Let me know if you need any other information. – Aitezaz Abdullah Oct 28 '11 at 21:06
The "transformation" P is a general set mapping, not a linear mapping. It would make sense to call it upper triangular only if it or some representation seemed upper triangular. You can use Carnahan's suggestion and ask if P' = (P then mod 2) is upper triangular; P will not look like matrix multiplication when the dust settles, except in special circumstances. Gerhard "Ask Me About 0-1 Matrices" Paseman, 2011.10.28 – Gerhard Paseman Oct 28 '11 at 21:16
Also, P' won't always be upper triangular. If G is upper triangular then it is routine to show that P' will be, because P' looks like H'G, where H' is the GF(2) version of H, if that makes sense. Gerhard "Ask Me About System Design" Paseman, 2011.10.28 – Gerhard Paseman Oct 28 '11 at 21:19

It seems to me that there may be some confusion here. As pointed out by all the commenters, the overall mapping cannot be linear. For me the most compelling reason for that would be that the only additive homomorphism from $GF(2)^k$ to $\mathbf{R}^n$ is the trivial map sending everything to all zeros. Anyway, here is my attempt to make sense out of the question. This is just educated guessing based on the scant given data.

It seems to me that the channel state matrix $H$ is upper triangular. This may have the following natural interpretation. The output of $Gm$ is a transmitted signal (usually mapped from $GF(2)$ to reals as follows: $0\mapsto +1$, $1\mapsto -1$, but other conversion mappings from binary to real are possible). This is transmitted sequentially: the first component in the first time slice, then the next,... The shape of the example matrix $H$ (as well as mentioning the term "channel convolution") suggests that what may be happening is that at instant of time $n$, the receiver sees a linear combination $r(n)=\sum_{i=0}^d w(i) t(n-i)$, where $t(n)$ is the signal transmitted at time $n$ and $w(i)$ is a weight assigned to a signal "delayed" by $i$ time units. I guess other interpretations are possible. Please comment!

If the above holds, then you in some sense equate 'upper triangular' with 'causal', in the sense that only the things transmitted in the past can affect what is being received now. If this (or another equivalent interpretation) is what you wanted to ask, then I can finally give an answer: "Yes". Your encoding matrix $G$ was specified to be upper triangular, meaning that the payload sequence of bits $m_1,m_2,\ldots,m_k$ is turned into an encoded sequence $c_1,c_2,\ldots,c_n$ of bits in such a way that for all $i$, the bit $c_i$ is a (binary linear) function of the bits $m_j, j\le i$, and does not depend on the "future" bits $m_j, j>i$. Several encoder have this property (e.g. convolutional), and all linear codes have an encoder like this (systematic part in the beginning).

But the relation between the $m_i$-sequence and the $r(i)$-sequence is not linear. With the $0\mapsto +1, 1\mapsto -1$ it could be expressed as something like $$ r(n)=\sum_{i=0}^n w(i)(-1)^{\sum_{j\ge0}c(i,j,n) m(n-i-j)}, $$ and the causality is kept, but I don't think this is saying very much?

I also think that you might be better off asking this at, e.g. dsp.stackechange. I don't think this is really a research level math question.

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.