AN EXPANSION PROPERTY OF BOOLEAN LINEAR MAPS

作者：Wu, Yaokun^*; Xu, Zeying; Zhu, Yinfeng

来源：Electronic Journal of Linear Algebra, 2016, 31(1): 381-407.

DOI：10.13001/1081-3810.3088

• Diameter
• Digraph
• Girth
• Phase space
• Primitive exponent
• Reachability
• Wielandt's inequality

Given a finite set K, a Boolean linear map on K is a map f from the set 2(K) of all subsets of K into itself with f (phi) = phi such that f (A U B) = f (A) U f (B) holds for all A, B is an element of 2(K). For fixed subsets X,Y of K, to predict if Y is reachable from X in the dynamical system driven by f, one can assume the existence of nonnegative integers h with f(h) (X) = Y, find an upper bound a for the minimum of all such assumed integers h, and test if Y really appears in f (X),, f (X). In order to get such an upper bound estimate, this paper establishes an expansion property for the Boolean linear map f. Namely, the authors find a lower bound on the size of fh (X) for any nonnegative integer h. Besides presenting several direct applications of the derived expansion property, this paper collects some related problems on Boolean linear dynamical systems, including problems on primitive multilinear maps and inhomogeneous topological Markov chains.

• 出版日期2016-6
• 单位上海交通大学