Skip to main content
2 of 2
edited title

Characterizing bases of 0-1-vectors in $\mathbb{R}^n$ in terms of their partial order

Given $n \in \mathbb{N}$ and $V \subseteq \{0,1\}^n$, can properties of $V$ with respect to the vector space $\mathbb{R}^n$ (not $\mathbb{Z}_2^n$),

  • $V$ is linearly independent
  • $\dim \mathrm{span} V = n$,

be characterized as properties of the poset $(V, \preceq)$ such that

$$\forall v,w \in \{0,1\}^n: \quad (v_1, \ldots, v_n) \preceq (w_1, \ldots, w_n) \quad \Leftrightarrow \quad \forall j \in [n]:\ v_j \leq w_j \enspace ,$$

a subposet of the lattice $(\{0,1\}^n, \preceq) := L$?

Motivation: The canonical basis consists of the atoms of $L$. The hierarchical basis is a chain in (the Hasse diagram of) $L$.