On the Minimal Realizations of a Finite Sequence

✍ Scribed by Graham Norton

• Publisher: Elsevier Science
• Year: 1995
• Tongue: English
• Weight: 651 KB
• Volume: 20
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1995.1040

✦ Synopsis

We develop a theory of minimal realizations of a finite sequence over an integral domain (R), from first principles. Our notion of a minimal realization is closely related to that of a linear recurring sequence and of a partial realization (as in Mathematical Systems Theory). From this theory, we derive Algorithm MR which computes a minimal realization of a sequence of (L) elements using at most (L(5 L+1) / 2 R)-multiplications. We also characterize all minimal realizations of a given sequence in terms of the computed minimal realization.

This algorithm computes the linear complexity of an (R) sequence, solves non-singular linear systems over (R) (extending Wiedemann's method), computes the minimal polynomial of an (R)-matrix, transfer/growth functions and symbolic Padé approximations. There are also a number of applications to Coding Theory.

We thus provide a common framework for solving some well-known problems in Systems Theory, Symbolic/Algebraic Computation and Coding Theory.