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?
 A: A suggestion (sketch):

*

*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$).


*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. [*]


*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.
