On a problem of Katona on minimal separating systems

Let S be an n-element set. In this paper, we determine the smallest number f(n) for which there exists a family of subsets of S{A₁,A₂,…,A_f(n)} with the following property: Given any two elements x, y ∈ S (x ≠ y), there exist k, l such that A_k ∩ A_l= ?, and x ∈ A_k, y ∈ A_l. In particular it is shown that f(n)= 3 log₃n when n is a power of 3.     

Cyclic irreducible non-holonomic modules over the Weyl algebra: An algorithmic characterization

Let K be a field of characteristic zero, n≥1 an integer and A_n+1=K[X,Y₁,…,Y_n]〈∂_X,∂_Y1,…,∂_Yn〉 the (n+1)th Weyl algebra over K. Let S∈A_n+1 be an order-1 differential operator of the type with a_i,b_i∈K[X] and g_i∈K[X,Y_i] for every i=1,…,n. We construct an algorithm that allows one to recognize whether S generates a maximal left ideal of A_n+1, hence also whether A_n+1/A_n+1S is an irreducible non-holonomic A_n+1-module. The algorithm, which is a powerful instrument for producing concrete examples of cyclic maximal left ideals of A_n, is easy to implement and quite useful; we use it to solve several open questions.The algorithm also allows one to recognize whether certain families of algebraic differential equations have a solution in K[X,Y₁,…,Y_n] and, when they have one, to compute it.     

The characterization of sort sequences

A sort sequenceS _n is a sequence of all unordered pairs of indices inI _n = 1, 2, ...,n. With a sort sequenceS _n, we associate a sorting algorithmA(S _n) to sort input setX = x ₁, x₂, ..., x_n as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS _n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S _n) denote the average number of comparisons required by the algorithmA(S _n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S _n) over all sort sequencesS _n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n).     

Sieve-equivalence and explicit bijections

Suppose A₁,…, A_n are subsets of a finite set A, and B₁,…, B_n are subsets of a finite set B. For each subset S of N = {1, 2,…, n}, let A_s = ∩_i?SA_i and B_S = ∩_i?SB_i. It is shown that if explicit bijections f_S:A_S → B_S for each S ? N are given, an explicit bijection h:A-∪_i=1A_i→B-∪_i=1B_i can be constructed. The map h is independent of any ordering of the elements of A and B, and of the order in which the subsets A_i and B_i are listed.     

Simultaneous congruence of convex compact sets of Hermitian matrices with constant rank

Let S be a compact convex set of n × n hermitian matrices (n ⩾ 2). Suppose every member of S is nonsingular and has exactly one negative eigenvalue. Let (ε₁,…,ε_n) be any ordered n-tuple from the set {- 1, 1}. One of our main results is that a nonsingular matrix X exists such that, for every A in S and every 1 ⩽ j ⩽ n, the (j, j) entry of X¹AX has sign ε_j. A similar result, with only negative ε_j allowed, is proved also for a compact convex set S of n × n hermitian matrices such that every member of S has the same rank and exactly one negative eigenvalue.     

An extremal property of the permanent and the determinant

Given an n × n matrix A, define the n! × n! matrix Ã, with rows and columns indexed by the permutation group S_n, with (σ, τ) entry Πⁿ_i=1a_{τ(i), σ(i)}. It is shown that if A is positive semidefinite, then det A is the smallest eigenvalue of Ã; it is conjectured that per A is the largest eigenvalue of Ã, and the conjecture proved for n⩽3. Several known and some unknown inequalities are derived as consequences.     

The endomorphism spectrum of a monounary algebra

The endomorphism spectrum specA of an algebra A is defined as the set of all positive integers, which are equal to the number of elements in an endomorphic image of A, for all endomorphisms of A. In this paper we study finite monounary algebras and their endomorphism spectrum. If a finite set S of positive integers is given, one can look for a monounary algebra A with S = specA. We show that for countably many finite sets S, no such A exists. For some sets S, an appropriate A with spec A = S are described. For n ∈ ? it is easy to find a monounary algebra A with {1, 2, ..., n} = specA. It will be proved that if i ∈ ?, then there exists a monounary algebra A such that specA skips i consecutive (consecutive eleven, consecutive odd, respectively) numbers. Finally, for some types of finite monounary algebras (binary and at least binary trees) A, their spectrum is shown to be complete.     

Random A-permutations: Convergence to a Poisson process

Suppose that S _n is the permutation group of degree n, A is a subset of the set of natural numbers ?, and T _n(A) is the set of all permutations from S _n whose cycle lengths belong to the set A. Permutations from T _n are usually called A-permutations. We consider a wide class of sets A of positive asymptotic density. Suppose that ζ _mn is the number of cycles of length m of a random permutation uniformly distributed on T _n. It is shown in this paper that the finite-dimensional distributions of the random process {tz _mn, m ε A} weakly converge as n → ∞ to the finite-dimensional distributions of a Poisson process on A.     

On the reduction of pairs of hermitian or symmetric matrices to diagonal form by congruence

Let A₁, A₂ be given n-by-n Hermitian or symmetric matrices, and consider the simultaneous transformations A_i→SA_iS^* if A_i is Hermitian or A_i→SA_iS^T if A_i is symmetric. We give necessary and sufficient conditions for the existence of a unitary S which reduces both A₁ and A₂ to diagonal form in this way. When at least one of A₁ or A₂ is nonsingular, we give necessary and sufficient conditions for a reduction of this sort with a nonsingular S. These results are a generalization of the classical theorem from mechanics that a positive definite matrix and a Hermitian matrix can always be diagonalized simultaneously by a nonsingular congruence.     

A relationship between stochastic matrices and eigenvalues of products

Let {B₁,…,B_n} be a set of n rank one n×n row stochastic matrices. The next two statements are equivalent: (1) If A is an n×n nonnegative matrix, then 1 is an eigenvalue ofB_kA for each k=1,…,n if and only if A is row stochastic. (2) The n×n row stochastic matrix S whose kth row is a row of B_k for k=1,…,n is nonsingular. For any set {B₁, B₂,…, B_p} of fewer than n row stochastic matrices of order n×n and of any rank, there exists a nonnegative n×n matrix A which is not row stochastic such that 1 is eigenvalue of every B_kA, k=1,…,p.     

Going in Circles: Variations on the Money-Coutts Theorem

Given a polygon A ₁,...,A _n, consider the chain of circles: S ₁ inscribed in the angle A ₁, S ₂ inscribed in the angle A ₂ and tangent to S ₁, S ₃ inscribed in the angle A ₃ and tangent to S ₂, etc. We describe a class of n-gons for which this process is 2n-periodic. We extend the result to the case when the sides of a polygon are arcs of circles. The case of triangles is known as the Money-Coutts theorem.     

Extendible elements of the alternating groups

An element?σ?of A_n , the Alternating group of degree n, is extendible in S_n , the Symmetric group of degree n, if there exists a subgroup H of S_n but not A_n whose intersection with A_n is the cyclic group generated by σ. A simple number-theoretic criterion, in terms of the cycle-decomposition, for an element of A_n to be extendible in S_n is given here.     

Eigenvalue distribution theorems for certain homogeneous spaces

A classical theorem of Szegö describes the limiting behavior of the eigenvalues of P_nAP_n, where A is a multiplication operator on L₂(S¹) and P_n is the projection on the subspace spanned by e^ikθ (0 ? k ? n). A generalization of this is proved, whereby S¹ is replaced by an arbitrary rank one homogeneous space (e.g. S^m), A by a pseudodifferential operator of order zero, and P_n by a sequence of spectral projections for the Laplace-Beltrami operator. A by-product is an alternate proof of a theorem of A. Weinstein on the eigenvalue clusters of the Laplacian plus a potential.     

The left and right inverse eigenvalue problems of generalized reflexive and anti-reflexive matrices

Let n×n complex matrices R and S be nontrivial generalized reflection matrices, i.e., R^∗=R=R⁻¹≠±I_n, S^∗=S=S⁻¹≠±I_n. A complex matrix A with order n is said to be a generalized reflexive (or anti-reflexive ) matrix, if RAS=A (or RAS=−A). In this paper, the solvability conditions of the left and right inverse eigenvalue problems for generalized reflexive and anti-reflexive matrices are derived, and the general solutions are also given. In addition, the associated approximation solutions in the solution sets of the above problems are provided. The results in present paper extend some recent conclusions.     

Exponential sums and rectangular partitions

Let F denote a finite field with q=p^f elements, and let σ(A) equal the trace of the square matrix A. This paper evaluates exponential sums of the form S(E,X₁,…,X_n)e{?σ(CX₁?X_nE)}, where S(E,X₁,…,X_n) denotes a summation over all matrices E,X₁,…,X_n of appropriate sizes over F, and C is a fixed matrix. This evaluation is then applied to the problem of counting ranked solutions to matrix equations of the form U₁?U_αA+DV₁?V_β=B where A,B,D are fixed matrices over F.     

Sperner systems consisting of pairs of complementary subsets

It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if $\text{A}$ = {;A₁,…, A_l}; consists of k-subsets of a set with n > 2k elements such that A_i ∩ A_j ≠ ? for all i, j then l ? (_k?1^n?1). Schönheim proved that if A₁, …, A_l are subsets of a set S with n elements such that A_i ? A_j, A_i ∩ A_j ≠ ø and A_i ∪ A_j ≠ S for all i ≠ j then $\text{l ? (}{}_{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]\; ?\; 1</mtext>}}{}^{\mathrm{n\; ?\; 1}}\text{)}$. In this note we prove a common strengthening of these results.     

Some new results on subset sums

Let n be a large integer and A be a subset of [n]={1,…,n}. The set SA is the collection of the subset sums of A. In this note, we discuss new results (and proofs) on few well-known problems concerning SA. In particular, we improve an estimate of Alon and Erd?s concerning monochromatic representations.     

Classification of small (0, 1) matrices

Denote by A_n the set of square (0, 1) matrices of order n. The set A_n, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let D_n, S_n denote the set of absolute determinant values and Smith normal forms of matrices from A_n. Denote by a_n the smallest integer not in D_n. The sets D₉ and S₉ are obtained; especially, a₉ = 103. The lower bounds for a_n, 10 ? n ? 19 (exceeding the known lower bound a_n ? 2f_n − 1, where f_n is nth Fibonacci number) are obtained. Row/permutation equivalence classes of A_n correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible.     

Robust interpolation of random fields homogeneous in time and isotropic on a sphere,which are observed with noise

We study the problem of optimal linear estimation of the functional $$A_N \xi = \sum\limits_{k = 0}^{\rm N} {\int\limits_{S_n } {a(k,x)\xi (k,x)m_n (dx),} }$$ , which depends on unknown values of a random field ξ(k, x),k?Z,x?S _n homogeneous in time and isotropic on a sphereS _n, by observations of the field ξ(k,x)+η(k,x) with k? Z{0, 1, ...,N},x?S_n (here, η (k, x) is a random field uncorrelated with ξ(k, x), homogeneous in time, and isotropic on a sphere S_n). We obtain formulas for calculation of the mean square error and spectral characteristic of the optimal estimate of the functionalA _Nξ. The least favorable spectral densities and minimax (robust) spectral characteristics are found for optimal estimates of the functionalA _Nξ.