Local primitivity of matrices and graphs

Abstract

We develop a matrix-graph approach to the estimation of the communicative properties of a system of connected objects. In particular, this approach can be applied to analyzing the mixing properties of iterative cryptographic transformations of binary vector spaces, i.e. dependence of the output block bits on the input bits. In some applied problems, the saturation of the connections between the objects corresponds to the required level if the matrix modeling the connections or its certain submatrix is positive (the graph modeling the connections or its certain subgraph is complete). The concepts of local primitivity and local exponents of a nonnegative matrix (graph) are introduced. These concepts generalize and expand the area of application as compared to the familiar concepts of primitivity and exponent.We obtain a universal criterion for the local primitivity of a digraph and both a universal bound for the local exponents and its refinements for various particular cases. The results are applied to analyzing the mixing properties of a cryptographic generator constructed on the basis of two shift registers.