1
$\begingroup$

(In this discussion I'm assuming all matrices are binary (0/1-valued).) We say that a matrix $M$ can be covered by another matrix $N$ if every entry in $M$ is either (1) NOT contained in $N$, or (2) contained in a submatrix of $M$ that equals to $N$, up to reordering the columns and rows. Note that if $N$ contains both 0- and 1-entries then condition (1) never holds. Lacking of a better name, let's call a matrix $M$ a self-covering matrix if $M$ can be covered by any submatrix $M'$ of itself, provided that the columns (and likewise the rows) of $M'$ are pairwise distinct.

For example, a zero matrix is vacuously self-covering, and so uninteresting. Thus let's focus only on the case where the columns (and likewise the rows) of $M$ are pairwise distinct.

My questions are: have self-covering matrices been studied before? If yes, what are they called in literature? I came across these matrices during my research but I have little understanding about them. I can construct a nontrivial family of self-covering matrices, but I am wondering if there exists any other. In particular, I am interested to know more about their characteristics, and the sufficient and necessary conditions for a matrix to be self-covering. Any reference or answer is appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ If "all submatrices" include $1\times 1$-submatrices, you won't get anything interesting. $\endgroup$
    – user6976
    Commented Feb 23, 2012 at 13:52
  • $\begingroup$ That's a good point. Thanks, Mark. I subconsciously ignore it when I gave the definition. The definition is now corrected. $\endgroup$ Commented Feb 23, 2012 at 14:14

0

You must log in to answer this question.

Browse other questions tagged .