Properties of binary matrix whose entries are subset inclusion

56 Views Asked by At

The setting

Consider a family of matrices of dimensions dimensions $2^d \times 2^d$, with entries:

$$ A_{ij} = \begin{cases} 1 & \text{if}~(i ~\land~ j) = i\\ 0 & \text{otherwise} \\ \end{cases} $$

where $(\land)$ is bitwise-AND.

That is, if we interpret $i$ and $j$ as the characteristic vectors for subsets subset of size $d$, then:

$$A_{ij} = 1 \iff i \subseteq j$$

An example

For example, in the 2-D case:

2x2
---
⎡1  1⎤  // emptyset in {*} | {*} in {*}
⎢    ⎥
⎣0  1⎦  //emptyset in emptyset, | {*} notin emptyset

This matrix corresponds to subsets of the set $\{ * \}$.

  • the row $[1, 1]$ corresponds to the subset $\{ * \}$, since $\{ * \} \subseteq \{ * \}$, $\emptyset \subseteq \{ * \}$,

  • the row $[0, 1]$ correspond to the subset $\emptyset$, since $\emptyset \not \subseteq \{ * \}$, $\emptyset \subseteq \emptyset$, .

The question

What is the name for this matrix? Experiments seem to indicate that it has all $1$ eigenvalues, is full-rank, non-diagonalizable.

Do its eigenvalues mean something?

Experiments

Experimentally, here are the first few:

4x4
----

⎡1  1  1  1⎤
⎢          ⎥
⎢0  1  0  1⎥
⎢          ⎥
⎢0  0  1  1⎥
⎢          ⎥
⎣0  0  0  1⎦
8x8
---
⎡1  1  1  1  1  1  1  1⎤
⎢                      ⎥
⎢0  1  0  1  0  1  0  1⎥
⎢                      ⎥
⎢0  0  1  1  0  0  1  1⎥
⎢                      ⎥
⎢0  0  0  1  0  0  0  1⎥
⎢                      ⎥
⎢0  0  0  0  1  1  1  1⎥
⎢                      ⎥
⎢0  0  0  0  0  1  0  1⎥
⎢                      ⎥
⎢0  0  0  0  0  0  1  1⎥
⎢                      ⎥
⎣0  0  0  0  0  0  0  1⎦