Sum of matrix vector products

Consider a sequence of fixed non-singular $n$ by $n$ matrices $A_i$ whose entries are chosen from $\{0,1\}$ and a sequence of independent random $n$ dimensional vectors $x_i$ whose entries are also chosen independently from $\{0,1\}$ . Assume $n$ is large.

We know $H(A_ix_i) = n$. This is because $A_i$ is invertible and so $A_ix_i$ tells us precisely what the values of $x_i$ are.

I am interested in $$y=H\left(\sum_{i=1}^{\ell} A_ix_i\right)$$ and in particular, under what circumstances is $y$ much larger than $n$?

We know that if every $A_i$ is identical and each is simply the identity matrix then $y = nh_B(\ell)$ were $h_B(t) = H(B(t,1/2))$ . Therefore, under these circumstances $y \approx C_1n\log_2{\ell}$ for some constant $C_1 >0$.

What properties do the matrices $A_i$ have to have for $y$ to be of the form $C_2n\ell$ for some constant $C_2>0$?

It seems plausible that at the least the matrices $A_i$ should be dense to ensure that the range of values each entry of $A_ix_i$ can take is large enough. But is this sufficient?

• Let $w_i=A_i x_i$ , If $A_i$ are fixed and $x_i$ and independent, then $w_i$ are independent and $H(Y) = \sum H(w_i) = \lfloor\log_2{n}\rfloor n$ What am I missing? – leonbloy Dec 18 '15 at 14:23
• In the above, by $H(Y)$ I meant $y$ – leonbloy Dec 18 '15 at 14:30
• @leonbloy This can't be right. Look at the case where the $A_i$ are all the identity matrix. In general it's not always true that $H(X+Y) = H(X) + H(Y)$ if $X$ and $Y$ are independent. – dorothy Dec 18 '15 at 14:49
• Of course, my bad – leonbloy Dec 18 '15 at 14:53

A suggestion (sketch):

1. The problem (leaving aside the non-singularity of $A_i$, which should not be necessary - it should be a result) can be put in this equivalent form: let $x$ be the concatenation of $\ell$ instances of $x_i$, so $w=Bx$ where $B$ is a binary $n\times m$ matrix, $m=n \ell$, (in the original statement $\ell = \lfloor\log_2{n}\rfloor$ but we won't impose this). (It might be preferable to use $\{-1,1\}$ instead of $\{0,1\}$, for $x$ and/or for $B$).

2. For large $n$, $w$ tends to a multivariate Gaussian, its entropy tends to $H(w)=\frac{1}{2}\log(|2 \pi e B B^t|)$. The task, then is to maximize $|B B^t|$ subjected to $B$ being binary. [*]

3. See here (page 2, problem 2)

[*] Update: Perhaps this can be more convincing in the original formulation: $w =B x = \sum_{i=1}^\ell A_i x_i=\sum_{i=1}^\ell w_i$ where $A_i$ are square $n\times n$. Then, assuming $x_i \in\{-1,1\}$, $E(w_i)=0$, $Cov(w_i)=A_i A_i^t$ Then we can apply the multivariate CLT to show that $w$ tends to a $N(0,\sum_i A_i A_i^t)$ distribution.

• I would be equally interested in any answer that applied using $\{-1,1\}$ instead of $\{0,1\}$. – dorothy Dec 18 '15 at 19:42
• Your point 2. is fascinating but I don't understand it yet. a) Does $w$ tend to a multivariate Gaussian irrespective of what $B$ is and in what sense is this true? b) How do we know that $H(w) = 1/2 |2\pi e B B^T|$? c) For finite $n$, the entropy $H(w)$ does not seem to be monotonic in $|BB^T|$. Is this to be expected? – dorothy Dec 19 '15 at 7:27
• @dorothy a) Wild guess, it seems that some CLT variation should apply when $B$ has "enough ones" - yes, this is very informal b) that's the entropy of a multivariate gaussian with covariance $\Sigma = B B^T$ c) I'd bet that's a small $n$ effect - but I wouldn't bet my life :-) – leonbloy Dec 19 '15 at 12:48
• @felipa It's not necessary to assume convergence to Gaussian: $w=Bx \implies C_w = B C_x B^t$ . What I'm assuming is $x$ in $\{-1,1\}$, which implies $C_x=I$ To use $\{0,1\}$ changes only a multiplicative factor. – leonbloy Dec 19 '15 at 20:27
• @dorothy See my update. – leonbloy Dec 21 '15 at 16:27