A matrix rank problem over finite fields: Is that a known problem? The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated.


Let $A \odot B$ denote elementwise multiplication of matrices $A$ and $B$.
Let $M|\mathbf w$, where $M$ is a matrix and $\mathbf w$ is a subset of the column indices, denote the matrix formed by selecting columns $\mathbf w$ from $M$.


Problem:


  Input: A binary matrix $B=\left[b_{ij} \right]_{m \times n}$, $b_{ij} \in \{0, 1\}$ and a collection $\{ \mathbf{w}_i \subset \{1,\cdots, n\} | i=1,\cdots,k \}$ of column indices.
  
  Output: Find a matrix $A=\left[ a_{ij} \right]_{m \times n}$, $a_{ij} \in \mathrm{GF}(p^q)$ such that for each $\mathbf{w}_i$, $i=1,\cdots, k$, rank of $(A \odot B)|\mathbf{w}_i$ is $|\mathbf{w}_i|$ or print IMPOSSIBLE if no such matrix exists.


Informally, the problem is that given an $m\times n$ matrix in which some of the elements are fixed to 0, assign values from a finite field to other elements such that the rank of some specific subsets of the columns is maximized.

Observations:


You can assume that $w=\max_i |\mathbf w_i|$ is a constant.
You can assume that $p^q$ is much larger than $3knw$.
If $\mathbf w_i$'s are disjoint, one can simply solve the problem by solving the problem for each $\mathbf w_i$ separately.
If $\mathbf w_i \subset \mathbf w_j$ for some $i \neq j$, $\mathbf w_i$ can be removed from the collection and the problem does not change.
From #3 and #4, the only difficult case of the problem is when $\mathbf w_i$'s intersect, but do not overlap completely (i.e. one is the subset of another).


Edit:


As "mobius dumpling" noted in his answer, with random assignment from the finite field to the matrix $A$, $(A\odot B)|\mathbf w_i$ has full rank with a constant probability $s$ for each $i=1,...,k$. The problem is that the probability that all $(A\odot B)|\mathbf w_i$ have full rank is $s^k$, which is not a constant. Should I use a more complicated method (such as inclusion/exclusion method) to compute the total probability?
A necessary condition for the problem is: for all $i$: for each $j\in \mathbf w_i$, there is a distinct row $k$ such that $b_{kj}=1$. This can be checked in polynomial time.
Having a full rank matrix $A \odot B$ as the result is neither a necessary nor a sufficient condition. The necessary part is apparent since in many cases, the answer is not a full rank matrix. For the case $m &lt; n$, it is not also sufficient.
When $p^q&gt;3k$, then there is an easy randomized algorithm for this problem (with error probability zero and polynomial expected running time). The algorithm prints "IMPOSSIBLE" if there is $i$ such that $B|w_i$ has more than $n-|w_i|$ rows that consist entirely of zeroes. Otherwise, the algorithm prints "POSSIBLE". It then chooses uniformly random matrices $A$ until it finds one that satisfies the requirements. Below I'll prove that a random matrix $A$ satisfies these requirements with at least constant probability.

If the algorithm printed "IMPOSSIBLE" then it is easy to see that indeed there is no $A$ that satisfies the requirements. Now, consider the case that the algorithm printed "POSSIBLE".

A known result states that a random matrix over a field of size $|F|$ is full-rank with probability $\ge 1-2/|F|$. To see this consider the columns one by one, and compute the size of the linear subspace that they have to "dodge". Work from the last column to the first. You get that the chance that the matrix is full rank is $(1-1/|F|)\cdot(1-1/|F|^2)\cdot\ldots$. In fact, the same proof can be seen to work even if some of the entries are fixed to zero, as long as no entire row is fixed to zero. QED.