Sequential machines realized by group representations
type: Item
instance of: scholarly article
title: Sequential machines realized by group representations
zbMATH Open document ID: 0729.68047
DOI: 10.1016/0890-5401(90)90047-L
author: Michael Conner
published in: Information and Computation
publication date: 1990-01-01T00:00:00Z
review text: The Krohn-Rhodes theorem characterizes finite automata in terms of permutation machines and reset-machines. The author suggests to replace the finite permutation group G corresponding to a permutation machine by a faithful low dimensional ordinary matrix representation of G. In a second stage he then reduces the constants to get a faithful low dimensional representation of G over a small finite field. In the introduction the author writes: ``The major new result given in the present paper is that computation over a finite field Z modulo p \((Z_ p)\) will always suffice for these methods. These new results yield a dramatic increase in the flexibility of the method as well as giving very tight control over the realizations.'' This sounds like a sensation but a closer look at this paper shows that nothing is new! Even worse, classical results (resp. methods) are reproved (resp. reformulated) in a complicated way. As an example, investigating ``the worst case'' M. Conner needs about five (!) pages to reprove the well-known result that the symmetric group \(S_ n\) (n\(\geq 3)\) has a faithful linear representation over GF(3) of degree n-1. In addition, it is well-known see e.g. \textit{G. D. James} [The representation theory of the symmetric groups, Berlin-Heidelberg-New York (1978; Zbl 0393.20009)] how to improve this result: For \(n\geq 3\), \(S_ n\) has a faithful linear representation over GF(2) of degree d, where \(d=n-2\) if n is even and \(d=n-1\) if n is odd. Proof: \(S_ n\) acts linearly on \(GF(2)^ n\) by permuting the standard basis: \(\pi e_ i:=e_{\pi (i)}\). The line \(L_ n\) generated by \(e_ 1+...+e_ n\) is an \(S_ n\)-submodule as well as its ``orthogonal complement'' \(M_ n\), freely generated by \(e_ 1+e_ 2,...,e_ 1+e_ n\). Obviously, \(M_ n\) is faithful for \(n\geq 3\). Now let n be even. Then \((e_ 1+e_ 2)+...+(e_ 1+e_ n)=e_ 1+...+e_ n\), hence \(L_ n\) is a submodule of \(M_ n\), and \(M_ n/L_ n\) is a faithful \(S_ n\)-module of dimension n-2. Done…
reviewed by: Michael Clausen
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4206002
zbMATH Keywords: group representations
zbMATH Keywords: Krohn-Rhodes theorem
zbMATH Keywords: permutation machines
MaRDI profile type: Publication
cites work: Q5512183
cites work: Q5535414
cites work: Cascade synthesis of finite-state machines
cites work: Q3666281
cites work: Q4079524
cites work: Q3853827
cites work: Q3769981
cites work: Q3943153
cites work: Q4126536
cites work: Q5719436
cites work: Q5586503
cites work: Q3222352
cites work: Q4090395
cites work: Q5340151
cites work: Q3856819
description: scientific article; zbMATH DE number 4206002