Skip to main content
Post Made Community Wiki by Benjamin Steinberg
added 26 characters in body
Source Link
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

Here is an algebraic proof inspired by Hugh's argument and ideas I had before asking this question. Please upvote his answer. First I need to slightly correct Question 1 to ask if any non-zero functional $\phi$ is of the form $x\to x_e$ or $x\to -x_e$ (that is, one may need to reorient the matroid).

First of all, we may assume without loss of generality that $\mathcal L$ has no loops, i.e., that there is no $e$ with $x_e=0$ for all $x\in \mathcal L$. Covectors $x$ with $x_e\neq 0$ for all $e\in E$ are called topes. If $T$ is a tope, then $T\circ x =T$ for all $x\in \mathcal L$ and so if $\phi(T)=0$, we obtain $\phi(x)=0$ for all $x\in \mathcal L$. Thus $\phi(T)\neq 0$ for all topes $T$. If $\mathcal T$ is the set of topes, we have $\phi(\mathcal T)=\lbrace+,-\rbrace$ because $\mathcal T=-\mathcal T$.

The tope graph of $\mathcal L$ is the graph with $\mathcal T$ as the set of vertices and where there is an edge frombetween $T$ toand $T'$ if $|S(T,T')|=1$. It is knowknown that the tope graph is connected and that the distance between two topes $T_1,T_2$ in this graph is exactly $|S(T_1,T_2)|$. Notice that there must be adjacent topes $T,T'$ with $\phi(T)=-\phi(T')$. Indeed, fix $T_0\in \mathcal T$ with $\phi(T_0)=+$ and let $p$ be a geodesic path from $T_0$ to $-T_0$. As $\phi(-T_0)=-$, there must be an edge of $p$ whose vertices have opposite signs.

Let $S(T,T')=e$. Replacing $\phi$ by $-\phi$ if necessary, we may assume $\phi(T)=+=T_e$ and $\phi(T') =-=T'_e$. Note that $T_f=T'_f$ for $f\neq e$. We claim that $\phi=\phi_e$, where $\phi_e(x)=x_e$. By axiom 4 there exists $z\in \mathcal L$ with $z_e=0$ and $z_f=T_f=T'_f$ for $f\neq e$. Note $z\circ T=T$ and $z\circ T'=T'$ and so $\phi(z)=0$.

Now let $x\in \mathcal L$. If $x_e=0$, then $z\circ x=z$ and so $\phi_e(x)=0=\phi(z)=\phi(z)\circ \phi(x)=\phi(x)$.

If If $x_e=+$, then $z\circ x=T$ and so $\phi_e(x)=+=\phi(T)=\phi(z)\circ \phi(x) =\phi(x)$. The same argument shows that if $x_e=-$, then $\phi(x)=-$. Thus $\phi=\phi_e$.

Here is an algebraic proof inspired by Hugh's argument and ideas I had before asking this question. Please upvote his answer. First I need to slightly correct Question 1 to ask if any non-zero functional $\phi$ is of the form $x\to x_e$ or $x\to -x_e$ (that is, one may need to reorient the matroid).

First of all, we may assume without loss of generality that $\mathcal L$ has no loops, i.e., that there is no $e$ with $x_e=0$ for all $x\in \mathcal L$. Covectors $x$ with $x_e\neq 0$ for all $e\in E$ are called topes. If $T$ is a tope, then $T\circ x =T$ for all $x\in \mathcal L$ and so if $\phi(T)=0$, we obtain $\phi(x)=0$ for all $x\in \mathcal L$. Thus $\phi(T)\neq 0$ for all topes $T$. If $\mathcal T$ is the set of topes, we have $\phi(\mathcal T)=\lbrace+,-\rbrace$ because $\mathcal T=-\mathcal T$.

The tope graph of $\mathcal L$ is the graph with $\mathcal T$ as the set of vertices and where there is an edge from $T$ to $T'$ if $|S(T,T')|=1$. It is know that the distance between two topes $T_1,T_2$ in this graph is exactly $|S(T_1,T_2)|$. Notice that there must be adjacent topes $T,T'$ with $\phi(T)=-\phi(T')$. Indeed, fix $T_0\in \mathcal T$ with $\phi(T_0)=+$ and let $p$ be a geodesic path from $T_0$ to $-T_0$. As $\phi(-T_0)=-$, there must be an edge of $p$ whose vertices have opposite signs.

Let $S(T,T')=e$. Replacing $\phi$ by $-\phi$ if necessary, we may assume $\phi(T)=+=T_e$ and $\phi(T') =-=T'_e$. Note that $T_f=T'_f$ for $f\neq e$. We claim that $\phi=\phi_e$, where $\phi_e(x)=x_e$. By axiom 4 there exists $z\in \mathcal L$ with $z_e=0$ and $z_f=T_f=T'_f$ for $f\neq e$. Note $z\circ T=T$ and $z\circ T'=T'$ and so $\phi(z)=0$.

Now let $x\in \mathcal L$. If $x_e=0$, then $z\circ x=z$ and so $\phi_e(x)=0=\phi(z)=\phi(z)\circ \phi(x)=\phi(x)$.

If $x_e=+$, then $z\circ x=T$ and so $\phi_e(x)=+=\phi(T)=\phi(z)\circ \phi(x) =\phi(x)$. The same argument shows that if $x_e=-$, then $\phi(x)=-$. Thus $\phi=\phi_e$.

Here is an algebraic proof inspired by Hugh's argument and ideas I had before asking this question. Please upvote his answer. First I need to slightly correct Question 1 to ask if any non-zero functional $\phi$ is of the form $x\to x_e$ or $x\to -x_e$ (that is, one may need to reorient the matroid).

First of all, we may assume without loss of generality that $\mathcal L$ has no loops, i.e., that there is no $e$ with $x_e=0$ for all $x\in \mathcal L$. Covectors $x$ with $x_e\neq 0$ for all $e\in E$ are called topes. If $T$ is a tope, then $T\circ x =T$ for all $x\in \mathcal L$ and so if $\phi(T)=0$, we obtain $\phi(x)=0$ for all $x\in \mathcal L$. Thus $\phi(T)\neq 0$ for all topes $T$. If $\mathcal T$ is the set of topes, we have $\phi(\mathcal T)=\lbrace+,-\rbrace$ because $\mathcal T=-\mathcal T$.

The tope graph of $\mathcal L$ is the graph with $\mathcal T$ as the set of vertices and where there is an edge between $T$ and $T'$ if $|S(T,T')|=1$. It is known that the tope graph is connected and that the distance between two topes $T_1,T_2$ is exactly $|S(T_1,T_2)|$. Notice that there must be adjacent topes $T,T'$ with $\phi(T)=-\phi(T')$. Indeed, fix $T_0\in \mathcal T$ with $\phi(T_0)=+$ and let $p$ be a geodesic path from $T_0$ to $-T_0$. As $\phi(-T_0)=-$, there must be an edge of $p$ whose vertices have opposite signs.

Let $S(T,T')=e$. Replacing $\phi$ by $-\phi$ if necessary, we may assume $\phi(T)=+=T_e$ and $\phi(T') =-=T'_e$. Note that $T_f=T'_f$ for $f\neq e$. We claim that $\phi=\phi_e$, where $\phi_e(x)=x_e$. By axiom 4 there exists $z\in \mathcal L$ with $z_e=0$ and $z_f=T_f=T'_f$ for $f\neq e$. Note $z\circ T=T$ and $z\circ T'=T'$ and so $\phi(z)=0$.

Now let $x\in \mathcal L$. If $x_e=0$, then $z\circ x=z$ and so $\phi_e(x)=0=\phi(z)=\phi(z)\circ \phi(x)=\phi(x)$. If $x_e=+$, then $z\circ x=T$ and so $\phi_e(x)=+=\phi(T)=\phi(z)\circ \phi(x) =\phi(x)$. The same argument shows that if $x_e=-$, then $\phi(x)=-$. Thus $\phi=\phi_e$.

Source Link
Benjamin Steinberg
  • 38.6k
  • 3
  • 104
  • 186

Here is an algebraic proof inspired by Hugh's argument and ideas I had before asking this question. Please upvote his answer. First I need to slightly correct Question 1 to ask if any non-zero functional $\phi$ is of the form $x\to x_e$ or $x\to -x_e$ (that is, one may need to reorient the matroid).

First of all, we may assume without loss of generality that $\mathcal L$ has no loops, i.e., that there is no $e$ with $x_e=0$ for all $x\in \mathcal L$. Covectors $x$ with $x_e\neq 0$ for all $e\in E$ are called topes. If $T$ is a tope, then $T\circ x =T$ for all $x\in \mathcal L$ and so if $\phi(T)=0$, we obtain $\phi(x)=0$ for all $x\in \mathcal L$. Thus $\phi(T)\neq 0$ for all topes $T$. If $\mathcal T$ is the set of topes, we have $\phi(\mathcal T)=\lbrace+,-\rbrace$ because $\mathcal T=-\mathcal T$.

The tope graph of $\mathcal L$ is the graph with $\mathcal T$ as the set of vertices and where there is an edge from $T$ to $T'$ if $|S(T,T')|=1$. It is know that the distance between two topes $T_1,T_2$ in this graph is exactly $|S(T_1,T_2)|$. Notice that there must be adjacent topes $T,T'$ with $\phi(T)=-\phi(T')$. Indeed, fix $T_0\in \mathcal T$ with $\phi(T_0)=+$ and let $p$ be a geodesic path from $T_0$ to $-T_0$. As $\phi(-T_0)=-$, there must be an edge of $p$ whose vertices have opposite signs.

Let $S(T,T')=e$. Replacing $\phi$ by $-\phi$ if necessary, we may assume $\phi(T)=+=T_e$ and $\phi(T') =-=T'_e$. Note that $T_f=T'_f$ for $f\neq e$. We claim that $\phi=\phi_e$, where $\phi_e(x)=x_e$. By axiom 4 there exists $z\in \mathcal L$ with $z_e=0$ and $z_f=T_f=T'_f$ for $f\neq e$. Note $z\circ T=T$ and $z\circ T'=T'$ and so $\phi(z)=0$.

Now let $x\in \mathcal L$. If $x_e=0$, then $z\circ x=z$ and so $\phi_e(x)=0=\phi(z)=\phi(z)\circ \phi(x)=\phi(x)$.

If $x_e=+$, then $z\circ x=T$ and so $\phi_e(x)=+=\phi(T)=\phi(z)\circ \phi(x) =\phi(x)$. The same argument shows that if $x_e=-$, then $\phi(x)=-$. Thus $\phi=\phi_e$.