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
    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$ Feb 23, 2012 at 14:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.