Skip to main content
2 of 2
added 916 characters in body
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

Let $A$ be an $m\times n$ Boolean matrix. Then the mapping $v\mapsto Av$ is 1:1 iff $n\leq m$ and some subset of $n$ rows of gives a permutation matrix.

The reason is duality of modules over the Boolean semiring shows that $A$ is 1:1 iff the transpose is onto. Since the standard basis vectors of a free $\mathbb B$-module are join irreducible a Boolean matrix gives an onto map iff each standard basis vector appears as a column.

Added per request for more detail.

A $\mathbb B$-module is the same thing as a join-semilattice $M$. The dual $M^*$ is the set of all join-semilattice homomorphisms $M\to \mathbb B$ with pointwise join. If $M$ is finite, then the dual consists of the mappings $f_m$ with $m\in M$ where $f_m(x)=0$ if $x\leq m$ and $1$ else. Indeed, choose $m$ to be the join of all elements mapping to $0$.

It follows if $N$ is a submodule of $M$ then the restriction $M^*\to N^*$ is surjective. Also the canonical map to the double dual is an ISO for $M$ finite. It now follows a map of finite $\mathbb B$-modules is injective iff the dual map is surjective. For a matrix map the dual is the transpose.

If we view $\mathbb B^n$ as a join semilattice, the basis consists of atoms. It follows a matrix transformation is onto iff each basis vector appears in some column. Dualizing gives the result.

Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186