Permanents of d-dimensional matrices

Let A = (A_i1i2…_id) be an n₁ × n₂ × · × n_d matrix over a commutative ring. The permanent of A is defined by per (A) = ∑πⁿ_1i = ₁A_iσ2(_i)σ₃(_i)…σ_d(_i), where the summation ranges over all one-to-one functions σ_k from {1,2,…, n₁} to {1,2,…, n_k}, k = 2,3,…, d. In this paper it is shown that a number of properties of permanents of 2-dimensional matrices extend to higher-dimensional matrices. In particular, permanents of nonnegative d-dimensional matrices with constant hyperplane sums are investigated. The paper concludes by introducing s-permanents, which generalize the definition above that the permanent becomes the 1-permanent, and showing that an s-permanent can always be converted into a 1-permanent.     

Spectra of principal submatrices of nonnegative matrices

Let A be an n×n nonnegative matrix with the spectrum (λ₁,λ₂,…,λ_n) and let A₁ be an m×m principal submatrix of A with the spectrum (μ₁,μ₂,…,μ_m). In this paper we present some cases where the realizability of (μ₁,μ₂,…,μ_m,ν₁,ν₂,…,ν_s) implies the realizability of (λ₁,λ₂,…,λ_n,ν₁,ν₂,…,ν_s) and consider the question whether this holds in general. In particular, we show that the list

(λ₁,λ₂,…,λ_n,-μ₁,-μ₂,…,-μ_m)     

Enumeration of sequences of given specification according to rises,falls and maxima

Letn = (a₁.a₂ … a_N) denote a sequence of integers a_i={1.2.…n}. A rise is a part a_i.a_i+1 with a_i <a_i+1: a fall is a pair with a_ia_i+1: a level is a pair with a_i = a_i+1. A maximum is a triple a_i-1.a_ia_i+1 with a_i-1?a_i.a_i?a_i+1. If e_i is the number of a_j?n witha_j = i, then [e₁…e_n] is called the specification of n. In addition, a conventional rise is counted to the left of a₁ and a conventional fall to the right of a_N: ifa₁?a₂, then a₁ is counted as a conventional maximum, similarly if a_N-1 ? a_N thena_N is a conventional maximum. Simon Newcomb's problem is to find the number of sequences n with given specification and r rises; the refined problem of determining the number of sequences of given specification with r rises and s falls has also been solved recently. The present paper is concerned with the problem of finding the number of sequences of given specification with r rises, s falls. λ levels and λ maxima. A generating function for this enumerant is obtained as the quotient of two continuants. In certain special cases this result simplifies considerably.     

Connectivity of Cartesian product graphs

Use v_i,κ_i,λ_i,δ_i to denote order, connectivity, edge-connectivity and minimum degree of a graph G_i for i=1,2, respectively. For the connectivity and the edge-connectivity of the Cartesian product graph, up to now, the best results are κ(G₁×G₂)?κ₁+κ₂ and λ(G₁×G₂)?λ₁+λ₂. This paper improves these results by proving that κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁} and λ(G₁×G₂)=min{δ₁+δ₂,λ₁v₂,λ₂v₁} if G₁ and G₂ are connected undirected graphs; κ(G₁×G₂)?min{κ₁+δ₂,κ₂+δ₁,2κ₁+κ₂,2κ₂+κ₁} if G₁ and G₂ are strongly connected digraphs. These results are also generalized to the Cartesian products of connected graphs and n strongly connected digraphs, respectively.     

An explicit expression for the cost of a class of Huffman trees

Let T_n denote a binary tree with n terminal nodes V={υ₁,…,υ_n} and let l_i denote the path length from the root to υ_i. Consider a set of nonnegative numbers W={w₁,…,w_n} and for a permutation π of {1,…,n} to {1,…,n}, associate the weight w_i to the node υ_π(i). The cost of T_n is defined as C(T_n∣W)=Min_π∑ⁿ_i=1w_il_π(i).A Huffman tree H_n is a binary tree which minimizes C(T_n∣W) over all possible T_n. In this note, we give an explicit expression for C(H_n∣W) when W assumes the form: w_i=k for i=1,…,n?m; w_i=x for i=n?m+1,…,n. This simplifies and generalizes earlier results in the literature.     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

Elementary divisors of induced transformations on symmetry classes of tensors

Let V_χ(G) denote the symmetry class of tensors over the vector space V associated with the permutation group G and irreducible character χ. Write v₁*v₂*...*v_m for the decomposable symmetrized product of the indicated vectors (m=degG). If T is a linear operator on V, let K(T) denote the associated operator on V_χ(G), i.e., K(T)v₁*v₂*...*v_m=Tv₁*Tv₂*...*Tv_m. Denote by D(T) the derivation operator D(T)v₁*v₂*...*v_m=Tv₁*v₂...*v_m+v₁*Tv₂*v₃* ...*v_m+...+v₁*v₂*...*v_m–1*Tv_m. The article concerns the elementary divisors of K(T) and D(T).     

The Ramsey number for a cycle of length six versus a clique of order eight

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let C_m denote a cycle of length m and K_n a complete graph of order n. In this paper, it is shown that R(C₆,K₈)=36.     

Automorphisms of free groups and the mapping class groups of closed compact orientable surfaces

Let N be the stabilizer of the word w = s ₁ t ₁ s ₁ ^?1 t ₁ ^?1 … s _g t _g s _g ^?1 t _g ^?1 in the group of automorphisms Aut(F _2g ) of the free group with generators ?ub;s _i, t _i?ub; _i=1,…,g . The fundamental group π₁(Σ_g) of a two-dimensional compact orientable closed surface of genus g in generators ?ub;s _i, t _i?ub; is determined by the relation w = 1. In the present paper, we find elements S _i, T _i ∈ N determining the conjugation by the generators s _i, t _i in Aut(π₁(Σ_g)). Along with an element β ∈ N, realizing the conjugation by w, they generate the kernel of the natural epimorphism of the group N on the mapping class group M _g,0 = Aut(π₁(Σ_g))/Inn(π₁(Σ_g)). We find the system of defining relations for this kernel in the generators S ₁, …, S _g, T ₁, …, T _g, α. In addition, we have found a subgroup in N isomorphic to the braid group B _g on g strings, which, under the abelianizing of the free group F _2g , is mapped onto the subgroup of the Weyl group for Sp(2g, ?) consisting of matrices that contain only 0 and 1.     

Entire solutions of certain type of differential equations II

We analyze the transcendental entire solutions of the following type of nonlinear differential equations: fn(z)+P(f)=p₁eα₁z+p₂eα₂z in the complex plane, where p₁, p₂ and α₁, α₂ are nonzero constants, and P(f) denotes a differential polynomial in f of degree at most n−1 with small functions of f as the coefficients.     

Continuity of invariant measures for families of maps

Let {τ_r} be the family of maps from [0,1] into [0,1] with properties similar to those of τ_r(x) = rx(1 ? x), 0 ≤ r ≤ 4. The limiting behaviour of orbits {τ_r^j(x)}_j^∞ = 1 is a complicated and discontinuous function of the parameter r. The stochastic approximation to the difference equation x_{n + 1} = τ_r(x_n), x_{n + 1} = τ_r(x_n) + W, where W is a fixed random variable independent of r and x_n, is considered. It is shown that this Markov process admits a unique absolutely continuous invariant measure μ_r and, furthermore, that the map r → μ_r is continuous. Such a result is important in applications, since slight changes in the shape of τ_r no longer cause discontinuous consequences in the limiting behaviour of the system.     

An ABS algorithm for a class of systems of stochastic linear equations

This paper is to explore a model of the ABS algorithms dealing with the solution of a class of systems of linear stochastic equations Aξ=η when η is a m-dimensional normal distribution. It is shown that the stepsize α _i is distributed as N(u _i ,σ _i ) (being u _i the expected value of α _i and σ _i its variance) and the approximation to the solutions ξ _i is distributed as N _n (U _i ,Σ _i ) (being U _i the expected value of ξ _i and Σ _i its variance), for this algorithm model.     

On covering a product of sets with products of their subsets

Suppose that S₁,…,S_N are collections of subsets of X₁,…,X_N, respectively, such that n_i subsets belonging to S_i, and no fewer, cover X_i for all i. the main result of this paper is that to cover X₁ x…x X_N requires no fewer than σ^N_i=1 (n_i–1) + 1 and no more than Π^N_i=1n_i subsets of the form A₁ x…x A_N, where A_i∈S₁foralli. Moreo ver, these bounds cannot be improved. Identical bounds for the spanning number of a normal product of graphs are also obtained.     

Idempotency of linear combinations of three idempotent matrices, two of which are commuting

The considerations of the present paper were inspired by Baksalary [O.M. Baksalary, Idempotency of linear combinations of three idempotent matrices, two of which are disjoint, Linear Algebra Appl. 388 (2004) 67-78] who characterized all situations in which a linear combination P=c₁P₁+c₂P₂+c₃P₃, with c_i, i=1,2,3, being nonzero complex scalars and P_i, i=1,2,3, being nonzero complex idempotent matrices such that two of them, P₁ and P₂ say, are disjoint, i.e., satisfy condition P₁P₂=0=P₂P₁, is an idempotent matrix. In the present paper, by utilizing different formalism than the one used by Baksalary, the results given in the above mentioned paper are generalized by weakening the assumption expressing the disjointness of P₁ and P₂ to the commutativity condition P₁P₂=P₂P₁.     

Hyperamarts: Conditions for regularity of continuous parameter processes

The regularity of trajectories of continuous parameter process (X_t)_t∈R+ in terms of the convergence of sequence E(X_Tn) for monotone sequences (T_n) of stopping times is investigated. The following result for the discrete parameter case generalizes the convergence theorems for closed martingales: For an adapted sequence (X_n)_1≤n≤∞ of integrable random variables, lim X_n exists and is equal to X_∞ and (X_T) is uniformly integrable over the set of all extended stopping times T, if and only if lim E(X_Tn) = E(X_∞) for every increasing sequence (T_n) of extended simple stopping times converging to ∞. By applying these discrete parameter theorems, convergence theorems about continuous parameter processes are obtained. For example, it is shown that a progressive, optionally separable process (X_t)_t∈R+ with E{X_T} < ∞ for every bounded stopping time T is right continuous if lim E(X_Tn) = E(X_T) for every bounded stopping time T and every descending sequence (T_n) of bounded stopping times converging to T. Also, Riesz decomposition of a hyperamart is obtained.     

Moments of square-integrable functions

This paper is motivated by [2], where we have given necessary and sufficient conditions for a given basis P in the space of polynomials to be orthogonal with respect to the measure ϱdφ for a certain function ϱ ϵ L₂(dφ). Let P = {p_i: i = 0, 1, …}, p₀ = 1. Then the conditions are (1) a multivariate analog of the three-term recurrence relation holds, see Section 4 for details; and (2) {q_i = ∑_{j = 0}^∞ c_ij P_j, i = 0, 1, …} is a φ-orthonormal basis in the space of polynomials for some coefficients c_ij such that ∑_{i = 0}^∞ c_i0² <-∞. This paper provides an algebraic condition (a condition on the coefficients c_i0) such that ϱ satisfies ∥p∥ <B, Bϵ (0, ∞], and has a cone-positivity property. In particular, our results imply that ϱ is nonnegative a.e. if ∑_{i = 0}^∞ c_i0² < ∞ and ∑_{jϵ Sk} c_j0 q_j defines nonnegative polynomials for certain finite sets S₁, S₂, … of integers.     

Characterization of elements of polynomials in ��S

Given the discrete space of natural numbers, we characterize the elements of polynomials evaluated on the points of ???. We establish these results by proving the characterization in a far more general setting. Let S be a discrete set which is a semigroup under two operations ? and +. Let g(z ₁,z ₂,??,z _k ) be any polynomial and p ₁,p ₂,??,p _k be elements of ??S. We provide a sufficient condition that a set A?S is a member of g(p ₁,p ₂,??,p _k ) and use it to characterize the members of g(p ₁,p ₂,??,p _k ) if each p _i is an idempotent in (??S,+).     

Criteria for embedding of spaces constructed by the method of means with arbitrary quasi-concave functional parameters

We consider a generalization ?(X₀,X₁)_p0,p1 of the method of means to arbitrary non-degenerate functional parameter. In this case non-trivial embedding ?(X₀,X₁)_p0,p1⊂ψ(X₀,X₁)_q0,q1 take place. We find necessary and sufficient condition for such embedding if 1?q₀?p₀?∞ and 1?q₁?p₁?∞ or 1?p₀?q₀?∞ and 1?p₁?q₁?∞.     

On mutually permutable products of finite groups

We say that the subgroups G ₁ and G ₂ of a group G are mutually permutable if G ₁ permutes with every subgroup of G ₂ and G ₂ permutes with every subgroup of G ₁. Let G=G ₁ G ₂…G _n be the product of its pairwise permutable subgroups G ₁,G ₂,…,G _n such that the product G _i G _j is mutually permutable. We investigate the structure of the finite group G if special properties of the factors G ₁,G ₂,…,G _n are known. Our results improve and extend some results of Asaad and Shaalan [1], Ezquerro and Soler-Escrivà [9] and Asaad and Monakhov [3].