I have already asked a similar question here, but since I have not got an acceptable answer, I decided to ask a simpler version of the question here.

  • 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$.


Input: Positive integers $m$ and $n$, and a collection $\mathcal W=\{ \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|\mathbf{w}_i$ is $|\mathbf{w}_i|$ or print IMPOSSIBLE if no such matrix exists.

For the case $m \ge n$ (i.e., matrix $A$ has more rows than columns), solving the problem is simple: just assign random numbers from the finite field to the elements of matrix $A$, and you get a full rank matrix with probability more than $1-\frac{2}{p^q}$. Any full rank matrix works in this case because any subset of the columns of matrix $A$ is also full rank.

For the case $m < n$ (i.e., matrix $A$ has more columns than rows), the problem seems different. A full rank matrix $A$ is not sufficient (nor necessary too).

A difficult case is described here: let $w$ be a positive integer. Let $m=w$ and let $n$ be arbitrarily large. Let $\mathcal W$ contain all the subsets of the column indices of size $w$, so $k=|\mathcal W|=\theta(n^w)$. It means that any column contributes to $\theta(n^{w-1})$ of $\mathbf w_i$'s. In other words, any assignment to a column should avoid collisions to $\theta(n^{w-1})$ subsets of $\mathbf w_i$. I guess that it means a random assignment to the whole matrix $A$ does not give a guaranteed constant probability.

If $\mathbf w_i$'s are not overlapping, one solution is to solve one $\mathbf w_i$ at a time. Because each $\mathbf w_i$ can be solved in poly-time, the whole thing can be solved in poly-time too. But what if $\mathbf w_i$'s are overlapping?

  • $\begingroup$ Some trivial observations. (1) If $|w_i|>m$ for any $i$, the answer is IMPOSSIBLE. (2) If $p^q \ge n^m$, a random assignment works (it has a guaranteed constant probability of being suitable). (3) If $A$ is a solution, then you can perform any row or column operation on it, and the result will remain a solution. (4) Therefore, when $n>m$, wlog you can assume that the first $m$ columns form the identity matrix. (5) If you then pick the remaining $n-m$ columns randomly (but with the requirement that each cell is non-zero), I suspect this might work for even larger matrices than idea (2). $\endgroup$ – D.W. May 28 '14 at 20:23
  • $\begingroup$ Trivial but helpful observations. About (3), I guess row operations are fine, but column operations are not. $\endgroup$ – Helium May 28 '14 at 20:56
  • $\begingroup$ This is similar to matroid realizability. $\endgroup$ – Yuval Filmus Mar 25 '16 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.