Let $M$ be an $m \times n$ matrix such that every $M_{ij} \in \{0,1\}$.
We say that $M$ is `$\lor$-irreducible' if (i) no row is a pointwise-or of other rows, and (ii) no column is a pointwise-or of other columns.
For any $M$ there is an obvious polynomial-time algorithm for constructing its "$\lor$-irreducible submatrix" i.e. (1) eliminate the row $r$ if it equals the pointwise-or of all other rows pointwise-below $r$, (2) eliminate columns in the analogous way.
The output is unique modulo reordering of rows and columns. Then my question is:
Are there any known non-trivial algorithms for constructing this $\lor$-irreducible submatrix?
For example, is it possible to efficiently encode it into Gaussian elimination over $GF(2)$?
Background: The translation from $M$ to its $\lor$-irreducible submatrix arises as a natural isomorphism in the sense of category theory. That is, it is the "other side" of the well-known fact that every finite join-semilattice $\mathbb{S}$ embeds into all subsets of its meet-irreducibles $M(\mathbb{S})$ where the join is union.
