Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T00:14:13.248Z Has data issue: false hasContentIssue false

An Algorithm for Recognising the Exterior Square of a Multiset

Published online by Cambridge University Press:  01 February 2010

Catherine Greenhill
Affiliation:
School of Computer Studies, University of Leeds, Leeds LS2 9JT, csg@scs.leeds.ac.uk

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.

Information

Type
Research Article
Copyright
Copyright © London Mathematical Society 2000