Matrix extensions of Liouville-Dirichlet-type integrals

The Dirichlet integral provides a formula for the volume over the k-dimensional simplex ω={x₁,…,x_k: x_i?0, i=1,…,k, s?∑^k₁x_i?T}. This integral was extended by Liouville. The present paper provides a matrix analog where now the region becomes $\text{Ω={V}{}_1\text{,…,V}{}_{\mathrm{k}}\text{: V}{}_{\mathrm{i}}\text{>0, i=1,…,k, 0?∑V}{}_{\mathrm{i}}\text{?t}}$, where now each V_i is a p×p symmetric matrix and A?B means that A?B is positive semidefinite.     

On 2-factors with cycles containing specified vertices in a bipartite graph

Let k≥1 be an integer and G=(V ₁,V ₂;E) a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+2. Our result is as follows: If $d(x)+d(y)\geq \lceil\frac{4n+k}{3}\rceil$ for any nonadjacent vertices x∈V ₁ and y∈V ₂, then for any k distinct vertices z ₁,…,z _k , G contains a 2-factor with k+1 cycles C ₁,…,C _k+1 such that z _i ∈V(C _i ) and l(C _i )=4 for each i∈{1,…,k}.     

Elasticity of factorizations in R 0 + X R1 + … + X lRl [X]

For an atomic domain R the elasticity ρ(R) is defined by ρ(R) = sup{m/n ¦ u₁ … u _m = v ₁ … v_n where u_i, v_i ∈ R are irreducible}. Let R ₀ ? … ? R _l be an ascending chain of domains which are finitely generated over ? and assume that R _l is integral over R ₀. Let X be an indeterminate. In this paper we characterize all domains D of the form D = R ₀ + XR₁ + … + X^lR_l[X] whose elasticity ρ(D) is finite.     

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.     

Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph

The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with x∈V ₁ and y∈V ₂, then, for any k independent edges e ₁,…,e _k of G, G contains k vertex-disjoint quadrilaterals C ₁,…,C _k such that e _i ∈E(C _i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V ₁|=|V ₂|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C ₁,…,C _k containing specified edges of G.     

On the irreducibility of multivariate subresultants

Let P₁,…,P_n be generic homogeneous polynomials in n variables of degrees d₁,…,d_n respectively. We prove that if ν is an integer satisfying ∑_i=1ⁿd_i?n+1?min{d_i}<ν, then all multivariate subresultants associated to the family P₁,…,P_n in degree ν are irreducible. We show that the lower bound is sharp. As a byproduct, we get a formula for computing the residual resultant of $\text{ρ?ν+n?1}\text{n?1}$ smooth isolated points in $\text{P}{}^{\mathrm{<mspace\; sp="0.2"\; width="2px"\; linebreak="nobreak"\; is="true"></mspace><mtext>n?1</mtext>}}\text{.}$To cite this article: L. Busé, C. D'Andrea, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Nonlinear Least Squares in ℝ N

Recent research and new paradigms in mathematics, engineering, and science assume nonlinear signal models of the form ?=∪ _i∈I V _i consisting of a union of subspaces V _i instead of a single subspace ?=V. These models have been used in sampling and reconstruction of signals with finite rate of innovation, the Generalized Principle Component Analysis and the subspace segmentation problem in computer vision, and problems related to sparsity, compressed sensing, and dictionary design. In this paper, we develop an algorithm that searches for the best nonlinear model of the form ?=∪ _i=1 ^l V _i ?? ^N that is optimally compatible with a set of observations ?={f ₁,…,f _m }?? ^N . When l=1 this becomes the classical least squares optimization. Thus, this problem is a nonlinear version of the least squares problem. We test our algorithm on synthetic data as well as images.     

Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

On the representation of integers by p-adic diagonal forms

Let p be an odd prime, let d be a positive integer such that (d,p?1)=1, let r denote the p-adic valuation of d and let m=1+3+3²+…+3^r. It is shown that for every p-adic integer n the equation Σ_i=1^mX_i^d=n has a nontrivial p-adic solution. It is also shown that for all p-adic units a₁, a₂, a₃, a₄ and all p-adic integers n the equation Σ_i=1⁴a_iX_i^p=n has a nontrivial p-adic solution. A corollary to each of these results is that every p-adic integer is a sum of four pth powers of p-adic integers.     

On the structure of Poincaré-Lyapunov constants for the weak focus of polynomial vector fields

In this paper generalized Poincaré-Lyapunov constants V_i, i = 1, 2,…, are defined and an explicit formula is given for the Lyapunov functions. It is shown that V_i is determined modulo V₁,…, V_{i ? 1}. This is used for the investigation and creation of limit cycles.     

Richardson's iteration for nonsymmetric matrices

To solve the linear N×N system (1) Ax=a for any nonsingular matrix A, Richardson's iteration (2) x_j+1=x_j-α_j(Ax_j-a), j=1,2,…,n, which is applied in a cyclic manner with cycle length n is investigated, where the α_j are free parameters. The objective is to minimize the error |x_n+1-x|, where x is the solution of (1). If the spectrum of A is known to lie in a compact set S, one is led to the Chebyshev-type approximation problem (3) min_p-1∈Vnmax_z∈S|p(z)|, where V_n is the linear span of z,z²,…,zⁿ. If p solves (3), then the reciprocals of the zeros of p are optimal iteration parameters α_j. It is shown that for a real problem (1) the iteration (2) can be carried out with real arithmetic alone, even when there are complex α_j. The stationary case n=1 is solved completely, i.e., for all compact sets S the problem (3) is solved explicitly. As a consequence, the converging stationary iteration processes can be characterized. For arbitrary closed disks S the problem (3) can be solved for all n∈$\text{N}$, and a simple proof is provided. The lemniscates associated with S are introduced. They appear as an important tool for studying the stability of the iteration (2).     

The chromatic numbers of random hypergraphs

For a pair of integers 1≤γ<r, the γ-chromatic number of an r-uniform hypergraph H=(V, E) is the minimal k, for which there exists a partition of V into subsets T₁,…,T_k such that |e∩T_i|≤γ for every e∈E. In this paper we determine the asymptotic behavior of the γ-chromatic number of the random r-uniform hypergraph H_r(n, p) for all possible values of γ and for all values of p down to p=Θ(n^−r+1). © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 381–403, 1998     

Non-simply connected copes

Let (W⁴,?W⁴) be a 4-manifold. Let f₁,f₂,…,f_k:(D²,?D²)→ (W⁴,?W⁴) be transverse immersions that have spherical duals $\text{α}{}_1\text{,α}{}_2\text{,…,α}{}_{\mathrm{k}}\text{:S}{}^2\text{→}\text{W}\text{?}$. Then there are open disjoint subsets V₁, V₂,…,V_k of W, such that for each 1?i?k, (a) ?V_i=V₁∩?W and ?V_i is an open regular neighborhood of f_i(?D²) in ?W, and (b) (V_i,?V_i,f_i(?D²)) is proper homotopy equivalent to (M, ?M, d)—a standard object in which d bounds an embedded flat disk. If we could get a homeomorphism instead of a proper homotopy equivalence, then we would be able to prove a 5-dimensional s-cobordism theorem.     

The Kernel of the Average Sylow Multiplicity Character and the Solvable Radical

Let G be a finite group, and let p ₁,…, p _m be the distinct prime divisors of |G|. Given a sequence 𝒫 =P ₁,…, P _m , where P _i is a Sylow p _i -subgroup of G, and g ∈ G, denote by m _𝒫(g) the number of factorizations g = g ₁…g _m such that g _i  ∈ P _i . Previously, it was shown that the properly normalized average of m _𝒫 over all 𝒫 is a complex character over G termed the Average Sylow Multiplicity Character. The present article identifies the kernel of this character as the subgroup of G consisting of all g ∈ G such that m _𝒫(gx) = m _𝒫(x) for all 𝒫 and all x ∈ G. This result implies a close connection between the kernel and the solvable radical of G.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

On orthogonal matrices with constant diagonal

In connection with the problem of finding the best projections of k-dimensional spaces embedded in n-dimensional spaces Hermann König asked: Given m∈$\text{R}$ and n∈$\text{N}$, are there n×n matrices C=(c_ij), i, j=1,…,n, such that c_ii=m for all i, |c_ij|=1 for i≠j, and C²=(m²+n?1)I_n? König was especially interested in symmetric C, and we find some families of matrices satisfying this condition. We also find some families of matrices satisfying the less restrictive condition CC^T=(m²+n?1)I_n.     

Estimating functions of canonical correlation coefficients

Let ρ²₁,…,ρ²_p be the squares of the population canonical correlation coefficients from a normal distribution. This paper is concerned with the estimation of the parameters δ₁,…,δ_p, where $\text{δ}{}_{\mathrm{i}}\text{=}\text{ρ}{}^2{}_{\mathrm{i}}\text{(1 ? ρ}{}^2{}_{\mathrm{i}}\text{)}$, i = 1,…,p, in a decision theoretic way. The approach taken is to estimate a parameter matrix Δ whose eigenvalues are δ₁,…,δ_p, given a random matrix F whose eigenvalues have the same distribution as $\text{r}{}^2{}_{\mathrm{i}}\text{(1 ? r}{}^2{}_{\mathrm{i}}\text{)}$, i = 1,…,p, where r₁,…,r_p are the sample canonical correlation coefficients.     

On the multiplicative structure of odd perfect numbers

Starting with Euler's theorem that any odd perfect number n has the form n = p^ep_i^2e_i … p_k^2e_k, where p, p₁,…,p_k are distinct odd primes and p ≡ e ≡ 1 (mod 4), we show that extensive subsets of these numbers (so described) can be eliminated from consideration. A typical result says: if p^e, p_i^2e_i,…,p_r^2e_r are all of the prime-power divisors of such an n with p ≡ p_i ≡ 1 (mod 4), then the ordered set {e₁,…,e_r} contains an even number or odd number of odd numbers according as e ≡ pore ≡ p (mod 8).