Lower Bounds on Matrix Factorization Ranks via Noncommutative Polynomial Optimization

We use techniques from (tracial noncommutative) polynomial optimization to formulate hierarchies of semidefinite programming lower bounds on matrix factorization ranks. In particular, we consider the nonnegative rank, the positive semidefinite rank, and their symmetric analogs: the completely positive rank and the completely positive semidefinite rank. We study convergence properties of our hierarchies, compare them extensively to known lower bounds, and provide some (numerical) examples.

     

矩阵多项式秩的和的恒等式及其应用

证明了矩阵A的两个多项式秩的和等于它们最大公因式与最小公倍式秩的和,这个结果不仅可以概括近期文献的相关工作,而且可以对应用矩阵多项式求逆矩阵的方法作进一步的研究,同时也可使关于矩阵秩恒等式的最新讨论获得一种简单统一的处理方法.     

On Ranks of Matrices Associated with Trees

A sign pattern matrix is a matrix whose entries are from the set {+,–,0}. The purpose of this paper is to obtain bounds on the minimum rank of any symmetric sign pattern matrix A whose graph is a tree T (possibly with loops). In the special case when A is nonnegative with positive diagonal and the graph of A is star-like, the exact value of the minimum rank of A is obtained. As a result, it is shown that the gap between the symmetric minimal and maximal ranks can be arbitrarily large for a symmetric tree sign pattern A. Supported by NSF grant No. DMS-00700AMS classification: 05C50, 05C05, 15A48     

A polynomial Hutton theorem with applications

Extending a classical linear result due to Hutton to a nonlinear setting, we prove that a continuous homogeneous polynomial between Banach spaces can be approximated by finite rank polynomials if and only if its adjoint can be approximated by finite rank linear operators. Among other consequences, we apply this result to generalize a classical result due to Aron and Schottenloher about the approximation property on spaces of polynomials and a recent result due to Çaliskan and Rueda about the quasi-approximation property on projective symmetric tensor products.     

Maximum Waring Ranks of Monomials and Sums of Coprime Monomials

We show that monomials and sums of pairwise coprime monomials in four or more variables have Waring rank less than the generic rank, with a short list of exceptions. We asymptotically compare their ranks with the generic rank.     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

A fraction-free unit-circle zero location test for a polynomial with any singularity profile

This paper presents a fraction-free (FF) version of the Bistritz test to determine the zero location (ZL) of a polynomial with respect to the unit circle. The test has the property that when it is invoked on a polynomial with Gaussian or real integer coefficients, it is an efficient integer algorithm completed without fractions over the respective integral domain. The test is not restricted to integers but remains integer preserving (IP) in all possible encounters of abnormalities and singularities. We define a symmetric subresultant polynomial sequence (SSPS) for the Sylvester matrix of two symmetric polynomials. We then show that the sequence of polynomials produced by the FF test coincides with the SSPS of its first two polynomials when the test is normal and the SSPS is strongly nonsingular, or else its polynomials match the non-singular subresultant polynomial and pass over intermediate gaps of singular subresultants in an IP and efficient manner. This relationship (interesting in its own right) is used to show that the test is IP and normally attains integers of minimal size.     

Extended nilHecke algebras and symmetric functions in type B

We formulate a type B extended nilHecke algebra, following the type A construction of Naisse and Vaz. We describe an action of this algebra on extended polynomials and describe some results on the structure on the extended symmetric polynomials. Finally, following Appel, Egilmez, Hogancamp, and Lauda, we prove a result analogous to a classical theorem of Solomon connecting the extended symmetric polynomial ring to a ring of usual symmetric polynomials and their differentials.     

Nonlinear degenerate curvature flows for weakly convex hypersurfaces

We study the evolution of closed, weakly convex hypersurfaces in in direction of their normal vector, where the speed equals a quotient of successive elementary symmetric polynomials of the principal curvatures. We show that there exists a solution for these weakly convex surfaces at least for some short time if the elementary symmetric polynomial in the denominator of the quotient is positive. The results for this nonlinear, degenerate flow are obtained by a cylindrically symmetric barrier construction.Received: 10 November 2003, Accepted: 5 April 2004, Published online: 16 July 2004     

Ranks of partitions modulo 10

In 1954, A.O.L. Atkin and H.P.F. Swinnerton-Dyer established the generating functions for rank differences modulo 5 and 7 for partition functions. In this paper, we derive formulas for the generating functions of ranks of partitions modulo 10 and some inequalities between them.     

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.     

Hermite interpolation with symmetric polynomials

We study the Hermite interpolation problem on the spaces of symmetric bivariate polynomials. We show that the multipoint Berzolari-Radon sets solve the problem. We also give a Newton formula for the interpolation polynomial and use it to prove a continuity property of the interpolation polynomial with respect to the interpolation points.     

The Stirling Polynomial of a Simplicial Complex

We introduce a new encoding of the face numbers of a simplicial complex, its Stirling polynomial, that has a simple expression obtained by multiplying each face number with an appropriate generalized binomial coefficient. We prove that the face numbers of the barycentric subdivision of the free join of two CW-complexes may be found by multiplying the Stirling polynomials of the barycentric subdivisions of the original complexes. We show that the Stirling polynomial of the order complex of any simplicial poset and of certain graded planar posets has non-negative coefficients. By calculating the Stirling polynomial of the order complex of the r-cubical lattice of rank n + 1 in two ways, we provide a combinatorial proof for the following identity of Bernoulli polynomials:

Jucys–Murphy elements,orthogonal matrix integrals,and Jack measures

We study symmetric polynomials whose variables are odd-numbered Jucys–Murphy elements. They define elements of the Hecke algebra associated to the Gelfand pair of the symmetric group with the hyperoctahedral group. We evaluate their expansions in zonal spherical functions and in double coset sums. These evaluations are related to integrals of polynomial functions over orthogonal groups. Furthermore, we give their extension based on Jack polynomials.     

On the perturbation of rank‐one symmetric tensors

The problem of symmetric rank‐one approximation of symmetric tensors is important in independent components analysis, also known as blind source separation, as well as polynomial optimization. We derive several perturbative results that are relevant to the well‐posedness of recovering rank‐one structure from approximately‐rank‐one symmetric tensors. We also specialize the analysis of the shifted symmetric higher‐order power method, an algorithm for computing symmetric tensor eigenvectors, to approximately‐rank‐one symmetric tensors. Copyright © 2012 John Wiley & Sons, Ltd.     

Rank polynomials of fence posets are unimodal

We prove a conjecture of Morier-Genoud and Ovsienko that says that rank polynomials of the distributive lattices of lower ideals of fence posets are unimodal. We do this by proving a stronger version of the conjecture due to McConville, Sagan, and Smyth. Our proof involves introducing a related class of posets, which we call circular fence posets and showing that their rank polynomials are symmetric. We also apply the recent work of Elizalde, Plante, Roby, and Sagan on rowmotion on fences and show many of their homomesy results hold for the circular case as well.     

限制李超代数的环面秩

本文将模李代数中环面与环面秩的理论推广到模李超代数中.应用模李超代数的限制包络得到了环面秩的若干重要性质.作为应用,计算了典型李超代数Slm|n与限制Cartan型李超代数W(m,n,1),S(m,n,1)的绝对环面秩及S(m,n,1)在W(m,n,1)中的环面秩.     

Decomposable polymatroids and connections with graph coloring

We introduce ideas that complement the many known connections between polymatroids and graph coloring. Given a hypergraph that satisfies certain conditions, we construct polymatroids, given as rank functions, that can be written as sums of rank functions of matroids, and for which the minimum number of matroids required in such sums is the chromatic number of the line graph of the hypergraph. This result motivates introducing chromatic numbers and chromatic polynomials for polymatroids. We show that the chromatic polynomial of any 2-polymatroid is a rational multiple of the chromatic polynomial of some graph. We also find the excluded minors for the minor-closed class of polymatroids that can be written as sums of rank functions of matroids that form a chain of quotients.     

Some characteristic properties of the weighted particular Schur polynomial mean

This paper provides some characteristic properties of the weighted particular Schur polynomial mean of several variables. In addition, an elementary proof of an important inequality involving the weighted particular Schur polynomial mean is given. Various related results involving a family of the Schur polynomials, symmetric polynomials, and other associated polynomials, together with the potential for their applications, are also considered.     

A basic class of symmetric orthogonal polynomials using the extended Sturm-Liouville theorem for symmetric functions

In this research, by applying the extended Sturm-Liouville theorem for symmetric functions, a basic class of symmetric orthogonal polynomials (BCSOP) with four free parameters is introduced and all its standard properties, such as a generic second order differential equation along with its explicit polynomial solution, a generic orthogonality relation, a generic three term recurrence relation and so on, are presented. Then, it is shown that four main sequences of symmetric orthogonal polynomials can essentially be extracted from the introduced class. They are respectively the generalized ultraspherical polynomials, generalized Hermite polynomials and two other sequences of symmetric polynomials, which are finitely orthogonal on (−∞,∞) and can be expressed in terms of the mentioned class directly. In this way, two half-trigonometric sequences of orthogonal polynomials, as special sub-cases of BCSOP, are also introduced.