Consider a random $m$ by $n$ partial circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$ and let $m < n$. Now consider a random $n$ dimensional vector $v$ whose entries are also chosen independently and uniformly from $\{0,1\}$. Let $N = Mv$ where multiplication is performed over the reals.
The matrices $M$ and $N$ are discrete random variables. Recall that the Shannon entropy for a discrete random variable $Z$ is $H(Z) = -\sum_z P(Z=z)\log_2{P(Z=z)}$. In the case where $P(Z=z)=0$ for some values $z$, the corresponding term in the sum is taken to be $0$.
We therefore know that the (base $2$) Shannon entropy $H(M) = H(v) = n$. The fact that $H(M) = n$ is a direct result of the fact that the entire matrix is defined by its first row.
If $m = \lfloor 10n/\ln{n} \rfloor$ then I would like to make the following conjecture.
Conjecture: For all sufficiently large $n$, $H(N) \geq n/10$.
The value $10$ is chosen somewhat arbitrarily to be a sufficiently large constant.
Is this a known problem and/or can anyone see a way to approach it? Is it in fact true?
Best Answer
This is not an answer, just a long comment.
As pointed out by John Mangual, this game is similar to Mastermind. In fact, it is even more similar to the game defined by Erdos and Renyi here: http://www.renyi.hu/~p_erdos/1963-12.pdf. In your language their game is the following: We are given the first row of the matrix $M$, denoted by $M'$, (so $m=1$) but what we multiply it with, $X$, is not a vector, but an $n\times a$ matrix. Our goal is to reconstruct $M$ from $N=M'X$. They show that this can be done whp if $X$ is a random matrix and $a\ge 10n/\log n$. Of course if $M$ can be reconstructed whp, that also implies that $H(N)\ge (1-\epsilon)n$.
So one possible way to answer your question would be to show that their theorem holds even in the case when $X$ is a circulant matrix, as this is equivalent to $X$ being a vector and $M$ being circulant.
new part
So suppose we want to compute the probability that for two different random vectors, denoted by $v$ and $u$, multiplying them with the rotations of a random vector $r$ we get the same values, i.e., if the rotations of $r$ are denote by $r_1,\ldots,r_k$, then what is the chance that for all $i$ we have $vr_i=ur_i$. For any $i$, this is like a random walk, as $v$ and $u$ are also random, so $Pr[vr_i=ur_i]\approx 1/\sqrt n$. Now I claim that this statement is true even in the following conditional form if $k$ is small enough: $Pr[vr_i=ur_i\mid \forall j\ne i: vr_j=ur_j]\approx 1/\sqrt n.$
I don't think this is that hard to prove, but I cannot see a solution now.