Search

We investigate questions related to the set $\mathcal{SEP}_d$ consisting of the linear maps $\rho$ acting on $\mathbb{C}^d\otimes \mathbb{C}^d$ that can be written as a convex combination of rank one matrices of the form $xx^*\otimes yy^*$. Such maps are known in quantum information theory as the separable bipartite states, while nonseparable states are called entangled. In particular we introduce bounds for the separable rank $\mathrm{rank_{sep}}(\rho)$, defined as the smallest number of rank one states $xx^*\otimes yy^*$ entering the decomposition of a separable state $\rho$. Our approach relies on the moment method and yields a hierarchy of semidefinite-based lower bounds, that converges to a parameter $\tau_{\mathrm{sep}}(\rho)$, a natural convexification of the combinatorial parameter $\mathrm{rank_{sep}}(\rho)$. A distinguishing feature is exploiting the positivity constraint $\rho-xx^*\otimes yy^* \succeq 0$ to impose positivity of a polynomial matrix localizing map, the dual notion of the notion of sum-of-squares polynomial matrices. Our approach extends naturally to the multipartite setting and to the real separable rank, and it permits strengthening some known bounds for the completely positive rank. In addition, we indicate how the moment approach also applies to define hierarchies of semidefinite relaxations for the set $\mathcal{SEP}_d$ and permits to give new proofs, using only tools from moment theory, for convergence results on the DPS hierarchy from (A.C. Doherty, P.A. Parrilo and F.M. Spedalieri. Distinguishing separable and entangled states. Phys. Rev. Lett. 88(18):187904, 2002).

We give lower bounds on the size and total size of clique partitions of a graph in terms of its spectral radius and minimum degree, and derive a spectral upper bound for the maximum number of edge-disjoint t-cliques. The extremal graphs attaining the bounds are exactly the block graphs of Steiner 2-designs and the regular graphs with K t -decompositions, respectively.

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.

A real symmetric matrix $M$ is completely positive semidefinite if it admits a Gram representation by (Hermitian) positive semidefinite matrices of any size $d$. The smallest such $d$ is called the (complex) completely positive semidefinite rank of $M$, and it is an open question whether there exists an upper bound on this number as a function of the matrix size. We construct completely positive semidefinite matrices of size $4k^2+2k+2$ with complex completely positive semidefinite rank $2^k$ for any positive integer $k$. This shows that if such an upper bound exists, it has to be at least exponential in the matrix size. For this we exploit connections to quantum information theory and we construct extremal bipartite correlation matrices of large rank. We also exhibit a class of completely positive matrices with quadratic (in terms of the matrix size) completely positive rank, but with linear completely positive semidefinite rank, and we make a connection to the existence of Hadamard matrices., 21 pages

This paper addresses the following three topics: positive semidefinite (psd) matrix completions, universal rigidity of frameworks, and the Strong Arnold Property (SAP). We show some strong connections among these topics, using semidefinite programming as unifying theme. Our main contribution is a sufficient condition for constructing partial psd matrices which admit a unique completion to a full psd matrix. Such partial matrices are an essential tool in the study of the Gram dimension $\gd(G)$ of a graph $G$, a recently studied graph parameter related to the low psd matrix completion problem. Additionally, we derive an elementary proof of Connelly's sufficient condition for universal rigidity of tensegrity frameworks and we investigate the links between these two sufficient conditions. We also give a geometric characterization of psd matrices satisfying the Strong Arnold Property in terms of nondegeneracy of an associated semidefinite program, which we use to establish some links between the Gram dimension $\gd(\cdot)$ and the Colin de Verdi\`ere type graph parameter $\nu^=(\cdot)$., Comment: 28 pages, 3 figures

We apply interlacing techniques for obtaining lower and upper bounds for the sums of Laplacian eigenvalues of graphs. Mainly, we generalize two theorems of Grone and Grone & Merris, providing tight bounds and studying the cases of equality. As a consequence, some results on well-known parameters of a graph, such as the maximum and minimum cuts, the edge-connectivity, the (almost) dominating number, and the edge isoperimetric number, are derived.

In this paper we show that certain almost distance-regular graphs, the so-called $h$-punctually walk-regular graphs, can be characterized through the cospectrality of their perturbed graphs. A graph $G$ with diameter $D$ is called $h$-punctually walk-regular, for a given $h\le D$, if the number of paths of length $\ell$ between a pair of vertices $u,v$ at distance $h$ depends only on $\ell$. The graph perturbations considered here are deleting a vertex, adding a loop, adding a pendant edge, adding/removing an edge, amalgamating vertices, and adding a bridging vertex. We show that for walk-regular graphs some of these operations are equivalent, in the sense that one perturbation produces cospectral graphs if and only if the others do. Our study is based on the theory of graph perturbations developed by Cvetkovi\'c, Godsil, McKay, Rowlinson, Schwenk, and others. As a consequence, some new characterizations of distance-regular graphs are obtained.

The lollipop graph, denoted by H n , p , is obtained by appending a cycle C p to a pendant vertex of a path P n - p . We will show that no two non-isomorphic lollipop graphs are cospectral with respect to the adjacency matrix. It is proved that for p odd the lollipop graphs H n , p and some related graphs H n , p ′ are determined by the adjacency spectrum, and that all lollipop graphs are determined by its Laplacian spectrum.

We show that if µj is the jth largest Laplacian eigenvalue, and dj is the jth largest degree (1 = j = n) of a connected graph G on n vertices, then µj = dj - j + 2 (1 = j = n - 1). This settles a conjecture due to Guo. © 2008 Elsevier Inc. All rights reserved.

Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value y ˆ of y. We call such graphs y ˆ -cospectral. It follows that y ˆ is a rational number, and we prove existence of a pair of y ˆ -cospectral graphs for every rational y ˆ . In addition, we generate by computer all y ˆ -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of y ˆ -cospectral graphs for all rational y ˆ ∈ ( 0 , 1 ) , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of y ˆ , and by computer we find all such pairs of y ˆ -cospectral graphs on at most eleven vertices.

We give sufficient conditions for existence of a perfect matching in a graph in terms of the eigenvalues of the Laplacian matrix. We also show that a distance-regular graph of degree k is k-edge-connected.

This paper analyses the effects of inaccurate linear solvers on the behaviour of inverse iteration and Rayleigh quotient iteration. We derive an expression for the worst-case perturbation of the convergence factor of the exact iteration, due to the inexact solution. A necessary and sufficient condition on the approximate eigenvector for the improvement of the next iterate follows from that formula. Preceding this, several new inequalities describe the relation between the errors in the approximate eigenvector, the approximate eigenvalue and the corresponding residual.