Question

Given a $m \times 2m$ matrix G with rank(G)=m, what is the maximal number of zeros in the product $WG$ where $W$ is an $m \times m$ nondegenerate matrix?

An obvious lower bound is $m(m-1)$ and $W$ is given by a matrix that transforms the first $m$ columns of $G$ to a standard basis in $\mathbb{R}^m$. When $m=1$ this lower bound is in fact attained. Is it possible to have more zeros when m>>1?

Answer 1

I expect not. If I get your question, you are asking for a basis for R, the row space of G, that has as many zero coordinates as possible. I can imagine that there are subspaces of dimension m inside F^2m for m small with respect to the cardinality of the base field F that avoid bases with more than the minimal number, but I cannot at this time provide explicit examples with proof for all n. Something that should work is having the ith row of G be e_i concatenated with f_i, where e_i is the canonical ith basis vector with m-1 zeros and one 1, and f_i is an m vector of values of (x^(i-1) +i) evaluated at x=1 to m, but I have only looked at the case m=2, where the rows are 1 0 2 2 and 0 1 3 4. The argument should go something like : if I produce k zeroes in "the second half" of such a G, I take away k or more zeros in "the first half" because the coefficients of the polynomial which is generated in the second half will dictate many nonzero entries in the first half, but I have not done the whole argument myself.

Gerhard "Ask Me About System Design" Paseman, 2013.01.15