0
$\begingroup$

If I want to write an $m\times n$ $0/1$ matrix with only rows or columns distinct, I could just pick $m$ or $n$ distinct natural numbers effectively writing them down as rows or columns in base $2$.

Is there a canonical way to write down an $m\times n$ $0/1$ matrix of rank $r$ such that every row is distinct and every column is distinct? Case $m=n$ is most interesting.

If not, what are some tricks and strategies to obtain such a matrix of rank $r$?

$\endgroup$

1 Answer 1

3
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .