Eigenvalues and invariants of tensors

A tensor is represented by a supermatrix under a co-ordinate system. In this paper, we define E-eigenvalues and E-eigenvectors for tensors and supermatrices. By the resultant theory, we define the E-characteristic polynomial of a tensor. An E-eigenvalue of a tensor is a root of the E-characteristic polynomial. In the regular case, a complex number is an E-eigenvalue if and only if it is a root of the E-characteristic polynomial. We convert the E-characteristic polynomial of a tensor to a monic polynomial and show that the coefficients of that monic polynomial are invariants of that tensor, i.e., they are invariant under co-ordinate system changes. We call them principal invariants of that tensor. The maximum number of principal invariants of mth order n-dimensional tensors is a function of m and n. We denote it by d(m,n) and show that d(1,n)=1, d(2,n)=n, d(m,2)=m for m?3 and d(m,n)?mn−1+?+m for m,n?3. We also define the rank of a tensor. All real eigenvectors associated with nonzero E-eigenvalues are in a subspace with dimension equal to its rank.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

High-order sum-of-squares structured tensors:theory and applications

Tensor decomposition is an important research area with numerous applications in data mining and computational neuroscience.An important class of tensor decomposition is sum-of-squares(SOS)tensor decomposition.SOS tensor decomposition has a close connection with SOS polynomials,and SOS polynomials are very important in polynomial theory and polynomial optimization.In this paper,we give a detailed survey on recent advances of high-order SOS tensors and their applications.It first shows that several classes of symmetric structured tensors available in the literature have SOS decomposition in the even order symmetric case.Then,the SOS-rank for tensors with SOS decomposition and the SOS-width for SOS tensor cones are established.Further,a sharper explicit upper bound of the SOS-rank for tensors with bounded exponent is provided,and the exact SOS-width for the cone consists of all such tensors with SOS decomposition is identified.Some potential research directions in the future are also listed in this paper.     

A sharp bound for the degree of proper monomial mappings between balls

The authors prove that a proper monomial holomorphic mapping from the two-ball to the N-ball has degree at most 2N-3, and that this result is sharp. The authors first show that certain group-invariant polynomials (related to Lucas polynomials) achieve the bound. To establish the bound the authors introduce a graph-theoretic approach that requires determining the number of sinks in a directed graph associated with the quotient polynomial. The proof also relies on a result of the first author that expresses all proper polynomial holomorphic mappings between balls in terms of tensor products.     

Characteristic polynomial and higher order traces of third order three dimensional tensors

Eigenvalues of tensors play an increasingly important role in many aspects of applied mathematics. The characteristic polynomial provides one of a very few ways that shed lights on intrinsic understanding of the eigenvalues. It is known that the characteristic polynomial of a third order three dimensional tensor has a stunning expression with more than 20000 terms, thus prohibits an effective analysis. In this article, we are trying to make a concise representation of this characteristic polynomial in terms of certain basic determinants. With this, we can successfully write out explicitly the characteristic polynomial of a third order three dimensional tensor in a reasonable length. An immediate benefit is that we can compute out the third and fourth order traces of a third order three dimensional tensor symbolically, which is impossible in the literature.     

Average case tractability of non-homogeneous tensor product problems with the absolute error criterion

We study average case tractability of non-homogeneous tensor product problems with the absolute error criterion. We consider algorithms that use finitely many evaluations of arbitrary linear functionals. For general non-homogeneous tensor product problems, we obtain the matching necessary and sufficient conditions for strong polynomial tractability in terms of the one-dimensional eigenvalues. We give some examples to show that strong polynomial tractability is not equivalent to polynomial tractability, and polynomial tractability is not equivalent to quasi-polynomial tractability. But for non-homogeneous tensor product problems with decreasing eigenvalues, we prove that strong polynomial tractability is always equivalent to polynomial tractability, and strong polynomial tractability is even equivalent to quasi-polynomial tractability when the one-dimensional largest eigenvalues are less than one. In particular, we find an example that quasi-polynomial tractability with the absolute error criterion is not equivalent to that with the normalized error criterion even if all the one-dimensional largest eigenvalues are one. Finally we consider a special class of non-homogeneous tensor product problems with improved monotonicity condition of the eigenvalues.     

Polynomial Reproduction in Subdivision

We study conditions on the matrix mask of a vector subdivision scheme ensuring that certain polynomial input vectors yield polynomial output again. The conditions are in terms of a recurrence formula for the vectors which determine the structure of polynomial input with this property. From this recurrence, we obtain an algorithm to determine polynomial input of maximal degree. The algorithm can be used in the design of masks to achieve a high order of polynomial reproduction.     

Extrema of a Real Polynomial

In this paper, we investigate critical point and extrema structure of a multivariate real polynomial. We classify critical surfaces of a real polynomial f into three classes: repeated, intersected and primal critical surfaces. These different critical surfaces are defined by some essential factors of f, where an essential factor of f means a polynomial factor of f–c ₀, for some constant c ₀. We show that the degree sum of repeated critical surfaces is at most d–1, where d is the degree of f. When a real polynomial f has only two variables, we give the minimum upper bound for the number of other isolated critical points even when there are nondegenerate critical curves, and the minimum upper bound of isolated local extrema even when there are saddle curves. We show that a normal polynomial has no odd degree essential factors, and all of its even degree essential factors are normal polynomials, up to a sign change. We show that if a normal quartic polynomial f has a normal quadratic essential factor, a global minimum of f can be either easily found, or located within the interior(s) of one or two ellipsoids. We also show that a normal quartic polynomial can have at most one local maximum.     

On the Euler characteristic of Kronecker moduli spaces

Combining the MPS degeneration formula for the Poincaré polynomial of moduli spaces of stable quiver representations and localization theory, it turns that the determination of the Euler characteristic of these moduli spaces reduces to a combinatorial problem of counting certain trees. We use this fact in order to obtain an upper bound for the Euler characteristic in the case of the Kronecker quiver. We also derive a formula for the Euler characteristic of some of the moduli spaces appearing in the MPS degeneration formula.     

A refinement of multivariate value set bounds

Over finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials.In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides improvement of a degree matrix-based result given by Zan and Cao, making our new bound the strongest upper bound thus far.     

The group and the minimal polynomial of a graph

This paper presents some results linking the minimal polynomial of the adjacency matrix of a graph with its group structure. An upper bound on the order of the group is derived for graphs whose minimal and characteristic polynomials are identical. It is also shown that for a graph with transitive group, the degree of the minimal polynomial is bounded above by the number of orbits of the stabilizer of any given element. Finally, the order of the group of a point-symmetric graph with a prime number of points is shown to depend on the degree of the minimal polynomial, and an algorithm for constructing such a group is given.     

A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W‐tensors, which not only extends the well‐studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H‐eigenvalue of an even‐order symmetric W‐tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H‐eigenvalue of W‐tensors and is based on a new structured sums‐of‐squares decomposition result for a nonnegative polynomial induced by W‐tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H‐eigenvalue of W‐tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H‐eigenvalues of large‐size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state‐of‐the‐art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z‐tensors, whose order may be even or odd.     

The degree of convergence of entire functions and generalized type

Summary The generalized order and generalized type of an entire function have been considered in this paper, using arbitrary growth functions. In place of the usual Taylor series expansion, polynomial series expansion having polynomial coefficients of an entire function have been considered and formula for generalized type obtained in terms of the polynomial coefficients. In the end, a result characterizing the set of entire functions of positive generalized order and finite type in terms of their degree of convergence on general sets has been obtained.     

A remark on polynomial function over finite commutative rings with identity

In the present paper, the degree of polynomial functions on a finite commutative ringR with identity is investigated. An upper bound for the degree is given (Theorem 3) with the help of a reduction formula for powers (Theorem 1).     

Estimates of the norm of a function orthogonal to the piecewise-constant functions in terms of higher-order moduli of continuity

The uniform norm of a function that is defined on the real line and has zero integrals between integer points is estimated in terms of its modulus of continuity of arbitrary even order. Sharp bounds of this kind are known for periodic functions. The passage to nonperiodic functions significantly complicates the problem. In general, the constant for nonperiodic functions is greater than that for periodic functions. The constants in the bound are improved compared with those known earlier. The proof is based on a representation of the error of the polynomial interpolation as the product of the influence polynomial and an integrated difference of higher order.     

Expansions for the Bollob��s-Riordan Polynomial of Separable Ribbon Graphs

We define 2-decompositions of ribbon graphs, which generalize 2-sums and tensor products of graphs. We give formulae for the Bollobás-Riordan polynomial of such a 2-decomposition, and derive the classical Brylawski formula for the Tutte polynomial of a tensor product as a (very) special case. This study was initially motivated from knot theory, and we include an application of our formulae to mutation in knot diagrams.     

Error Bounds for the Solution Sets of Quadratic Complementarity Problems

In this article, two types of fractional local error bounds for quadratic complementarity problems are established, one is based on the natural residual function and the other on the standard violation measure of the polynomial equalities and inequalities. These fractional local error bounds are given with explicit exponents. A fractional local error bound with an explicit exponent via the natural residual function is new in the tensor/polynomial complementarity problems literature. The other fractional local error bounds take into account the sparsity structures, from both the algebraic and the geometric perspectives, of the third-order tensor in a quadratic complementarity problem. They also have explicit exponents, which improve the literature significantly.     

带重结点的三角求积公式的迭代构造

本文以三角多项式类作为工具讨论了偶数个结点情况下的带重结点的具有最大三角精度的三角求积公式,由拟正交三角多项式的性质给出了求积公式系数的迭代构造。     

A bivariate Markov inequality for Chebyshev polynomials of the second kind

This note presents a Markov-type inequality for polynomials in two variables where the Chebyshev polynomials of the second kind in either one of the variables are extremal. We assume a bound on a polynomial at the set of even or odd Chebyshev nodes with the boundary nodes omitted and obtain bounds on its even or odd order directional derivatives in a critical direction. Previously, the author has given a corresponding inequality for Chebyshev polynomials of the first kind and has obtained the extension of V.A. Markov’s theorem to real normed linear spaces as an easy corollary.To prove our inequality we construct Lagrange polynomials for the new class of nodes we consider and give a corresponding Christoffel–Darboux formula. It is enough to determine the sign of the directional derivatives of the Lagrange polynomials.     

Integral error formulæ for the scale of mean value interpolations which includes Kergin and Hakopian interpolation

Summary. In this paper, we provide an integral error formula for a certain scale of mean value interpolations which includes the multivariate polynomial interpolation schemes of Kergin and Hakopian. This formula involves only derivatives of order one higher than the degree of the interpolating polynomial space, and from it we can obtain sharp -estimates. These -estimates are precisely those that numerical analysts want, to guarantee that a scheme based on such an interpolation has the maximum possible order. Received July 11, 1994 / Revised version received February 12, 1996