Probability of collision in linear hashing?

Question

Take an $u × m$ matrix $A$ filled with random bits(0,1). Given a non-zero vector $x$ in $\{0,1\}^u$, what is the probability that $x$ is in null space of $A$. All calculations are done modulo 2. Source of randomness is selection of $A$ from $2^{um}$ choices.

Answer 1

If $x$ is in the nullspace of $A$, then all the coordinates of $Ax$ are equal to $0$, ie for any $i \in \{1, \dots, u\}$: $\displaystyle\sum_{k=0}^m a_{ik} x_k = 0$.

Now, all $a_{ik}$ and all $x_k$ are uniformly random, so you can deduce the distribution of the product $a_{ik}x_k$. Then, in modulo 2, the sum can be found by computing how many terms of the sum are nonzero.