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 generalization 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 data; (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 Morgen's problem for control systems is formulated as a numerically solvable problem.

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.

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.

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

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.

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.

基于矩阵半张量积解四元数广义Sylvester矩阵方程组

该文利用矩阵半张量积求解四元数广义Sylvester矩阵方程组.首先将实矩阵半张量积运算推广到四元数矩阵,进而利用四元数矩阵半张量积提出四元数矩阵在向量算子下的一些新结论,利用这些结论将四元数矩阵方程组转化为四元数线性方程组,最后转化为实线性方程组,从而得到四元数广义Sylvester矩阵方程组有解的充要条件及通解表达式,并给出其极小范数解.最后通过数值算例说明该方法的有效性.

四元数矩阵方程(A_(1)XB_(1),…,A_(k)XB_(k))=(C_(1),…,C_(k))的极小范数最小二乘Toeplitz解

基于四元数矩阵实表示,结合矩阵H-表示和矩阵半张量积提出一种求解四元数矩阵方程(A_(1)XB_(1),…,A_(k)XB_(k))=(C_(1),…,C_(k))的极小范数最小二乘Toeplitz解的有效方法,给出该四元数矩阵方程存在Toeplitz解的充要条件及通解表达式.给出数值算法并通过算例分别从误差与计算时间两个方面验证该方法的有效性.

Contracted product of hypermatrices via STP of matrices

An equivalent definition of hypermatrices is introduced.The matrix expression of hypermatrices is proposed.Using permu-tation matrices,the conversion between different matrix expressions is revealed.The various kinds of contracted products of hypermatrices are realized by semi-tensor products(STP)of matrices via matrix expressions of hypermatrices.