Re: random equation system solvable?
dvsarwate
wrote:
> Hey!
>
> I am thinking about the following question, and it'd be great if someone
> could let me know if questions like this have been studied and where to
> look for solutions:
>
> Let A be a uniformly random variable over F2^{km} and let C be uniform over
> F2^k. Let us view A as a k x m matrix (i.e., m columns and k rows) with k
> <= m and C as k bit vector.
>
> Now, I am interested in the probability (depending on k and m) that there
> is a solution (not necessarily unique) for the equation system: A * B = C.
>
> Thanks,
> Bernd
I assume that A is a k x m matrix over the binary field F_2.
These kinds of questions are studied in coding theory.
For example, in
<http://courses.engr.illinois.edu/ECE556/fall2004/homework/PS03.pdf>
the following (related) question is considered. Consider
the ensemble of k x n matrices over F_2 of the form
[I : P] where I is the k x k identity matrix and P is a
k x (n-k) matrix. Then, given any n-bit vector x, this
vector is either *not* in the row-space of *any* of the
2^{k(n-k)} matrices in the ensemble, or it is in the
row-space of exactly 2^{(k-1)(n-k)} matrices in the
ensemble. The proof (it is not too hard) can be
found in
<http://courses.engr.illinois.edu/ECE556/fall2004/homework/HW03.pdf>
For the more general case asked for here, one
would need to account for the fact that not all
binary k x n matrices are of full rank etc.
--Dilip Sarwate
Robert Israel
> Hey!
>
> I am thinking about the following question, and it'd be great if someone
> could let me know if questions like this have been studied and where to
> look for solutions:
>
> Let A be a uniformly random variable over F2^{km} and let C be uniform over
>
> F2^k. Let us view A as a k x m matrix (i.e., m columns and k rows) with k
> <= m and C as k bit vector.
>
> Now, I am interested in the probability (depending on k and m) that there
> is a solution (not necessarily unique) for the equation system: A * B = C.
F2, I assume, is the field F_2 of integers mod 2.
If A has rank r, the range of A has cardinality 2^r and the probability
that C is in this range would be 2^(r-k). So the answer will be
2^(-k) E[2^R] where the random variable R = rank(A).
Now let R_j be the rank of the first j columns of A. Thus R_0 = 0.
Given R_j, R_{j+1} = R_j if the (j+1)'th column of A is one of the 2^(R_j)
linear combinations of the first j columns, and R_j + 1 otherwise.
Thus E[2^(R_{j+1}) | R_j] = 2^(R_j + 1) - (2^(R_j-k)) 2^(R_j)
= 2^(R_j + 1) - 2^(2 R_j - k)
or if f(j) = E[2^{R_j}]/2^k, f(0) = 2^(-k) and f(j+1) = 2 f(j) - f(j)^2.
The solution of the recurrence is f(j) = 1 - (1-f(0))^(2^j). Thus the answer
is f(m) = 1 - (1 - 2^(-k))^(2^m).
--
Robert Israel isr...@math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada