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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.