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

V. M. Fomichev ; V. M. Bobrov

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 32-35

Résumé

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=\left\{0,1,2\right\}$ be multiplicative semigroup where $a0=0$ for each $a\in G$, $ab=\max\left\{a,b\right\}$ for each $a,b\neq0$. Ternary matrix (matrix over $G$) is called $\alpha$-matrix, $\alpha\in\Pi\left(2\right)=\left\{ \left2c\right>;\left2s\right>;\left2sc\right>;\left2\right> \right\}$, if all its lines ($\left2s\right>$-matrix), columns ($\left2c\right>$-matrix) or lines and columns ($\left2sc\right>$-matrix) contain $2$ or if all its elements are equal to $2$ ($\left2\right>$-matrix). Set of all ternary matrices $M$ of order $n$ whose $I\!\times\!J$-submatrices are $\alpha$-matrices is denoted $M_{n}^{\alpha} \left( I\!\times\!J \right)$, $I,J\subseteq\left\{1,\dots,n\right\}$. For the set of ternary matrices, multiplication operation is defined. If $A=\left(a_{i,j}\right)$, $B=\left(b_{i,j}\right)$, then $AB=C=\left( c_{i,j}\right) $, where $c_{i,j}=\max\left\{a_{i,1}b_{1,j},\dots,a_{i,n}b_{n,j}\right\}$ and for all $i,j$ multiplication is executed in semigroup $G$. Matrix $M$ is called $I\!\times\!J\text{-}\alpha$-primitive if there is such $\gamma\in\mathbb{N}$ that $M^{t}\in M_{n}^{\alpha}\left(I\!\times\!J\right)$ for all natural $t\ge\gamma$, $\alpha\in\Pi\left(2\right)$. The smallest such $\gamma$ is denoted $I\!\times\!J\text{-}\alpha\text{-exp}M$ and called $I\!\times\!J\text{-}\alpha$-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 $I\!\times\!J\text{-}\alpha$-primitivity and $I\!\times\!J\text{-}\alpha$-exponent can be transferred to digraphs. Some sufficient conditions for $I\!\times\!J\text{-}\alpha$-exponent of a matrix to be the smallest its power, raised to which $I\!\times\!J$-submatrix is $\alpha$-matrix, $\alpha\in\Pi\left(2\right)$, have been established. For $I=\left\{i\right\}$, $J=\left\{j\right\}$ upper estimates of $I\!\times\!J\text{-}\alpha$-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.

Détail

Keywords: matrix-graph approach, ternary matrix, labeled digraph, local nonlinearity, local $\alpha$-exponent.

Bibliographie

[1] Fomichev V. M., “O proizvoditelnosti nekotorykh iterativnykh algoritmov blochnogo shifrovaniya iz klassa WBC”, New Trends in Coding Systems and Techniques, Intech Publishing, LDN, 2019, 14

[2] Kyazhin S. N., “Lokalnaya primitivnost grafov i neotritsatelnykh matrits”, Prikladnaya diskretnaya matematika, 2014, no. 3(25), 68–80