Back to Search
Start Over
Algorithmic aspects of arithmetical structures
- Source :
- Linear Algebra and its Applications. 640:191-208
- Publication Year :
- 2022
- Publisher :
- Elsevier BV, 2022.
-
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 $(\mathbf{d},\mathbf{r})\in \mathbb{N}_+^n\times \mathbb{N}_+^n$ such that \[ (\textrm{Diag}(\mathbf{d})-L)\mathbf{r}^t=\mathbf{0}^t\text{ and }\gcd(r_1,\ldots,r_n)=1. \] Thus, arithmetical structures on $L$ are solutions of the polynomial Diophantine equation \[ f_L(X):=\det(\text{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.<br />14 pages. Major changes, sections 4 and 5 was deleted. Section 4 is the base of the article "Arithmetical structures on dominated polynomials"
Details
- ISSN :
- 00243795
- Volume :
- 640
- Database :
- OpenAIRE
- Journal :
- Linear Algebra and its Applications
- Accession number :
- edsair.doi.dedup.....8798b2b9d4cc549eabc09e3dd03e0dad