<p>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.</p>

<p>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".</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-06T00:03:28.043Z
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?
Helium
CC BY-SA 3.0
2014-05-06T00:19:07.903Z
(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...)
greg
CC BY-SA 3.0
2014-05-06T00:25:18.463Z
(...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.
greg
CC BY-SA 3.0
2014-05-12T11:28:13.327Z
This reference describes your approach in the introduction section: http://www.inf.kcl.ac.uk/staff/ccooper/papers/Li_Matrix_GFt.pdf
Helium
CC BY-SA 3.0
2014-05-12T11:32:54.523Z
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 ...
Helium
CC BY-SA 3.0
2014-05-12T11:42:54.257Z
(2) The proof of the algorithm relies on the assumption that if the first $l$ columns are independent, $(l+1)$th column "dodges" the subspace of the first $l$ columns with probability $1-\frac{|F|^{l}}{|F|^m}$, since there are $|F|^l$ points in the subspace of the first $l$ columns and there are $|F|^n$ options to select column $l+1$. This is not true about my problem, since the number of options for column $l+1$ is only $|F|^o$, where $o$ is the number of ones in column $l+1$.
Helium
CC BY-SA 3.0
2014-05-12T12:23:37.150Z
About the fist issue: the condition should be something like this: if for all $i$ and for each $j \in \mathbf w_i$, there is a distinct row $k$ such that $b_{kj} = 1$, then print "POSSIBLE"; otherwise print "IMPOSSIBLE".
Helium
CC BY-SA 3.0
2014-05-05T22:28:48.483Z
2014-05-05T22:28:48.483Z
greg
<p>The following problem is simple to state, but seems quite complicated to solve to me. Any hint or reference to related work is appreciated.</p>

<ul>
<li><p>Let $A \odot B$ denote elementwise multiplication of matrices $A$ and $B$.</p></li>
<li><p>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$.</p></li>
</ul>

<p><strong>Problem:</strong></p>

<blockquote>
  <p><strong>Input:</strong> 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.</p>
  
  <p><strong>Output:</strong> 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.</p>
</blockquote>

<p>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.</p>

<p><strong>Observations:</strong></p>

<ol>
<li><p>You can assume that $w=\max_i |\mathbf w_i|$ is a constant.</p></li>
<li><p>You can assume that $p^q$ is much larger than $3knw$.</p></li>
<li><p>If $\mathbf w_i$'s are disjoint, one can simply solve the problem by solving the problem for each $\mathbf w_i$ separately.</p></li>
<li><p>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.</p></li>
<li><p>From #3 and #4, the only difficult case of the problem is when $\mathbf w_i$'s intersect, but do not overlap completely (<em>i.e.</em> one is the subset of another).</p></li>
</ol>

<p><strong>Edit:</strong></p>

<ol>
<li><p>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?</p></li>
<li><p>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$. <a href="https://cs.stackexchange.com/questions/25931/a-variant-of-the-set-cover-problem-is-that-a-known-problem">This can be checked in polynomial time</a>.</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2014-05-06T04:58:52.203Z
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.
CC BY-SA 3.0
2014-05-06T05:44:47.650Z
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|$.
Helium
CC BY-SA 3.0
2014-05-06T05:46:00.147Z
@D.W.: Have a look at mobius's answer. That's promising.
Helium
<linear-algebra><matrices><finite>
A matrix rank problem over finite fields: Is that a known problem?
Helium
# A matrix rank problem over finite fields: Is that a known problem?

(Asked by: username_0 on 2014-05-05)

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](https://cs.stackexchange.com/questions/25931/a-variant-of-the-set-cover-problem-is-that-a-known-problem).
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.

**Tags:** linear-algebra, matrices, finite
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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|$.  
> **username_0**: @D.W.: Have a look at mobius's answer. That's promising.  

---

## 1 answers

### Answer by username_2 on 2014-05-05. Score: 4

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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: (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...)  
> **username_2**: (...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.  
> **username_0**: This reference describes your approach in the introduction section: http://www.inf.kcl.ac.uk/staff/ccooper/papers/Li_Matrix_GFt.pdf  
> **username_0**: 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 ...  
> **username_0**: (2) The proof of the algorithm relies on the assumption that if the first $l$ columns are independent, $(l+1)$th column "dodges" the subspace of the first $l$ columns with probability $1-\frac{|F|^{l}}{|F|^m}$, since there are $|F|^l$ points in the subspace of the first $l$ columns and there are $|F|^n$ options to select column $l+1$. This is not true about my problem, since the number of options for column $l+1$ is only $|F|^o$, where $o$ is the number of ones in column $l+1$.  
> **username_0**: About the fist issue: the condition should be something like this: if for all $i$ and for each $j \in \mathbf w_i$, there is a distinct row $k$ such that $b_{kj} = 1$, then print "POSSIBLE"; otherwise print "IMPOSSIBLE".  

---

