Simultaneous similarity of matrices

In this paper we solve completely and explicitly the long-standing problem of classifying pairs of n × n complex matrices (A, B) under the simultaneous similarity (TAT⁻¹, TBT⁻¹). Roughly speaking, the classification decomposes to a finite number of steps. In each step we consider an open algebraic set ⁰_n,2,r,π M_n × M_n (M_n = the set of n × n complex-valued matrices). Here r and π are two positive integers. Then we construct a finite number of rational functions ø₁,…,ø_s in the entries of A and B whose values are constant on all pairs similar in _n,2,r,π to (A, B). The values of the functions ø_i(A, B), I = 1,…, s, determine a finite number (at most κ(n, 2, r)) of similarity classes in _n,2,r,π. Let S_n be the subspace of complex symmetric matrices in M_n. For (A, B) ε S_n × S_n we consider the similarity class (TAT^t, TBT^t), where T ranges over all complex orthogonal matrices. Then the characteristic polynomial |λI − (A + xB)| determines a finite number of similarity classes for almost all pairs (A, B) ε S_n × S_n.     

Exhaustive weakly wandering sequences

A sequence of integers {n_i : i = 0, 1…} is an exhaustive weakly wandering sequence for a transformation T if for some measurable set W, X=^∞_i=0TⁿⁱW(disj. We introduce a hereditary Property (H) for a sequence of integers associated with an infinite ergodic transformation T, and show that it is a sufficient condition for the sequence to be an exhaustive weakly wandering sequence for T. We then show that every infinite ergodic transformation admits sequences that possess Property (H), and observe that Property (H) is inherited by all subsequences of a sequence that possess it. As a corollary, we obtain an application to tiling the set of integers with infinite subsets.     

An asymptotic minimax risk bound for estimation of a linear functional relationship

We consider estimation of the parameter B in a multivariate linear functional relationship X_i=ξ_i+ξ_1i, Y_i=Bξ_i+ξ_2i, i=1,…,n, where the errors (ζ_1i^′, ζ_2i^′) are independent standard normal and (ξ_i, i ) is a sequence of unknown nonrandom vectors (incidental parameters). If there are no substantial a priori restrictions on the infinite sequence of incidental parameters then asymptotically the model is nonparametric but does not fit into common settings presupposing a parameter from a metric function space. A special result of the local asymptotic minimax type for the m.1.e. of B is proved. The accuracy of the normal approximation for the m.l.e. of order n^−1/2 is also established.     

Chains of Rings with Local Formal Fibers

Let (T, M) be a complete local domain containing the integers. Let p ₁ ? p ₂ ? ··· ? p _n be a chain of nonmaximal prime ideals of T such that T _{p n} is a regular local ring. We construct a chain of excellent local domains A _n  ? A _n?1 ? ··· ? A ₁ such that for each 1 ≤ i ≤ n, the completion of A _i is T, the generic formal fiber of A _i is local with maximal ideal p _i , and if I is a nonzero ideal of A _i then A _i /I is complete. We then show that if Q is a nonmaximal prime ideal of T and 1 ≤ h = ht _T Q, then there is a chain of excellent local domains B ₀ ? B ₁ ? ··· ? B _h  ? T such that for every i = 0, 1, 2,…, h we have ht(Q ∩ B _i ) = i, the completion of B _i is isomorphic to T[[X ₁, X ₂,…, X _i ]] where the X _j 's are indeterminants, and the formal fiber of Q ∩ B _i is local.     

On a problem in additive number theory

For a set A, let P(A) be the set of all finite subset sums of A. We prove that if a sequence B={b ₁<b ₂<⋯} of integers satisfies b ₁≧11 and b _n+1≧3b _n +5 (n=1,2,…), then there exists a sequence of positive integers A={a ₁<a ₂<⋯} for which P(A)=ℕ∖B. On the other hand, if a sequence B={b ₁<b ₂<⋯} of positive integers satisfies either b ₁=10 or b ₂=3b ₁+4, then there is no sequence A of positive integers for which P(A)=ℕ∖B.     

Extremal values of continuants and transcendence of certain continued fractions

We prove a criterion for the transcendence of continued fractions whose partial quotients are contained in a finite set {b₁,…,b_r} of positive integers such that the density of occurrences of b_i in the sequence of partial quotients exists for 1ir. As an application we study continued fractions [0,a₁,a₂,a₃,…] with a_n=1+([nθ]modd) where θ is irrational and d2 is a positive integer.     

An extension of the Erdős–Ginzburg–Ziv Theorem to hypergraphs

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct with the result that they can be considered as sets. For a sequence S, subsequence S^′, and set T, |T∩S| denotes the number of terms x of S with xT, and |S| denotes the length of S, and SS^′ denotes the subsequence of S obtained by deleting all terms in S^′. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A=A₁,…,A_n, such that

then there exists a subsequence S^′ of S, with length |S^′|≤max{|S|−n+1,2n}, and with an n-set partition, , such that . Furthermore, if ||A_i|−|A_j||≤1 for all i and j, or if |A_i|≥3 for all i, then .(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a,bG such that . If |S|≥2m−1, then there exists an m-term zero-sum subsequence S^′ of S with or .Let be a connected, finite m-uniform hypergraph, and be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group ) of the vertices of the complete m-uniform hypergraph , there exists a subhypergraph isomorphic to such that every edge in is monochromatic (such that for every edge e in the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph of contains an edge with at least half of its vertices monovalent in , or if consists of two intersecting edges, then . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when is a single edge.     

A remark on degree sequences of multigraphs

A sequence {d ₁, d ₂, . . . , d _n } of nonnegative integers is graphic (multigraphic) if there exists a simple graph (multigraph) with vertices v ₁, v ₂, . . . , v _n such that the degree d(v _i ) of the vertex v _i equals d _i for each i = 1, 2, . . . , n. The (multi) graphic degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is (multi)graphic or not. In this paper we characterize sequences that are multigraphic in a similar way, Havel (Časopis Pěst Mat 80:477–480, 1955) and Hakimi (J Soc Indust Appl Math 10:496–506, 1962) characterized graphic sequences. Results of Hakimi (J Soc Indust Appl Math 10:496–506, 1962) and Butler, Boesch and Harary (IEEE Trans Circuits Syst CAS-23(12):778–782, 1976) follow.     

Small divisors of Bernoulli sums

Let ?= {?_i,i ≥1} be a sequence of independent Bernoulli random variables (P{?_i = 0} = P{?_i = 1 } = 1/2) with basic probability space (Ω, A, P). Consider the sequence of partial sums B_n=?₁+...+?_n, n=1,2..... We obtain an asymptotic estimate for the probability P{P^-(B_n) > >} for >≤n^{e/log log n}, c a positive constant.     

An Asymptotic Property of Schachermayer's Space under Renorming

Let X be a Banach space with closed unit ball B. Given k , X is said to be k-β, respectively, (k + 1)-nearly uniformly convex ((k + 1)-NUC), if for every ε > 0 there exists δ, 0 < δ < 1, so that for every x B and every ε-separated sequence (x_n) B there are indices (n_i)^k_{i = 1}, respectively, (n_i)^{k + 1}_{i = 1}, such that (1/(k + 1))||x + ∑^k_{i = 1} x_ni|| ≤ 1 − δ, respectively, (1/(k + 1))||∑^{k + 1}_{i = 1} x_ni|| ≤ 1 − δ. It is shown that a Banach space constructed by Schachermayer is 2-β, but is not isomorphic to any 2-NUC Banach space. Modifying this example, we also show that there is a 2-NUC Banach space which cannot be equivalently renormed to be 1-β.     

两类惯量惟一的对称符号模式

§ 1　 IntroductionA sign pattern(matrix) A is a matrix whose entries are from the set{ +,-,0 } .De-note the setofall n× n sign patterns by Qn.Associated with each A=(aij)∈ Qnis a class ofreal matrices,called the qualitative class of A,defined byQ(A) ={ B =(bij)∈ Mn(R) |sign(bij) =aijfor all i and j} .　　 For a symmetric sign pattern A∈ Qn,by G(A) we mean the undirected graph of A,with vertex set { 1 ,...,n} and (i,j) is an edge if and only if aij≠ 0 .A sign pattern A∈ Qnis a do…     

Bit-parallel -matching and suffix automata

(δ,γ)-matching is a string matching problem with applications to music retrieval. The goal is, given a pattern P_1…m and a text T_1…n on an alphabet of integers, find the occurrences P^′ of the pattern in the text such that (i) , and (ii) . The problem makes sense for δγδm. Several techniques for (δ,γ)-matching have been proposed, based on bit-parallelism or on skipping characters. We first present an O(mnlog(γ)/w) worst-case time and O(n) average-case time bit-parallel algorithm (being w the number of bits in the computer word). It improves the previous O(mnlog(δm)/w) worst-case time algorithm of the same type. Second, we combine our bit-parallel algorithm with suffix automata to obtain the first algorithm that skips characters using both δ and γ. This algorithm examines less characters than any previous approach, as the others do just δ-matching and check the γ-condition on the candidates. We implemented our algorithms and drew experimental results on real music, showing that our algorithms are superior to current alternatives with high values of δ.     

A sufficient condition for pairing problem of generators in symmetrizable Kac–Moody algebras

In a symmetrizable Kac–Moody algebra g(A), let α=∑_i=1ⁿk_iα_i be an imaginary root satisfying k_i>0 and α,α_i<0 for i=1,2,…,n. In this paper, it is proved that for any x_αg_α{0}, satisfying [x_α,f_n]≠0 and [x_α,f_i]=0 for i=1,2,…,n−1, there exists a vector y such that the subalgebra generated by x_α and y contains g′(A), the derived subalgebra of g(A).     

Perfect Skolem sets

A Skolem sequence is a sequence s₁,s₂,…,s_2n (where s_i∈A={1,…,n}), each s_i occurs exactly twice in the sequence and the two occurrences are exactly s_i positions apart. A set A that can be used to construct Skolem sequences is called a Skolem set. The problem of deciding which sets of the form A={1,…,n} are Skolem sets was solved by Thoralf Skolem in the late 1950s. We study the natural generalization where A is allowed to be any set of n positive integers. We give necessary conditions for the existence of Skolem sets of this generalized form. We conjecture these necessary conditions to be sufficient, and give computational evidence in favor of our conjecture. We investigate special cases of the conjecture and prove that the conjecture holds for some of them. We also study enumerative questions and show that this problem has strong connections with problems related to permutation displacements.     

On the Common Substring Alignment Problem

The Common Substring Alignment Problem is defined as follows: Given a set of one or more strings S₁, S₂ … S_c and a target string T, Y is a common substring of all strings S_i, that is, S_i = B_iYF_i. The goal is to compute the similarity of all strings S_i with T, without computing the part of Y again and again. Using the classical dynamic programming tables, each appearance of Y in a source string would require the computation of all the values in a dynamic programming table of size O(nℓ) where ℓ is the size of Y. Here we describe an algorithm which is composed of an encoding stage and an alignment stage. During the first stage, a data structure is constructed which encodes the comparison of Y with T. Then, during the alignment stage, for each comparison of a source S_i with T, the pre-compiled data structure is used to speed up the part of Y. We show how to reduce the O(nℓ) alignment work, for each appearance of the common substring Y in a source string, to O(n)-at the cost of O(nℓ) encoding work, which is executed only once.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

Nonlinear Lie derivations on upper triangular matrices

Let M _n (𝔸) and T _n (𝔸) be the algebra of all n?×?n matrices and the algebra of all n?×?n upper triangular matrices over a commutative unital algebra 𝔸, respectively. In this note we prove that every nonlinear Lie derivation from T _n (𝔸) into M _n (𝔸) is of the form A?→?AT???TA?+?A _??+?ξ(A)I _n , where T?∈?M _n (𝔸), ??:?𝔸?→?𝔸 is an additive derivation, ξ?:?T _n (𝔸)?→?𝔸 is a nonlinear map with ξ(AB???BA)?=?0 for all A,?B?∈?T _n (𝔸) and A _? is the image of A under???applied entrywise.     

Rates of convergence for classes of functions: The non-i.i.d. case

Let X_i, i ≥ 1, be a sequence of φ-mixing random variables with values in a sample space (X, A). Let L(X_i) = P_(i) for all i ≥ 1 and let _n, n ≥ 1, be classes of real-valued measurable functions on (X, A). Given any function g on (X, A), let S_n(g) = Σ_{i = 1}ⁿ {g(X_i) − Eg(X_i)}. Under weak metric entropy conditions on _n and under growth conditions on both the mixing coefficients and the maximal variance V V(n) max_{i ≤ n} sup_{g n} ∫ g² dP_(i), we show that there is a numerical constant U < ∞ such that

Full-size image

a.s. ^*, where _{i = 1}^xP_(i) and H H(n) is the square root of the entropy of the class _n. Additionally, the rate of convergence H⁻¹(n/V)^1/2 cannot, in general, be improved upon. Applications of this result are considered.     

On a generalization of a theorem of Erdős and Fuchs

Let A={a₁,a₂,…}(a₁<a₂<) be an infinite sequence of nonnegative integers, let k≥2 be a fixed integer and denote by r_k(A,n) the number of solutions of a_i1+a_i2++a_ik≤n. Montgomery and Vaughan proved that r₂(A,n)=cn+o(n^1/4) cannot hold for any constant c>0. In this paper, we extend this result to k>2.     

On two set-systems with restricted cross-intersections

If A₁, …, A_m; B₁, …, B_m are finite sets such that for l t 0 and any r, s, we have |A_i| r, |B_i| s and |_i ∩ B_i| t for 1 i m and |A_i ∩ B_i| > l for 1 i < j m, what is the maximum value that m can attain? In this paper we answer this question of Füredi and extend an inequality of Bollobás.im]0658.TIF