MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

(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.

share|cite|improve this question
If "all submatrices" include $1\times 1$-submatrices, you won't get anything interesting. – Mark Sapir Feb 23 '12 at 13:52
That's a good point. Thanks, Mark. I subconsciously ignore it when I gave the definition. The definition is now corrected. – Trinh Huynh Feb 23 '12 at 14:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.