Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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:

  1. You can assume that $w=\max_i |\mathbf w_i|$ is a constant.

  2. You can assume that $p^q$ is much larger than $3knw$.

  3. If $\mathbf w_i$'s are disjoint, one can simply solve the problem by solving the problem for each $\mathbf w_i$ separately.

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

  5. 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:

  1. 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?

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

  3. 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 < n$, it is not also sufficient.

share|improve this question
    
Sounds like you want each $(A \odot B)|\mathbf{w}_i$ to be full-rank, i.e., to have determinant non-zero. Thus the question becomes to fill in the remaining elements (which weren't fixed to zero) so that all of these submatrices have non-zero determinant. Does that help? –  D.W. May 6 at 4:58
    
You are right, almost right. The only case that's not right is the when $m < \max_i \mathbf |w_i|$. Then the full-rank sub-matrix may have a rank smaller than $|\mathbf w_i|$. –  Mohsen May 6 at 5:44
    
@D.W.: Have a look at mobius's answer. That's promising. –  Mohsen May 6 at 5:46
add comment

1 Answer 1

When $p^q>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.

share|improve this answer
    
Thanks mobius. That's a great answer. I could see that a randomized algorithm works for the problem, but the bound that you suggested is the key point. Just a few questions: (1) Could you please point me to a reference for the "known result"? (2) Can't you imagine a case that your algorithm prints "POSSIBLE", but finding the matrix $A$ is in fact impossible? (3) Do you have any idea about a deterministic algorithm? –  Mohsen May 6 at 0:03
    
(1) I actually couldn't find a reference for it. I solved it in a homework assignment once so that's where I know the proof from, but I can't actually track any reference to it. The computation is very easy to do (I gave a sketch above) so maybe it's just folklore. (2) I don't know what it means for finding a solution to be impossible. The algorithm I gave finishes with probability 1 and has polynomial expected running time. Can the running time be infinite for some input? No: the running time is always finite. Can it be unbounded? Yes, for any number $M$ there is an input of size 10 (cont...) –  mobius dumpling May 6 at 0:19
    
(...cont) on which my algorithm takes more time than M. (3) It should be easy to give a deterministic algorithm if p^q is large enough, e.g. exponential in k (or maybe doubly-exponential in k). This will work similar for derandomizations of polynomial identity testing for simple types of polynomials: you find a subset $S$ of the field where the elements are algebraically independent with respect to polynomials of degree $(nkm)^2$, where $|S| \ge n^2$. And then you fill $A$ with the elements of this set. –  mobius dumpling May 6 at 0:25
    
This reference describes your approach in the introduction section: inf.kcl.ac.uk/staff/ccooper/papers/Li_Matrix_GFt.pdf –  Mohsen May 12 at 11:28
    
Your approach is very promising, but your algorithm has some issues. Two issues about it that I have in mind right know are: (1) As I said, in some cases it may print "POSSIBLE" while in fact an assignment is impossible. E.g., when $B|\mathbf w_i$ consists of one column of all 1s and the rest of the elements are all zeros. It does not have more than $n-|\mathbf w_i|$ entirely zero rows, but the rank of $B|\mathbf w_i$ can be at most one ... –  Mohsen May 12 at 11:32
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.