Combinatorics and Graph Theory

   

Embedding Cycles Within Adjacency Matrices to Represent Rational Generating Functions

Authors: Yonah Berwaldt

This paper explores populating adjacency matrices with connected cycles whose final outputs represent the coefficients of rational generating functions (RGFs). An RGF takes the form of: $p(x)/q(x) + r(x)$. The denominator, $q(x)$, takes the form of: Constant $\cdot (1-c_1x^{x_1})(1-c_2x^{x_2})... (1-c_nx^{x_n})$ where the $c_i$ are complex numbers and where factors can possibly have multiplicities greater than one. It is well known that a closed form solution exists for computing coefficients of RGFs. Also, one can write the linear recurrence relation associated with every RGF into a matrix format. Using matrices, one can compute coefficients for an RGF, such as Molien series for finite groups, in logarithmic time. What has not yet been shown (or is not yet commonly discussed) is that one can conceptualize an RGF as a system of connected cycles within an overarching adjacency matrix. For example, a single cycle of length two would have vertex A connect to vertex B which itself connects back to vertex A with a directed arrow of weight $c_i$. In this conceptualization, each coefficient of an RGF can be reproduced by taking a suitable adjacency matrix to an integer power. Nothing essential is lost by taking this perspective. Due to the self-similar nature of the matrix, we devise an algorithm that can calculate coefficients of RGFs in constant time. Using memoization, a technique for caching intermediate results, calculating coefficients of RGFs can also be done in logarithmic time. One observation is that, depending on the situation (i.e. what $q(x)$ is), there may be a computational benefit to taking the cyclical perspective. For example, for certain $q(x)$, the traditional matrix has cells containing positive and negative values whereas the cyclical approach has cells containing only positive values. The computational benefit is probably irrelevant for computers; however, it may be important for restrictive systems, such as biological systems / neural networks that may have a tight operating envelope. We make a final observation that each cyclical matrix representation can be thought of as a graph which is an epsilon away from being strongly connected. Studying the behavior of these matrices may yield insight into the behavior of a broader class of function. In essence, the study of sequences modeled by RGFs can be converted to the study of connected cyclical graphs that model the RGFs or vice versa.

Comments: 24 Pages.

Download: PDF

Submission history

[v1] 2021-05-19 17:03:13

Unique-IP document downloads: 411 times

Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus