Spectrally arbitrary ray patterns

An n×n ray pattern A is said to be spectrally arbitrary if for every monic nth degree polynomial f(x) with coefficients from C, there is a matrix in the pattern class of A such that its characteristic polynomial is f(x). In this article the authors extend the nilpotent-Jacobi method for sign patterns to ray patterns, establishing a means to show that an irreducible ray pattern and all its superpatterns are spectrally arbitrary. They use this method to establish that a particular family of n×n irreducible ray patterns with exactly 3n nonzeros is spectrally arbitrary. They then show that every n×n irreducible, spectrally arbitrary ray pattern has at least 3n-1 nonzeros.     

New classes of spectrally arbitrary ray patterns

An n×n ray pattern matrix S is said to be spectrally arbitrary if for every monic nth degree polynomial f(λ) with coefficients from C, there is a complex matrix in the ray pattern class of S such that its characteristic polynomial is f(λ). In this article we give new classes of spectrally arbitrary ray pattern matrices.     

Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

A CLASS OF SPECTRALLY ARBITRARY RAY PATTERNS

An n × n ray pattern A is said to be spectrally arbitrary if for every monic nth degree polynomial f(x) with coefficients from C, there is a complex matrix in the ray pattern class of A such that its characteristic polynomial is f(x). In this paper, a family ray patterns is proved to be spectrally arbitrary by using Nilpotent-Jacobian method.     

A new family of spectrally arbitrary ray patterns

An n × n ray pattern A is called a spectrally arbitrary ray pattern if the complex matrices in Q(A) give rise to all possible complex polynomials of degree n.     

On pointwise approximation of arbitrary functions by countable families of continuous functions

The following problem is considered. Given a real-valued function f defined on a topological space X, when can one find a countable familyf _n :n∈ω of continuous real-valued functions on X that approximates f on finite subsets of X? That is, for any finite set F?X and every real number ε>0 one can choosen∈ω such that ∥f(x)?f_n(x)∥<ε for everyx∈F. It will be shown that the problem has a positive solution if and only if X splits. A space X is said to split if, for any A?X, there exists a continuous mapf _A:X→R ^ω such that A=f _A ^?1 (A). Splitting spaces will be studied systematically.     

Nullstellenzahlen von Polynomfunktionen auf Restklassenringen

Let ?/n? denote the ring of integers mod n. By a polynomial function f over ?/n? will be meant a mapping of ?/n? into itself which is induced by a polynomial f(x) ∈ ?[x]. We ask how many zeros of f are possible. The main result is a formula for the maximal number of zeros of non-vanishing polynomial functions mod n.     

一类新的极小谱任意符号模式

若给定任意一个$n$次首一实系数多项式$f(\lambda)$,都存在一个实矩阵$B\in Q(A)$, 使得$B$的特征多项式为$f(\lambda)$,则称$A$为谱任意符号模式. 如果一个谱任意符号模式的任意非零元被零取代后所得到的符号模式不是谱任意,那么这个谱任意符号模式称为极小谱任意符号模式.本文证明一类极小谱任意符号模式.     

On the convergence of averaging Hermite interpolators

We investigate two sequences of polynomial operators, H_{2n − 2}(A₁,f; x) and H_{2n − 3}(A₂,f; x), of degrees 2n − 2 and 2n − 3, respectively, defined by interpolatory conditions similar to those of the classical Hermite-Féjer interpolators H_{2n − 1}(f, x). If H_{2n − 2}(A₁,f; x) and H_{2n − 3}(A₂,f; x) are based on the zeros of the jacobi polynomials P_n^(α,β)(x), their convergence behaviour is similar to that of H_{2n − 1}(f;, x). If they are based on the zeros of (1 − x²)T_{n − 2}(x), their convergence behaviour is better, in some sense, than that of H_{2n − 1}(f, x).     

Positive Results and Counterexamples in Comonotone Approximation

We estimate the degree of comonotone polynomial approximation of continuous functions f, on [?1,1], that change monotonicity s??1 times in the interval, when the degree of unconstrained polynomial approximation E _n (f)??n ^??? , n??1. We ask whether the degree of comonotone approximation is necessarily ??c(??,s)n ^??? , n??1, and if not, what can be said. It turns out that for each s??1, there is an exceptional set A _s of ????s for which the above estimate cannot be achieved.     

An extremal property of Hermite polynomials

Let H_n be the nth Hermite polynomial, i.e., the nth orthogonal on polynomial with respect to the weight w(x)=exp(−x²). We prove the following: If f is an arbitrary polynomial of degree at most n, such that |f||H_n| at the zeros of H_n+1, then for k=1,…,n we have f^(k)H_n^(k), where · is the norm. This result can be viewed as an inequality of the Duffin and Schaeffer type. As corollaries, we obtain a Markov-type inequality in the norm, and estimates for the expansion coefficients in the basis of Hermite polynomials.     

On Approximate ℓ 1 Systems in Banach Spaces

Let X be a real Banach space and let (f(n)) be a positive nondecreasing sequence. We consider systems of unit vectors (x_i)^∞_i=1 in X which satisfy ∑_iA±x_i|A|−f(|A|), for all finite A and for all choices of signs. We identify the spaces which contain such systems for bounded (f(n)) and for all unbounded (f(n)). For arbitrary unbounded (f(n)), we give examples of systems for which [x_i] is H.I., and we exhibit systems in all isomorphs of ℓ₁ which are not equivalent to the unit vector basis of ℓ₁. We also prove that certain lacunary Haar systems in L₁ are quasi-greedy basic sequences.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

An Erd?s-Ko-Rado theorem for partial permutations

Let [n] denote the set of positive integers {1,2,…,n}. An r-partial permutation of [n] is a pair (A,f) where A⊆[n], |A|=r and f:A→[n] is an injective map. A set A of r-partial permutations is intersecting if for any (A,f), (B,g)∈A, there exists x∈A∩B such that f(x)=g(x). We prove that for any intersecting family A of r-partial permutations, we have .It seems rather hard to characterize the case of equality. For 8?r?n-3, we show that equality holds if and only if there exist x₀ and ε₀ such that A consists of all (A,f) for which x₀∈A and f(x₀)=ε₀.     

幂零--中心化方法

An nxn complex sign pattern(ray pattern) S is said to be spectrally arbitrary if for every monic nth degree polynomial f(λ) with coefficients from C,there is a complex matrix in the complex sign pattern class(ray pattern class) of S such that its characteristic polynomial is f(λ).We derive the Nilpotent-Centralizer methods for spectrally arbitrary complex sign patterns and ray patterns,respectively.We find that the Nilpotent-Centralizer methods for three kinds of patterns(sign pattern,complex sign pattern,ray pattern) are the same in form.     

Eigenvalues of products of matrices

Let A and B be n?×?n matrices over an algebraically closed field F. The pair ( A,?B ) is said to be spectrally complete if, for every sequence c₁,…,c_n ∈F such that det (AB)=c₁ ,…,c_n , there exist matrices A′,B,′∈F,^n×n similar to A,?B, respectively, such that A′B′ has eigenvalues c₁,…,c_n . In this article, we describe the spectrally complete pairs. Assuming that A and B are nonsingular, the possible eigenvalues of A′B′ when A′ and B′ run over the sets of the matrices similar to A and B, respectively, were described in a previous article.     

Polynomial Lie Algebras

We introduce and study a special class of infinite-dimensional Lie algebras that are finite-dimensional modules over a ring of polynomials. The Lie algebras of this class are said to be polynomial. Some classification results are obtained. An associative co-algebra structure on the rings k[x ₁,...,x _n]/(f ₁,...,f _n) is introduced and, on its basis, an explicit expression for convolution matrices of invariants for isolated singularities of functions is found. The structure polynomials of moving frames defined by convolution matrices are constructed for simple singularities of the types A,B,C, D, and E ₆.     

An Erdös-Ko-Rado theorem for restricted signed sets

A restricted signed r-set is a pair （A, f）, where A lohtain in [n] = {1, 2,…, n} is an r-set and f is a map from A to [n] with f（i） ≠ i for all i ∈ A. For two restricted signed sets （A, f） and （B, g）, we define an order as （A, f） ≤ （B, g） if A C B and g｜A ： f A family .A of restricted signed sets on [n] is an intersecting antiehain if for any （A, f）, （B, g） ∈ A, they are incomparable and there exists x ∈ A ∩ B such that f（x） = g（x）. In this paper, we first give a LYM-type inequality for any intersecting antichain A of restricted signed sets, from which we then obtain ｜A｜≤ （r-1^n-1）（n-1）^r-1 if A. consists of restricted signed r-sets on [n]. Unless r = n = 3, equality holds if and only if A consists of all restricted signed r-sets （A, f） such that x0∈ A and f（x0） =ε0 for some fixed x0 ∈ [n], ε0 ∈ [n] ／ {x0}.     

On Unimodular Rows over Polynomial Rings

Let A be a commutative ring and n 3 a positive integer. In this paper, we consider unimodular rows (f₁(x),..., f_n(x)) over A[x]. We prove that, if the row of the leading coefficients of f_i(x) is unimodular over A and a A, then there exists E_n(A[x]) such that (f₁(x),...,f_n(x)) = (f₁(a),...,f_n(a)). Also, if A is a Noetherian ring with finite Krull dimension and the row of leading coefficients satisfies the same condition, then we give a bound for the length of in terms of elementary transvections.Partially supported by INTAS 93–436EXT and DFG–RFBR grant No. 96–01–00092G.2000 Mathematics Subject Classification: 19A13, 19B14, 13C10, 13B25, 13F20     

Integrally Closed Domains,Minimal Polynomials,and Null Ideals of Matrices

Abstract

We show that every element of the integral closure D′ of a domain D occurs as a coefficient of the minimal polynomial of a matrix with entries in D. This answers affirmatively a question of Brewer and Richman, namely, if integrally closed domains are characterized by the property that the minimal polynomial of every square matrix with entries in D is in D[x]. It follows that a domain D is integrally closed if and only if for every matrix A with entries in D the null ideal of A, N _D (A)?=?{f?∈?D[x]?∣?f(A)?=?0} is a principal ideal of D[x].