I asked this question on Mathematics Stackexchange, but got no answer.

Let $K$ be a field and $n$ a positive integer. To a finite dimensional $K$-vector space $V$, equipped with a family $V_1,\dots,V_n$ of subspaces, we attach the map $d:\mathcal P(\{1,\dots,n\})\to\mathbb N$ defined by $$ d(S)=\dim\left(\bigcap_{s\in S}V_s\right). $$ [Here $\mathcal P(\{1,\dots,n\})$ denotes the set of subsets of $\{1,\dots,n\}$.] Then we have

$(1)\quad S\subset T\implies d(S)\ge d(T)$,

$(2)\quad d(S\cap T)\ge d(S)+d(T)-d(S\cup T)$

for all $S,T\in\mathcal P(\{1,\dots,n\})$. [Here $S\subset T$ means that each element of $S$ belongs to $T$.]

Conversely, given $d:\mathcal P(\{1,\dots,n\})\to\mathbb N$ satisfying $(1)$ and $(2)$, is there a family $(V,V_1,\dots,V_n)$ as above inducing $d$ in the way just described?

The answer is No in general, a counterexample being given as follows: $K=\mathbb F_2, n=4$, $$ d(\varnothing)=2=\dim V,\quad d(\{i\})=1=\dim V_i, $$ and $d(S)=0$ if $S$ has at least two elements. [We use the fact that there are only three lines through the origin in $\mathbb F_2^2$.] There is an obvious analog for any finite field.

In view of the above observations, it seems natural to ask:

Assume that our field $K$ is infinite, and that $d:\mathcal P(\{1,\dots,n\})\to\mathbb N$ satisfies $(1)$ and $(2)$. Is there a family $(V,V_1,\dots,V_n)$ as above such that $$ d(S)=\dim\left(\bigcap_{s\in S}V_s\right) $$ for all $S\ ?$


I find this easier to think about if we dualize everything: replace $d(S)$ with $\dim V - d(S)$ and each subspace with its annihilator in $V'$. Recall that the annihilator of a sum is the intersection of the annihilators. Thus your question is the following:

Assume $d:\mathcal{P}(\{1,\dots,n\}) \to \mathbb{N}$ is increasing and submodular (this is just the cool name for the condition $d(S \cup T) + d(S\cap T) \leq d(S) + d(T)$) and satisfies $d(\emptyset)=0$ and $d(\{1,\dots,n\}) \leq \dim V$. Then does there exists a collection of subspaces $V_i$ of $V$ such that $\dim \sum_{i \in S} V_i = d(S)$ for each $S \subset \{1,\dots,n\}$?

If we further assume that $d(\{x\}) \leq 1$ for each $x$ then this is exactly one of the equivalent definitions of a matroid, and your question is whether every matroid is linear. Apparently the answer is no.

  • 7
    $\begingroup$ And the keyword to search for is "representable polymatroid". There are some additional inequalities beyond submodularity e.g. in this paper. For example, any four subspaces must satisfy the Ingleton inequality. $\endgroup$ Jun 25 '18 at 7:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.