查看更多>>摘要：We investigate questions related to the set SEPd consisting of the linear maps rho acting on Cd circle times Cd that can be written as a convex combination of rank one matrices of the form xx*circle times 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 ranksep(rho), defined as the smallest number of rank one states xx* circle times 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 sep(rho), a natural convexification of the combinatorial parameter ranksep(rho). A distinguishing feature is exploiting the positivity constraint rho - xx* circle times yy* 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 SEPd and permits to give new proofs,
Vill, JulianMichalek, MateuszBlomenhofer, Alexander Taveira
14页
查看更多>>摘要：The variety Sing(n,m) consists of all tuples X=(X-1,..., X-m) of n x n matrices such that every linear combination of X-1,..., X-m is singular. Equivalently, X is an element of Sing(n,m) if and only if det(lambda X-1(1)+...+lambda X-m(m)) = 0 for all lambda(1),...,lambda(m) is an element of Q. Makam and Wigderson [12] asked whether the ideal generated by these equations is always radical, that is, if any polynomial identity that is valid on Sing(n,m) lies in the ideal generated by the polynomials det(lambda X-1(1)+...+lambda X-m(m)). We answer this question in the negative by determining the vanishing ideal of Sing(2,m) for all m is an element of N. Our results exhibit that there are additional equations arising from the tensor structure of X. More generally, for any nand m >= n(2) - n + 1, we prove there are equations vanishing on Sing(n,m) that are not in the ideal generated by polynomials of type det(lambda X-1(1)+...+lambda X-m(m)). Our methods are based on classical results about Fano schemes, representation theory and Grobner bases. (C) 2022 Elsevier Inc. All rights reserved.
Fallat, Shaun M.Hall, H. TracyLin, Jephian C. -H.Shader, Bryan L....
18页
查看更多>>摘要：The inverse eigenvalue problem of a graph studies the real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of the graph. The strong spectral property (SSP) is an important tool for this problem. This note establishes the bifurcation lemma, which states that if a spectrum can be realized by a matrix with the SSP for some graph, then all the nearby spectra can also be realized by matrices with the SSP for the same graph. The idea of the bifurcation lemma also works for other strong properties and for not necessarily symmetric matrices. This is used to develop new techniques for verifying a spectrally arbitrary pattern or inertially arbitrary pattern. The bifurcation lemma provides a unified theoretical foundation for several known results, such as the stable northeast lemma and the nilpotent-centralizer method.(c) 2022 Elsevier Inc. All rights reserved.
查看更多>>摘要：We consider a discrete-time quantum walk, called the Grover walk, on a distance regular graph X. Given that X has diameter d and invertible adjacency matrix, we show that the square of the transition matrix of the Grover walk on X is a product of at most d commuting transition matrices of continuous-time quantum walks, each on some distance digraph of the line digraph of X. We also obtain a similar factorization for any graph X in a Bose Mesner algebra. (c) 2022 Elsevier Inc. All rights reserved.
Barrett, WayneEvans, EmilyHall, H. TracyKempton, Mark...
29页
查看更多>>摘要：We conjecture a new lower bound on the algebraic connectivity of a graph that involves the number of vertices of high eccentricity in a graph. We prove that this lower bound implies a strengthening of the Laplacian Spread Conjecture. We discuss further conjectures, also strengthening the Laplacian Spread Conjecture, that include a conjecture for simple graphs and a conjecture for weighted graphs. (c) 2022 Elsevier Inc. All rights reserved.
查看更多>>摘要：In this paper, we consider the non-symmetric positive semidefinite Procrustes (NSPSDP) problem: Given two matrices X, B is an element of R-n,R-m , find the matrix A is an element of R-n,R-n that minimizes the Frobenius norm of AX - B and which is such that A + A(T) is positive semidefinite. We generalize the semi-analytical approach for the symmetric positive semidefinite Procrustes problem, where A is required to be positive semidefinite, that was proposed by Gillis and Sharma (A semi-analytical approach for the positive semidefinite Procrustes problem, Linear Algebra Appl. 540, 112-137, 2018). As for the symmetric case, we first show that the NSPSDP problem can be reduced to a smaller NSPSDP problem that always has a unique solution and where the matrix X is diagonal and has full rank. Then, an efficient semi-analytical algorithm to solve the NSPSDP problem is proposed, solving the smaller and well-posed problem with a fast gradient method which guarantees a linear rate of convergence. This algorithm is also applicable to solve the complex NSPSDP problem, where & nbsp;& nbsp;X,B is an element of C-n,C-m, as we show that the complex NSPSDP problem can be written as an overparametrized real NSPSDP problem. The efficiency of the proposed algorithm is illustrated on several numerical examples. (C) 2022 Elsevier Inc. All rights reserved.
Cardoso, Domingos M.Gomes, HelenaPinheiro, Sofia J.
21页
查看更多>>摘要：The H-join of a family of graphs g = 1G1, .. . , Gp}, also called generalized composition, H[G1, . . . , Gp], where all graphs are undirected, simple and finite, is the graph obtained by replacing each vertex i of H by Gi and adding to the edges of all graphs in g the edges of the join Gi V Gj, for every edge ij of H. Some well known graph operations are particular cases of the H-join of a family of graphs g as it is the case of the lexicographic product (also called composition) of two graphs H and G, H[G]. During long time the known expressions for the determination of the entire spectrum of the H-join in terms of the spectra of its components (that is, graphs in g) and an associated matrix, related with the main eigenvalues of the components and the graph H, were limited to families g of regular graphs. In this work, with an approach based on the walk-matrix, we extend such a determination, as well as the determination of the characteristic polynomial, to the universal adjacency matrix of the H-join of families of arbitrary graphs. From the obtained results, the eigenvectors of the universal adjacency matrix of the H-join can also be determined in terms of the eigenvectors of the universal adjacency matrices of the components and an associated matrix. (c) 2022 Elsevier Inc. All rights reserved.
查看更多>>摘要：In this paper, we define and obtain several properties of the (adjacency) energy of a hypergraph. In particular, bounds for this energy are obtained as functions of structural and spectral parameters, such as Zagreb index and spectral radius. We also study how the energy of a hypergraph varies when a vertex/edge is removed or when an edge is divided. In addition, we solve the extremal problem energy for the class of hyperstars, and show that the energy of a hypergraph is never an odd number.(c) 2022 Elsevier Inc. All rights reserved.
Chalkis, ApostolosEmiris, Ioannis Z.Fisikopoulos, VissarionRepouskos, Panagiotis...
28页
查看更多>>摘要：We present algorithmic, complexity, and implementation re-sults on the problem of sampling points from a spectrahedron, that is, the feasible region of a semidefinite program. Our main tool is geometric random walks. We analyze the arithmetic and bit complexity of certain primitive geometric operations that are based on the algebraic properties of spec-trahedra and the polynomial eigenvalue problem. This study leads to the implementation of a broad collection of random walks for sampling from spectrahedra that experimentally show faster mixing times than methods currently employed either in theoretical studies or in applications, including the popular family of Hit-and-Run walks. The different random walks offer a variety of advantages, thus allowing us to ef-ficiently sample from general probability distributions, for example the family of log-concave distributions which arise in numerous applications. We focus on two major applica-tions of independent interest: (i) approximate the volume of a spectrahedron, and (ii) compute the expectation of functions coming from robust optimal control.We exploit efficient linear algebra algorithms and implemen-tations to address the aforementioned computations in very high dimension. In particular, we provide a C++ open source implementation of our methods that scales efficiently, for the first time, up to dimension 200. We illustrate its efficiency on various data sets.(c) 2022 Elsevier Inc. All rights reserved.
查看更多>>摘要：We consider pairs of operators A, B is an element of B(H), where H & nbsp; is a Hilbert space, such that there exist a linear isometry f from the span of {A, B} into C-2 mapping A, B into orthonormal vectors. We prove some necessary conditions for the existence of such an f and determine all such pairs among commuting normal operators. Then we characterize all such pairs A, B (in fact, we consider general sets instead of just pairs) under the additional requirement that f is a complete isometry, when H carries the column (or row) operator space structure. We also metrically characterize elements in a C & lowast;-algebra with orthogonal ranges. (C) 2022 Elsevier Inc. All rights reserved.
NSTL
Elsevier