M.Sc., Faculty of Science, University of the Witwatersrand, 2011 / Continued fractions have been extensively studied in number-theoretic ways. In this text, we will illuminate some of the geometric properties of contin- ued fractions by considering them as compositions of MÄobius transformations which act as isometries of the hyperbolic plane H2. In particular, we examine the geometry of simple continued fractions by considering the action of the extended modular group on H2. Using these geometric techniques, we prove very important and well-known results about the convergence of simple con- tinued fractions. Further, we use the Farey tessellation F and the method of cutting sequences to illustrate the geometry of simple continued fractions as the action of the extended modular group on H2. We also show that F can be interpreted as a graph, and that the simple continued fraction expansion of any real number can be can be found by tracing a unique path on this graph. We also illustrate the relationship between Ford circles and the action of the extended modular group on H2. Finally, our work will culminate in the use of these geometric techniques to prove well-known results about the relationship between periodic simple continued fractions and quadratic irrationals.

Representations of SO(4,2;R) are constructed using 4 x 4 and 2 x 2 matrices with elements in H' ��� C . Using 2 x 2 matrix representations of C and H', the 4 x 4 representation is interpreted in terms of 16 x 16 real matrices. Finally, the known isomorphism between the conformal group and SO(4,2;R) is written explicitly in terms of the 4 x 4 representation. The 4 x 4 construction should generalize to matrices with elements in K' ��� K for K any normed division algebra over the reals and K' any split algebra over the reals. / Graduation date: 2013

<p> We look at methods to generate uniformly distributed points from the classical matrix groups, spheres, projective spaces, and Grassmannians. We motivate the discussion with a number of applications ranging from number theory to wireless communications. The uniformity of the samples and the efficiency of the algorithms are compared. </p> / Thesis / Master of Science (MSc)

Let S be a semigroup with zero and let a S\O. Denote by V(a) the set of all inverses of a, that is, V(a) = (x ∈ S: axa=a. xax=x). Let n be a fixed positive integer. A semigroup S with zero is said to be homogeneous n regular if the cardinal number of the set V(a) of all inverses of a is n for every nonzero element a in S. Let T be a subset of S. We denote by E(T) the set of all idempotents of S in T. The next theorem is a generalization of R. McFadden and Hans Schneider's theorem [1] . Theorem 1. Let S be a 0-simple semigroup and let n be a fixed positive integer. Then the following are equivalent. (i) S is a homogeneous n regular and completely 0-simple semigroup. (ii) For every a≠0 in S there exist precisely n distinct nonzero elements (xᵢ)_{i [= symbol with an n on top]l} such that axᵢa=a for i=1, 2, ..., n and for all c, d in S cdc=c≠0 implies dcd=d. (iii) For every a≠0 in S there exist precisely h distinct nonzero idempotents (eᵢ)_{i [= symbol with an h above]l} Eₐ and k distinct nonzero idempotents (fⱼ)_{j[= symbol with a k above]}= Fₐ such that eᵢa=a=afⱼ for i =1, 2, …, h, j = 1, 2, …, k hk=n, Eₐ contains every nonzero idempotent which is a left unit of a, Fₐ contains every nonzero idempotent which is a right unit of a and Eₐ ⋂ Fₐ contains at most one element. (iv) For every a≠0 in S there exist precisely k nonzero principal right ideals (Rᵢ)_{i[= symbol with a k above]1} and h nonzero principal left ideals (Lⱼ)_{j[= symbol with h above]1} such that Rᵢ and Lⱼ contain h and k inverses of a, respectively, every inverse of a is contained in a suitable set Rᵢ ⋂ Lⱼ for i = 1, 2, .., k, j = 1, 2, .., h and Rᵢ ⋂ Lⱼ for i = 1, 2, .., k, j = 1, 2, .., h, and Rᵢ ⋂ Lⱼ contains at most one nonzero idempotent, where hk = n. (v) Every nonzero principal right ideal R contains precisely h nonzero idempotents and every nonzero principal left ideal L contains precisely k nonzero idempotents such that hk=n, and R⋂L contains at most one nonzero idempotent. (vi) S is completely 0-simple. For every 0-minimal right ideal R there exist precisely h 0-minimal left ideals (Li)_{i[= symbol with an h above]1} and for every 0-minimal left ideal L there exist precisely k 0-minimal right ideals (Rj)_{j[= symbol with a k above]1} such that LRⱼ=LiR=S, for every i=1,2,..,h, j=l,2,.. ,k, where hk=n. (vii) S is completely 0-simple. Every 0-minimal right ideal R of S is the union of a right group with zero G°, a union of h disjoint groups except zero, and a zero subsemigroup Z uhich annihilates the right ideal R on the left and every 0-minimal left ideal L of S is the union of a left group with zero G’° a union of k disjoint groups except zero, and a zero subsemigroup Z' which annihilates the left ideal L on the right and hk=n. (viii) S contains at least n nonzero distinct idempotents, and for every nonzero idempotent e there exists a set E of n distinct nonzero idempotents of S such that eE is a right zero subsemigroup of S containing precisely h nonzero idempotents, Ee is a left zero subsemigroup of S containing precisely k nonzero idempotents of S, e (E(S)\E) = (0) = (E(S)\E)e, and eE⋂Ee = (e), where hk=n. S is said to be h-k type if every nonzero principal left ideal of S contains precisely k nonzero idempotents and every nonzero principal right ideal of S contains precisely h nonzero idempotents of S. W. D. Munn defined the Brandt congruence [2]. A congruence ρ on a sernigroup S with zero is called a Brandt congruence if S/ρ is a Brandt semigroup. Theorem 2. Let S be a 1-n type homogeneous n regular and complete:y 0-simple semigroup. Define a relation ρ on S in such a way that a ρb if and only if there exists a set (eᵢ) _{i[=symbol with an n above]1} of n distinct nonzero idempotents such that eᵢa=ebᵢ≠0, for every i=1, 2, . , n. Then ρ is an equivalence S\0. If we extend ρ on S by defining (0) to be ρ-class on S, then ρ is a proper Brandt congruence on S, then ρ ⊂ σ. Let P=(pᵢⱼ) be any n x n matrix over a group with G°, and consider any n distinct points A₁, A₂, . , A_n in the plane, which we shall call vertices. For every nonzero entry pᵢⱼ≠0 of the matrix P, we connect the vertex Aᵢ to the vertex Aⱼ by means of a path [a bar over both AᵢAⱼ] which we shall call an edge (a loop if i = j) directed from Aᵢ to Aⱼ. In this way, with every n x n matrix P can be associated a finite directed graph G(P). Let S=M°(G;In,In;P) be a Rees matrix semigroup. Then the graph G(P) is called the associated graph of the semigroup S, or simply it is the graph G(P) of S. Theorem 3. A Rees matrix semigroup S=M°(G;In,In;P) is homogenous m² regular if the directed graph G(P) of the semigroup S is regular of degree m [3, p. 11]. / Doctor of Philosophy

[Abstract] This thesis is divided into two parts, both containing algorithms for dealing with matrices and matrix groups. Part I is concerned with individual matrices over an arbitrary field. Our algorithms make use of a sequence called the rank profile which is related to the linear dependence relations between the columns of a matrix. First we look at LSP decompositions of matrices as defined by Ibarra et al. in 1982. This decomposition is related to, and a little more general than, the LUP decomposition. The algorithm given by Ibarra et al. to compute an LSP decomposition was only defined for m?n matrices where m ≤ n and is claimed to have the same asymptotic cost as matrix multiplication. We prove that their cost analysis overlooked some aspects of the computation and present a new version of the algorithm which finds both an LSP decomposition and the rank profile of any matrix. The cost of our algorithm is the same as that claimed by Ibarra et al. when m ≤ n and has a similar cost when m > n. One of the steps in the Ibarra et al. algorithm is not completely explicit, so that any one of several choices can be made. Our algorithm is designed so that the particular choice made at this point allows for the simultaneous calculation of the rank profile. Next we study algorithms to find the characteristic polynomial of a square matrix. The current fastest algorithm to find the characteristic polynomial of a square matrix was developed by Keller-Gehrig in 1985. We present a new, simpler version of this algorithm with the same cost which makes the algorithm?s reliance on the rank profile explicit. In Part II we present generalised sifting, a scheme for creating Monte Carlo black box constructive group recognition algorithms. Generalised sifting is designed to facilitate computation in a known group, specifically re-writing arbitrary elements as words or straight-line programs in a standard generating set. It can also be used to create membership tests in black-box groups. Generalised sifting was inspired by the subgroup sifting techniques originally introduced by Sims in 1970 but uses a chain of subsets rather than subgroups. We break the problem down into a sequence of separately analysed and proven steps which sift down into each subset in turn ... All of the algorithms in Parts I and II are given with a theoretical proof and (where appropriate) complexity analysis. The LSP decomposition, characteristic polynomial and generalised sifting algorithms have all been implemented and tested in the computer algebra package GAP.

The purpose of this thesis is to investigate a class of four left-invariant optimal control problems on the special orthogonal group SO(3). The set of all control-affine left-invariant control systems on SO(3) can, without loss, be reduced to a class of four typical controllable left-invariant control systems on SO(3) . The left-invariant optimal control problem on SO(3) involves finding a trajectory-control pair on SO (3), which minimizes a cost functional, and satisfies the given dynamical constraints and boundary conditions in a fixed time. The problem is lifted to the cotangent bundle T*SO(3) = SO(3) x so (3)* using the optimal Hamiltonian on so(3)*, where the maximum principle yields the optimal control. In a contribution to the study of this class of optimal control problems on SO(3), the extremal equations on so(3)* (ident ified with JR3) are integrated via elliptic functions to obtain explicit expressions for the solution curves in each typical case. The energy-Casimir method is used to give sufficient conditions for non-linear stability of the equilibrium states. / KMBT_363 / Adobe Acrobat 9.54 Paper Capture Plug-in

The aim of this thesis is to study a class of left-invariant optimal control problems on the matrix Lie group SE(2). We classify, under detached feedback equivalence, all controllable (left-invariant) control affine systems on SE(2). This result produces six types of control affine systems on SE(2). Hence, we study six associated left-invariant optimal control problems on SE(2). A left-invariant optimal control problem consists of minimizing a cost functional over the trajectory-control pairs of a left-invariant control system subject to appropriate boundary conditions. Each control problem is lifted from SE(2) to T*SE(2) ≅ SE(2) x se (2)*and then reduced to a problem on se (2)*. The maximum principle is used to obtain the optimal control and Hamiltonian corresponding to the normal extremals. Then we derive the (reduced) extremal equations on se (2)*. These equations are explicitly integrated by trigonometric and Jacobi elliptic functions. Finally, we fully classify, under Lyapunov stability, the equilibrium states of the normal extremal equations for each of the six types under consideration.

The finite affine group is a matrix group whose entries come from a finite field. A natural subgroup consists of those matrices whose entries all come from a subfield instead. In this paper, I will introduce intermediate sub- groups with entries from both the field and a subfield. I will also examine the representations of these intermediate subgroups as well as the branch- ing diagram for the resulting subgroup chain. This will allow us to create a fast Fourier transform for the group that uses asymptotically fewer opera- tions than the brute force algorithm.

Part I of this thesis studies P[subscript(G)](d), the probability of generating a nonabelian simple group G with d randomly chosen elements, and extends this idea to consider the conditional probability P[subscript(G,Soc(G))](d), the probability of generating an almost simple group G by d randomly chosen elements, given that they project onto a generating set of G/Soc(G). In particular we show that for a 2-generated almost simple group, P[subscript(G,Soc(G))](2) 53≥90, with equality if and only if G = A₆ or S₆. Furthermore P[subscript(G,Soc(G))](2) 9≥10 except for 30 almost simple groups G, and we specify this list and provide exact values for P[subscript(G,Soc(G))](2) in these cases. We conclude Part I by showing that for all almost simple groups P[subscript(G,Soc(G))](3)≥139/150. In Part II we consider a related notion. Given a probability ε, we wish to determine d[superscript(ε)] (G), the number of random elements needed to generate a finite group G with failure probabilty at most ε. A generalisation of a result of Lubotzky bounds d[superscript(ε)](G) in terms of l(G), the chief length of G, and d(G), the minimal number of generators needed to generate G. We obtain bounds on the chief length of permutation groups in terms of the degree n, and bounds on the chief length of completely reducible matrix groups in terms of the dimension and field size. Combining these with existing bounds on d(G), we obtain bounds on d[superscript(ε)] (G) for permutation groups and completely reducible matrix groups.