ON THE MINIMAL REALIZATIONS OF A FINITE SEQUENCE

We develop a theory of minimal realizations of a finite sequence over an integral domain R, from first principles. Our notion of a minimal r ealization is closely related to that of a linear recurring sequence a nd of a partial realization (as in Mathematical Systems Theory). From this theory, we derive Algorithm MR which computes a minimal realizati on of a sequence of L elements using at most L(5L + 1)/2 R-multiplicat ions, Wa also characterize all minimal realizations of a given sequenc e in terms of the computed minimal realization. This algorithm compute s the linear complexity of an R sequence, solves non-singular linear s ystems over R (extending Wiedemann's method), computes the minimal pol ynomial of an R-matrix, transfer/growth functions and symbolic Pade ap proximations. There are also a number of applications to Coding Theory . We thus provide a common framework for solving some well-known probl ems in Systems Theory, Symbolic/Algebraic Computation and Coding Theor y.