Consider a field $F$. Suppose we have two vectors $a,b\in F^n$, and an invertible matrix $G\in F^{n\times n}$. Let $c\in F^n$ be the point-wise product of $a$ and $b$, that is, $c_i=a_ib_i$. Let $x=Ga$, $y=Gb$, and $z=Gc$ (so $x,y,z\in F^n$).

Let $D\in F^{n\times n}$ be the outer product of $x$ and $y$, that is $D_{i,j}=x_iy_j$.

Question: Can the $z_i$ be expressed as a linear combination of the $D_{i,j}$?

If it helps, feel free to assume the field $F$ is finite.

This question arose in the following context. All linear error-correcting codes are additively homomorphic: adding two message vectors and encoding is the same as encoding both message vectors and then adding the corresponding codewords. Some error-correcting codes are simultaneously multiplicatively homomorphic, in the sense outlined above, where $G$ is the generator matrix. For example, for non-systematic Reed-Solomon codes, each $z_i$ correspond to sums of shifted diagonals of $D$. (This result is more commonly expressed as "the convolution of two vectors in the time domain corresponds to their point-wise multiplication in the frequency domain".) I'm trying to understand this phenomenon more generally.

I think it suffices to consider the case for rate 1 (non-systematic) codes, which is why the question concerns square matrices (rather than a typical non-square generator matrix).

  • $\begingroup$ I am probably being dense. Can you explain further, the Reed Solomon case? $\endgroup$ – kodlu May 16 '18 at 21:36

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.