0
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ No. Already for $n=1$, the posets for $V=\{0\}$ and $V=\{1\}$ are isomorphic. $\endgroup$
    – Emil Jeřábek
    Commented May 15, 2014 at 13:01
  • $\begingroup$ Is the question as trivial if we consider affine independence instead of linear independence? $\endgroup$
    – Max Flow
    Commented May 15, 2014 at 17:23
  • $\begingroup$ Well, $\{(0,0,0),(0,0,1),(0,1,0),(1,1,1)\}$ is affinely independent, $\{(0,0,0),(0,0,1),(0,1,0),(0,1,1)\}$ is dependent, and they have the same poset. $\endgroup$
    – Emil Jeřábek
    Commented May 15, 2014 at 18:47
  • $\begingroup$ Thanks for answering this question. I suppose the problem is more interesting if we consider, in your 2nd example, that the two (isomorphic) posets are different subposets of the lattice $L$. Can we characterize affine independence of $V$ in $\mathbb{R}^n$ by a property of the subposet $(V,\preceq)$ of the lattice $L$? Consider, for instance, a simple necessary condition: If there exist $U \subseteq V$ and $v \in V \setminus U$ such that $\sup U = v$ and $\forall u,u' \in U: \inf(u,u') = \emptyset$ then $U$ is lin. dependent because $\sum_{u \in U} u = v$. Is there an if-and-only-if-condition? $\endgroup$
    – Max Flow
    Commented Jun 23, 2014 at 10:50

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .