Estimation of local nonlinearity characteristics of vector space transformation iteration using matrix-graph approach

To generalize the matrix-graph approach to examination of nonlinearity characteristics of vector spaces transformations proposed by V. M. Fomichev, we propose mathematical tools for local nonlinearity of transformations. Let G = {0,1, 2} be multiplicative semigroup where a0 = 0 for each a £ G, ab = max {a, b} for each a,b = 0. Ternary matrix (matrix over G) is called a-matrix, a £ П (2) = {(2c); (2s); (2sc); (2)}, if all its lines ((2s)-matrix), columns ((2c)-matrix) or lines and columns ((2sc)-matrix) contain 2 or if all its elements are equal to 2 ((2)-matrix). Set of all ternary matrices M of order n whose I x J-submatrices are a-matrices is denoted МП (I x J), I, J С {1,..., n}. For the set of ternary matrices, multiplication operation is defined. If A = (a_i,j), B = (bi,j), then AB = C = (c_i,j), where c_i,j = max {a_i,_ib₁,j,..., ai,_nb_n,j} and for all i,j multiplication is executed in semigroup G. Matrix M is called I x J-a-primitive if there is such 7 £ N that M^f £ M^ (I x J) for all natural t ^ 7, a £ П(2). The smallest such 7 is denoted I x J-a-expM and called I x J-a-exponent of matrix M. There is bijective mapping between the set of ternary matrices of order n and the set of labeled digraphs with n vertices and with elements from G as labels, so the definitions of Ix J-a-primitivity and I x J-a-exponent can be transferred to digraphs. Some sufficient conditions for I x J-a-exponent of a matrix to be the smallest its power, raised to which I x J-submatrix is a-matrix, a £ П (2), have been established. For I = {i}, J = {j} upper estimates of I x J-a-exponents have been obtained for some classes of labeled digraphs, particularly, for digraph in which a path from i to j goes through primitive component of strong connectivity.

Keywords

Authors

References