GRAPH CONTRACTIONS AND A GENERALIZED MÖBIUS INVERSION

Publisher Website
Google Scholar
Abstract
Summary: This work presents a generalization of Möbius inversion by constructing, on partially ordered sets, pairs of “contracted” matrices which are inverses of each other. We commence by defining some nonstandard matrix operations, for which a number of results are derived, culminating in a theorem that furnishes conditions under which matrix contraction will commute with matrix multiplication. One consequence of mapping these results into graph theoretical operations on partial ordering graphs (transitive, antisymmetric digraphs) is to suggest a novel class of functions defined thereon which generalize the Riemann and Möbius functions in a way that may lead to new algorithms for matrix inversion. The usefulness of these functions in physical science is illustrated with two examples which in recent publications made implicit use of graph contraction. The work suggests a number of tantalizing (as yet unsolved) problems; our paper concludes with a summary of these.

This publication has 4 references indexed in Scilit: