# total order on finite dimensional vector space over $\mathbb{R}$

We know that, If we start with a basis of a finite dimensional vector space $V$ over $\mathbb{R}$ by using lexicographic ordering with respect to that basis, we have a total ordering $\lt$ on $V$ satisfying,

i) $v \in V, v_1 \lt v_2 \implies v_1 + v \lt v_2 + v$

ii) $\alpha \in \mathbb{R}, v_1 \lt v_2 \implies$

a) $\alpha v_1 \lt \alpha v_2$ if $\alpha \gt 0$

b) $\alpha v_1 \gt \alpha v_2$ if $\alpha \lt 0$

I just wondering, given a such a total ordering on $V$ , can we find a basis of $V$ with respect to which the lexicographic order will be the same as the one we start with?

is there any similar theory of infinite dimensional vector spaces?

• I would conjecture that for sucn an order, there is a subspace $U$ of codimension one (a hyperplane) so that all vectors to one side of $U$ are $>0$, and all vectors on the other side are $<0$. If so, you just pick the first vector of your basis on the positive side of $U$, then proceed inductively by doing the same thing in $U$. – Harald Hanche-Olsen May 10 '14 at 10:54
• @HaraldHanche-Olsen cant we find that $U$ explicitly or prove its existence?. Then the problem is over as you remarked. Is it really a conjecture? – GA316 May 10 '14 at 10:58
• See the answer by @Hans below. Yes, it was a conjecture in the sense that I was pretty sure that is how it goes, but I didn't have the time to cobble together a proof – so I could have been wrong, but as it turns out, I wasn't. – Harald Hanche-Olsen May 10 '14 at 15:57

Let $<$ be such a total ordering on $V$ (which is, as in the question, finite dimensional). Then the set $C=\{v \in V: v\geq 0\}$ clearly is a convex cone. Since $C \cap (-C) =\{0\}$ and since $V=(-C) \cup C$ there is a $v_0 \in V$ which does not lie in the closure of $C$. Thus there is a nonzero linear form $l$ on $V$ such that $l \geq 0$ on $C$ (see below in "edit"). Now the zero set of $l$ is a hyperplane as Harald thought of:

Let $l(v)<0$ then $v \not\in C$ thus $v<0$.

Let $l(v)>0$ and assume $v \leq 0$ then $-v \in C$ which contradicts $l(-v)<0$.

edit: This follows from biduality of convex cones, see http://arxiv.org/abs/1006.4894 (section 2.1): Assume that $C^*=\{0\}$ (notation as in the paper), then we have $V=\{0\}^*=(C^*)^*=\textrm{cl}(C)$, but we have $V \neq \textrm{cl}(C)$ ($\textrm{cl}(C)$ is the closure of $C$).

I expect that you can find the proof of this biduality theorem (which uses the separation theorem that I mentioned in the first place) in a standard book about convexity, for example in Barvinok's "A First Course in Convexity".

• what is separation theorem for convex cones? any reference. In google search I couldnt find much. thanks. – GA316 May 10 '14 at 12:04
• please see the edit... – Hans May 10 '14 at 14:07
• Unfortunately there extsts a counterexample to the hyperplane assumption. – Keinstein May 11 '14 at 20:34
• but not in the case of $V$ finite dimensional, which is part of the assumptions in the original question. but perhaps I should mention it in my answer again... – Hans May 12 '14 at 9:19
• Ok. Then you should mention that this is well known as Hahn's theorem in the finite case. There are many introductory books about lattice-ordered should contain it. – Keinstein May 13 '14 at 16:18

In case of an infinite dimensional vector space there exists a basis that represents the order.

Nevertheless the separating “Hyperplane” may be the whole vector space itself. For example take $\mathbb{R}^{\mathbb N}$ with the natural orders on $\mathbb R$ and $\mathbb N$. In this vector space every vector is infinitesimal with respect to some other vector. If there were a hyperplane that separates the positive cone and the negative cone, then there would have been a vector that is not infinetesimal with respect to any other vectors.

This topic is discussed in this article.