Further Investigations Involving Rook Polynomials With Only Real Zeros

We study the zeros of two families of polynomials related to rook theory and matchings in graphs. One of these families is based on the cover polynomial of a digraph introduced by Chung and Graham . Another involves a version of the ‘hit polynomial’ of rook theory, but which applies to weighted matchings in (non-bipartite) graphs. For both of these families we prove a result which is analogous to a theorem of the author, K. Ono, and D. G. Wagner, namely that for Ferrers boards the hit polynomial has only real zeros. We also show that for each of these families there is a general conjecture involving arrays of numbers satisfying inequalities which contains these theorems as special cases. We provide evidence for the truth of these conjectures by proving other special cases and discussing computational experiments.     

To solving multiparameter problems of algebra. 9. The Ψ<Emphasis Type="Italic">F-q</Emphasis> method for factorizing invariant polynomials and its applications

A new method (the ΨF-q method) for computing the invariant polynomials of a q-parameter (q ≥ 1) polynomial matrix F is suggested. Invariant polynomials are computed in factored form, which permits one to analyze the structure of the regular spectrum of the matrix F, to isolate the divisors of each of the invariant polynomials whose zeros belong to the invariant polynomial in question, to find the divisors whose zeros belong to at least two of the neighboring invariant polynomials, and to determine the heredity levels of points of the spectrum for each of the invariant polynomials. Applications of the ΨF-q method to representing a polynomial matrix F(λ) as a product of matrices whose spectra coincide with the zeros of the corresponding divisors of the characteristic polynomial and, in particular, with the zeros of an arbitrary invariant polynomial or its divisors are considered. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 165–173.     

Polynomial zerofinders based on Szegő polynomials

The computation of zeros of polynomials is a classical computational problem. This paper presents two new zerofinders that are based on the observation that, after a suitable change of variable, any polynomial can be considered a member of a family of Szegő polynomials. Numerical experiments indicate that these methods generally give higher accuracy than computing the eigenvalues of the companion matrix associated with the polynomial.     

The spread of matrices and polynomials

The spread of a matrix (or polynomial) is the maximum distance between any two of its eigenvalues (or its zeros). E. Deutsch has recently given upper bounds for the spread of matrices and polynomials. We obtain sharper, simpler upper bounds and observe that they are also upper bounds for the sum of the absolute values of the two largest eigenvalues (or zeros).     

车多项式对Ferrers矩阵的刻画

In this paper,we show that there exist precisely W(A) Ferrers matrices F(C1,C2,…,cm)such that the rook polynomials is equal to the rook polynomial of Ferrers matrix F(b1,b2,…,bm), where A={b1,b2-1,…,bm-m 1} is a repeated set,W(A) is weight of A.     

Separable polynomials over finite dimensional algebras

In [5] it was shown that for a polynomial P of precise degree n with coefficients in an arbitrary m-ary algebra of dimension d as a vector space over an algebraically closed fields, the zeros of P together with the homogeneous zeros of the dominant part of P form a set of cardinality n^d or the cardinality of the base field. We investigate polynomials with coefficients in a d dimensional algebra A without assuming the base field k to be algebraically closed. Separable polynomials are defined to be those which have exactly n^d distinct zeros in [Ktilde] ?_k A [Ktilde] where [Ktilde] denotes an algebraic closure of k. The main result states that given a separable polynomial of degree n, the field extension L of minimal degree over k for which L ?_k A contains all nd zeros is finite Galois over k. It is shown that there is a non empty Zariski open subset in the affine space of all d-dimensional k algebras whose elements A have the following property: In the affine space of polynomials of precise degree n with coefficients in A there is a non empty Zariski open subset consisting of separable polynomials; in other polynomials with coefficients in a finite dimensional algebra are “generically” separable.     

Ordering of nested square roots of 2 according to the Gray code

In this paper, we discuss some relations between zeros of Lucas–Lehmer polynomials and the Gray code. We study nested square roots of 2 applying a “binary code” that associates bits 0 and 1 to “plus” and “minus” signs in the nested form. This gives the possibility to obtain an ordering for the zeros of Lucas–Lehmer polynomials, which take the form of nested square roots of 2.     

Bounds for resultants of univariate and bivariate polynomials

The paper considers bounds on the size of the resultant for univariate and bivariate polynomials. For univariate polynomials we also extend the traditional representation of the resultant by the zeros of the argument polynomials to formal resultants, defined as the determinants of the Sylvester matrix for a pair of polynomials whose actual degree may be lower than their formal degree due to vanishing leading coefficients. For bivariate polynomials, the resultant is a univariate polynomial resulting by the elimination of one of the variables, and our main result is a bound on the largest coefficient of this univariate polynomial. We bring a simple example that shows that our bound is attainable and that a previous sharper bound is not correct.     

Gaussian quadrature rules with exponential weights on (−1, 1)

We study the behavior of some “truncated” Gaussian rules based on the zeros of Pollaczek-type polynomials. These formulas are stable and converge with the order of the best polynomial approximation in suitable function spaces. Moreover, we apply these results to the related Lagrange interpolation process and to prove the stability and the convergence of a Nyström method for Fredholm integral equations of the second kind. Finally, some numerical examples are shown.     

A generalization of the Gauss-Lucas theorem

Given a set of points in the complex plane, an incomplete polynomial is defined as the one which has these points as zeros except one of them. The classical result known as Gauss-Lucas theorem on the location of zeros of polynomials and their derivatives is extended to convex linear combinations of incomplete polynomials. An integral representation of convex linear combinations of incomplete polynomials is also given.     

Polynomials orthogonal with respect to discrete convolution

The concept of “Discrete Convolution Orthogonality” is introduced and investigated. This leads to new orthogonality relations for the Charlier and Meixner polynomials. This in turn leads to bilinear representations for them. We also show that the zeros of a family of convolution orthogonal polynomials are real and simple. This proves that the zeros of the Rice polynomials are real and simple.     

Do Orthogonal Polynomials Dream of Symmetric Curves?

The complex or non-Hermitian orthogonal polynomials with analytic weights are ubiquitous in several areas such as approximation theory, random matrix models, theoretical physics and in numerical analysis, to mention a few. Due to the freedom in the choice of the integration contour for such polynomials, the location of their zeros is a priori not clear. Nevertheless, numerical experiments, such as those presented in this paper, show that the zeros not simply cluster somewhere on the plane, but persistently choose to align on certain curves, and in a very regular fashion. The problem of the limit zero distribution for the non-Hermitian orthogonal polynomials is one of the central aspects of their theory. Several important results in this direction have been obtained, especially in the last 30 years, and describing them is one of the goals of the first parts of this paper. However, the general theory is far from being complete, and many natural questions remain unanswered or have only a partial explanation. Thus, the second motivation of this paper is to discuss some “mysterious” configurations of zeros of polynomials, defined by an orthogonality condition with respect to a sum of exponential functions on the plane, that appeared as a results of our numerical experiments. In this apparently simple situation the zeros of these orthogonal polynomials may exhibit different behaviors: for some of them we state the rigorous results, while others are presented as conjectures (apparently, within a reach of modern techniques). Finally, there are cases for which it is not yet clear how to explain our numerical results, and where we cannot go beyond an empirical discussion.     

Rook placements and cellular decomposition of partition varieties

In this paper, we study the geometric implication of rook length polynomials introduced in the author's thesis. We introduce the idea of partition varieties. These are certain algebraic varieties which have CW-complex structures. We prove that the cell structure of a partition variety is in one-to-one correspondence with rook placements on a Ferrers board defined by a corresponding partition. This correspondence enables one to characterize the geometric attachment between a cell and the closure of another cell combinatorially. The main result of this paper is that the Poincaré polynomial of cohomology for a partition variety is given by the corresponding rook length polynomial.

This paper serves as a transition of our studies from combinatorial aspects to the geometric aspects. To make the transition accessible, we give three appendices on the known results on Grassmann manifolds and flag manifolds which are used frequently. One appendix is on a technical lemma on embeddings of manifolds.     

Approximations for chromatic polynomials

A sequence of finite graphs may be constructed from a given graph by a process of repeated amalgamation. Associated with such a sequence is a transfer matrix whose minimum polynomial gives a recursion for the chromatic polynomials of the graphs in the sequence. Taking the limit, a generalised “chromatic polynomial” for infinite graphs is obtained.     

On the spread of matrices and polynomials

The spread of a matrix (polynomial) is defined as the maximum distance between two of its eigenvalues (zeros). In this note upper bounds are found for the spread of matrices and polynomials.     

Pseudozeros of polynomials and pseudospectra of companion matrices

Summary. It is well known that the zeros of a polynomial are equal to the eigenvalues of the associated companion matrix . In this paper we take a geometric view of the conditioning of these two problems and of the stability of algorithms for polynomial zerofinding. The is the set of zeros of all polynomials obtained by coefficientwise perturbations of of size ; this is a subset of the complex plane considered earlier by Mosier, and is bounded by a certain generalized lemniscate. The is another subset of defined as the set of eigenvalues of matrices with ; it is bounded by a level curve of the resolvent of $A$. We find that if $A$ is first balanced in the usual EISPACK sense, then and are usually quite close to one another. It follows that the Matlab ROOTS algorithm of balancing the companion matrix, then computing its eigenvalues, is a stable algorithm for polynomial zerofinding. Experimental comparisons with the Jenkins-Traub (IMSL) and Madsen-Reid (Harwell) Fortran codes confirm that these three algorithms have roughly similar stability properties. Received June 15, 1993     

Congenial matrices

For a given polynomial in the usual power form, its associated companion matrix can be applied to investigate qualitative properties, such as the location of the roots of the polynomial relative to regions of the complex plane, or to determine the greatest common divisor of a set of polynomials. If the polynomial is in “generalized” form, i.e. expressed relative to an orthogonal basis, then an analogue to the companion matrix has been termed the comrade form. This followed a special case when the basis is Chebyshev, for which the term colleague matrix had been introduced. When a yet more general basis is used, the corresponding matrix has been named confederate. These constitute the class of congenial matrices, which allow polynomials to be studied relative to an appropriate basis. Block-partitioned forms relate to polynomial matrices.     

An algorithm for decomposing a polynomial system into normal ascending sets

We present an algorithm to decompose a polynomial system into a finite set of normal ascending sets such that the set of the zeros of the polynomial system is the union of the sets of the regular zeros of the normal ascending sets.If the polynomial system is zero dimensional,the set of the zeros of the polynomials is the union of the sets of the zeros of the normal ascending sets.     

Relationship between the zeros of two polynomials

In this paper, we shall follow a companion matrix approach to study the relationship between zeros of a wide range of pairs of complex polynomials, for example, a polynomial and its polar derivative or Sz.-Nagy’s generalized derivative. We shall introduce some new companion matrices and obtain a generalization of the Weinstein-Aronszajn Formula which will then be used to prove some inequalities similar to Sendov conjecture and Schoenberg conjecture and to study the distribution of equilibrium points of logarithmic potentials for finitely many discrete charges. Our method can also be used to produce, in an easy and systematic way, a lot of identities relating the sums of powers of zeros of a polynomial to that of the other polynomial.