# What is the maximal sparsity of a matrix?

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?

-
What do you mean by "nondegenerate matrix"? Nonsingular? –  Felix Goldberg Jan 15 '13 at 17:28