The following question appears trivial, but it's outside my limited experience so I'd appreciate a little feedback.

A total order on a real vector space $V$ is a total ordering on its vectors which is invariant under translation and positive scalar multiples, i.e. a transitive relation $<$ on $V$ such that

  1. If $v, w \in V$ with $v \neq w$, then either $v < w$ or $w > v$
  2. If $v, w, u \in V$ with $v < w$, then $v + u < w + u$.
  3. If $v, w \in V$ with $v < w$ and $c > 0$ then $cv < cw$.

If $>$ is a total order on $V$ and $0 \neq v \in V$, then if $v > 0$ we must have $0 > -v$ by translation invariance, and symmetrically, so for every nonzero $v$ we have precisely one of $v > 0$ or $-v > 0$.

Consider the following argument:

Suppose $>$ is a total order on an $n$-dimensional real vector space $V$. Equip $V$ with an arbitrary inner product $(-,-)$. For each $v$ either $v > 0$ or $-v > 0$, so there is some hyperplane in $V$ which has positive elements on one side and negative elements on the other. There are two unit normals to this hyperplane, one positive and one negative. Let $v_1$ indicate the positive one. Apply this same procedure to the hyperplane itself to get $v_2$, and continue. When this procedure terminates, we're left with a uniquely-determined orthonormal basis for $V$. On the other hand, if we are given an orthonormal basis for $V$, taking the lexicographic ordering on $V$ with respect to this basis inverts this construction. Consequently, the total orders on $V$ are parametrized by the Stiefel manifold $V_n(V, (-,-))$.


  1. Does this work? Something about taking an arbitrary inner product makes me feel a little uneasy here, but I can't see anything actually wrong with the proof, except that I am a little unsure as to how to cleanly show that the fact that $v > 0$ or $-v > 0$ implies there is a hyperplane with only positive vectors on one side and only negative vectors on the other. Further, it doesn't help that Google doesn't seem to turn up any reference to this fact, which seems like it should be a natural thing to remark on were it true.
  2. The only reason I have to use the inner product is to specify orientation. There doesn't seem to be a similarly clean way of doing something like this using a flag manifold -- you'd have to specify an arbitrary positive vector at each step, rather than having one uniquely determined for you. Is there a nice way of dealing with orientation without explicitly dealing with angles?
  3. Is there a book I could read that make questions like this appear trivial once I'd finished?

Thanks in advance!

  • $\begingroup$ What vectors would belong to your hyperplane? $0$ is the only vector that is neither $>0$ nor $<0$. $\endgroup$ – Brian M. Scott Sep 19 '11 at 2:15
  • $\begingroup$ Right, that's why I need an entire orthonormal basis to specify the ordering, rather than just a single normal vector. So e.g. if I take $\mathbb{R}^2$ with the lex order, then the first hyperplane is the y-axis, and the normal is (1, 0). The second hyperplane is then the origin (considered as a subspace of the y-axis), with normal (0, 1). $\endgroup$ – Daniel McLaury Sep 19 '11 at 2:38
  • $\begingroup$ Ah, okay: you didn't actually mean that the hyperplane separates the positive and negative vectors, as you said in (1); you just meant that everything on one side was positive and everything on the other side negative. $\endgroup$ – Brian M. Scott Sep 19 '11 at 2:55
  • $\begingroup$ Fixed, thanks. Any thoughts on the revised question? $\endgroup$ – Daniel McLaury Sep 19 '11 at 3:31
  • $\begingroup$ In (2) do you mean U < W as the first inequality? $\endgroup$ – zyx Sep 30 '11 at 20:01

Let $P$ be the positive cone, and let $N = -P$. Clearly $P$ and $N$ are disjoint convex sets in V. If $C$ is a convex set, its relative interior is its interior relative to its affine hull. Both $P$ and $N$ have $V$ as affine hull, so their relative interiors are their interiors in $V$. Obviously these are disjoint, so the existence of your hyperplane follows from the finite-dimensional separating hyperplane theorem (Theorem 11 of these notes):

Two non-empty convex sets in $\mathbb{R}^n$ can be properly separated by a hyperplane if and only if their relative interiors are disjoint.

(Properly separated is defined early in the notes and is what you need. Relative interiors of convex sets are discussed briefly in Appendix B of the notes.)

It seems to me that as long as you’re looking only at finite-dimensional real vector spaces, you might as well be looking at $\mathbb{R}^n$ and using the usual inner product to define the hyperplane. So far as I can, there’s then no problem with your recursive construction of an orthonormal basis $B$ such that $<$ is the lexicographic order on the coordinate $n$-tuples relative to $B$.

This is all pretty far from any of my usual mathematical haunts, so I can’t direct you to any books that I know to be useful; the notes that I found have references to a couple of books on convex analysis that might be helpful.


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.