Search

The inverse eigenvalue problem of a graph G is the problem of characterizing all lists of eigenvalues of real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of G. The strong spectral property is a powerful tool in this problem, which identifies matrices whose entries can be perturbed while controlling the pattern and preserving the eigenvalues. The Matrix Liberation Lemma introduced by Barrett et al. in 2020 advances the notion to a more general setting. In this paper we revisit the Matrix Liberation Lemma and prove an equivalent statement, that reduces some of the technical difficulties in applying the result. We test our method on matrices of the form M = A ⊕ B and show how this new approach supplements the results that can be obtained from the strong spectral property only. While extending this notion to the direct sums of graphs, we discover a surprising connection with the zero forcing game on Cartesian products of graphs. Throughout the paper we apply our results to resolve a selection of open cases for the inverse eigenvalue problem of a graph on six vertices. [ABSTRACT FROM AUTHOR]

We introduce a notion of compatibility for multiplicity matrices. This gives rise to a necessary condition for the join of two (possibly disconnected) graphs G and H to be the pattern of an orthogonal symmetric matrix, or equivalently, for the minimum number of distinct eigenvalues q of G ∨ H to be equal to two. Under additional hypotheses, we show that this necessary condition is also sufficient. As an application, we prove that q (G ∨ H) is either two or three when G and H are unions of complete graphs, and we characterise when each case occurs. [ABSTRACT FROM AUTHOR]

We prove that the Laplacian matrix of the total graph of a finite commutative ring with identity has integer eigenvalues and present a recursive formula for computing its eigenvalues and eigenvectors. We also prove that the total graph of a finite commutative local ring with identity is super integral and give an example showing that this is not true for arbitrary rings. [ABSTRACT FROM AUTHOR]

In this work, the inverse eigenvalue problem is completely solved for a subfamily of clique-path graphs, in particular for lollipop graphs and generalized barbell graphs. For a matrix A with associated graph G , a new technique utilizing the strong spectral property is introduced, allowing us to construct a matrix A ′ whose graph is obtained from G by appending a clique while arbitrary list of eigenvalues is added to the spectrum. Consequently, many spectra are shown realizable for block graphs. [ABSTRACT FROM AUTHOR]

We introduce the set G SSP of all simple graphs G with the property that each symmetric matrix corresponding to a graph G ∈ G SSP has the strong spectral property. We find several families of graphs in G SSP and, in particular, characterise the trees in G SSP. [ABSTRACT FROM AUTHOR]

We prove that over a commutative semiring every symmetric strongly invertible matrix with nonnegative numerical range has a Cholesky decomposition. [ABSTRACT FROM AUTHOR]

Abstract We propose a Nordhaus–Gaddum conjecture for q (G) , the minimum number of distinct eigenvalues of a symmetric matrix corresponding to a graph G : for every graph G excluding four exceptions, we conjecture that q (G) + q (G c) ≤ | G | + 2 , where G c is the complement of G. We compute q (G c) for all trees and all graphs G with q (G) = | G | − 1 , and hence we verify the conjecture for trees, unicyclic graphs, graphs with q (G) ≤ 4 , and for graphs with | G | ≤ 7. [ABSTRACT FROM AUTHOR]

In this paper we introduce a parameter Mm ( G ) , defined as the maximum over the minimal multiplicities of eigenvalues among all symmetric matrices corresponding to a graph G . We develop basic properties of Mm ( G ) and compute it for several families of graphs. [ABSTRACT FROM AUTHOR]

We study the simultaneously nilpotent index of a simultaneously nilpotent set of matrices over an antinegative commutative semiring S . We find an upper bound for this index and give some characterizations of the simultaneously nilpotent sets when this upper bound is met. In the special case of antinegative semirings with all zero divisors nilpotent, we also find a bound on the simultaneously nilpotent index for all nonmaximal simultaneously nilpotent sets of matrices and establish their cardinalities in case of a finite S . [ABSTRACT FROM AUTHOR]

Abstract: Let G be an undirected graph on n vertices and let be the set of all real symmetric matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The Inverse Eigenvalue Problem for a graph G is a problem of determining all possible lists that can occur as the lists of eigenvalues of matrices in . This question is, in general, hard to answer and several variations were studied, most notably the minimum rank problem. In this paper we introduce the problem of determining for which graphs G there exists a matrix in whose characteristic polynomial is a square, i.e. the multiplicities of all its eigenvalues are even. We solve this question for several families of graphs. [Copyright &y& Elsevier]

In this paper we study zero-divisor graphs of rings and semirings. We show that all zero-divisor graphs of (possibly noncommutative) semirings are connected and have diameter less than or equal to 3. We characterize all acyclic zero-divisor graphs of semirings and prove that in the case zero-divisor graphs are cyclic, their girths are less than or equal to 4. We find all possible cyclic zero-divisor graphs over commutative semirings having at most one 3-cycle, and characterize all complete k-partite and regular zero-divisor graphs. Moreover, we characterize all additively cancellative commutative semirings and all commutative rings such that their zero-divisor graph has exactly one 3-cycle. [ABSTRACT FROM AUTHOR]

We study the structure of the nilpotent commutator 𝒩 B of a nilpotent matrix B. We show that 𝒩 B intersects all nilpotent orbits for conjugation if and only if B is a square-zero matrix. We describe nonempty intersections of 𝒩 B with nilpotent orbits in the case the n × n matrix B has rank n − 2. Moreover, we give some results concerning the inverse image of the map taking B to the maximal nilpotent orbit intersecting 𝒩 B . [ABSTRACT FROM AUTHOR]

Abstract: We study diameters and girths of noncommuting graphs of semirings. For a noncommutative semiring that is either multiplicatively or additively cancellative, we find the diameter and the girth of its noncommuting graph and prove that it is Hamiltonian. Moreover, we find diameters and girths of noncommuting graphs of all nilpotent matrices over a semiring, all invertible matrices over a semiring, all noninvertible matrices over a semiring, and the full matrix semiring. In nearly all cases we prove that diameters are less than or equal to 2 and girths are less than or equal to 3, except in the case of nilpotent matrices. [Copyright &y& Elsevier]

Abstract: We calculate diameters and girths of commuting graphs of the set of all nilpotent matrices over a semiring, the group of all invertible matrices over a semiring, and the full matrix semiring. [Copyright &y& Elsevier]

Abstract: We study the idempotent matrices over a commutative antiring. We give a characterization of idempotent matrices by digraphs. We study the orbits of conjugate action and find the cardinality of orbits of basic idempotents. Finally, we prove that invertible, linear and idempotent preserving operators on matrices over entire antirings are exactly conjugate actions for . We also give a complete characterization of the case. [Copyright &y& Elsevier]

Abstract: In this paper, we characterize invertible matrices over an arbitrary commutative antiring S with 1 and find the structure of . We find the number of nilpotent matrices over an entire commutative finite antiring. We prove that every nilpotent matrix over an entire antiring can be written as a sum of square-zero matrices and also find the necessary number of square-zero summands for an arbitrary trace-zero matrix to be expressible as their sum. [Copyright &y& Elsevier]

We study the set [image omitted]( [image omitted]) of all possible Jordan canonical forms of nilpotent matrices commuting with a given nilpotent matrix B. We describe [image omitted]( [image omitted]) in the special case when B has only one Jordan block and discuss some consequences. In the general case, we find the maximal possible index of nilpotency in the set of all nilpotent matrices commuting with a given nilpotent matrix. We consider several examples. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we completely characterize all possible pairs of Jordan canonical forms for mutually annihilating nilpotent pairs, i.e. pairs of nilpotent matrices such that . [Copyright &y& Elsevier]

In this paper we characterize all nilpotent orbits under the action by conjugation that intersect the nilpotent centralizer of a nilpotent matrix B consisting of two Jordan blocks of the same size. We list all the possible Jordan canonical forms of the nilpotent matrices that commute with B by characterizing the corresponding partitions. [ABSTRACT FROM AUTHOR]

Background: Matrix factorization methods are linear models, with limited capability to model complex relations. In our work, we use tropical semiring to introduce non-linearity into matrix factorization models. We propose a method called Sparse Tropical Matrix Factorization (STMF) for the estimation of missing (unknown) values in sparse data. Results: We evaluate the efficiency of the STMF method on both synthetic data and biological data in the form of gene expression measurements downloaded from The Cancer Genome Atlas (TCGA) database. Tests on unique synthetic data showed that STMF approximation achieves a higher correlation than non-negative matrix factorization (NMF), which is unable to recover patterns effectively. On real data, STMF outperforms NMF on six out of nine gene expression datasets. While NMF assumes normal distribution and tends toward the mean value, STMF can better fit to extreme values and distributions. Conclusion: STMF is the first work that uses tropical semiring on sparse data. We show that in certain cases semirings are useful because they consider the structure, which is different and simpler to understand than it is with standard linear algebra. [ABSTRACT FROM AUTHOR]

An important facet of the inverse eigenvalue problem for graphs is to determine the minimum number of distinct eigenvalues of a particular graph. We resolve this question for the join of a connected graph with a path. We then focus on bordering a matrix and attempt to control the change in the number of distinct eigenvalues induced by this operation. By applying bordering techniques to the join of graphs, we obtain numerous results on the nature of the minimum number of distinct eigenvalues as vertices are joined to a fixed graph. [ABSTRACT FROM AUTHOR]

In this paper, we initiate the study of the total zero-divisor graph over a commutative ring with unity. This graph is constructed by both relations that arise from the zero-divisor graph and from the total graph of a ring and give a joint insight of the structure of zero-divisors in a ring. We characterize Artinian rings with the connected total zero-divisor graphs and give their diameters. Moreover, we compute major characteristics of the total zero-divisor graph of the ring ℤ m of integers modulo m and prove that the total zero-divisor graphs of ℤ m and ℤ n are isomorphic if and only if m = n. [ABSTRACT FROM AUTHOR]

We calculate the diameters of commuting graphs of matrices over the binary Boolean semiring, the tropical semiring and an arbitrary nonentire commutative semiring. We also find the lower bound for the diameter of the commuting graph of the semigroup of matrices over an arbitrary commutative entire antinegative semiring. [ABSTRACT FROM AUTHOR]

It is shown that the commuting graph of a matrix algebra over a finite field has diameter at most five if the size of the matrices is not a prime nor a square of a prime. It is further shown that the commuting graph of even-sized matrices over finite field has diameter exactly four. This partially proves a conjecture stated by Akbari, Mohammadian, Radjavi, and Raja [Linear Algebra Appl. 418 (2006) 161–176]. [ABSTRACT FROM AUTHOR]

Abstract: Matrices with maximal or minimal centralizers are classified over fields with sufficiently large orders. [Copyright &y& Elsevier]