Permutation Similarity Of Matrices And Its Application On Graph Theory

Permutation similarity of matrices is a vital transformation in field of matrix theory.Its application varies in graph isomorphism,model of social network,database and computation on high-dimension matrices.According to the theory of invariant,to explore permutation similarity is to find invariants of matrices during the permutation and to construct the permutation mapping respectively.The works finished in the paper are as following:The matrices of equivalence relation are treated as the research object.Any matrix of equivalence relation is congruent of permutation to the certain canonical form of block 1-diagonal-matrix.Some properties of congruent permutation are obtained via the aspect of permutation computation.The generation algorithm for permutation matrix based on the depth-first-search algorithm of graph is set up:according to the properties of searching road from Equivalent Relation Graph(ERG)by Depth-First Search(DFS),the permutation is obtained by the comparison of searching road from ERG by DFS and initial node-numbers.Then the permutation is resolved into the product of several interchanges.At last the final permutation matrix is conducted and the judgement of congruent permutation for certain two matrices of equivalence relation is finished.From the particular to the general,graph isomorphism problem is equal to general 0-1 matrix permutation similarity decision problem at the perspective of the matrix.The Decision of Human Nerves Network model(DHNN)is built by setting energy function in additional constraint on permutation similarityFinally,the condition on decomposition of permutation is analyzed separately for even and odd permutation.The criteria for trivial decomposition of permutation is coming up with.At last the relationship among mode-length,order of permutation and minimum exchange number is also proofed which could provide the foundation for research on permutation similarity and graph isomorphism.