[Truncated abstract] A matrix is said to be cyclic if its characteristic polynomial is equal to its minimal polynomial. Cyclic matrices play an important role in some algorithms for matrix group computation, such as the Cyclic Meataxe of Neumann and Praeger. In 1999, Wall and Fulman independently proved that the proportion of cyclic matrices in general linear groups over a finite field of fixed order q has limit [formula] as the dimension approaches infinity. First we study cyclic matrices in maximal reducible matrix groups, that is, the stabilisers in general linear groups of proper nontrivial subspaces. We modify Wall’s generating function approach to determine the limiting proportion of cyclic matrices in maximal reducible matrix groups, as the dimension of the underlying vector space increases while that of the invariant subspace remains fixed. This proportion is found to be [formula] note the change of the exponent of q in the leading term of the expansion. Moreover, we exhibit in each maximal reducible matrix group a family of noncyclic matrices whose proportion is [formula]. Maximal completely reducible matrix groups are the stabilisers in a general linear group of a nontrivial decomposition U1⊕U2 of the underlying vector space. We take a similar approach to determine the limiting proportion of cyclic matrices in maximal completely reducible matrix groups, as the dimension of the underlying vector space increases while the dimension of U1 remains fixed. This limiting proportion is [formula]. ... We prove that this proportion is[formula] provided the dimension of the fixed subspace is at least two and the size q of the field is at least three. This is also the limiting proportion as the dimension increases for separable matrices in maximal completely reducible matrix groups. We focus on algorithmic applications towards the end of the thesis. We develop modifications of the Cyclic Irreducibility Test - a Las Vegas algorithm designed to find the invariant subspace for a given maximal reducible matrix algebra, and a Monte Carlo algorithm which is given an arbitrary matrix algebra as input and returns an invariant subspace if one exists, a statement saying the algebra is irreducible, or a statement saying that the algebra is neither irreducible nor maximal reducible. The last response has an upper bound on the probability of incorrectness.
| Identifer | oai:union.ndltd.org:ADTP/221242 |
| Date | January 2006 |
| Creators | Brown, Scott |
| Publisher | University of Western Australia. School of Mathematics and Statistics |
| Source Sets | Australiasian Digital Theses Program |
| Language | English |
| Detected Language | English |
| Rights | Copyright Scott Brown, http://www.itpo.uwa.edu.au/UWA-Computer-And-Software-Use-Regulations.html |
Page generated in 0.002 seconds