Random A-permutations and Brownian motion

We consider a random permutation τ _n uniformly distributed over the set of all degree n permutations whose cycle lengths belong to a fixed set A (the so-called A-permutations). Let X _n (t) be the number of cycles of the random permutation τ _n whose lengths are not greater than n ^t , t ∈ [0, 1], and $l(t) = \sum\nolimits_{i \leqslant t,i \in A} {1/i,t > 0} $ . In this paper, we show that the finite-dimensional distributions of the random process $\{ Y_n (t) = (X_n (t) - l(n^t ))/\sqrt {\varrho \ln n} ,t \in [0,1]\} $ converge weakly as n → ∞ to the finite-dimensional distributions of the standard Brownian motion {W(t), t ∈ [0, 1]} in a certain class of sets A of positive asymptotic density ?.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

PCR algorithm for parallel computing the solution of the general restricted linear equations

In this paper we present a parallel algorithm for parallel computing the solution of the general restricted linear equations Ax=b,x∈T, where T is a subspace of ? ⁿ and b∈AT. By this algorithm the solution x=A _T,S ⁽²⁾ b is obtained in n(log?₂ m+log?₂(n?s+1)+7)+log?₂ m+1 steps with P=mn processors when m≥2(n?1) and with P=2n(n?1) processors otherwise.     

Row-ordering schemes for sparse givens transformations. I. bipartite graph model

Let A be an m-by-n matrix, m?n, and let P_r and P_c be permutation matrices of order m and n respectively. Suppose P_rAP_c is reduced to upper trapezoidal form $\text{(}\text{R}\text{O}\text{)}$ using Givens rotations, where R is n by n and upper triangular. The sparsity structure of R depends only on P_c. For a fixed P_c, the number of arithmetic operations required to compute R depends on P_r. In this paper, we consider row-ordering strategies which are appropriate when P_c is obtained from nested-dissection orderings of A^TA. Recently, it was shown that so-called “width-2” nested-dissection orderings of A^TA could be used to simultaneously obtain good row and column orderings for A. In this series of papers, we show that the conventional (width-1) nested-dissection orderings can also be used to induce good row orderings. In this first paper, we analyze the application of Givens rotations to a sparse matrix A using a bipartite-graph model.     

Equivalence classes of matrices over finite fields

Let F=GF(q) denote the finite field of order q, and F_mn the ring of m×n matrices over F. Let Ω be a group of permutations of F. If A,B∈F_mn, then A is equivalent to B relative to Ω if there exists ?∈Ω such that ?(a_ij) = b_ij. Formulas are given for the number of equivalence classes of a given order and for the total number of classes induced by various permutation groups. In particular, formulas are given if Ω is the symmetric group on q letters, a cyclic group, or a direct sum of cyclic groups.     

A random intersection digraph: Indegree and outdegree distributions

Let S(1),…,S(n),T(1),…,T(n) be random subsets of the set [m]={1,…,m}. We consider the random digraph D on the vertex set [n] defined as follows: the arc i→j is present in D whenever S(i)∩T(j)≠0?. Assuming that the pairs of sets (S(i),T(i)), 1≤i≤n, are independent and identically distributed, we study the in- and outdegree distributions of a typical vertex of D as n,m→∞.     

On the number of A-mappings

Suppose that $ \mathfrak{S} $ _n is the semigroup of mappings of the set of n elements into itself, A is a fixed subset of the set of natural numbers ?, and V _n (A) is the set of mappings from $ \mathfrak{S} $ _n whose contours are of sizes belonging to A. Mappings from V _n (A) are usually called A-mappings. Consider a random mapping σ _n , uniformly distributed on V n(A). Suppose that ν _n is the number of components and λ _n is the number of cyclic points of the random mapping σ _n . In this paper, for a particular class of sets A, we obtain the asymptotics of the number of elements of the set V _n (A) and prove limit theorems for the random variables ν _n and λ _n as n → ∞.     

On 4-cycles in random bipartite tournaments

We consider a random m by n bipartite tournament T_mn consisting of mn independent random arcs which have a common probability p of being directed from the m part to the n part. We determine the expected value and variance of the number of 4-cycles in T_mn and the probability that T_mn has no cycles. An asymptotic expression for this probability is also given when p = 1/2 and m and n tend to infinity.     

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.     

A central limit theorem for mixing stationary point processes

Suppose A₀ is a strictly stationary, second order point process on Z^d that is ?-mixing. The particles initially present are then continually subjected to random translations via random walks. If A_n is the point process resulting at time n, then we prove, under certain technical conditions, that the total occupation time by time n of a finite nonempty subset B of Z^d, namely, S_n(B)=Σⁿ_k=1A_k(B), is asymptotically normally distributed.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

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.     

How to stay in a set or König’s lemma for random paths

Starting at statex?X, a player selects the next statex ₁ from the collection Τ(x) of those available and then selectsx ₂ from Τ(x ₁) and so on. Suppose the object is to control the pathx ₁,x ₂, … so that everyx _i will lie in a subsetA ofX. A famous lemma of König is equivalent to the statement that if every Τ(x) is finite and if, for everyn, the player can obtain a path inA of lengthn, then the player can obtain an infinite path inA. Here paths are not necessarily deterministic and, for eachx, Τ(x) is the collection of possible probability distributions for the next state. Under mild measurability conditions, it is shown that if, for everyn, there is a random path of lengthn which lies inA with probability larger than α, then there is an infinite random path with the same property. Furthermore, the measurability and finiteness assumptions can be dropped if, in the hypothesis, the positive integersn are replaced by stop rulest. An analogous result holds when the object is to visitA infinitely many times.     

Permutation groups generated by cycles of fixed length

Combinatorial conditions on a set of cycles of fixed degree inS _n are studied, so that they generateA _n orS _n . It is shown thatA _n orS _n is so generated if and only if a graph associated with the set of cycles is connected, provided two of the cycles satisfy certain, not too restrictive, criteria. As a corollary, the minimum number of cycles of degreem ≧ 2 that generateA _n or S_n is determined.     

Simple image set of linear mappings in a max-min algebra

For a given linear mapping, determined by a square matrix A in a max-min algebra, the set S_A consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of S_A is a subset of the set of all eigenvectors of A. In the general case, there is a permutation π, such that the closure of S_A is a subset of the set of all eigenvectors permuted by π. The simple image set of the matrix square and the topological aspects of the problem are also described.     

Periodic regeneration

We consider stochastic processes Z = (Z_t)_[0,∞), on a general state space, having a certain periodic regeneration property: there is an increasing sequence of random times (S_n)^∞₀ such that the post-S_n process is conditionally independent of S₀,…,S_n given (S_n mod 1) and the conditional distribution does not depend on n. Our basic condition is that the distributions $\text{P}{}_{\mathrm{s}}\text{(A) =}\text{P}\text{(S}{}_{\mathrm{n+1}}\text{? S}{}_{\mathrm{n}}\text{∈ A|S}{}_{\mathrm{n}}\text{= s), s ∈[0, 1)}$, have a common component that is absolutely continuous w.r.t. Lebesgue measure. Then Z has the following time-homogeneous regeneration property: there exists a discrete aperiodic renewal process T = (T_n)^∞₀ such that the post-T_n process is independent of T₀,…,T_n and its distribution does not depend on n; this yields weak ergodicity. Further, the Markov chain (S_nmod 1)^∞₀ has an invariant distribution π_[0,1) and it holds that T_n+1 ? T_n has finite first moment if and only if m = ∫ m(P_s)π_[0,1)(ds) < ∞ where m(P_s) is the first moment of P_s; this yields periodic ergodicity. Also, some distributional properties of T₀ and T_n+1 ? T_n are established leading to improved ergodic regults. Finally, a uniform key periodic renewal theorem is derived.     

On distribution by rank of bases for vector spaces of matrices over a finite field

Let F^m×n_q denote the vector space of all m×n matrices over the finite field F_q of order q, and let $\text{B}\text{=(A}{}_1\text{,A}{}_2\text{,…,A}{}_{\mathrm{mn}}\text{)}$ denote an ordered basis for F^m×n_q. If the rank of A_i is r_i,i=1,2,…,mn, then $\text{B}$ is said to have rank (r₁,r₂,…,r_mn), and the number of ordered bases of F^mxn_q with rank (r₁,r₂,…,r_mn is denoted by N_q(r₁, r₂,…,r_mn). This paper determines formulas for the numbers N_q(r₁,r₂,…,r_mn) for the case m=n=2, q arbitrary, and while some of the techniques of the paper extend to arbitrary m and n, the general formulas for the numbers N_q(r₁,r₂,…,r_mn) seem quite complicated and remain unknown. An idea on a possible computer attack which may be feasible for low values of m and n is also discussed.     

Abstract oscillation theorems for multiparameter eigenvalue problems

We prove abstract analogous of Klein's oscillation theorem by demonstrating the existence (and in some cases uniqueness) of eigenpairs with a given index for the multiparameter problem $\text{T}{}_{\mathrm{m}}\text{x}{}_{\mathrm{m}}\text{=}\text{∑}\text{n = 1}\text{k}\text{λ}{}_{\mathrm{n}}\text{V}{}_{\mathrm{mn}}\text{x}{}_{\mathrm{m}}$, 0 ≠ x_m?H_m, m = 1 … k. (1) Here T_m and V_mn are self-adjoint operators on Hilbert spaces H_m. The index is based on the number of negative eigenvalues of T_m ? ∑_{n = 1}^kλ_nV_mn and on the sign of the determinant δ₀ with (m, n)th entry (x_m, V_mnx_m). We assume that certain cofactors of δ₀ are positive, and we complement previous work of Sleeman on Sturm-Liouville systems, and of Binding and Browne on (1) in the case where δ₀ is positive.     

The cyclic structure of random permutations

Letα _r denote the number of cycles of length r in a random permutation, taking its values with equal probability from among the set S_n of all permutations of length n. In this paper we study the limiting behavior of linear combinations of random permutationsα ₁, ...,α _r having the form $$\zeta _{n, r} = c_{r1^{a_1 } } + ... + c_{rr} a_r $$ in the case when n, r→∞. We shall show that the class of limit distributions forξ _n,r as n, r→∞ and r In r/h→0 coincides with the class of unbounded divisible distributions. For the random variables η_n, r=α ₁+2α ₂+... rα _r, equal to the number of elements in the permutation contained in cycles of length not exceeding r, we find' limit distributions of the form r In r/n→0 and r=γ ⁿ, 0<γ<1.