The total reducibility order of a polynomial in two variables

LetK be an algebraically closed field of characteristic zero. ForA ∈K[x, y] let σ(A) = {λ ∈K:A − λ is reducible}. For λ ∈ σ(A) letA − λ = ∏ _i=1 ^n(λ) A _iλ ^k _μ whereA _iλ are distinct primes. Let ϱ_λ(A) =n(λ) − 1 and let ρ(A) = Σ_λɛσ(A)ϱ_λ(A). The main result is the following: Theorem.If A ∈ K[x, y] is not a composite polynomial, then ρ(A) < degA.     

Computing an eigenvector of an inverse Monge matrix in max-plus algebra

The problem of computing an eigenvector of an inverse Monge matrix in max-plus algebra is addressed. For a general matrix, the problem can be solved in at most O(n³) time. This note presents an O(n²) algorithm for computing one max-plus algebraic eigenvector of an inverse Monge matrix . It is assumed that is irreducible.     

Sturm Sequences and Random Eigenvalue Distributions

This paper proposes that the study of Sturm sequences is invaluable in the numerical computation and theoretical derivation of eigenvalue distributions of random matrix ensembles. We first explore the use of Sturm sequences to efficiently compute histograms of eigenvalues for symmetric tridiagonal matrices and apply these ideas to random matrix ensembles such as the β-Hermite ensemble. Using our techniques, we reduce the time to compute a histogram of the eigenvalues of such a matrix from O(n ²+m) to O(mn) time where n is the dimension of the matrix and m is the number of bins (with arbitrary bin centers and widths) desired in the histogram (m is usually much smaller than n). Second, we derive analytic formulas in terms of iterated multivariate integrals for the eigenvalue distribution and the largest eigenvalue distribution for arbitrary symmetric tridiagonal random matrix models. As an example of the utility of this approach, we give a derivation of both distributions for the β-Hermite random matrix ensemble (for general β). Third, we explore the relationship between the Sturm sequence of a random matrix and its shooting eigenvectors. We show using Sturm sequences that assuming the eigenvector contains no zeros, the number of sign changes in a shooting eigenvector of parameter λ is equal to the number of eigenvalues greater than λ. Finally, we use the techniques presented in the first section to experimentally demonstrate a O(log n) growth relationship between the variance of histogram bin values and the order of the β-Hermite matrix ensemble. This research was supported by NSF Grant DMS–0411962.     

On eigenvalues of symmetric (+1, −1) matrices

To every symmetric matrixA with entries ±1, we associate a graph G(A), and ask (for two different definitions of distance) for the distance ofG(A) to the nearest complete bipartite graph (cbg). Letλ ₁(A),λ ¹ (A) be respectively the algebraically largest and least eigenvalues ofA. The Frobenius distance (see Section 4) to the nearest cbg is bounded above and below by functions ofn −λ ₁ (A), wheren=ord A. The ordinary distance (see Section 1) to the nearest cbg is shown to be bounded above and below by functions ofλ ¹ (A). A curious corollary is: there exists a functionf (independent ofn, and given by (1.1)), such that |λ _i (A) | ≦f(λ ¹(A), whereλ _i (A) is any eigenvalue ofA other thanλ _i (A). This work was supported (in part) by the U.S. Army under contract #DAHC04-C-0023.     

Generating Uniform Random Vectors in Z p k : The General Case

We consider the rate of convergence of the Markov chain X _n+1=A X _n +B _n (mod p), where A is an integer matrix with nonzero eigenvalues, and {B _n } _n is a sequence of independent and identically distributed integer vectors, with support not parallel to a proper subspace of Q ^k invariant under A. If for all eigenvalues λ _i of A, then n=O((ln p)²) steps are sufficient and n=O(ln p) steps are necessary to have X _n sampling from a nearly uniform distribution. Conversely, if A has the eigenvalues λ _i that are roots of positive integer numbers, |λ ₁|=1 and |λ _i |>1 for all , then O(p ²) steps are necessary and sufficient.      

A note on Sobolev orthogonality for Laguerre matrix polynomials

Let {Ln(A,λ)(x)}n≥0 be the sequence of monic Laguerre matrix polynomials defined on [0, ∞) by Ln(A,λ)(x)=n!/(-λ)n∑nk=0(-λ)κ/k!(n-1)! (A I)n[(A I)k]-1 xk,where A ∈ Cr×r. It is known that {Ln(A,λ)(x)}n≥0 is orthogonal with respect to a matrix moment functional when A satisfies the spectral condition that Re(z) ＞ - 1 for every z ∈σ(A).In this note we show that forA such that σ(A) does not contain negative integers, the Laguerre matrix polynomials Ln(A,λ) (x) are orthogonal with respect to a non-diagonal SobolevLaguerre matrix moment functional, which extends two cases: the above matrix case and the known scalar case.     

On the influence of parameters determining anisotropic spaces of smooth functions on characteristics of the embedding theorems

An anisotropic Sobolev and Nikol'skii-Besov space on a domain G is determined by its integro-differential (shortly, ID) parameters. On the other hand, the geometry of G is characterized by the set Λ(G) of all vectors λ=(λ₁,..., λ_n) such that G satisfies the λ-horn condition. We study the dependence of the totality of possible embeddings upon the set Λ(G) and theID-parameters of the space. We consider only embeddings with q≥pⁱ, where pⁱ are the integral parameters of the space and q is the integral embedding parameter. For a given space, we introduce its initial matrix A₀ determined by theID-parameters. A₀ turns out to be a Z-matrix. On the basis of a natural classification of Z-matrices, a classification of anisotropic spaces is introduced. This classification allows one to restate the existence of an embedding with q≥pⁱ in terms of certain specific properties of A₀. Let A₀ be a nondegenerate M-matrix. Any vector λ∈Λ(G) gives rise to a certain set of admissible values of the embedding parameters. We call λ optimal if this set is the largest possible. It turns out that the optimal vector λ _G ^* is determined by Λ(G) and A₀, and may be found by a linear optimization procedure. The following cases are possible: a) , b) , c) λ _G ^* does not exist. In case a) the set of admissible values of the embedding parameters is the biggest, while in case c) no embeddings with q≥pⁱ exist. In case b) the so-called saturation phenomenon occurs, i.e., certain variations of some differential parameters of the space do not change the set of admissible values of the embedding parameters. The latter fact has some applications to the problem of extension of all functions belonging to the given space from G to Eⁿ. Bibliography: 20 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 201, 1992, pp. 22–94. Translated by A. A. Mekler.     

Modified Cholesky algorithms: a catalog with new approaches

Given an n ×  n symmetric possibly indefinite matrix A, a modified Cholesky algorithm computes a factorization of the positive definite matrix A +  E, where E is a correction matrix. Since the factorization is often used to compute a Newton-like downhill search direction for an optimization problem, the goals are to compute the modification without much additional cost and to keep A +  E well-conditioned and close to A. Gill, Murray and Wright introduced a stable algorithm, with a bound of ||E||₂ =  O(n ²). An algorithm of Schnabel and Eskow further guarantees ||E||₂ =  O(n). We present variants that also ensure ||E||₂ =  O(n). Moré and Sorensen and Cheng and Higham used the block LBL ^T factorization with blocks of order 1 or 2. Algorithms in this class have a worst-case cost O(n ³) higher than the standard Cholesky factorization. We present a new approach using a sandwiched LTL ^T -LBL ^T factorization, with T tridiagonal, that guarantees a modification cost of at most O(n ²). H.-r. Fang’s work was supported by National Science Foundation Grant CCF 0514213. D. P. O’Leary’s work was supported by National Science Foundation Grant CCF 0514213 and Department of Energy Grant DEFG0204ER25655.     

Limit theorems for convolutions of probabilities on non abelian semigroups

Let S be a locally compact semigroup. We study the sequence (λⁿ) of the convolution powers of a probability measure λ on S and their shifts by a probability measure η on S. We shall give sufficient conditions for lim ‖λⁿ−η*λⁿ‖ = 0 (where ‖.‖ denotes the norm). In particular we consider the case the η is a point measure and we study the subsemigroup L_O(λ) = {x ∈ S : lim ‖λⁿ−δ_X*λⁿ‖ = 0}. We shall give necessary and sufficient conditions for L_o(λ)=S. In this case we want to treat the problem of the convergence of the sequence (λⁿ).     

Comparison theorems for the volume of a complex submanifold of a Kaehler manifold

LetM be a Kaehler manifold of real dimension 2n with holomorphic sectional curvatureK _H≥4λ and antiholomorphic Ricci curvatureρ _A≥(2n−2)λ, andP is a complex hypersurface. We give a bound for the quotient (volume ofP)/(volume ofM) and prove that this bound is attained if and only ifP=C P ⁿ⁻¹(λ) andM=C P ⁿ(λ). Moreover, we give some results on the volume of of tubes aboutP inM. Work partially supported by a DGICYT Grant No. PS87-0115-CO3-01.     

On the complexity of linear boolean operators with thin matrices

Under consideration is the problem of constructing a square Booleanmatrix A of order n without “rectangles” (it is a matrix whose every submatrix of the elements that are in any two rows and two columns does not consist of 1s). A linear transformation modulo two defined by A has complexity o(ν(A) − n) in the base {⊕}, where ν(A) is the weight of A, i.e., the number of 1s (the matrices without rectangles are called thin). Two constructions for solving this problem are given. In the first construction, n = p ² where p is an odd prime. The corresponding matrix H _p has weight p ³ and generates the linear transformation of complexity O(p ² log p log log p). In the second construction, the matrix has weight nk where k is the cardinality of a Sidon set in ℤ _n . We may assume that

(<Emphasis Type="Italic">p, λ</Emphasis>)-Koszul algebras and modules

In this paper, the notions of (p, λ)-Koszul algebra and (p, λ)-Koszul module are introduced. Some criteria theorems for a positively graded algebra A to be (p, λ)-Koszul are given. The notion of weakly (p, λ)-Koszul module is defined as well and let WK _λ ^p (A) denote the category of weakly (p, λ)-Koszul modules. We show that M ∈ WK _λ ^p (A) if and only if it can be approximated by (p, λ)-Koszul submodules, which is equivalent to that G(M) is a (p, λ)-Koszul module, where G(M) denotes the associated graded module of M. As applications, the relationships of the minimal graded projective resolutions of M, G(M) and (p, λ)-Koszul submodules are established. In particular, for a module M ∈ WK _λ ^p (A) we prove that ⊕ _i≥0 Ext _A ⁱ (M,A ₀) ∈ gr ₀(E(A)), we also get as a consequence that the finitistic dimension conjecture is valid in WK _λ ^p (A) under certain conditions.     

On simple modules of Hecke algebras of type Dn

This is a continuation of our previous work. We classify all the simple ℋ_q(D _n )-modules via an automorphismh defined on the set { λ | D^λ ≠ 0}. Whenf _n(q) ≠ 0, this yields a classification of all the simple ℋ ^q (D _n)- modules for arbitrary n. In general ( i. e., q arbitrary), if λ⁽¹⁾ = λ⁽²⁾,wegivea necessary and sufficient condition ( in terms of some polynomials ) to ensure that the irreducible ℋ_q,1(B _n )- module D^λ remains irreducible on restriction to ℋ_q(D _n ).     

Geometric computation of the numerical radius of a matrix

We use methods of geometric computing combined with hermitean matrix eigenvalue/eigenvector evaluations to find the numerical radius w(A) of a real or complex square matrix A simply, quickly, and accurately. The numerical radius w(A) is defined as the maximal distance of points in the field of values F(A) = { x^* A x | ||x||₂ = 1 }F(A) = \{ x^* A x \mid \|x\|_2 = 1 \} from zero in ℂ. Its value is an indicator of the transient behavior of the discrete dynamical system f _k + 1 = Af _k . We describe and test a MATLAB code for solving this optimization problem that can have multiple and even infinitely many solutions with maximal distance.     

Produits infinis de resolvantes

This paper is concerned with the convergence of the sequence χ _n =(I+λ _n A)⁻¹χ _n−1 whereA is maximal monotone and λ _n >0. Various assumptions onA and λ _n are considered.      

{0, 1/2}-Chvátal-Gomory cuts

Given the integer polyhedronP _t := conv{x ∈ℤ ⁿ :Ax⩽b}, whereA ∈ℤ ^{m × n} andb ∈ℤ ^m , aChvátal-Gomory (CG)cut is a valid inequality forP ₁ of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ ₊ ^m such that λτA∈ℤ ⁿ . In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2} ^m . We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of strong inequalities forP ₁. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering polytopes are briefly discussed.     

Counting points in hypercubes and convolution measure algebras

It is shown that ifA andB are non-empty subsets of {0, 1} ⁿ (for somenεN) then |A+B|≧(|A||B|)^α where α=(1/2) log₂ 3 here and in what follows. In particular if |A|=2 ^n-1 then |A+A|≧3 ^n-1 which anwers a question of Brown and Moran. It is also shown that if |A| = 2 ^n-1 then |A+A|=3 ^n-1 if and only if the points ofA lie on a hyperplane inn-dimensions. Necessary and sufficient conditions are also given for |A +B|=(|A||B|)^α. The above results imply the following improvement of a result of Talagrand [7]: ifX andY are compact subsets ofK (the Cantor set) withm(X),m(Y)>0 then λ(X+Y)≧2(m(X)m(Y))^α wherem is the usual measure onK and λ is Lebesgue measure. This also answers a question of Moran (in more precise terms) showing thatm is not concentrated on any proper Raikov system.     

Bounded imaginary powers and <Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript>-calculus of the Stokes operator in two-dimensional exterior domains

The present contribution deals with the Stokes operator A_q on L^q_σ(Ω), 1<q<∞, where Ω is an exterior domain in ℝ² of class C². It is proved that A_q admits a bounded H_∞-calculus. This implies the existence of bounded imaginary powers of A_q, which has several important applications. – So far this property was only known for exterior domains in ℝⁿ, n≥3. – In particular, this shows that A_q has maximal regularity on L^q_σ(Ω). For the proof the resolvent (λ+A_q)⁻¹ has to be analyzed for |λ|→∞ and λ→0. For large λ this is done using an approximate resolvent based on the results of [3], which were obtained by applying the calculus of pseudodifferential boundary value problems. For small λ we analyze the representation of the resolvent developed in [11] by a potential theoretical method.     

The Ξ operator and its relation to Krein's spectral shift function

We explore connections between Krein's spectral shift function ζ(λ,H ₀, H) associated with the pair of self-adjoint operators (H ₀, H),H=H ₀+V, in a Hilbert spaceH and the recently introduced concept of a spectral shift operator Ξ(J+K ^*(H ₀−λ−i0)⁻¹ K) associated with the operator-valued Herglotz functionJ+K ^*(H ₀−z)⁻¹ K, Im(z)>0 inH, whereV=KJK ^* andJ=sgn(V). Our principal results include a new representation for ζ(λ,H ₀,H) in terms of an averaged index for the Fredholm pair of self-adjoint spectral projections (E J+A(λ)+tB(λ)(−∞, 0)),E _J((−∞, 0))), ℝ, whereA(λ)=Re(K ^*(H ₀−λ−i0⁻¹ K),B(λ)=Im(K ^*(H ₀−λ-i0)⁻¹ K) a.e. Moreover, introducing the new concept of a trindex for a pair of operators (A, P) inH, whereA is bounded andP is an orthogonal projection, we prove that ζ(λ,H ₀, H) coincides with the trindex associated with the pair (Ξ(J+K ^*(H ₀−λ−i0)K), Ξ(J)). In addition, we discuss a variant of the Birman-Krein formula relating the trindex of a pair of Ξ operators and the Fredholm determinant of the abstract scattering matrix. We also provide a generalization of the classical Birman—Schwinger principle, replacing the traditional eigenvalue counting functions by appropriate spectral shift functions.     

Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001