A conjecture about the entropy of matrix vector products

Question

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?

Answer 1

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.

Answer 2

This reminds me a bit of the game of mastermind.

---

Since your matrix is circulant, this entire matrix is determined by the first row ${\bf m}$, the vector $X$ and the shift map taking $T:(m_1, \dots, m_n) \mapsto (m_2, \dots, m_n, m_1)$

You are given $m$ numbers (please excuse the notation clash): $T^i({\bf m})\cdot {\bf X}$ for $i = 1, \dots, m$ so there are at most $m \log n$ bits of information.

The bound $ \log n \cdot \tfrac{10n}{\log n} \geq H(N) \geq \tfrac{n}{10}$ is consistent with your problem, at least.

Answer 3

One approach is computer exploration: write a program to plot a few points, and plot of the functions you want to compare to on the same graphics.

I wrote a quick Sage program to compute and plot the entropy H(Z(n,m)) for all 0 <= m <= n <= 10, and I added the plots of (x=t, y=t, z=t) and (x=t, y=sqrt(t), z=t/10). You can add a plot for (x=t, y=t/ln(t), z=t/10), and/or modify the others to find something closer to the graph.

You can find it and try it on the Sage Cell Server.

For n > 10 plotting points from exhaustive computations becomes very slow...

Massive speedups are certainly possible with a better program and/or using Cython or a faster programming language, but in any case the number of cases grows so fast that more efficient code will only get you so far.

The next trick is to replace exhaustive enumeration by random sampling, which might give you a rough idea of the graph in a larger range.

Of course, besides this exploration, a clever way to estimate H(Z(n,m)), in general or along a curve (n, m(n)), would better answer your question, but failing that, pictures are always nice.

In case it's any interest, Here is the Sage code I wrote.

from collections import defaultdict

def h(d):
    sn = 0r
    sl = 0r
    for n in d.itervalues():
        if n:
            nn = RDF(n)
            sl += nn * nn.log2()
            sn += nn
    if sn:
        return sn.log2() - sl/sn
    return RDF.one()

def hh(n):
    xn = xrange(n)
    xnn = xrange(n+1)
    cp = CartesianProduct(*((0r,1r),)*n)
    dd = [defaultdict(int) for _ in xnn]
    for y in cp:
        for x in cp:
            z = tuple(sum(x[(i+k)%n]*y[i] for i in xn) for k in xn)
            for m in xnn:
                dd[m][z[:m]] += 1r
    return [h(d) for d in dd]

hhh = []
nmax = 10
for k in xrange(nmax):
    hhh.append(hh(k))

ph = []
for n,hh in enumerate(hhh):
    for m, h in enumerate(hh):
        ph.append((n,m,h))

fx = lambda x: x
fy = lambda x: sqrt(x)
fz = lambda x: x/10

gx = lambda x: x
gy = lambda x: x
gz = lambda x: x

Gf = parametric_plot3d((fx,fy,fz),(0,n),color='red')
Gg = parametric_plot3d((gx,gy,gz),(0,n),color='red')
Gh = point3d(ph,size=3)
G = Gf + Gg + Gh
G.show(viewer='tachyon')
G.show()