Matching Algorithms of Minimum Input Selection for Structural Controllability Based on Semi-Tensor Product of Matrices

In 2011,Liu,et al.investigated the structural controllability of directed networks.They proved that the minimum number of input signals,driver nodes,can be determined by seeking a maximum matching in the directed network.Thus,the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks.In this study,the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu,et al.(2011)via a new matrix product called semi-tensor product,based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs,which make determining the number of driver nodes tractable in computer.In addition,according to the proposed algorithm,the authors also construct an algorithm to distinguish critical arcs,redundant arcs and ordinary arcs of the directed network,which plays an important role in studying the robust control problem.An example of a small network from Liu’s paper is used for algorithm verification.

Semi-tensor product of matrices and its application to Morgen's problem

This paper proposes a new matrix product, namely, semi-tensor product. It is a general-ization of the conventional matrix product. Meanwhile, it is also closely related to Kronecker (tensor) product of matrices. The purpose of introducing this product is twofold: (i) treat multi-dimensional da-ta; (ii) treat nonlinear problems in a linear way. Then the computer and numerical methods can be easily used for solving nonlinear problems. Properties and formulas are deduced. As an application, the Morgan's problem for control systems is formulated as a numerically solvable problem.

A SURVEY ON SEMI-TENSOR PRODUCT OF MATRICES

Semi-tensor product of matrices is a generalization of conventional matrix product for the case when the two factor matrices do not meet the dimension matching condition. It was firstly proposed about ten years ago. Since then it has been developed and applied to several different fields. In this paper we will first give a brief introduction. Then give a survey on its applications to dynamic systems, to logic, to differential geometry, to abstract algebra, respectively.

Solving type-2 fuzzy relation equations via semi-tensor product of matrices

The problem of solving type-2 fuzzy relation equations is investigated. In order to apply semi-tensor product of matrices, a new matrix analysis method and tool, to solve type-2 fuzzy relation equations, a type-2 fuzzy relation is decomposed into two parts as principal sub-matrices and secondary sub-matrices; an r-ary symmetrical-valued type-2 fuzzy relation model and its corresponding symmetrical-valued type-2 fuzzy relation equation model are established. Then, two algorithms are developed for solving type-2 fuzzy relation equations, one of which gives a theoretical description for general type-2 fuzzy relation equations; the other one can find all the solutions to the symmetrical-valued ones. The results can improve designing type-2 fuzzy controllers, because it provides knowledge to search the optimal solutions or to find the reason if there is no solution. Finally some numerical examples verify the correctness of the results/algorithms.

Semi-tensor product of matrices approach to reachability of finite automata with application to language recognition

This paper investigates the transition function and the reachability conditions of finite automata by using a semitensor product of matrices, which is a new powerful matrix analysis tool. The states and input symbols are first expressed in vector forms, then the transition function is described in an algebraic form. Using this algebraic representation, a sufficient and necessary condition of the reachability of any two states is proposed, based on which an algorithm is developed for discovering all the paths from one state to another. Furthermore, a mechanism is established to recognize the language acceptable by a finite automaton. Finally, illustrative examples show that the results/algorithms presented in this paper are suitable for both deterministic finite automata （DFA） and nondeterministic finite automata （NFA）.

On Semi-tensor Product of Matrices and Its Applications

Abstract The left semi-tensor product of matrices was proposed in [2]. In this paper the right semi-tensor product is introduced first. Some basic properties are presented and compared with those of the left semi-tensor product.Then two new applications are investigated. Firstly, its applications to connection, an important concept in differential geometry, is considered. The structure matrix and the Christoffel matrix are introduced. The transfer formulas under coordinate transformation are expressed in matrix form. Certain new results are obtained. Secondly, the structure of finite dimensional Lie algebra, etc. are investigated under the matrix expression.These applications demonstrate the usefulness of the new matrix products.

Modeling and reachability analysis of synchronizing transitions bounded Petri net systems based upon semi-tensor product of matrices

The reachability problem of synchronizing transitions bounded Petri net systems （BPNSs） is investigated in this paper by constructing a mathematical model for dynamics of BPNS. Using the semi-tensor product （STP） of matrices, the dynamics of BPNSs, which can be viewed as a combination of several small bounded subnets via synchronizing transitions, are described by an algebraic equation. When the algebraic form for its dynamics is established, we can present a necessary and sufficient condition for the reachability between any marking （or state） and initial marking. Also, we give a corresponding algorithm to calculate all of the transition paths between initial marking and any target marking. Finally, an example is shown to illustrate proposed results. The key advantage of our approach, in which the set of reachable markings of BPNSs can be expressed by the set of reachable markings of subnets such that the big reachability set of BPNSs do not need generate, is partly avoid the state explosion problem of Petri nets （PNs）.

Dynamic output feedback stabilization of deterministic finite automata via the semi-tensor product of matrices approach

This paper deals with the dynamic output feedback stabilization problem of deterministic finite automata(DFA).The static form of this problem is defined and solved in previous studies via a set of equivalent conditions.In this paper,the dynamic output feedback(DOF)stabilization of DFAs is defined in which the controller is supposed to be another DFA.The DFA controller will be designed to stabilize the equilibrium point of the main DFA through a set of proposed equivalent conditions.It has been proven that the design problem of DOF stabilization is more feasible than the static output feedback(SOF)stabilization.Three simulation examples are provided to illustrate the results of this paper in more details.The first example considers an instance DFA and develops SOF and DOF controllers for it.The example explains the concepts of the DOF controller and how it will be implemented in the closed-loop DFA.In the second example,a special DFA is provided in which the DOF stabilization is feasible,whereas the SOF stabilization is not.The final example compares the feasibility performance of the SOF and DOF stabilizations through applying them to one hundred random-generated DFAs.The results reveal the superiority of the DOF stabilization.

Compatible-invariant subset analysis of deterministic finite automata via semi-tensor product of matrices approach

The compatible-invariant subset of deterministic finite automata（ DFA） is investigated to solve the problem of subset stabilization under the frameworks of semi-tensor product（ STP） of matrices. The concepts of compatibleinvariant subset and largest compatible-invariant subset are introduced inductively for Moore-type DFA,and a necessary condition for the existence of largest compatible-invariant subset is given. Meanwhile,by using the STP of matrices,a compatible feasible event matrix is defined with respect to the largest compatible-invariant subset.Based on the concept of compatible feasible event matrix,an algorithm to calculate the largest compatible-invariant subset contained in a given subset is proposed. Finally,an illustrative example is given to validate the results.

Linear Maps Preserving Idempotency of Products of Matrices on Upper Triangular Matrix Algebras

Let Tn be the algebra of all n × n complex upper triangular matrices. We give the concrete forms of linear injective maps on Tn which preserve the nonzero idempotency of either products of two matrices or triple Jordan products of two matrices.

On the Infinite Products of Matrices

In different fields in space researches, Scientists are in need to deal with the product of matrices. In this paper, we develop conditions under which a product Пi=0∞ of matrices chosen from a possibly infinite set of matrices M={Pj, j∈J} converges. There exists a vector norm such that all matrices in M are no expansive with respect to this norm and also a subsequence {ik}k=0∞ of the sequence of nonnegative integers such that the corresponding sequence of operators {Pik}k=0∞ converges to an operator which is paracontracting with respect to this norm. The continuity of the limit of the product of matrices as a function of the sequences {ik}k=0∞ is deduced. The results are applied to the convergence of inner-outer iteration schemes for solving singular consistent linear systems of equations, where the outer splitting is regular and the inner splitting is weak regular.

PROBLEM OF EQUALITIES IN EIGENVALUE INEQUALITIES FOR PRODUCTS OF POSITIVE SEMIDEFINITE HERMITIAN MATRICES

Let A∈Cm×n,set eigenvalues of matrix A with |λ1 （A）|≥|λ2（A）|≥…≥|λn（A）|,write A≥0 if A is a positive semidefinite Hermitian matrix, and denote∧k （A）=diag （λ1（A）,…,λk（A））,∧(（n-k）.（A）=diag (λk+1（A）,…,λn（A）)for any k=1, 2,...,n if A≥0. Denote all n order unitary matrices by Un×n.Problem of equalities to hold in eigenvalue inequalities for products of matrices

REVERSE ORDER LAW FOR GROUP INVERSE OF PRODUCT OF MATRICES ON SKEW FIELDS

Let Kn×n be the set of all n×n matrices and Krn×n the set {A∈Kn×n|rankA=r} on askew field K. Zhuang [1] denotes by A# the group inverse of A∈Kn×n which is the solu-tion of the euqations:AXA=A, XAX=X, AX=AX.

Compound Product of Hypermatrices

The semi-tensor product(STP)of matrices is generalized to multidimensional arrays,called the compound product of hypermatrices.The product is first defined for three-dimensional hypermatrices with compatible orders and then extended to general cases.Three different types of hyperdeterminants are introduced and certain properties are revealed.The Lie groups and Lie algebras corresponding to the hypermatrix products are constructed.Finally,these results are applied to dynamical systems.

Semi-tensor product approach to controllability and stabilizability of finite automata

Using semi-tensor product of matrices, the controllability and stabilizability of finite automata are investigated. By expressing the states, inputs, and outputs in vector forms, the transition and output functions are represented in matrix forms.Based on this algebraic description, a necessary and sufficient condition is proposed for checking whether a state is controllable to another one. By this condition, an algorithm is established to find all the control sequences of an arbitrary length. Moreover, the stabilizability of finite automata is considered, and a necessary and sufficient condition is presented to examine whether some states can be stabilized. Finally, the study of illustrative examples verifies the correctness of the presented results/algorithms.

Berry-Esseen bounds and moderate deviations for the norm, entries and spectral radius of products of positive random matrices

Let(g_(n))_(n≥1) be a sequence of independent and identically distributed positive random d×d matrices and consider the matrix product G_(n)=g_(n)…g_1.Under suitable conditions,we establish the Berry-Esseen bounds on the rate of convergence in the central limit theorem and Cramer-type moderate deviation expansions,for any matrix norm ‖G_(n)‖ of G_(n),its entries G_(n)^(i,j) and its spectral radius ρ(G_(n)).Extended versions of their joint law with the direction of the random walk G_(n)x are also established,where x is a starting point in the unit sphere of R~d.

Networked Evolutionary Model of Snow-Drift Game Based on Semi-Tensor Product

This paper investigates the networked evolutionary model based on snow-drift game with the strategy of rewards and penalty. Firstly, by using the semi-tensor product of matrices approach, the mathematical model of the networked evolutionary game is built. Secondly, combined with the matrix expression of logic, the mathematical model is expressed as a dynamic logical system and next converted into its evolutionary dynamic algebraic form. Thirdly, the dynamic evolution process is analyzed and the final level of cooperation is discussed. Finally, the effects of the changes in the rewarding and penalty factors on the level of cooperation in the model are studied separately, and the conclusions are verified by examples.

Self-Triggered Set Stabilization of Boolean Control Networks and Its Applications

Set stabilization is one of the essential problems in engineering systems, and self-triggered control(STC) can save the storage space for interactive information, and can be successfully applied in networked control systems with limited communication resources. In this study, the set stabilization problem and STC design of Boolean control networks are investigated via the semi-tensor product technique. On the one hand, the largest control invariant subset is calculated in terms of the strongly connected components of the state transition graph, by which a graph-theoretical condition for set stabilization is derived. On the other hand, a characteristic function is exploited to determine the triggering mechanism and feasible controls. Based on this, the minimum-time and minimum-triggering open-loop, state-feedback and output-feedback STCs for set stabilization are designed,respectively. As classic applications of self-triggered set stabilization, self-triggered synchronization, self-triggered output tracking and self-triggered output regulation are discussed as well. Additionally, several practical examples are given to illustrate the effectiveness of theoretical results.

Semi-tensor product approach for partially symmetric games

In this paper,a criterion for the partially symmetric game(PSG)is derived by using the semitensor product approach.The dimension and the basis of the linear subspace composed of all the PSGs with respect to a given set of partial players are calculated.The testing equations with the minimum number are concretely determined,and the computational complexity is analysed.Finally,two examples are displayed to show the theoretical results.

公理化的矩阵半张量积

本文给出矩阵半张量积的一个公理化框架,它包括矩阵–矩阵半张量积、矩阵–向量半张量积和向量–向量半张量积.首先,对目前通用的各类矩阵半张量积的基本性质与应用做一个综述性的回顾.然后,介绍一种新近出现的矩阵半张量积,即保维数矩阵半张量积.跟普通矩阵乘法一样,它是多功能的,即它可同时实现矩阵–矩阵乘积、矩阵–向量乘积和向量–向量乘积这3种功能.最后,本文介绍保维数矩阵半张量积的一些代数性质,包括非方矩阵的Cayley-Hamilton定理,非方矩阵的特征值、特征向量等.