Search

We consider elements of finite order in the Riordan group $\cal R$ over a field of characteristic $0$. Viewing $\cal R$ as a semi-direct product of groups of formal power series, we solve, for all $n \geq 2$, two foundational questions posed by L. Shapiro for the case $n = 2$ (`involutions'): Given a formal power series $F(x)$ of finite compositional order and an integer $n\geq 2$, Theorem 1 states, exactly which $g(x)$ make $\big(g(x), F(x)\big)$ a Riordan element of order $n$. Theorem 2 classifies finite-order Riordan group elements up to conjugation in $\cal R$. Viewing $\cal R$ as a group of infinite lower triangular matrices, we interpret Theorem 1 in terms of existence of eigenvectors and Theorem 2 as a normal form for finite order Riordan arrays under similarity. These lead to Theorem 3, a formula for all eigenvectors of finite order Riordan arrays; and we show how this can lead to interesting combinatorial identities. We then relate our work to papers of Cheon and Kim which motivated this paper and we solve the Open question which they posed. Finally, this circle of ideas gives a new proof of C. Marshall's theorem, which finds the unique $F(x)$, given bi-invertible $g(x)$, such that $\big(g(x), F(x))$ is an involution., Comment: 25 pages. Version 4 corrects the statement of Example 5.6 in the case when $n$ is odd, and adjusts the last four lines of the proof accordingly

In this paper we study the adjacency spectrum of families of finite rooted trees with regular branching properties. In particular, we show that in the case of constant branching, the eigenvalues are realized as the roots of a family of generalized Fibonacci polynomials and produce a limiting distribution for the eigenvalues as the tree depth goes to infinity. We indicate how these results can be extended to periodic branching patterns and also provide a generalization to higher order simplicial complexes., 18 pages, 3 figures. Updated version contains additional results and expanded references. Accepted for publication in Linear Algebra and its Applications

Distance ideals generalize the Smith normal form of the distance matrix of a graph. The family of graphs with 2 trivial distance ideals contains the family of graphs whose distance matrix has at most 2 invariant factors equal to 1. Here we give an infinite family of forbidden induced subgraphs for the graphs with 2 trivial distance ideals. These are also related with other well known graph classes., Some typos were corrected

We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with k blocks of equal size. More precisely, we consider a random d-uniform hypergraph H with n vertices partitioned into k clusters of size s = n / k . Hyperedges e are added independently with probability p if e is contained within a single cluster and q otherwise, where 0 ≤ q p ≤ 1 . We present a spectral algorithm which recovers the clusters exactly with high probability, given mild conditions on n , k , p , q , and d. Our algorithm is based on the adjacency matrix of H, which is a symmetric n × n matrix whose ( u , v ) -th entry is the number of hyperedges containing both u and v. To the best of our knowledge, our algorithm is the first to guarantee exact recovery when the number of clusters k = Θ ( n ) .

For all n > k ≥ 1 , we give formulas for the nullity N ( n , k ) of the n × n skew-symmetric Toeplitz band matrix whose first k superdiagonals have all entries 1 and whose remaining superdiagonals have all entries 0. This is accomplished by counting the number of cycles in certain directed graphs. As an application, for each fixed integer z ≥ 0 and large fixed k, we give an asymptotic formula for the percentage of n > k satisfying N ( n , k ) = z . For the purpose of rapid computation, an algorithm is devised that quickly computes N ( n , k ) even for extremely large values of n and k.

Recently, Anderson et al. (2019) proposed the concept of rankability, which refers to a dataset's inherent ability to produce a meaningful ranking of its items. In the same paper, they proposed a rankability measure that is based on an integer program for computing the minimum number of edge changes made to a directed graph in order to obtain a complete dominance graph, i.e., an acyclic tournament graph. In this article, we prove a spectral-degree characterization of complete dominance graphs and apply this characterization to produce a new measure of rankability that is cost-effective and more widely applicable. We support the details of our algorithm with several results regarding the conditioning of the Laplacian spectrum of complete dominance graphs and the Hausdorff distance between their Laplacian spectrum and that of an arbitrary directed graph with weights between zero and one. Finally, we analyze the rankability of datasets from the world of chess and college football.

The purpose of this paper is to highlight the role played by the anti-regular graph within the class of threshold graphs. Using the fact that every threshold graph contains a maximal anti-regular graph, we show that some known results, and new ones, on the spectral properties of threshold graphs can be deduced from (i) the known results on the eigenvalues of anti-regular graphs, (ii) the subgraph structure of threshold graphs, and (iii) eigenvalue interlacing. In particular, we prove a strengthened version of the recently proved fact that no threshold graph contains an eigenvalue in the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] , except possibly the trivial eigenvalues −1 and/or 0, determine the inertia of a threshold graph, and give partial results on a conjecture regarding the optimality of the non-trivial eigenvalues of an anti-regular graph within the class of threshold graphs.

A set of lines through the origin in Euclidean space is called equiangular when any pair of lines from the set intersects with each other at a common angle. We study the maximum size of equiangular lines in Euclidean space and use graph theoretic approach to prove that all the currently known construction for maximum equiangular lines in $\mathbb R^d$ cannot add another line to form a larger equiangular set of lines if $14 \leq d \leq 20$ and $d \neq 15$. We give new constructions of large equiangular lines which are 248 equiangular lines in $\mathbb R^{42}$, 200 equiangular lines in $\mathbb{R}^{41}$, 168 equiangular lines in $\mathbb{R}^{40}$, 152 equiangular lines in $\mathbb R^{39}$ with angle $1/7$, and 56 equiangular lines in $\mathbb R^{18}$ with angle $1/5$., 6 pages; title changed; new results about constructions of large equiangular sets are added in Section 3

We discuss the Grassmann graph $J_q(N,D)$ with $N \geq 2D$, having as vertices the $D$-dimensional subspaces of an $N$-dimensional vector space over the finite field $\mathbb{F}_q$. This graph is distance-regular with diameter $D$; to avoid trivialities we assume $D\geq 3$. Fix a pair of a Delsarte clique $C$ of $J_q(N,D)$ and a vertex $x$ in $C$. We construct a $2D$-dimensional irreducible module $\mathbf{W}$ for the Terwilliger algebra $\mathbf{T}$ of $J_q(N,D)$ associated with the pair $x$, $C$. We show that $\mathbf{W}$ is an irreducible module for the confluent Cherednik algebra $\mathcal{H}_\mathrm{V}$ and describe how the $\mathbf{T}$-action on $\mathbf{W}$ is related to the $\mathcal{H}_\mathrm{V}$-action on $\mathbf{W}$. Using the $\mathcal{H}_\mathrm{V}$-module $\mathbf{W}$, we define non-symmetric dual $q$-Hahn polynomials and prove their recurrence and orthogonality relations from a combinatorial viewpoint., Comment: 31 pages, 3 figures

Applied to a nonnegative $m\times n$ matrix with a nonzero $\sigma$-diagonal, the sequence of matrices constructed by alternate row and column scaling conveges to a doubly stochastic matrix. It is proved that if this sequence converges after only a finite number of scalings, then it converges after at most two scalings., Comment: Corrected typo in statement of Theorem 1; 6 pages

Let $\pi=\{V_1,\dots,V_r\}$ be an equitable partition of the vertex set of a directed graph (digraph) $X$. It is well known that the characteristic polynomial $\phi(X/\pi,x)$ of a quotient graph $X/\pi$ divides that of $X$, but the remainder part is not well investigated. In this paper, we define a deletion graph $X\backslash\pi$ over an equitable partition $\pi$, which is a signed directed graph defined for a fixed set of deleting vertices $\{\bar{v}_i\in V_i, i=1,\cdots,r\}$, and give a similarity transformation exchanging the adjacency matrix $A(X)$ which is compatible with the equitable partition for a block triangular matrix whose diagonal blocks are the adjacency matrix of the quotient graph and the deletion graph. In fact, we show the result for more general matrices including adjacency matrix of graphs, and as corollaries, we show the followings: (i) a decomposition formula of the reciprocal of the Ihara-Bartholdi zeta function over an equitably partitioned undirected graph into the quotient graph part and the deletion graph part, and (ii) Chen and Chen's result ([CC17, Theorem 3.1]) on the Ihara-Bartholdi zeta functions on generalized join graphs, and (iii) Teranishi's result [Ter03, Theorem 3.3]., Comment: 18 pages

We introduce the Bhattacharya-Mesner rank of third order hypermatrices as a relaxation to the tensor rank and devise from it some bounds for the tensor rank. We use the Bhattacharya-Mesner rank to extend to third order hypermatrices the connection relating the rank to a notion of linear dependence. We also derive explicit necessary and sufficient conditions for the existence of third order hypermatrix inverse pair. Finally we use inverse pair to extend to third order hypermatrices the formulation and proof of the matrix rank–nullity theorem.

We consider the symmetric group Sym n , n ⩾ 2 , generated by the set S of transpositions ( 1 i ) , 2 ⩽ i ⩽ n , and the Cayley graph S n = C a y ( Sym n , S ) called the Star graph. For any positive integers n ⩾ 3 and m with n > 2 m , we present a family of eigenfunctions of S n with eigenvalue n − m − 1 and call them PI-eigenfunctions. We then establish a connection of these functions with the standard basis of a Specht module. Finally, in the case of the largest non-principal eigenvalue n − 2 we prove that any eigenfunction of S n can be reconstructed by its values on the second neighbourhood of a vertex.

A d-dimensional matrix is called 1-polystochastic if it is non-negative and the sum over each line equals 1. Such a matrix that has a single 1 in each line and zeros elsewhere is called a 1-permutation matrix. A diagonal of a d-dimensional matrix of order n is a choice of n elements, no two in the same hyperplane. The permanent of a d-dimensional matrix is the sum over the diagonals of the product of the elements within the diagonal. For a given order n and dimension d, the set of 1-polystochastic matrices forms a convex polytope that includes the 1-permutation matrices within its set of vertices. For even n and odd d, we give a construction for a class of 1-permutation matrices with zero permanent. Consequently, we show that the set of 1-polystochastic matrices with zero permanent contains at least n n 3 / 2 ( 1 / 2 − o ( 1 ) ) 1-permutation matrices and contains a polytope of dimension at least c n 3 / 2 for fixed c , d and even n → ∞ . We also provide counterexamples to a conjecture by Taranenko [11] about the location of local extrema of the permanent. For odd d, we give a construction of 1-permutation matrices that decompose into a convex linear sum of positive diagonals. These combine with a theorem of Taranenko [11] to provide counterexamples to a conjecture by Dow and Gibson [4] generalising van der Waerden's conjecture to higher dimensions.

For any graph X with the adjacency matrix A, the transition matrix of the continuous-time quantum walk at time t is given by the matrix-valued function H X ( t ) = e i t A . We say that there is perfect state transfer in X from the vertex u to the vertex v at time τ if | H X ( τ ) u , v | = 1 . It is an important problem to determine whether perfect state transfers can happen on a given family of graphs. In this paper we characterize all the graphs in the Johnson scheme which have this property. Indeed, we show that the Kneser graph K ( 2 k , k ) is the only class in the scheme which admits perfect state transfers. We also show that, under some conditions, some of the unions of the graphs in the Johnson scheme admit perfect state transfer.

In an earlier work, the author together with Guo [Hermitian adjacency matrix of digraphs and mixed graphs, J. Graph Theory 85 (2017) 217-248] introduced the Hermitian adjacency matrix of directed (and partially directed) graphs. However, it appears that a more natural Hermitian matrix exists, and it is the purpose of this note to bring this new Hermitian matrix to the attention of researchers in algebraic graph theory., Comment: Linear Algebra Appl. (2019), in press. arXiv admin note: text overlap with arXiv:1505.01321

A signed graph $\Gamma(G)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $\Gamma(G)$. The energy of a signed graph $\Gamma(G)$ is the sum of the absolute values of the eigenvalues of the adjacency matrix $A(\Gamma(G))$ of $\Gamma(G)$. The random signed graph model $\mathcal{G}_n(p, q)$ is defined as follows: Let $p, q \ge 0$ be fixed, $0 \le p+q \le 1$. Given a set of $n$ vertices, between each pair of distinct vertices there is either a positive edge with probability $p$ or a negative edge with probability $q$, or else there is no edge with probability $1-(p+ q)$. The edges between different pairs of vertices are chosen independently. In this paper, we obtain an exact estimate of energy for almost all signed graphs. Furthermore, we establish lower and upper bounds to the energy of random multipartite signed graphs., Comment: 11 page, 0 figures. arXiv admin note: text overlap with arXiv:0909.4923 by other authors

Every Riordan array has what we call a horizontal half and a vertical half. These halves of a Riordan array have been studied separately before. Here, we place them in a common context, showing that one may be obtained from the other. We also ask and answer the question: given a Riordan array, when is it the half (either horizontal of vertical) of a Riordan array?, 19 pages, extended from first version

This paper deals with the eigenvalues of the adjacency matrices of threshold graphs for which $-1$ and $0$ are considered as trivial eigenvalues. We show that threshold graphs have no non-trivial eigenvalues in the interval $\left[(-1-\sqrt{2})/2,\,(-1+\sqrt{2})/2\right]$. This confirms a conjecture by Aguilar, Lee, Piato, and Schweitzer (2018)., Comment: Comments from referee incorporated; Final version

In this note we prove that the vertex energy of a graph, as defined in Arizmendi and Juarez (2018), can be calculated in terms of a Coulson integral formula. We present examples of how this formula can be used, and we show some applications to bipartite graphs., 14 pages, 5 figures

Let $G$ be a weakly connected directed graph with asymmetric graph Laplacian ${\cal L}$. Consensus and diffusion are dual dynamical processes defined on $G$ by $\dot x=-{\cal L}x$ for consensus and $\dot p=-p{\cal L}$ for diffusion. We consider both these processes as well their discrete time analogues. We define a basis of row vectors $\{\bar \gamma_i\}_{i=1}^k$ of the left null-space of ${\cal L}$ and a basis of column vectors $\{\gamma_i\}_{i=1}^k$ of the right null-space of ${\cal L}$ in terms of the partition of $G$ into strongly connected components. This allows for complete characterization of the asymptotic behavior of both diffusion and consensus --- discrete and continuous --- in terms of these eigenvectors. As an application of these ideas, we present a treatment of the pagerank algorithm that is dual to the usual one. We further show that the teleporting feature usually included in the algorithm is not strictly necessary. This is a complete and self-contained treatment of the asymptotics of consensus and diffusion on digraphs. Many of the ideas presented here can be found scattered in the literature, though mostly outside mainstream mathematics and not always with complete proofs. This paper seeks to remedy this by providing a compact and accessible survey., Comment: 19 pages, Survey Article, 1 figure

Let G be a connected m-uniform hypergraph. In this paper we mainly consider the eigenvectors of the Laplacian or signless Laplacian tensor of G associated with zero eigenvalue, called the first Laplacian or signless Laplacian eigenvectors of G. By means of the incidence matrix of G, the number of first Laplacian or signless Laplacian (or H-)eigenvectors can be obtained explicitly by solving the Smith normal form of the incidence matrix over Z m (or Z 2 ). Consequently, we prove that the number of first Laplacian (H-)eigenvectors is equal to the number of first signless Laplacian (H-)eigenvectors when zero is an (H-)eigenvalue of the signless Laplacian tensor. We establish a connection between first Laplacian (signless Laplacian) H-eigenvectors and the even (odd) bipartitions of G.

We give a counterexample to a conjecture of Wang and Hou related with the sum of the $k$ largest Laplacian eigenvalues of signed graphs., 3 pages, 2 figures

Given a rooted tree T with leaves v 1 , v 2 , … , v n , we define the ancestral matrix C ( T ) of T to be the n × n matrix for which the entry in the i-th row, j-th column is the level (distance from the root) of the first common ancestor of v i and v j . We study properties of this matrix, in particular regarding its spectrum: we obtain several upper and lower bounds for the eigenvalues in terms of other tree parameters. We also find a combinatorial interpretation for the coefficients of the characteristic polynomial of C ( T ) , and show that for d-ary trees, a specific value of the characteristic polynomial is independent of the precise shape of the tree.

Let G be a finite graph, and let G_n be the n-th iterated cone over G. We study the structure of the critical group of G_n arising in divisor and sandpile theory., 4 pages; to appear in Linear Algebra and its Applications; an example is added in version 2

Submitted by Enide Martins (enide@ua.pt) on 2018-12-29T19:16:02Z No. of bitstreams: 1 Trabajo sometidoEnideGeirLauraREV.pdf: 287985 bytes, checksum: b42325a10a306059a51293a6acc9b31f (MD5) Approved for entry into archive by Diana Silva (dianasilva@ua.pt) on 2019-01-10T17:22:19Z (GMT) No. of bitstreams: 1 Trabajo sometidoEnideGeirLauraREV.pdf: 287985 bytes, checksum: b42325a10a306059a51293a6acc9b31f (MD5) Made available in DSpace on 2019-01-10T17:22:19Z (GMT). No. of bitstreams: 1 Trabajo sometidoEnideGeirLauraREV.pdf: 287985 bytes, checksum: b42325a10a306059a51293a6acc9b31f (MD5) Previous issue date: 2019-04 published

It is known that complete multipartite graphs are determined by their distance spectrum but not by their adjacency spectrum. The Seidel spectrum of a graph $G$ on more than one vertex does not determine the graph, since any graph obtained from $G$ by Seidel switching has the same Seidel spectrum. We consider $G$ to be determined by its Seidel spectrum, up to switching, if any graph with the same spectrum is switching equivalent to a graph isomorphic to $G$. It is shown that any graph which has the same spectrum as a complete $k$-partite graph is switching equivalent to a complete $k$-partite graph, and if the different partition sets sizes are $p_1,\ldots, p_l$, and there are at least three partition sets of each size $p_i$, $i=1,\ldots, l$, then $G$ is determined, up to switching, by its Seidel spectrum. Sufficient conditions for a complete tripartite graph to be determined by its Seidel spectrum are discussed, and a conjecture is made on complete tripartite graphs on more than 18 vertices., 12 page 2 figures

It is proved that for any finite connected graph G, there exists an orientation of G such that the spectral radius of the corresponding Hermitian adjacency matrix is smaller or equal to the spectral radius of the universal cover of G (with equality if and only if G is a tree). This provides a suitable answer to a problem proposed by Mohar. The proof uses the method of interlacing families of polynomials that was developed by Marcus, Spielman, and Srivastava in their seminal work on the existence of infinite families of Ramanujan graphs.

In this paper, we determine the maximum number of nonzero entries in 0-1 matrices of order $n$ with zero trace whose squares are 0-1 matrices when $n\ge 8$. The extremal matrices attaining this maximum number are also characterized., Comment: 20 pages, 11 figures

A partial matrix over a field $\mathbb{F}$ is a matrix whose entries are either an element of $\mathbb{F}$ or an indeterminate and with each indeterminate only appearing once. A completion is an assignment of values in $\mathbb{F}$ to all indeterminates. Given a partial matrix, through elementary row operations and column permutation it can be decomposed into a block matrix of the form $\left[\begin{smallmatrix}{\bf W} & * & * \\ 0 & {\bf S} & * \\ 0 & 0 & {\bf T} \end{smallmatrix}\right]$ where ${\bf W}$ is wide (has more columns than rows), ${\bf S}$ is square, ${\bf T}$ is tall (has more rows than columns), and these three blocks have at least one completion with full rank. And importantly, each one of the blocks ${\bf W}$, ${\bf S}$ and ${\bf T}$ is unique up to elementary row operations and column permutation whenever ${\bf S}$ is required to be as large as possible. When this is the case $\left[\begin{smallmatrix}{\bf W} & * & * \\ 0 & {\bf S} & * \\ 0 & 0 & {\bf T} \end{smallmatrix}\right]$ will be called a WST-decomposition. With this decomposition it is trivial to compute maximum rank of a completion of the original partial matrix: $\#\mbox{rows}({\bf W})+\#\mbox{rows}({\bf S})+\#\mbox{cols}({\bf T})$. In fact we introduce the WST-decomposition for a broader class of matrices: the ACI-matrices.

A finite set of points in $\mathbb R^d$ is called almost-equidistant if among any three distinct points in the set, some two are at unit distance. We prove that an almost-equidistant set in $\mathbb R^d$ has cardinality at most $5d^{13/9}$., Comment: v3: 8 pages, minor corrections. Key words: equilateral sets, almost-equidistant sets, unit distance graph

Finding a diagonal matrix congruent to $A - cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expression is known, then diagonalization can be done in time $O(\text{poly}(k) n)$ where $n$ is the order of $G$., Comment: 25 pages

We study the eigenvalues of the unique connected anti-regular graph $A_n$. Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval $\Omega=[\tfrac{-1-\sqrt{2}}{2}, \tfrac{-1+\sqrt{2}}{2}]$ contains only the trivial eigenvalues $\lambda = -1$ or $\lambda=0$, and any closed interval strictly larger than $\Omega$ will contain eigenvalues of $A_n$ for all $n$ sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as $n$ increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of $A_n$, namely, as $n$ increases the eigenvalues are (approximately) symmetric about the number $-\tfrac{1}{2}$. We also obtain an asymptotic distribution of the eigenvalues as $n\rightarrow\infty$. Finally, the relationship between the eigenvalues of $A_n$ and the eigenvalues of a general threshold graph is discussed., Comment: 20 pages, 6 figures, 1 table

We show that there is no (75,32,10,16) strongly regular graph. The result is obtained by a mix of algebraic and computational approaches. The main idea is to build large enough induced structure and apply the star complement technique. Our result implies that there is no regular two-graph on 76 vertices and no partial geometry with parameters pg(4,7,2). In particular, it implies that there is no (76,35,18,14) strongly-regular graph. In order to solve this classification problem we also develop an efficient algorithm for the problem of finding a maximal clique in a graph., 28 pages

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved.

For a graph G, let λ 2 ( G ) denote its second smallest Laplacian eigenvalue. It was conjectured that λ 2 ( G ) + λ 2 ( G ‾ ) ≥ 1 , where G ‾ is the complement of G. In this paper, it is shown that max ⁡ { λ 2 ( G ) , λ 2 ( G ‾ ) } ≥ 2 5 .

We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The k-token graph Fk(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers h and k such that 1 ≤ h ≤ k ≤ n 2 , the Laplacian spectrum of Fh(G) is contained in the Laplacian spectrum of Fk(G). We also show that the doubled odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph Kn and the star Sn = K1,n−1, respectively. Besides, we obtain a relationship between the spectra of the k-token graph of G and the k-token graph of its complement G. This generalizes to tokens graphs a wellknown property stating that the Laplacian eigenvalues of G are closely related to the Laplacian eigenvalues of G. Finally, the doubled odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph G and its token graph. This research of C. Dalfó and M.A. Fiol has been partially supported by AGAUR from the Catalan Government under project 017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of C. Dalfó has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The research of C. Huemer was supported by MICINN from the Spanish Government under project PID2019-104129GB-I00/AEI/10.13039/501100011033 and AGAUR from the Catalan Government under project 017SGR1336. F.J. Zaragoza Martínez acknowledges the support of the National Council of Science and Technology (Conacyt) and its National System of Researchers (SNI). This research has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 734922

A signed graph Γ is said to be determined by its spectrum if every signed graph with the same spectrum as Γ is switching isomorphic with Γ. Here it is proved that the path P n , interpreted as a signed graph, is determined by its spectrum if and only if n ≡ 0 , 1 , or 2 (mod 4), unless n ∈ { 8 , 13 , 14 , 17 , 29 } , or n = 3 .

We study linear systems of equations with coefficients in a generic partially ordered ring R and a unique solution, and seek conditions for the solution to be nonnegative, that is, every component of the solution is a quotient of two nonnegative elements in R. The requirement of a nonnegative solution arises typically in applications, for example in biology and ecology, where quantities of interest are concentrations and abundances. We provide novel conditions on a labeled multidigraph associated with the linear system that guarantee the solution to be nonnegative. Furthermore, we study a generalization of the first class of linear systems, where the coefficient matrix has a specific block form and provide analogous conditions for nonnegativity of the solution, similarly based on a labeled multidigraph. The latter scenario arises naturally in chemical reaction network theory, when studying full or partial parameterizations of the positive part of the steady state variety of a polynomial dynamical system in the concentrations of the molecular species.

For $r\geq 3$, let $f_r\colon [0,\infty)\to [1,\infty)$ be the unique analytic function such that $f_r({k\choose r})={k-1\choose r-1}$ for any $k\geq r-1$. We prove that the spectral radius of an $r$-uniform hypergraph $H$ with $e$ edges is at most $f_r(e)$. The equality holds if and only if $e={k\choose r}$ for some positive integer $k$ and $H$ is the union of a complete $r$-uniform hypergraph $K_k^r$ and some possible isolated vertices. This result generalizes the classical Stanley's theorem on graphs., 16 pages

In this paper we compute the critical group of the Kneser graph $KG(n,2)$. This is equivalent to computing the Smith normal form of a Laplacian matrix of this graph., The statement of Lemma 2.2, part (4) was missing a case. This has been corrected, and it has no effect on the rest of the paper

We show that the tensor rank of tensor product of two three-qubit W states is not less than eight. Combining this result with the recent result of M. Christandl, A. K. Jensen, and J. Zuiddam that the tensor rank of tensor product of two three-qubit W states is at most eight, we deduce that the tensor rank of tensor product of two three-qubit W states is eight. We also construct the upper bound of the tensor rank of tensor product of many three-qubit W states., Comment: 10 pages, accepted by Linear Algebra and Applications

Arithmetical structures on a graph were introduced by Lorenzini as some intersection matrices that arise in the study of degenerating curves in algebraic geometry. In this article we study these arithmetical structures, in particular we are interested in the arithmetical structures on complete graphs, paths, and cycles. We begin by looking at the arithmetical structures on a multidigraph from the general perspective of $M$-matrices. As an application, we recover the result of Lorenzini about the finiteness of the number of arithmetical structures on a graph. We give a description on the arithmetical structures on the graph obtained by merging and splitting a vertex of a graph in terms of its arithmetical structures. On the other hand, we give a description of the arithmetical structures on the clique--star transform of a graph, which generalizes the subdivision of a graph. As an application of this result we obtain an explicit description of all the arithmetical structures on the paths and cycles and we show that the number of the arithmetical structures on a path is a Catalan number., 23 pages, 5 Figures, Minor changes

We study generalized eigenvalue problems for meet and join matrices with respect to incidence functions on semilattices. We provide new bounds for generalized eigenvalues of meet matrices with respect to join matrices under very general assumptions. The applied methodology is flexible, and it is shown in the case of GCD and LCM matrices that even sharper bounds can be obtained by applying the known properties of the divisor lattice. These results can also be easily modified for the dual problem of eigenvalues of join matrices with respect to meet matrices, which we briefly consider as well. We investigate the effectiveness of the obtained bounds for select examples involving number-theoretical lattices., 18 pages, 2 figures

A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Lui and Huang [F.J. Liu and Q.X. Huang, Laplacian spectral characterization of 3-rose graphs, Linear Algebra Appl. 439 (2013), 2914--2920]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927-2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.

The distance matrix of a connected graph is the symmetric matrix with columns and rows indexed by the vertices and entries that are the pairwise distances between the corresponding vertices. We give a construction for graphs which differ in their edge counts yet are cospectral with respect to the distance matrix. Further, we identify a subgraph switching behavior which constructs additional distance cospectral graphs. The proofs for both constructions rely on a perturbation of (most of) the distance eigenvectors of one graph to yield the distance eigenvectors of the other., Comment: 17 pages, 4 figures

The notions of weakly bipartitive and bipartitive families were introduced by Montgolfier (2003) as a general tool for studying some decomposition of graphs and other combinatorial structures. In this paper, we give a matrix description of these notions., 10 pages, 2 figures

We extend the theory of equitable decompositions introduced in [2] , where it was shown that if a graph has a particular type of symmetry, i.e. a uniform or basic automorphism ϕ, it is possible to use ϕ to decompose a matrix M appropriately associated with the graph. The result is a number of strictly smaller matrices whose collective eigenvalues are the same as the eigenvalues of the original matrix M. We show here that a large class of automorphisms, which we refer to as separable, can be realized as a sequence of basic automorphisms, allowing us to equitably decompose M over any such automorphism. We also show that not only can a matrix M be decomposed but that the eigenvectors of M can also be equitably decomposed. Additionally, we prove under mild conditions that if a matrix M is equitably decomposed the resulting divisor matrix, which is the divisor matrix of the associated equitable partition, will have the same spectral radius as the original matrix M. Last, we describe how an equitable decomposition effects the Gershgorin region Γ ( M ) of a matrix M, which can be used to localize the eigenvalues of M. We show that the Gershgorin region of an equitable decomposition of M is contained in the Gershgorin region Γ ( M ) of the original matrix. We demonstrate on a real-world network that by a sequence of equitable decompositions it is possible to significantly reduce the size of a matrix Gershgorin region.

We define the Grassmannians of an infinite-dimensional vector space $V$ as the orbits of the action of the general linear group ${\rm GL}(V)$ on the set of all subspaces. Let ${\mathcal G}$ be one of these Grassmannians. An apartment in ${\mathcal G}$ is the set of all elements of ${\mathcal G}$ spanned by subsets of a certain basis of $V$. We show that every bijective transformation $f$ of ${\mathcal G}$ such that $f$ and $f^{-1}$ send apartments to apartments is induced by a semilinear automorphism of $V$. In the case when ${\mathcal G}$ consists of subspaces whose dimension and codimension both are infinite, a such kind result will be proved also for the connected components of the associated Grassmann graph.

The spectral $p$-norm of $r$-matrices generalizes the spectral $2$-norm of $2$-matrices. In 1911 Schur gave an upper bound on the spectral $2$-norm of $2$-matrices, which was extended in 1934 by Hardy, Littlewood, and Polya to $r$-matrices. Recently, Kolotilina, and independently the author, strengthened Schur's bound for $2$-matrices. The main result of this paper extends the latter result to $r$-matrices, thereby improving the result of Hardy, Littlewood, and Polya. The proof is based on combinatorial concepts like $r$-partite $r$-matrix and symmetrant of a matrix, which appear to be instrumental in the study of the spectral $p$-norm in general. Thus, another application shows that the spectral $p$-norm and the $p$-spectral radius of a symmetric nonnegative $r$-matrix are equal whenever $p\geq r$. This result contributes to a classical area of analysis, initiated by Mazur and Orlicz around 1930. Additionally, a number of bounds are given on the $p$-spectral radius and the spectral $p$-norm of $r$-matrices and $r$-graphs., Comment: 29 pages. Credit has been given to Ragnarsson and Van Loan for the symmetrant of a matrix