Algorithms for matrix groups and the tits alternative

Research output: Contribution to journalConference article

2 Citations (Scopus)

Abstract

Tits has shown that a finitely generated linear group either contains a nonabelian free group or has a solvable subgroup of finite index. This paper gives a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. The complexity of problems relating to linear groups with solvable subgroups of finite index is also investigated.

Original languageEnglish (US)
Pages (from-to)593-602
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1995
Externally publishedYes
EventProceedings of the 1995 IEEE 36th Annual Symposium on Foundations of Computer Science - Milwaukee, WI, USA
Duration: Oct 23 1995Oct 25 1995

Fingerprint

Polynomials

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this

@article{934034b072b045aaa8b2f5cd65e6efdc,
title = "Algorithms for matrix groups and the tits alternative",
abstract = "Tits has shown that a finitely generated linear group either contains a nonabelian free group or has a solvable subgroup of finite index. This paper gives a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. The complexity of problems relating to linear groups with solvable subgroups of finite index is also investigated.",
author = "Robert Beals",
year = "1995",
month = "12",
day = "1",
language = "English (US)",
pages = "593--602",
journal = "Annual Symposium on Foundations of Computer Science - Proceedings",
issn = "0272-5428",

}

Algorithms for matrix groups and the tits alternative. / Beals, Robert.

In: Annual Symposium on Foundations of Computer Science - Proceedings, 01.12.1995, p. 593-602.

Research output: Contribution to journalConference article

TY - JOUR

T1 - Algorithms for matrix groups and the tits alternative

AU - Beals, Robert

PY - 1995/12/1

Y1 - 1995/12/1

N2 - Tits has shown that a finitely generated linear group either contains a nonabelian free group or has a solvable subgroup of finite index. This paper gives a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. The complexity of problems relating to linear groups with solvable subgroups of finite index is also investigated.

AB - Tits has shown that a finitely generated linear group either contains a nonabelian free group or has a solvable subgroup of finite index. This paper gives a polynomial time algorithm for deciding which of these two conditions holds for a given finitely generated matrix group over an algebraic number field. The complexity of problems relating to linear groups with solvable subgroups of finite index is also investigated.

UR - http://www.scopus.com/inward/record.url?scp=0029510685&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029510685&partnerID=8YFLogxK

M3 - Conference article

SP - 593

EP - 602

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

SN - 0272-5428

ER -