Fundamental structures of invariant dual subspaces with respect to a Boolean network

This paper presents the following research findings on a Boolean network (BN) and the invariant dual subspaces with respect to the BN. First, we establish a bijection between the dual subspaces over the BN's state set X and the partitions of X. Furthermore, we prove that a dual subspace is M-invariant if and only if the associated partition of the BN's state-transition graph is equitable (i.e., for every two cells of the partition, all states in the former cell have the same number of out-neighbors in the latter), where M represents the state transition matrix of the BN. Secondly, we leverage the concept of equitable graphic representation to develop a graphical algorithm for determining the smallest M-invariant dual subspaces generated by a set of Boolean functions. Based on this algorithm, we provide, for the first time, a complete structural characterization of these M-invariant dual subspaces. Finally, we prove that a BN with a given set of (Boolean) output functions is observable if and only if the partition corresponding to the smallest M-invariant dual subspace generated by this set of functions is discrete (i.e., all partition cells are singletons). Building upon our structural characterization, we introduce a method for constructing output functions that render the BN observable.