Algorithmic aspects of arithmetical structures

Arithmetical structures on graphs were first introduced in [11]. Later in [3] 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 (d,r)∈N₊ⁿ×N₊ⁿ such that (Diag(d)−L)r^t=0^t and gcd⁡(r₁,…,r_n)=1. Thus, arithmetical structures on L are solutions of the polynomial Diophantine equation f_L(X):=det⁡(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.