An Algebraic and Graph Theoretic Framework to Study Monomial Dynamical Systems over a Finite Field
Edgar Delgado-Eckert
ETH Zürich, Department of Biosystems Science and Engineering (D-BSSE)
WRO-1058-8.46, Mattenstrasse 26, 4058 Basel, Switzerland
edgar.delgado-eckert@mytum.de
Abstract
A monomial dynamical system f : Kn → Kn over a finite field K is a nonlinear deterministic time discrete dynamical system with the property that each component function fi : Kn → K is a monic nonzero monomial function. In this paper we provide an algebraic and graph theoretic framework to study the dynamic properties of monomial dynamical systems over a finite field. Within this framework, characterization theorems for fixed point systems, that is, systems in which all trajectories end in steady states, are proved. These characterizations are stated in terms of connectedness properties of the dependency graph. Our formalism allowed us to develop an algorithm of polynomial complexity for testing whether or not a given monomial dynamical system over an arbitrary finite field is a fixed point system. In addition, we were able to identify a class of monomial dynamical systems, namely, the (q - 1)-fold redundant monomial systems. Within this class of systems a characterization of fixed point systems is proved that represents a generalization of previous work on Boolean monomial dynamical systems.
