\n\\mathbf{v}\\cdot \\mathbf{a}\\geq b\\}$, where\u00a0$\\mathbf{a}$ is a fixed (non-zero) vector, $b$ is a real number,\u00a0and the dot denotes the standard inner product. A polyhedron<\/em> is an intersection of\u00a0finitely many half-spaces.\u00a0A polyhedron is a polytope<\/em> if it is bounded, meaning\u00a0that there there must be some ball of finite radius centred on the origin\u00a0that contains every point of the polytope.\u00a0A vertex<\/em> of a polyhedron is a point\u00a0$\\mathbf{p}$ in the polyhedron with the property that\u00a0some affine hyperplane intersects the polyhedron\u00a0exactly in $\\mathbf{p}$.\u00a0Similarly, an edge<\/em> of a polyhedron is a\u00a0line segment, $l$, such that some affine hyperplane\u00a0intersects the polyhedron exactly in $l$.\u00a0The terminal points of an edge are always vertices\u00a0of the polytope.<\/p>\n
Now let $P$ be a polytope.\u00a0For every edge $l$ of $P$, there is an affine\u00a0hyperplane that is perpendicular to $l$ and that\u00a0passes through the mid-point of $l$. This affine hyperplane determines an isometry\u00a0(a distance-preserving transformation) of\u00a0$\\mathbb{R}^{n}$: namely, reflection through\u00a0the hyperplane.<\/p>\n
What can we say about the group of isometries generated by\u00a0these reflections?\u00a0As the composition of any reflection with\u00a0itself is the identity, this group is a Coxeter group<\/em>, since the definition of\u00a0such a group is that it must have a set of generators\u00a0each of which has order two.\u00a0When will this Coxeter group be finite?\u00a0It is easy to find examples of polytopes that\u00a0lead to finite Coxeter groups:\u00a0just take any regular polygon.\u00a0In this case the reflections generate the dihedral group.\u00a0On the other hand, consider the points with\u00a0polar coordinates $(0,0)$, $(1,-\\alpha)$,\u00a0$(1,\\alpha)$, and $(1,3\\alpha)$, where $\\alpha$\u00a0is an irrational fraction of a full rotation.\u00a0The intersection of all half-spaces that contain these\u00a0four points is a polytope.\u00a0The reflections corresponding to the edges of the polytope\u00a0include the reflection in the horizontal axis,\u00a0and also the reflection in the line with an angle of $2\\alpha$\u00a0from the horizontal.\u00a0Between them, these reflections generate a rotation of $4\\alpha$ around the origin.\u00a0The way that we chose $\\alpha$ means that no finite power of this\u00a0rotation will ever be equal to the identity isometry.\u00a0Therefore the generated Coxeter group is infinite.\u00a0The definition of Coxeter matroids is motivated by a partial solution of this problem\u00a0of determining whether this generated group\u00a0of isometries will be finite or infinite.<\/p>\n We have said that any regular polygon gives rise to a\u00a0finite Coxeter group of isometries. Now let $\\mathbf{a}$ be a fixed and arbitrary vector, and let\u00a0$R^{+}=\\{\\mathbf{u}\\in R\\colon \\mathbf{u}\\cdot\\mathbf{a}>0\\}$ be the\u00a0set of positive roots<\/em>.\u00a0The positive roots generate the positive cone<\/em>, consisting of all\u00a0linear combinations of vectors in $R^{+}$ with all coefficients\u00a0non-negative.\u00a0This positive cone is a polyhedron.\u00a0Those vectors in $R^{+}$ that are parallel with an edge of the\u00a0positive cone form a simple system<\/em> of roots.\u00a0In the following diagram, we have chosen $\\mathbf{a}$ to be\u00a0the vector $(1,0)$.\u00a0There are three positive roots, and they generate the shaded\u00a0positive cone. The two vectors coloured red form the corresponding simple\u00a0system.<\/p>\n Let $I$ be the simple system of roots, and let $J$ be a non-empty subset\u00a0of $I$.\u00a0The roots in $J$ correspond to a collection of reflections in $W$.\u00a0Let $P$ be the subgroup of $W$ generated by these reflections.\u00a0This subgroup is called a standard parabolic subgroup<\/em> of $W$.\u00a0In our example, let $P$ be the subgroup generated by the\u00a0reflection along the line parallel to $(1,1)$, that is, the reflection corresponding to the blue vector in the diagram below. Let $\\mathcal{M}$ be a collection of cosets of $P$.\u00a0In our example, we will keep things simple, and just let $\\mathcal{M}$ be the\u00a0collection of all cosets.\u00a0We choose a point $\\mathbf{v}$ that is fixed by $P$.\u00a0For every coset $wP$ in $\\mathcal{M}$, we find the image of\u00a0$\\mathbf{v}$ under $w$.\u00a0Note that this image is well-defined, in the sense that it does not depend on\u00a0the representative $w$, since $\\mathbf{v}$ will be fixed by every isometry in $P$.\u00a0Now we have generated a collection of images of $\\mathbf{v}$. We construct the convex hull of these images: that is,\u00a0we take the polytope consisting of the intersection of all half-spaces that\u00a0contain the images of $\\mathbf{v}$.\u00a0It turns out that the Coxeter group generated by the edges of this\u00a0polytope is finite (a subgroup of $W$ in fact).\u00a0In the diagram below, the vector $\\mathbf{v}$ is marked.\u00a0There are four images of $\\mathbf{v}$ under cosets of $P$, and the\u00a0convex hull of those images is the shaded square.<\/p>\n What is surprising about this construction, is that every polytope\u00a0generating a finite Coxeter group can essentially be constructed in this way.\u00a0This is a consequence of a theorem due to Gelfand and Serganova\u00a0(details are in the book Coxeter matroids<\/em>). In this post I’m going to conclude my investigation\u00a0of Coxeter matroids and related objects. We can motivate the definition of Coxeter matroids by\u00a0thinking about a geometrical problem in the Euclidean space\u00a0$\\mathbb{R}^{n}$.\u00a0Recall that a (closed) half-space is a set of the … Continue reading ![\"Coxeter-1\"](\"https:\/\/matroidunion.org\/wp-content\/uploads\/2013\/11\/Coxeter-1.png\")
<\/a><\/p>\n
\nLet us now develop another method for finding such polytopes.\u00a0Let $W$ be a finite group of isometries of $\\mathbb{R}^{n}$ and assume that\u00a0$W$ is generated by a collection of reflections.\u00a0We will show that there is a point that is fixed by every isometry in $W$.\u00a0Indeed, if $\\mathbf{v}\\in \\mathbb{R}^{n}$ is arbitrarily chosen,\u00a0then the barycentre of the images of $\\mathbf{v}$ is fixed by every isometry in\u00a0$W$, because
\n\\[
\nu\\left(\\frac{1}{|W|}\\sum_{w\\in W}w(\\mathbf{v})\\right)
\n= \\frac{1}{|W|}\\sum_{w\\in W}u(w(\\mathbf{v}))
\n= \\frac{1}{|W|}\\sum_{w\\in W}w(\\mathbf{v})
\n\\]
\nfor every $u\\in W$.\u00a0Therefore, by translating, we might as well assume that the reflections that\u00a0generate $W$ all fix the origin.\u00a0For each reflection $r\\in W$, choose two vectors, $\\mathbf{v}_{r}$ and\u00a0$-\\mathbf{v}_{r}$ that are orthogonal to the $r$-invariant hyperplane. Thus $r(\\pm\\mathbf{v}_{r})=\\mp\\mathbf{v}_{r}$.\u00a0We shall call the collection $R=\\{\\pm \\mathbf{v}_{r}\\colon r\\ \\text{is a reflection in}\\ W\\}$\u00a0a root system<\/em> of $W$.\u00a0Note that the vectors in $R$ correspond in a natural way to the reflections in $W$.\u00a0We have given no consideration to the length of the vectors\u00a0$\\mathbf{v}_{r}$, which means that we are not using the\u00a0standard definition<\/a> of a root system.\u00a0This diagram shows a possible root system in $2$ dimensions.<\/p>\n<\/a><\/p>\n<\/a><\/p>\n<\/a><\/p>\n
\nSo far, the link to matroids is not at all obvious, so I will conclude by\u00a0drawing a connection back to my first post<\/a>.\u00a0Let $w_{1},\\ldots, w_{t}$ be the reflections in $W$ that correspond to the\u00a0vectors in a simple root system.\u00a0Then $W$ is generated by $w_{1},\\ldots, w_{t}$, so every\u00a0$u\\in W$ can be expressed as a word in these reflections.\u00a0Such a word is said to be reduced<\/em> if it is as short as possible.\u00a0Now for $u,v\\in W$ we say that $v\\leq u$ in the Bruhat ordering<\/em>\u00a0if there is a reduced word that represents $u$, with the property that\u00a0I can obtain a word representing $v$ by deleting some characters.\u00a0If $w\\in W$, then we write $v\\leq^{w} u$ to mean $w^{-1}v\\leq w^{-1}u$.\u00a0If $A$ and $B$ are cosets, then $A\\leq^{w} B$ means that $v\\leq^{w} u$ for some representatives $v\\in A$ and $u\\in B$. The connection to matroids comes from the collection $\\mathcal{M}$ of cosets.\u00a0In our construction, $\\mathcal{M}$ has the following property:\u00a0if $w$ is any reflection in $W$, then there is a coset $B\\in \\mathcal{M}$\u00a0with the property that $A\\leq^{w} B$ for all $A\\in \\mathcal{M}$.\u00a0Now the resemblance to matroids, as axiomatised via Gale’s Theorem,\u00a0is quite striking.\u00a0The cosets in $\\mathcal{M}$ play the role of bases in Gale’s Theorem.\u00a0Now we can finally give the definition of a Coxeter matroid, which is justified by this resemblance to Gale’s axiomatization. If $W$ is a Coxeter group with $P$ as a parabolic subgroup, and $\\mathcal{M}$ is a collection of cosets, then $\\mathcal{M}$ is a Coxeter matroid if, for every $w\\in W$, there is a coset $B\\in \\mathcal{M}$ such that $A\\leq^{w} B$ for all $A\\in \\mathcal{M}$.<\/p>\n","protected":false},"excerpt":{"rendered":"