Algorithmic aspects of arithmetical structures

Matrices, determinants in number theory (11C20) Diophantine equations in many variables (11D72) Computer solution of Diophantine equations (11Y50) Positive matrices and their generalizations; cones of matrices (15B48)

Abstract: Arithmetical structures on graphs were first introduced in cite{Lorenzini89}. Later in cite{arithmetical} they were further studied in the setting of square non-negative integer matrices. In both cases, necessary and sufficient conditions for the finiteness of the set of arithmetical structures were given. More precisely, an arithmetical structure on a non-negative integer matrix

L

with zero diagonal is a pair

(m a t h b f d, m a t h b f r) i n m a t h b b N_{+}^{n} i m e s m a t h b b N_{+}^{n}

such that [ ( extrm{Diag}(mathbf{d})-L)mathbf{r}^t=mathbf{0}^t ext{ and }gcd(r_1,ldots,r_n)=1. ] Thus, arithmetical structures on

L

are solutions of the polynomial Diophantine equation [ f_L(X):=det( ext{Diag}(X)-L)=0. ] Therefore, it is of interest to ask for an algorithm that compute them. We present an algorithm that computes arithmetical structures on a square integer non-negative matrix

L

with zero diagonal. In order to do this we introduce a new class of Z-matrices, which we call quasi

M

-matrices.

Review text

This paper studies the set of arithmetical structures on non-negative integer \(n\times n\)-matrices \(L\) with zero diagonal, defined as follows: \[ \mathcal{A}(L)=\left\{(\mathbf{d},\mathbf{r})\in\mathbb{N}_+^n\times \mathbb{N}_+^n \, | \, (\textrm{Diag}(\mathbf{d})-L)\mathbf{r}^t = \mathbf{0}^t \, \textrm{and} \gcd(r_1,\dots,r_n)=1\right\}. \] This is a finite set, and the main result of the article is Algorithm 3.4, which computes the set \(\mathcal{D}(L)\) defined below, given the matrix \(L\) as input. \[ \mathcal{D}(L)=\left\{\mathbf{d}\in \mathbb{N}_+^n \, | \, (\mathbf{d},\mathbf{r})\in\mathcal{A}(L)\right\}. \] In order to develop this algorithm, the author's introduce the class of \textit{quasi \(M\)-matrices}, which are a simple generalization of \(M\)-matrices. The paper concludes by using the algorithm to provide computational evidence for the following conjecture:\\ Conjecture: Let \(G\) be a simple graph with \(n\) vertices. Then \[ |\mathcal{A}(P_n)|\le |\mathcal{A}(G)|\le|\mathcal{A}(K_n)|, \] where \(P_n\) and \(K_n\) are the path and complete graph on \(n\) vertices respectively. Here, \(\mathcal{A}(G)=\mathcal{A}(L_G)\) denotes the set of arithmetical structures on the Laplacian matrix of the graph \(G\).

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: Algorithmic aspects of arithmetical structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2668075)