Algorithms for matrix groups I

Duration: 55 mins 18 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/3140637/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	O'Brien, E Thursday 9th January 2020 - 10:00 to 11:00


Created:	2020-01-14 08:48
Collection:	Groups, representations and applications: new perspectives
Publisher:	Isaac Newton Institute
Copyright:	O'Brien, E
Language:	eng (English)


Abstract:	Most first-generation algorithms for matrix groups defined over finite fields rely on variations of the Schreier-Sims algorithm, and exploit the action of the group on an set of vectors or subspaces of the underlying vector space. Hence they face serious practical limitations. Over the past 25 years, much progress has been achieved on developing new algorithms to study such groups. Relying on a generalization of Aschbacher's theorem about maximal subgroups of classical groups, they exploit geometry arising from the natural action of the group on its underlying vector space to identify useful homomorphisms. Recursive application of these techniques to image and kernel now essentially allow us to construct in polynomial time the composition factors of the linear group. Using the notion of standard generators, we can realise effective isomorphisms between a final simple group and its "standard copy". In these lectures we will discuss the "composition tree" algorithm which realises these ideas; and the "soluble radical model" which exploits them to answer structural questions about the input group.

Abstract:

Most first-generation algorithms for matrix groups defined over finite fields rely on variations of the Schreier-Sims algorithm, and exploit the action of the group on an set of vectors or subspaces of the underlying vector space. Hence they face serious practical limitations. Over the past 25 years, much progress has been achieved on developing new algorithms to study such groups. Relying on a generalization of Aschbacher's theorem about maximal subgroups of classical groups, they exploit geometry arising from the natural action of the group on its underlying vector space to identify useful homomorphisms. Recursive application of these techniques to image and kernel now essentially allow us to construct in polynomial time the composition factors of the linear group. Using the notion of standard generators, we can realise effective isomorphisms between a final simple group and its "standard copy". In these lectures we will discuss the "composition tree" algorithm which realises these ideas; and the "soluble radical model" which exploits them to answer structural questions about the input group.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.93 Mbits/sec	803.52 MB	View	Download
WebM	640x360	355.57 kbits/sec	144.06 MB	View	Download
iPod Video	480x270	522.11 kbits/sec	211.47 MB	View	Download
MP3	44100 Hz	249.73 kbits/sec	101.27 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)