Algorithms for computing linear invariants if directed graphs

Details Algorithms for computing linear invariants if directed graphs Algorithms for computing linear invariants if directed graphs

2005-03-11

arxiv.org/abs/math/0503228v1

Mathematics

Combinatorics

A longer version submitted to Linear Algebra and its Applications

Scientific paper

Call two pairs $(M,N)$ and $(M',N')$ of $m\times n$ matrices over a field $K$, \emph{simultaneously K-equivalent} if there exist square invertible matrices $S,T$ over K, with $M'=SMT$ and $N'=SNT$. Kronecker \cite{Kronecker} has given a complete set of invariants for simultaneous equivalence of pairs of matrices. Associate in the natural way to a finite directed graph $\Gamma$, with $v$ vertices and $e$ edges, an ordered pair $(M,N)$ of $e\times v$ matrices of zeros and ones. It is natural to try to compute the Kronecker invariants of such a pair $(M,N)$, particularly since they clearly furnish isomorphism-invariants of $\Gamma$. Let us call two graphs `linearly equivalent' when their two corresponding pairs are simultaneously equivalent. The purpose of the present paper, is to compute directly these Kronecker invariants of finite directed graphs, from elementary combinatorial properties of the graphs. A pleasant surprise is that these new invariants are purely {\bf rational} --indeed, {\bf integral}, in the sense that the computation needed to decide if two directed graphs are linearly equivalent only involves counting vertices in various finite graphs constructed from each of the given graphs-- and {\bf does not involve finding the irreducible factorization of a polynomial over K} (in apparent contrast both to the familiar invariant-computations of graphs furnished by the eigenvalues of the connection matrix, and to the isomorphism problem for general pairs of matrices.)

Affiliated with

Also associated with

No associations

Rating

Algorithms for computing linear invariants if directed graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for computing linear invariants if directed graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for computing linear invariants if directed graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-452726