An analysis of (h,k, 1)-Shellsort

One classical sorting algorithm, whose performance in many cases remains unanalyzed, is Shellsort. Let h be a t-component vector of positive integers. An h-Shellsort will sort any given n elements in t passes, by means of comparisons and exchanges of elements. Let S>_j(h; n) denote the average number of element exchanges in the jth pass, assuming that all the n! initial orderings are equally likely. In this paper we derive asymptotic formulas of S_j(h; n) for any fixed h = (h, k, l), making use of a new combinatorial interpretation of S₃. For the special case h = (3, 2, 1), the analysis is further sharpened to yield exact expressions.     

Antichains in the set of subsets of a multiset

A set F of distinct subsets x of a finite multiset M (that is, a set with several different kinds of elements) is a c-antichain if for no c + 1 elements x₀, x₁, …, x_c of F does x₀ ? x₁ ? ··· ? x_c hold. The weight of F, wF, is the total number of elements of M in the various elements x of F. For given integers f and c, we find min wF, where the minimum is taken over all f-element c-antichains F. Daykin [9, 10] has solved this problem for ordinary sets and Clements [3] has solved it for multisets, but only for c = 1.     

Simple components of group algebras Q[G] central over real quadratic fields

Let k be a real quadratic field, and $\text{U}$ a central division quaternion algebra over k. In this paper sufficient conditions are given to insure that $\text{U}$ appears in a simple component of the group algebra Q[G] of some finite group G over the rational field Q. In particular, when k is assumed to be Q(√2) or Q(√5), the necessary and sufficient conditions for $\text{U}$ to appear in some Q[G] are given.     

A duality principle for lattices and categories of modules

Let R be a ring with 1, R^op the opposite ring, and R-Mod the category of left unitary R-modules and R-linear maps. A characterization of well-powered abelian categories $\text{A}$ such that there exists an exact embedding functor $\text{A}$→R-Mod is given. Using this characterization and abelian category duality, the following duality principles can be established.Theorem. There exists an exact embedding functor $\text{A}$→R-Mod if and only if there exists an exact embedding functor $\text{A}$^op→R^op-Mod.Corollary. If R-Mod has a specified diagram-chasing property, then R^op-Mod has the dual property.A lattice L is representable by R-modules if it is embeddable in the lattice of submodules of some unitary left R-module; $\text{L}$(R) denotes the quasivariety of all lattices representable by R-modules.Theorem. A lattice L is representable by R-modules if and only if its order dual L¹ is representable by R^op-modules. That is, $\text{L}\text{(}\text{R}{}^{\mathrm{op}}\text{)={L}{}^1\text{:L?}\text{L}\text{(}\text{R}\text{)}}$.If $\text{R}$ is a commutative ring with 1 and a specified diagram-chasing result is satisfied in R-Mod, then the dual result is also satisfied in R-Mod. Furthermore, $\text{L}\text{(}\text{R}\text{)}$ is self-dual: $\text{L}\text{(}\text{R}\text{)= {L}{}^1\text{:L?}\text{L}\text{(}\text{R}\text{)}.}$     

On the structure of the Wishart distribution

In this paper it is shown that every nonnegative definite symmetric random matrix with independent diagonal elements and at least one nondegenerate nondiagonal element has a noninfinitely divisible distribution. Using this result it is established that every Wishart distribution W_p(k, Σ, M) with both p and rank (Σ) ≥ 2 is noninfinitely divisible. The paper also establishes that any Wishart matrix having distribution W_p(k, Σ, 0) has the joint distribution of its elements in the rth row and rth column to be infinitely divisible for every r = 1,2,…,p.     

Quadratic mappings of spheres

In this paper we obtain a basis-free method for determining the general form of quadratic maps over R between spheres. We show that all quadratic maps (over certain R-lattices) between spheres are Hopf maps, and that the classical Hopf fibrations, S^2m?1→S^m, for m=2, 4, 8, are the unique nontrivial maps over Z, up to action by the orthogonal group.     

Factorizing multivariate time series operators

Motivated by problems occurring in the empirical identification and modelling of a n-dimensional ARMA time series X(t) we study the possibility of obtaining a factorization (I + a₁B + … + a_pB^p) X(t) = [Π_i=1^p (I ? α_iB)] X(t), where B is the backward shift operator. Using a result in [3] we conclude that as in the univariate case such a factorization always exists, but unlike the univariate case in general the factorization is not unique for given a₁, a₂,…, a_p. In fact the number of possibilities is limited upwards by $\text{(np)!}\text{(n!)}{}^{\mathrm{p}}$, there being cases, however, where this maximum is not reached. Implications for the existence and possible use of transformations which removes nonstationarity (or almost nonstationarity) of X(t) are mentioned.     

A generalization of a result of Sylvester's

Let v₁,…,v_n be vectors in Zⁿ with D = det(v₁,…,v_n) > 0. Let v_{n + 1} be in the cone generated by v₁,…,v_n and such that v₁,…,v_v, v_{n + 1} generate Zⁿ as a Z-module. There exists a unique “largest“ χ not expressible as a nonnegative integer combination of v₁,…,v_n, v_{n + 1} and χ = Dv_{n + 1} ? (v₁ + … v_n + v_{n + 1}).     

Positively regular homeomorphisms of Euclidean spaces

A homeomorphism of Rⁿ onto itself is called positively regular (or EC⁺) iff its family of non-negative iterates is pointwise equicontinuous. For EC⁺ homeomorphism of Rⁿ such that some point of Rⁿ has bounded positive semi-orbit, the nucleus M is defined, and the following theorems are proved.Theorem 1. If such a homeomorphism h:Rⁿ→Rⁿ has compact nucleus M, then M is a fully invariant compact AR. Further, for n≠4,5,h:Rⁿ/M→Rⁿ/M is conjugate to a contraction on Rⁿ.Theorem 2. In Rⁿ,n≠4,5,M compact iff there existsa disk D such that h(D)?IntD.Theorem 3. In R², either M is a disk and h|M is a rotation, or h|M is periodic. The relationship between M and the irregular set of ? is also studied.     

Matricial logarithmic derivatives

If θ is a norm on Cⁿ, then the mapping $\text{A→}\text{lim}{}_{\mathrm{h\downarrow 0}}\text{6I+hA6}{}_{\mathrm{\theta }}\text{?1}\text{/h}$ from M_n(C) (=C^{n × n}) into R is called the logarithmic derivative induced by the vector norm θ. In this paper we generalize this concept to a mapping γ from M_n(C) into M_k(R), where k ? n. Denoting by α(B) the spectral abscissa of a square matrix B (the largest of the real parts of the eigenvalues), we show, in particular, that α(A) ?α(γ(A)). As a byproduct we obtain simple sufficient conditions for the stability of a matrix.     

Bilattices for deductions in multi-valued logic

In this exploratory paper we propose a framework for the deduction apparatus of multi-valued logics based on the idea that a deduction apparatus has to be a tool to manage information on truth values and not directly truth values of the formulas. This is obtained by embedding the algebraic structure V defined by the set of truth values into a bilattice B. The intended interpretation is that the elements of B are pieces of information on the elements of V. The resulting formalisms are particularized in the framework of fuzzy logic programming. Since we see fuzzy control as a chapter of multi-valued logic programming, this suggests a new and powerful approach to fuzzy control based on positive and negative conditions.     

The entropy condition and the admissibility of shocks

The author proposed (Trans. Amer. Math. Soc.199 (1974), 89–112) the extended entropy condition (E) and solved the Riemann problem for general 2 × 2 conservation laws. The Riemann problem for 3 × 3 gas dynamics equations was treated by the author (J. Differential Equations18 (1975), 218–231). In this paper we justify condition (E) by the viscosity method in the spirit of Gelfand [Uspehi Mat. Nauk14 (1959), 87–158]. We show that a shock satisfies condition (E) if and only if the shock is admissible, that is, it is the limit of progressive wave solutions of the associated viscosity equations. For the “genuinely nonlinear” 2 × 2 conservation laws, Conley and Smoller [Comm. Pure Appl. Math.23 (1970), 867–884] proved that a shock satisfies Lax's shock inequalities [cf. Comm. Pure Appl. Math.14 (1957), 537–566] if and only if it is admissible. In this paper, we consider systems that are not necessarily genuinely nonlinear.     

A characterization of the multivariate normal distribution

Let X_j (j = 1,…,n) be i.i.d. random variables, and let Y′ = (Y₁,…,Y_m) and X′ = (X₁,…,X_n) be independently distributed, and A = (a_jk) be an n × n random coefficient matrix with a_jk = a_jk(Y) for j, k = 1,…,n. Consider the equation U = AX, Kingman and Graybill [Ann. Math. Statist.41 (1970)] have shown U ～ N(O,I) if and only if X ～ N(O,I). provided that certain conditions defined in terms of the a_jk are satisfied. The task of this paper is to delete the identical assumption on X₁,…,X_n and then generalize the results to the vector case. Furthermore, the condition of independence on the random components within each vector is relaxed, and also the question raised by the above authors is answered.     

Positive definite rational functions of two variables which are not the sum of three squares

Cassels, Ellison, and Pfister have shown that there is a positive semidefinite function of R(x, y) that is not the sum of three squares. In this paper positive definite functions of R(x, y) are found having the same property. The proof involves showing the nonexistence of points on some elliptic curves defined over C(x), and extends the methods of [1].     

On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them

A full-rank under-determined linear system of equations Ax = b has in general infinitely many possible solutions. In recent years there is a growing interest in the sparsest solution of this equation—the one with the fewest non-zero entries, measured by ∥x∥₀. Such solutions find applications in signal and image processing, where the topic is typically referred to as “sparse representation”. Considering the columns of A as atoms of a dictionary, it is assumed that a given signal b is a linear composition of few such atoms. Recent work established that if the desired solution x is sparse enough, uniqueness of such a result is guaranteed. Also, pursuit algorithms, approximation solvers for the above problem, are guaranteed to succeed in finding this solution.Armed with these recent results, the problem can be reversed, and formed as an implied matrix factorization problem: Given a set of vectors {b_i}, known to emerge from such sparse constructions, Ax_i = b_i, with sufficiently sparse representations x_i, we seek the matrix A. In this paper we present both theoretical and algorithmic studies of this problem. We establish the uniqueness of the dictionary A, depending on the quantity and nature of the set {b_i}, and the sparsity of {x_i}. We also describe a recently developed algorithm, the K-SVD, that practically find the matrix A, in a manner similar to the K-Means algorithm. Finally, we demonstrate this algorithm on several stylized applications in image processing.     

Some extensions of Carlitz on cyclic sums and generating functions

Recently, the author (Proc. Amer. Math. Soc., 57 1976, 271–275) derived two theorems involving double series, which gave as a consequence new and known generating functions for the Jacobi polynomial. The method of proof differed from that of previous workers. Using an extension of this procedure, we present in this paper two theorems for double and m-dimensional series which generalize our previous work. These formulas also yield new generating functions for the Jacobi polynomial and extend some formulas of Carlitz (Boll. U.M.I. (3), 16 1961, 150–155) and others. A feature of this work is the inclusion of the Jacobi polynomial within the framework of m-dimensional cyclic sums, thus generalizing a main result of Carlitz (SIAM Rev., 6 1964, 20–30).     

On linear forms with algebraic coefficients and diophantine equations

In my paper, [Man. Math.18 (1976), Satz 1.1] I proved a result on simultaneous diophantine inequalities for p-adic linear forms with algebraic coefficients. In this paper I shall generalize this result and give a necessary and sufficient criterion for the estimation of a product of complex and p-adic linear forms with algebraic coefficients, implying a theorem of Schmidt, [Math. Ann.191 (1971), Satz 1]. Using this estimate I shall obtain the p-adic generalization of Schmidt's theorems on diophantine equations of norm form type [Ann. of Math.96 (1972)].     

On a property of tan x

In a paper of Hirzebruch (Ann. of Math.60 (1954), 213–235) the following number-theoretical question occurs in a problem (Problem 5, p. 217): Determine those coefficients in the Taylor expansion of tan xwhose reciprocals are inZ. We give here the complete solution.In 1960, Adams solved Problem 5 along algebraic-topological lines so that the question about tan x was no longer important for this problem.     

The spectra of some families of digraphs

Let G be a digraph (or a graph, when seen as a symmetric digraph) with adjacency matrix A, having the eigenvalue λ with associated eigenvector v. As it is well known, the entries of v can be interpreted as charges in each vertex. Then, the linear transformation v ? Av corresponds to a natural displacement of charges, where each vertex sends a copy of its charge to its in-neighbors and absorbs a copy of the charges of its out-neighbors, so the resulting charge distribution is just λv. In this work we use this approach to derive some old and new results about the spectral characterization of G. More precisely, we show how to obtain the spectra of some families of (di)graphs, such as the partial line digraphs and the line graphs of regular or semiregular graphs.