Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-23T12:50:34.407Z Has data issue: false hasContentIssue false
  • English
  • Français

An Algorithm for Recognising the Exterior Square of a Multiset

Published online by Cambridge University Press:  01 February 2010

Catherine Greenhill
Catherine Greenhill
Affiliation:
School of Computer Studies, University of Leeds, Leeds LS2 9JT, [email protected]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The exterior square of a multiset is a natural combinatorial construction which is related to the exterior square of a vector space. We consider multisets of elements of an abelian group. Two properties are defined which a multiset may satisfy: recognisability and involution-recognisability. A polynomial-time algorithm is described which takes an input multiset and returns either (a) a multiset which is either recognisable or involution-recognisable and whose exterior square equals the input multiset, or (b) the message that no such multiset exists. The proportion of multisets which are neither recognisable nor involution-recognisable is shown to be small when the abelian group is finite but large. Some further comments are made about the motivating case of multisets of eigenvalues of matrices.

Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 3 , 2000 , pp. 96 - 116
Copyright
Copyright © London Mathematical Society 2000

References

1. Greenhill, Catherine, ‘From multisets to matrix groups: some algorithms related to the exterior square’, D. Phil. Thesis, The Mathematical Institute, University of Oxford, 1996.Google Scholar
2. Greenhill, Catherine, ‘An algorithm for recognising the exterior square of a matrix’, Linear and Multilinear Algebra 46 (1999) 213–244.CrossRefGoogle Scholar
3. Kantor, William M. and Serees, Ákos, ‘Black box classical groups’, Mem. Amer. Math. Soc. To appear.Google Scholar
4. Knuth, D. E., The art of computer programming, Vol. 3: Sorting and searching, 2nd edn (Wesley, Addison-, Reading, MA, 1981).Google Scholar
5. Neumann, Peter M. and Praeger, Cheryl E., ‘A recognition algorithm for special linear groups’, Proc. London Math. Soc. (3) 65 (1992) 555–603.CrossRefGoogle Scholar
6. Neumann, Peter M. and Praeger, Cheryl E., ‘On tensor factorisation problems’, Unpublished manuscript, Oxford, 1997.Google Scholar
7. Schönert, Martin and others, GAP — groups, algorithms, and programming, 5th edn (Lehrstuhl D für Mathematik, Rheinisch Westfälische Technische Hochschule, Aachen, Germany, 1995). Available from the Department of Computer Science, University of St. Andrews, http://www-gap.dcs.st-and.ac.uk/gap/.Google Scholar