Divisibility of matrices associated with multiplicative functions

Let S={x₁,…,x_n} be a set of n distinct positive integers. For x,y∈S and y<x, we say the y is a greatest-type divisor of x in S if y∣x and it can be deduced that z=y from y∣z,z∣x,z<x and z∈S. For x∈S, let G_S(x) denote the set of all greatest-type divisors of x in S. For any arithmetic function f, let (f(x_i,x_j)) denote the n×n matrix having f evaluated at the greatest common divisor (x_i,x_j) of x_i and x_j as its i,j-entry and let (f[x_i,x_j]) denote the n×n matrix having f evaluated at the least common multiple [x_i,x_j] of x_i and x_j as its i,j-entry. In this paper, we assume that S is a gcd-closed set and . We show that if f is a multiplicative function such that (f∗μ)(d)∈Z whenever and f(a)|f(b) whenever a|b and a,b∈S and (f(x_i,x_j)) is nonsingular, then the matrix (f(x_i,x_j)) divides the matrix (f[x_i,x_j]) in the ring M_n(Z) of n×n matrices over the integers. As a consequence, we show that (f(x_i,x_j)) divides (f[x_i,x_j]) in the ring M_n(Z) if (f∗μ)(d)∈Z whenever and f is a completely multiplicative function such that (f(x_i,x_j)) is nonsingular. This confirms a conjecture of Hong raised in 2004.     

Gersgorin variations II: On themes of Fan and Gudkov

Assume F={f₁,. . .,f_n} is a family of nonnegative functions of n−1 nonnegative variables such that, for every matrix A of order n, |a_ii|>f_i (moduli of off-diagonal entries in row i of A) for all i implies A nonsingular. We show that there is a positive vector x, depending only on F, such that for all A=(a_ij), and all i, f_i≥∑_j|a_ij|{x_j}/x_i. This improves a theorem of Ky Fan, and yields a generalization of a nonsingularity criterion of Gudkov. Dedicated to Charles A. Micchelli, in celebration of his 60th birthday and our 30 years of friendship     

A determinantal description of GCD-closed sets and k-sets

Let S={x ₁,x ₂,…,x_n } be a naturally ordered set of distinct positive integers. S is called a k-set if k= gcd(x_i ,x_j ) for x_i ≠x_j any in S. In this paper k-sets are characterized by certain conditions on the determinants of some matrices associated with S.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

On the divisibility of power LCM matrices by power GCD matrices

Let S = {x ₁, ..., x _n } be a set of n distinct positive integers and e ⩾ 1 an integer. Denote the n × n power GCD (resp. power LCM) matrix on S having the e-th power of the greatest common divisor (x _i , x _j ) (resp. the e-th power of the least common multiple [x _i , x _j ]) as the (i, j)-entry of the matrix by ((x _i , x _j ) ^e ) (resp. ([x _i , x _j ] ^e )). We call the set S an odd gcd closed (resp. odd lcm closed) set if every element in S is an odd number and (x _i , x _j ) ∈ S (resp. [x _i , x _j ] ∈ S) for all 1 ⩽ i, j ⩽ n. In studying the divisibility of the power LCM and power GCD matrices, Hong conjectured in 2004 that for any integer e ⩾ 1, the n × n power GCD matrix ((x _i , x _j ) ^e ) defined on an odd-gcd-closed (resp. odd-lcm-closed) set S divides the n × n power LCM matrix ([x _i , x _j ] ^e ) defined on S in the ring M _n (ℤ) of n × n matrices over integers. In this paper, we use Hong’s method developed in his previous papers [J. Algebra 218 (1999) 216–228; 281 (2004) 1–14, Acta Arith. 111 (2004), 165–177 and J. Number Theory 113 (2005), 1–9] to investigate Hong’s conjectures. We show that the conjectures of Hong are true for n ⩽ 3 but they are both not true for n ⩾ 4. Research is partially supported by Program for New Century Excellent Talents in University, by SRF for ROCS, SEM, China and by the Lady Davis Fellowship at the Technion, Israel Research is partially supported by a UGC (HK) grant 2160210 (2003/05).     

A Regularization Procedure for Σn−i=1fi(zj)xi = g(zj), ( j = 1, 2, …, n)

A regularization procedure for linear systems of the type fi(z_j)x_i = g(zj), (j = 1, 2, …, n) is presented, which is particularly useful in the case when z₁, z₂, …, z_n are close to each other. The associated numerical algorithm was tested on several examples for which analytic solutions do exist and was found to yield highly accurate results.     

Analytic properties of conditional curvatures of convex hypersurfaces and the dirichlet problem for the Monge-Ampère equation

The existence and uniqueness of a surface with given geometric characteristics is one of the important topical problems of global differential geometry. By stating this problem in terms of analysis, we arrive at second-order elliptic and parabolic partial differential equations. In the present paper we consider generalized solutions of the Monge-Ampère equation ||z _ij || = ϕ(x, z, p) in Λ ⁿ , wherez = z(x ₁,...,z _n ) is a convex function,p = (p ₁,...,P _n) = (∂z/∂x ₁,...,ϖz/ϖx _n), andz _ij =ϖ ² z/ϖx _i ϖx _j. We consider the Cayley-Klein model of the space Λ ⁿ and use a method based on fixed point principle for Banach spaces. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 763–768, November, 1998.     

DNA labelled graphs with DNA computing

Let k≥2, 1≤i≤k andα≥1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; two points are connected by an arc from the first point to the second one if the i rightmost uucleotides of the first point overlap with the i leftmost nucleotides of the second one. We say that a directed graph D can be(k, i;α)-labelled if it is possible to assign a label(l_1(x),..., l_k(x))to each point x of D such that l_j(x)∈{0,...,a-1}for any j∈{1,...,k}and(x,y)∈E(D)if and only if(l_k-i 1(x),..., l_k(x))=(l_1(y),..., l_i(y)). By the biological background, a directed graph is a DNA labelled graph if there exist two integers k, i such that it is(k, i; 4)-labelled. In this paper, a detailed discussion of DNA labelled graphs is given. Firstly, we study the relationship between DNA labelled graphs and some existing directed graph classes. Secondly, it is shown that for any DNA labelled graph, there exists a positive integer i such that it is(2i, i; 4)-labelled. Furthermore, the smallest i is determined, and a polynomial-time algorithm is introduced to give a(2i, i; 4)-labelling for a given DNA labelled graph. Finally, a DNA algorithm is given to find all paths from one given point to another in a(2i, i; 4)-labelled directed graph.     

Pascal k-elminated functional matrix and eulerian numbers

In this paper we shall first introduce the Pascal k-eliminated functional matrices P_n,k [x y z] and CP_n,k [x y z]. Then, using these matrices we obtain several important combinatorial identities. Finally, using the matrix inversion of P_n,k [x y z] and CP_n,k [x y z], we derive an interesting formula for Eulerian numbers [7]     

Zeros of linear recurrence sequences

Let be an exponential polynomial over a field of zero characteristic. Assume that for each pair i,j with i≠j, α _i /α _j is not a root of unity. Define . We introduce a partition of into subsets (1≤i≤m), which induces a decomposition of f into , so that, for 1≤i≤m, , while for , the number either is transcendental or else is algebraic with not too small a height. Then we show that for all but at most solutions x∈ℤ of f(x)= 0, we have

Type II Matrices of Size Five

. A type II matrix is an n×n matrix W with non-zero entries W _i,j which satisfies , i, j=1, …, n. Two type II matrices W, W′ are said to be equivalent if W′=P ₁Δ₁ WΔ₂ P ₂ holds for some permutation matrices P ₁, P ₂ and for some non-singular diagonal matrices Δ₁, Δ₂. In the present paper, it is shown that there are up to equivalence exactly three type II matrices in M ₅(C). Received: August 15, 1996 Revised: May 16, 1997     

Classification of the centers, of their cyclicity and isochronicity for two classes of generalized quintic polynomial differential systems

In this paper we classify the centers localized at the origin of coordinates, the cyclicity of their Hopf bifurcation and their isochronicity for the polynomial differential systems in \mathbbR²{\mathbb{R}^2} of degree d that in complex notation z = x + i y can be written as

The Number of Permutation Polynomials of a Given Degree Over a Finite Field

We relate the number of permutation polynomials in F_q[x] of degree d≤q−2 to the solutions (x₁,x₂,…,x_q) of a system of linear equations over F_q, with the added restriction that x_i≠0 and x_i≠x_j whenever i≠j. Using this we find an expression for the number of permutation polynomials of degree p−2 in F_p[x] in terms of the permanent of a Vandermonde matrix whose entries are the primitive pth roots of unity. This leads to nontrivial bounds for the number of such permutation polynomials. We provide numerical examples to illustrate our method and indicate how our results can be generalised to polynomials of other degrees.     

On a metric generalization of ramsey’s theorem

An increasing sequence of realsx=〈x _i :i<ω〉 is simple if all “gaps”x _i +1−x _i are different. Two simple sequencesx andy are distance similar ifx _i +1−x _i <x _j +1−x _j if and only ify _i +1−y _i <y _j +1−y _j for alli andj. Given any bounded simple sequencex and any coloring of the pairs of rational numbers by a finite number of colors, we prove that there is a sequencey distance similar tox all of whose pairs are of the same color. We also consider many related problems and generalizations. Partially supported by OTKA-4269. Partially supported by NSF grant STC-91-19999. Partially supported by OTKA-T-020914, NSF grant CCR-9424398 and PSC-CUNY Research Award 663472.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent

Regard an element of the set of ranked discrete distributions Δ := {(x ₁, x ₂,…):x ₁≥x ₂≥…≥ 0, ∑ _i x _i = 1} as a fragmentation of unit mass into clusters of masses x _i . The additive coalescent is the Δ-valued Markov process in which pairs of clusters of masses {x _i , x _j } merge into a cluster of mass x _i + x _j at rate x _i + x _j . Aldous and Pitman (1998) showed that a version of this process starting from time −∞ with infinitesimally small clusters can be constructed from the Brownian continuum random tree of Aldous (1991, 1993) by Poisson splitting along the skeleton of the tree. In this paper it is shown that the general such process may be constructed analogously from a new family of inhomogeneous continuum random trees. Received: 6 October 1998 / Revised version: 16 May 1999 / Published online: 20 October 2000     

On the blow-up of solutions to anisotropic parabolic equations with variable nonlinearity

The aim of this paper is to establish sufficient conditions of the finite time blow-up in solutions of the homogeneous Dirichlet problem for the anisotropic parabolic equations with variable nonlinearity $ u_t = \sum\nolimits_{i = 1}^n {D_i (a_i (x,t)|D_i u|^{p^i (x) - 2} D_i u) + \sum\nolimits_{i = 1}^K {b_i (x,t)|u|^{\sigma _i (x,t) - 2} u} } $ u_t = \sum\nolimits_{i = 1}^n {D_i (a_i (x,t)|D_i u|^{p^i (x) - 2} D_i u) + \sum\nolimits_{i = 1}^K {b_i (x,t)|u|^{\sigma _i (x,t) - 2} u} } . Two different cases are studied. In the first case a _i ≡ a _i (x), p _i ≡ 2, σ _i ≡ σ _i (x, t), and b _i (x, t) ≥ 0. We show that in this case every solution corresponding to a “large” initial function blows up in finite time if there exists at least one j for which min σ _j (x, t) > 2 and either b _j > 0, or b _j (x, t) ≥ 0 and Σ_π b _j ^−ρ(t)(x, t) dx < ∞ with some σ(t) > 0 depending on σ _j . In the case of the quasilinear equation with the exponents p _i and σ _i depending only on x, we show that the solutions may blow up if min σ _i ≥ max p _i , b _i ≥ 0, and there exists at least one j for which min σ _j > max p _j and b _j > 0. We extend these results to a semilinear equation with nonlocal forcing terms and quasilinear equations which combine the absorption (b _i ≤ 0) and reaction terms.     

The Relative Brauer Group of an Affine Double Plane

We study algebra classes and divisor classes on a normal affine surface of the form z ² = f(x, y). The affine coordinate ring is T = k[x, y, z]/(z ² ? f), and if R = k[x, y][f ^?1] and S = R[z]/(z ² ? f), then S is a quadratic Galois extension of R. If the Galois group is G, we show that the natural map H¹(G, Cl(T)) → H¹(G, Pic(S)) factors through the relative Brauer group B(S/R) and that all of the maps are onto. Sufficient conditions are given for H¹(G, Cl(T)) to be isomorphic to B(S/R). The groups and maps are computed for several examples.     

Commutative Rings Whose Cozero-Divisor Graphs are Unicyclic or of Bounded Degree

Let R be a commutative ring with unity. The cozero-divisor graph of R, denoted by Γ′(R), is a graph with vertex set W*(R), where W*(R) is the set of all nonzero and nonunit elements of R, and two distinct vertices a and b are adjacent if and only if a ? Rb and b ? Ra, where Rc is the ideal generated by the element c in R. Recently, it has been proved that for every nonlocal finite ring R, Γ′(R) is a unicyclic graph if and only if R ? ?₂ × ?₄, ?₃ × ?₃, ?₂ × ?₂[x]/(x ²). We generalize the aforementioned result by showing that for every commutative ring R, Γ′(R) is a unicyclic graph if and only if R ? ?₂ × ?₄, ?₃ × ?₃, ?₂ × ?₂[x]/(x ²), ?₂[x, y]/(x, y)², ?₄[x]/(2x, x ²). We prove that for every positive integer Δ, the set of all commutative nonlocal rings with maximum degree at most Δ is finite. Also, we classify all rings whose cozero-divisor graph has maximum degree 3. Among other results, it is shown that for every commutative ring R, gr(Γ′(R)) ∈ {3, 4, ∞}.     

Representations for partially exchangeable arrays of random variables

Consider an array of random variables (X_i,j), 1 ≤ i,j < ∞, such that permutations of rows or of columns do not alter the distribution of the array. We show that such an array may be represented as functions f(α, ξ_i, η_j, λ_i,j) of underlying i.i.d, random variables. This result may be useful in characterizing arrays with additional structure. For example, we characterize random matrices whose distribution is invariant under orthogonal rotation, confirming a conjecture of Dawid.