On bounds for eigenvalues of real symmetric matrices

Let A=(a_ij) be a real symmetric matrix of order n. We characterize all nonnegative vectors x=(x₁,...,x_n) and y=(y₁,...,y_n) such that any real symmetric matrix B=(b_ij), with b_ij=a_ij, i≠jhas its eigenvalues in the union of the intervals [b_ij?y_i, b_ij+ x_i]. Moreover, given such a set of intervals, we derive better bounds for the eigenvalues of B using the 2n quantities {b_ii?y, b_ii+x_i}, i=1,..., n.     

Presentations of alternating semigroups

One presentation of the alternating groupA _n hasn?2 generatorss ₁,…,s_n?2 and relationss ₁ ³ =s _i ² =(s_1?1s_i)³=(s_js_k)²=1, wherei>1 and |j?k|>1. Against this backdrop, a presentation of the alternating semigroupA _n ^c )A _n is introduced: It hasn?1 generatorss ₁,…,S _n?2,e, theA _n-relations (above), and relationse ²=e, (es ₁)⁴, (es _j)²=(es _j)⁴,es _i=s _i s ₁ ^-1 es ₁, wherej>1 andi≥1.     

Upper triangular operator matrices with the single-valued extension property

If A=(Aij)_1?i,j?n∈B(X) is an upper triangular Banach space operator such that AiiAij=AijAjj for all 1?i?j?n, then A has SVEP or satisfies (Dunford's) condition (C) or (Bishop's) property (β) or (the decomposition) property (δ) if and only if Aii, 1?i?n, has the corresponding property.     

Least squares solutions to AX = B for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation

A matrix A∈R^n×n is called a bisymmetric matrix if its elements a_i,j satisfy the properties a_i,j=a_j,i and a_i,j=a_n-j+1,n-i+1 for 1?i,j?n. This paper considers least squares solutions to the matrix equation AX=B for A under a central principal submatrix constraint and the optimal approximation. A central principal submatrix is a submatrix obtained by deleting the same number of rows and columns in edges of a given matrix. We first discuss the specified structure of bisymmetric matrices and their central principal submatrices. Then we give some necessary and sufficient conditions for the solvability of the least squares problem, and derive the general representation of the solutions. Moreover, we also obtain the expression of the solution to the corresponding optimal approximation problem.     

A new inequality for symmetric functions

Let x_i ≥ 0, y_i ≥ 0 for i = 1,…, n; and let a_j(x) be the elementary symmetric function of n variables given by a_j(x) = ∑_{1 ≤ ii < … <ij ≤ n}x_ii … x_ij. Define the partical ordering x <y if a_j(x) ≤ a_j(y), j = 1,… n. We show that $\text{x}\text{\$}\text{?}\text{y ? x}{}^{\mathrm{\alpha }}\text{\$}\text{?}\text{y}{}^{\mathrm{\alpha }}\text{, 0}\text{\$}\text{?}\text{α ≤ 1}$, where {x^α}_i = x^α_i. We also give a necessary and sufficient condition on a function f(t) such that x <y ? f(x) <f(y). Both results depend crucially on the following: If x <y there exists a piecewise differentiable path z(t), with z_i(t) ≥ 0, such that z(0) = x, z(1) = y, and z(s) <z(t) if 0 ≤ s ≤ t ≤ 1.     

Divisibility properties of power GCD matrices and power LCM matrices

Let a,b and n be positive integers and the set S={x₁,…,x_n} of n distinct positive integers be a divisor chain (i.e. there exists a permutation σ on {1,…,n} such that x_σ(1)|…|x_σ(n)). In this paper, we show that if a|b, then the ath power GCD matrix (S^a) having the ath power (x_i,x_j)^a of the greatest common divisor of x_i and x_j as its i,j-entry divides the bth power GCD matrix (S^b) in the ring M_n(Z) of n×n matrices over integers. We show also that if a?b and n?2, then the ath power GCD matrix (S^a) does not divide the bth power GCD matrix (S^b) in the ring M_n(Z). Similar results are also established for the power LCM matrices.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Continuity properties of the Drazin pseudoinverse

Let B^D denote that Drazin inverse of the n×n complex matrix B. Define the core-rank of B as rank (B^i(B)) where i(B) is the index of B. Let j = 1,2,…, and A_j and A be square matrices such that A_i converges to A with respect to some norm. The main result of this paper is that A_j^D converges to A^D if and only if there exist a j₀ such that core-rank A_j=core-rankA for j ? j₀.     

On the number of linear forms in logarithms

Let n be a positive integer. In this paper we estimate the size of the set of linear forms b₁loga₁+b₂loga₂+?+bnlogan, where |bi|?Bi and 1?ai?Ai are integers, as Ai,Bi→∞.     

A Katona-type proof of an Erd?s-Ko-Rado-type theorem

Let p?1/2 and let μ_p be the product measure on {0,1}ⁿ, where μ_p(x)=p^∑x_i(1-p)^n-∑x_i. Let A⊂{0,1}ⁿ be an intersecting family, i.e. for every x,y∈A there exists 1?i?n such that x_i=y_i=1. Then μ_p(A)?p. Our proof uses a probabilistic trick first applied by Katona to prove the Erd?s-Ko-Rado theorem.     

Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1?x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1?i, $$ - \frac{{2^{k - 1} }}{{k!}}< f\left[ {x_1 ,... + x_{i + k} } \right]< \frac{{x_{i + k + 1} - x_{i + k} + 2^{k - 1} }}{{k!}},$$ where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial \(f(x) = \sum\limits_{j = 0}^n {a_j x^j } ,n \geqq 2\) . Let δ be positive with δ^n?1=|2^n?1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1?x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a “nice” upper bound on a generalization of the van der Waerden numbers. Ap _k -sequence of length n is defined to be a strictly increasing sequence of positive integers {x ₁, ...,x _n } for which there exists a polynomial of degree at mostk with integer coefficients and satisfyingf(x _j )=x _j+1 forj=1, 2, ...,n?1. Definep _k (n) to be the least positive integer such that if {1, 2, ...,p _k (n)} is partitioned into two sets, then one of the two sets must contain ap _k -sequence of lengthn. THEOREM. p_n?2(n)≦(n!)^(n?2)!/2.     

On a conjecture of R.F. Scott (1881)

A formula is given for the permanent of a general Cauchy matrix ((x_i?y_j)^?1). In a special case, where the x_i and the y_j are the distinct nth roots of 1 and ?1 respectively, a formula for the permanent, conjectured by R. F. Scott, is proved by computing the eigenvalues of related circulants.     

On a question of Sárközy on gaps of product sequences

Motivated by a question of Sárközy, we study the gaps in the product sequence B = A · A = {b ₁ < b ₂ < …} of all products a _i a _j with a _i , a _j ∈ A when A has upper Banach density α > 0. We prove that there are infinitely many gaps b _n+1 ? b _n ? α ^?3 and that for t ≥ 2 there are infinitely many t-gaps b _n+t ? b _n ? t ² α ^?4. Furthermore, we prove that these estimates are best possible.We also discuss a related question about the cardinality of the quotient set A/A = {a _i /a _j , a _i , a _j ∈ A} when A ? {1, …, N} and |A| = αN.     

Simultaneous quasidiagonalization of complex matrices

Let

be the complex algebra generated by a pair of n × n Hermitian matrices A, B. A recent result of Watters states that A, B are simultaneously unitarily quasidiagonalizable [i.e., A and B are simultaneously unitarily similar to direct sums C₁⊕…⊕C_t,D₁⊕…⊕D_t for some t, where C_i, D_i are k_i × k_i and k_i?2(1?i?t)] if and only if [p(A, B), A]² and [p(A, B), B]² belong to the center of

for all polynomials p(x, y) in the noncommuting variables x, y. In this paper, we obtain a finite set of conditions which works. In particular we show that if A, B are positive semidefinite, then A, B are simultaneously quasidiagonalizable if (and only if) [A, B]², [A², B]² and [A, B²]² commute with A, B.     

Products of central collineations

An n by n matrix M over a (commutative) field F is said to be central if M ? I has rank 1. We say that M is an involution if M²=I; if M is also central we call M a simple involution. We will prove that any n-by-n matrix M satisfying detM=±1 is the product of n+2 or fewer simple involutions. This can be reduced to n+1 if F contains no roots of the equation xⁿ=(?1)ⁿ other than ±1. Any ordered field is of this kind. Our main result is that if M is any n-by-n nonsingular nonscalar matrix and if x_i ∈ F such that x₁?x_n=detM, then there exist central matrices M_i such that M=M₁?M_n and x_i=detM_i for i=1,…,n. We will apply this result to the projective group PGL(n,F) and to the little projective group PSL(n,F).     

Divisibility of determinants of power GCD matrices and power LCM matrices on finitely many quasi-coprime divisor chains

Let a, n ? 1 be integers and S = {x₁, … , x_n} be a set of n distinct positive integers. The matrix having the ath power (x_i, x_j)^a of the greatest common divisor of x_i and x_j as its i, j-entry is called ath power greatest common divisor (GCD) matrix defined on S, denoted by (S^a). Similarly we can define the ath power LCM matrix [S^a]. We say that the set S consists of finitely many quasi-coprime divisor chains if we can partition S as S = S₁ ∪ ? ∪ S_k, where k ? 1 is an integer and all S_i (1 ? i ? k) are divisor chains such that (max(S_i), max(S_j)) = gcd(S) for 1 ? i ≠ j ? k. In this paper, we first obtain formulae of determinants of power GCD matrices (S^a) and power LCM matrices [S^a] on the set S consisting of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. Using these results, we then show that det(S^a)∣det(S^b), det[S^a]∣det[S^b] and det(S^a)∣det[S^b] if a∣b and S consists of finitely many quasi-coprime divisor chains with gcd(S) ∈ S. But such factorizations fail to be true if such divisor chains are not quasi-coprime.     

An index classification of M-matrices

An M-matrix as defined by Ostrowski [5] is a matrix that can be split into A = sI ? B, where s > 0, B ? 0, with s ? r(B), the spectral radius of B. Following Plemmons [6], we develop a classification of all M-matrices. We consider v, the index of zero for A, i.e., the smallest nonnegative integer n such that the null spaces of Aⁿ and Aⁿ⁺¹ coincide. We characterize this index in terms of convergence properties of powers of s^?1B. We develop additional characterizations in terms of nonnegativity of the Drazin inverse of A on the range of A^v, extending (as conjectured by Poole and Boullion [7]) the well-known property that A^?1?0 whenever A is nonsingular.     

The Jordan canonical form for a class of zero-one matrices

Let f:N→N be a function. Let A_n=(a_ij) be the n×n matrix defined by a_ij=1 if i=f(j) for some i and j and a_ij=0 otherwise. We describe the Jordan canonical form of the matrix A_n in terms of the directed graph for which A_n is the adjacency matrix. We discuss several examples including a connection with the Collatz 3n+1 conjecture.     

Jordan higher all-derivable points on nontrivial nest algebras

Let A be a Banach algebra with unity I and M be a unital Banach A-bimodule. A family of continuous additive mappings D=(δ_i)_i∈N from A into M is called a higher derivable mapping at X, if δ_n(AB)=∑_i+j=nδ_i(A)δ_j(B) for any A,B∈A with AB=X. In this paper, we show that D is a Jordan higher derivation if D is a higher derivable mapping at an invertible element X. As an application, we also get that every invertible operator in a nontrivial nest algebra is a higher all-derivable point.