Copositivity Detection of Tensors: Theory and Algorithm

A symmetric tensor is called copositive if it generates a multivariate form taking nonnegative values over the nonnegative orthant. Copositive tensors have found important applications in polynomial optimization, tensor complementarity problems and vacuum stability of a general scalar potential. In this paper, we consider copositivity detection of tensors from both theoretical and computational points of view. After giving several necessary conditions for copositive tensors, we propose several new criteria for copositive tensors based on the representation of the multivariate form in barycentric coordinates with respect to the standard simplex and simplicial partitions. It is verified that, as the partition gets finer and finer, the concerned conditions eventually capture all strictly copositive tensors. Based on the obtained theoretical results with the help of simplicial partitions, we propose a numerical method to judge whether a tensor is copositive or not. The preliminary numerical results confirm our theoretical findings.     

Nonnegative matrices with prescribed spectrum and elementary divisors

In this paper we give new sufficient conditions for the existence and construction of nonnegative matrices with prescribed elementary divisors, which drastically improve and contain some of the previous known conditions. We also show how to perturb complex eigenvalues of a nonnegative matrix while keeping its nonnegativity. These results allow us, under certain conditions, to easily decide if a given list is realizable with prescribed elementary divisors.     

Intervals of totally nonnegative matrices

Totally nonnegative matrices, i.e., matrices having all their minors nonnegative, and matrix intervals with respect to the checkerboard ordering are considered. It is proven that if the two bound matrices of such a matrix interval are nonsingular and totally nonnegative (and in addition all their zero minors are identical) then all matrices from this interval are also nonsingular and totally nonnegative (with identical zero minors).     

Equivalent conditions for noncentral generalized Laplacianness and independence of matrix quadratic forms

Let Y be an n×p multivariate normal random matrix with general covariance Σ_Y and W be a symmetric matrix. In the present article, the property that a matrix quadratic form Y^′WY is distributed as a difference of two independent (noncentral) Wishart random matrices is called the (noncentral) generalized Laplacianness (GL). Then a set of algebraic results are obtained which will give the necessary and sufficient conditions for the (noncentral) GL of a matrix quadratic form. Further, two extensions of Cochran’s theorem concerning the (noncentral) GL and independence of a family of matrix quadratic forms are developed.     

Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme

It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix.     

A GENERALIZATION OF FINSLER'S THEOREM FOR QUADRATIC INEQUALITIES AND EQUALITIES

ABSTRACT

A generalization is given of Finsler's theorem on the positivity of a quadratic form subject to a quadratic equality. The generalized result is, under a certain assumption, a set of necessary and sufficient conditions for non-negativity of a quadratic form subject to an arbitrary number of quadratic inequality and equality constraints. Certain properties of matrix inverses are deduced using the conditions.     

Nonnegative quadratic estimation and quadratic sufficiency in general linear models

Notions of linear sufficiency and quadratic sufficiency are of interest to some authors. In this paper, the problem of nonnegative quadratic estimation for β^′Hβ+hσ² is discussed in a general linear model and its transformed model. The notion of quadratic sufficiency is considered in the sense of generality, and the corresponding necessary and sufficient conditions for the transformation to be quadratically sufficient are investigated. As a direct consequence, the result on (ordinary) quadratic sufficiency is obtained. In addition, we pose a practical problem and extend a special situation to the multivariate case. Moreover, a simulated example is conducted, and applications to a model with compound symmetric covariance matrix are given. Finally, we derive a remark which indicates that our main results could be extended further to the quasi-normal case.     

Definitizable hermitian matrix pencils

Summary An hermitian matrix pencilA – B withA nonsingular is called strongly definitizable ifAp(A ^–1 B) is positive definite for some polynomialp. We present three characterizations of strongly definitizable pencils, which generalize the classical results for definite pencils. They are, in particular, stably simultaneously diagonable. We also discuss this form of stability with respect to an open subset of the real line. Implications for some quadratic eigenvalue problems are included.Research supported in part by the National Sciences and Engineering Research Council of Canada.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

An algorithm for determining copositive matrices

In this paper, we present an algorithm of simple exponential growth called COPOMATRIX for determining the copositivity of a real symmetric matrix. The core of this algorithm is a decomposition theorem, which is used to deal with simplicial subdivision of on the standard simplex Δ_m, where each component of the vector β is −1, 0 or 1.     

Extremal numbers of positive entries of imprimitive nonnegative matrices

We determine the maximum and minimum numbers of positive entries of imprimitive nonnegative matrices with a given imprimitivity index. One application of the results is to estimate the imprimitivity index by the number of positive entries. The proofs involve the study of a cyclic quadratic form. This completes a research initiated by Lewin in 1990.     

On the quadratic two-parameter eigenvalue problem and its linearization

We introduce the quadratic two-parameter eigenvalue problem and linearize it as a singular two-parameter eigenvalue problem. This, together with an example from model updating, shows the need for numerical methods for singular two-parameter eigenvalue problems and for a better understanding of such problems.There are various numerical methods for two-parameter eigenvalue problems, but only few for nonsingular ones. We present a method that can be applied to singular two-parameter eigenvalue problems including the linearization of the quadratic two-parameter eigenvalue problem. It is based on the staircase algorithm for the extraction of the common regular part of two singular matrix pencils.     

An improved algorithm to test copositivity

Copositivity plays a role in combinatorial and nonconvex quadratic optimization. However, testing copositivity of a given matrix is a co-NP-complete problem. We improve a previously given branch-and-bound type algorithm for testing copositivity and discuss its behavior in particular for the maximum clique problem. Numerical experiments indicate that the speedup is considerable.     

Temperley-Lieb Immanants

We use the Temperley-Lieb algebra to define a family of totally nonnegative polynomials of the form . The cone generated by these polynomials contains all totally nonnegative polynomials of the form , where, are matrix minors. We also give new conditions on the sets I,...,K′ which characterize differences of products of minors which are totally nonnegative. Received September 30, 2004     

Bidiagonalization of oscillatory matrices

We prove that an oscillatory matrix is similar to a bidiagonal nonnegative matrix by means of a totally positive matrix of change of basis. New characterizations of oscillatory and nonsingular totally positive matrices in terms of similarity are provided.     

On visualization scaling, subeigenvectors and Kleene stars in max algebra

The purpose of this paper is to investigate the interplay arising between max algebra, convexity and scaling problems. The latter, which have been studied in nonnegative matrix theory, are strongly related to max algebra. One problem is that of strict visualization scaling, defined as, for a given nonnegative matrix A, a diagonal matrix X such that all elements of X^-1AX are less than or equal to the maximum cycle geometric mean of A, with strict inequality for the entries which do not lie on critical cycles. In this paper such scalings are described by means of the max algebraic subeigenvectors and Kleene stars of nonnegative matrices as well as by some concepts of convex geometry.     

Construction and nonnegativity of sign idempotent sign pattern matrices

In this paper, we modify Eschenbach’s algorithm for constructing sign idempotent sign pattern matrices so that it correctly constructs all of them. We find distinct classes of sign idempotent sign pattern matrices that are signature similar to an entrywise nonnegative sign pattern matrix. Additionally, if for a sign idempotent sign pattern matrix A there exists a signature matrix S such that SAS is nonnegative, we prove such S is unique up to multiplication by -1 if the signed digraph D(A) is not disconnected.     

Jordan structures of alternating matrix polynomials

Alternating matrix polynomials, that is, polynomials whose coefficients alternate between symmetric and skew-symmetric matrices, generalize the notions of even and odd scalar polynomials. We investigate the Smith forms of alternating matrix polynomials, showing that each invariant factor is an even or odd scalar polynomial. Necessary and sufficient conditions are derived for a given Smith form to be that of an alternating matrix polynomial. These conditions allow a characterization of the possible Jordan structures of alternating matrix polynomials, and also lead to necessary and sufficient conditions for the existence of structure-preserving strong linearizations. Most of the results are applicable to singular as well as regular matrix polynomials.     

Convexity of the inverse and Moore-Penrose inverse

Convexity properties of the inverse of positive definite matrices and the Moore-Penrose inverse of nonnegative definite matrices with respect to the partial ordering induced by nonnegative definiteness are studied. For the positive definite case null-space characterizations are derived, and lead naturally to a concept of strong convexity of a matrix function, extending the conventional concept of strict convexity. The positive definite results are shown to allow for a unified analysis of problems in reproducing kernel Hilbert space theory and inequalities involving matrix means. The main results comprise a detailed study of the convexity properties of the Moore-Penrose inverse, providing extensions and generalizations of all the earlier work in this area.     

New permanental bounds for Ferrers matrices

We survey the most recent results on permanental bounds of a nonnegative matrix. Some older bounds are revisited as well. Applying refinements of the arithmetic mean-geometric mean inequality leads to sharp bounds for the permanent of a fully indecomposable Ferrers matrix. In the end, several relevant examples comparing the bounds are discussed.