MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
What do you mean by "nondegenerate matrix"? Nonsingular? – Felix Goldberg Jan 15 '13 at 17:28

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

share|cite|improve this answer
It may be possible to base a proof on a result (Sturm?) that counts zeros by counting alternations in sign of the coefficients. Gerhard "Leaving The Fun For Others" Paseman, 2013.01.15 – Gerhard Paseman Jan 15 '13 at 18:28

Your Answer


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.