Browsing by Author "Mitchell, James D."
Now showing 1 - 7 of 7
Results Per Page
Sort Options
- An elementary proof that every singular matrix is a product of idempotent matricesPublication . Araújo, João; Mitchell, James D.In this note we give an elementary proof of a theorem first proved by J. A. Erdos [3]. This theorem, which is the main result of [3], states that every noninvertible n ⇥ n matrix is a finite product of matrices M with the property that M2 = M. (These are known as idempotent matrices. Noninvertible matrices are also called singular matrices.) An alternative formulation of this result reads: every noninvertible linear mapping of a finite dimensional vector space is a finite product of idempotent linear mappings ↵, linear mappings that satisfy ↵2 = ↵. This result was motivated by a result of J. M. Howie asserting that each selfmapping ↵ of a nonempty finite set X with image size at most |X|−1 (which occurs precisely when ↵ is noninvertible) is a product of idempotent mappings. We shall see that Erdos’s theorem is a consequence of Howie’s result. Together the papers [3] and [4] are cited in over one hundred articles, dealing with subjects including universal algebra, ring theory, topology, and combinatorics. Since its publication, various proofs of the result in [3] have appeared. For example, a semigroup theoretic proof appears in [1, pp. 121-131] and linear operator theory is used to prove the theorem in [2]. Here we give a new proof using a basic combinatorial argument. Unlike the previous proofs our argument involves only elementary results from linear algebra and one basic result concerning permutations. On the way to proving the main result of this note we provide a short proof of Howie’s result. Throughout this paper X signifies an arbitrary nonempty finite set. If ↵ : A ! X, where A is a subset of X, then A is the domain of ↵; we denote this set by dom(↵). Naturally, the set ↵(A) is called the image of ↵ and is denoted by im(↵). Recall that a mapping ↵ is injective (or one-to-one) if ↵(x) 6= ↵(y) for all x and y in dom(↵) with x 6= y. Let TX denote the set of all mappings from X to X with domain X. We note that this set is closed under composition of mappings and that this composition is associative. We now define one of the most important notions we require in the proofs in this note. For a mapping ↵ : dom(↵) ! X we say that ↵ is a restriction of an element " of TX if " and ↵ agree on the domain of ↵. In other words, "(x) = ↵(x) for all x in dom(↵). For x and y in X we denote the transposition that fixes every point of X other than x or y and that maps x to y, and vice versa, by (x y).
- Automorphisms of partial endomorphism semigroupsPublication . Araújo, João; Fernandes, Vítor H.; Jesus, Manuel M.; Maltcev, V.; Mitchell, James D.In this paper we propose a general recipe for calculating the automorphism groups of semigroups consisting of partial endomorphisms of relational structures with a single m-ary relation for any m 2 N over a finite set. We use this recipe to determine the automorphism groups of the following semigroups:the full transformation semigroup, the partial transformation semigroup, and the symmetric inverse semigroup, and their wreath products, partial endomorphisms of partially ordered sets, the full spectrum of semigroups of partial mappings preserving or reversing a linear or circular order. We also determine the automorphism groups of the so-called Madhaven semigroups as an application of the methods developed herein.
- Computing automorphisms of semigroupsPublication . Araújo, João; Bünau, P. V.; Mitchell, James D.; Neunhöffer, M.In this paper an algorithm is presented that can be used to calculate the automorphism group of a finite transformation semigroup. The general algorithm employs a special method to compute the auto- morphism group of a finite simple semigroup. As applications of the algorithm all the automorphism groups of semigroups of order at most 7 and of the multiplicative semigroups of some group rings are found. We also consider which groups occur as the automor- phism groups of semigroups of several distinguished types.
- Groups that together with any transformation generate regular semigroups or idempotent generated semigroupsPublication . Araújo, João; Mitchell, James D.; Csaba, SchneiderLet a be a non-invertible transformation of a finite set and let G be a group of permutations on that same set. Then 〈G,a〉∖G〈G,a〉∖G is a subsemigroup, consisting of all non-invertible transformations, in the semigroup generated by G and a . Likewise, the conjugates ag=g−1agag=g−1ag of a by elements of G generate a semigroup denoted by 〈ag|g∈G〉〈ag|g∈G〉. We classify the finite permutation groups G on a finite set X such that the semigroups 〈G,a〉〈G,a〉, 〈G,a〉∖G〈G,a〉∖G, and 〈ag|g∈G〉〈ag|g∈G〉 are regular for all transformations of X. We also classify the permutation groups G on a finite set X such that the semigroups 〈G,a〉∖G〈G,a〉∖G and 〈ag|g∈G〉〈ag|g∈G〉 are generated by their idempotents for all non-invertible transformations of X.
- On embedding countable sets of endomorphismsPublication . Araújo, João; Mitchell, James D.; Silva, NunoSierpi´nski proved that every countable set of mappings on an infinite set X is contained in a 2-generated subsemigroup of the semigroup of all mappings on X. In this paper we prove that every countable set of endomorphisms of an algebra A which has an infinite basis (independent generating set) is contained in a 2-generated subsemigroup of the semigroup of all endomorphisms of A.
- Relative ranks in the monoid of endomorphisms of an independence algebraPublication . Mitchell, James D.; Araújo, JoãoThe relative ranks of the monoid of endomorphisms of a strong independence algebra of infinite rank modulo two distinguished subsets are calculated. These subsets are the group of auto- morphisms and the endomorphisms b satisfying b^2 = b. The extra generators are characterised in each case.
- The classification of normalizing groupsPublication . Araújo, João; Cameron, Peter J.; Mitchell, James D.; Max, NeunhöfferLet X be a finite set such that |X|=n. Let Tn and Sn denote the transformation monoid and the symmetric group on n points, respectively. Given a∈Tn∖Sn, we say that a group G⩽Sn is a-normalizing if ,where a, G and g−1ag | g ∈ G denote the subsemigroups of Tn generated by the sets {a} ∪ G and {g−1ag | g ∈ G}, respectively. If G is a-normalizing for all a ∈ Tn \ Sn, then we say that G is normalizing.The goal of this paper is to classify the normalizing groups and hence answer a question of Levi, McAlister, and McFadden. The paper ends with a number of problems for experts in groups, semigroups and matrix theory.