Skip to main content
2 of 2
added 1 character in body
ARupinski
  • 5.2k
  • 1
  • 30
  • 51

If $n > 2^m$ (or vice versa) then clearly there is no hope. If not, assume WLOG $m < n$ and put an $m\times m$ identity matrix in the first $m$ columns; then complete your last $n-m$ columns with any set of distinct columns chosen from the set of all columns which do not have exactly one 1 in them.

More generally, choose any $m\times m$ matrix $M$ which does not have any repeated rows to fill any set of $m$ columns, then fill the remaining $n-m$ columns with any set of distinct columns chosen from the among the set of 0-1 vectors which are not columns of $M$.

ARupinski
  • 5.2k
  • 1
  • 30
  • 51