[math-fun] Algorithm for computing linear representation of a Coxeter group?
Given a presentation of a Coxeter group with n generators, what's the most straightforward algorithm for producing a set of n matrices that satisfy the same relations? -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Are you seeking a representation by finite matrices over the reals? How do you know that a representation of the desired type exists? Any proof of existence for the groups you're interested in would probably implicitly provide an algorithm for construction, though the dimension might be impracticably large: cf. the standard proof for the finite order case. Or if you have a reflection group, presumably you can just pull up a subgroup of the appropriate Lie group: there are online tables of such things. [This is not an area in which I can claim any special expertise: maybe somebody else out there can cast more light?] WFL On 11/28/12, Mike Stay <metaweta@gmail.com> wrote:
Given a presentation of a Coxeter group with n generators, what's the most straightforward algorithm for producing a set of n matrices that satisfy the same relations?
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Wed, Nov 28, 2012 at 10:54 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Are you seeking a representation by finite matrices over the reals? How do you know that a representation of the desired type exists?
I don't. There's something about a "canonical linear representation" in the Wikipedia article http://en.wikipedia.org/wiki/Coxeter_complex#The_canonical_linear_representa... that suggests to me that such a thing is possible, but I don't quite understand it yet. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
The canonical representation works by defining the basis vectors to have whatever inner products you want them to have in order to satisfy the Coxeter relationships you're given. You end up with a vector space and a metric, but the metric is presumably not going to have any nice properties. --Michael On Wed, Nov 28, 2012 at 2:05 PM, Mike Stay <metaweta@gmail.com> wrote:
On Wed, Nov 28, 2012 at 10:54 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
Are you seeking a representation by finite matrices over the reals? How do you know that a representation of the desired type exists?
I don't. There's something about a "canonical linear representation" in the Wikipedia article
http://en.wikipedia.org/wiki/Coxeter_complex#The_canonical_linear_representa... that suggests to me that such a thing is possible, but I don't quite understand it yet. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
On Wed, Nov 28, 2012 at 11:12 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
The canonical representation works by defining the basis vectors to have whatever inner products you want them to have in order to satisfy the Coxeter relationships you're given. You end up with a vector space and a metric, but the metric is presumably not going to have any nice properties.
So, I suppose I'd have to do something involving the Gram-Schmidt procedure to get an orthonormal basis in order to encode the reflections into matrices... -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
On Nov 29, 2012, at 1:56 AM, Mike Stay <metaweta@gmail.com> wrote:
On Wed, Nov 28, 2012 at 11:12 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
The canonical representation works by defining the basis vectors to have whatever inner products you want them to have in order to satisfy the Coxeter relationships you're given. You end up with a vector space and a metric, but the metric is presumably not going to have any nice properties.
So, I suppose I'd have to do something involving the Gram-Schmidt procedure to get an orthonormal basis in order to encode the reflections into matrices...
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
You get the reflection-vectors directly from the Cholesky decomposition of their Gram matrix (matrix of inner products). Since the latter has only rational elements in the case of Coxeter groups, the Cholesky vectors will at worst have square roots. Forming reflection matrices from the vectors is of course automatic. -Veit
If you define a Coxeter group as one with a finite presentation [x_j | x_j^2 = (x_j x_k)^(m_jk) = 1, 1 <= j,k <= n] (where m_jk is allowed to be oo, meaning x_j x_k is infinite order) then I understand that sometimes this group cannot be represented as a reflection group. --Dan On 2012-11-29, at 5:01 AM, Veit Elser wrote:
On Nov 29, 2012, at 1:56 AM, Mike Stay <metaweta@gmail.com> wrote:
On Wed, Nov 28, 2012 at 11:12 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
The canonical representation works by defining the basis vectors to have whatever inner products you want them to have in order to satisfy the Coxeter relationships you're given. You end up with a vector space and a metric, but the metric is presumably not going to have any nice properties.
So, I suppose I'd have to do something involving the Gram-Schmidt procedure to get an orthonormal basis in order to encode the reflections into matrices...
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
You get the reflection-vectors directly from the Cholesky decomposition of their Gram matrix (matrix of inner products). Since the latter has only rational elements in the case of Coxeter groups, the Cholesky vectors will at worst have square roots. Forming reflection matrices from the vectors is of course automatic.
On Thu, Nov 29, 2012 at 1:56 AM, Mike Stay <metaweta@gmail.com> wrote:
On Wed, Nov 28, 2012 at 11:12 AM, Michael Kleber <michael.kleber@gmail.com> wrote:
The canonical representation works by defining the basis vectors to have whatever inner products you want them to have in order to satisfy the Coxeter relationships you're given. You end up with a vector space and a metric, but the metric is presumably not going to have any nice properties.
So, I suppose I'd have to do something involving the Gram-Schmidt procedure to get an orthonormal basis in order to encode the reflections into matrices...
No no, that might well be impossible. The metric that comes directly from the Coxeter relationships is only going to be positive-definite if the Coxeter group is finite. Otherwise the canonical representation isn't in Euclidean space -- when you try to do Gram-Schmidt, you'll find some vectors have length-squared that's zero or negative. --Michael
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
participants (5)
-
Dan Asimov -
Fred lunnon -
Michael Kleber -
Mike Stay -
Veit Elser