On the g-circulant solutions to the matrix equation Am = λJ, II

Let g and n be positive integers and let $\text{k =}\text{n(g, n)}\text{(g}{}^{\mathrm{m}}\text{, n)}$. If θ(x) is a multiple of Σ_{i = 0}^{k ? 1}xⁱ, then the g-circulant whose Hall polynomial is equal to θ(x) satisfies the matrix equation in the title. If the g-circulant whose Hall polynomial is equal to Σ_{i = 0}^{h ? 1}xⁱ satisfies the matrix equation in the title, then h is a multiple of k.     

A system of linear equations related to the transportation problem with application to probability theory

Let P=[p_ij] be a m×n matrix and let C be the coefficient matrix of Σ_j=1ⁿ p_ijx_ij=u_i, 1≤i≤m, Σ_i=1^mp_ijx_ij=vj, 1≤j≤n. The relation between the reducibility of P and the rank of C is investigated. An application to martingale extension is given.     

On a partition problem of Frobenius

We consider the following problem, which was raised by Frobenius: Given n relatively prime positive integers, what is the largest integer M(a₁, a₂, …, a_n) omitted by the linear form Σ_i=1ⁿa_ix_i, where the x_i are variable nonnegative integers. We give the solution for certain special cases when n = 3.     

Fonctions holomorphes cliffordiennes

Let be the Clifford algebra of with a quadratic form of negative signature, D = e_i ∂/∂x_i, Δ the ordinary Laplacian. The holomorphic cliffordian functions are solutions of D Δ^mƒ = 0. We study the polynomial and singular solutions, representation integral formulas, and the foundation of the Cliffordian elliptic function theory.     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

Sequences of orthogonal vectors with a fixed norm

Let A = (a_ij) be an n × m matrix with a_ij ∈ K, a field of characteristic not 2, where Σ_i=1ⁿa_ij² = e, 1 ≤ j ≤ m, and Σ_i=1ⁿa_ija_ij′ = 0 for j ≠ j′. The question then is when is it possible to extend A, by adding columns, to obtain a matrix with orthogonal columns of the same norm. The question is answered for n ? 7 ≤ m ≤ n as well as for more general cases. Complete solutions are given for global and local fields, the answer depending on what congruence class modulo 4 n belongs to and how few squares are needed to sum to e.     

The asymptotic distribution of a goodness of fit statistic for factorial invariance

Suppose that random factor models with k factors are assumed to hold for m, p-variate populations. A model for factorial invariance has been proposed wherein the covariance or correlation matrices can be written as Σ_i = LC_iL′ + σ_i²I, where C_i is the covariance matrix of factor variables and L is a common factor loading matrix, i = 1,…, m. Also a goodness of fit statistic has been proposed for this model. The asymptotic distribution of this statistic is shown to be that of a quadratic form in normal variables. An approximation to this distribution is given and thus a test for goodness of fit is derived. The problem of dimension is considered and a numerical example is given to illustrate the results.     

Effective Fast Algorithms for Polynomial Spectral Factorization

Let p(z) be a polynomial of degree n having zeros |ξ₁|≤???≤|ξ _m |<1<|ξ _m+1|≤???≤|ξ _n |. This paper is concerned with the problem of efficiently computing the coefficients of the factors u(z)=∏ _i=1 ^m (z?ξ _i ) and l(z)=∏ _i=m+1 ⁿ (z?ξ _i ) of p(z) such that a(z)=z ^?m p(z)=(z ^?m u(z))l(z) is the spectral factorization of a(z). To perform this task the following two-stage approach is considered: first we approximate the central coefficients x _?n+1,. . .x _n?1 of the Laurent series x(z)=∑ _i=?∞ ^+∞ x _i z ⁱ satisfying x(z)a(z)=1; then we determine the entries in the first column and in the first row of the inverse of the Toeplitz matrix T=(x _i?j ) _i,j=?n+1,n?1 which provide the sought coefficients of u(z) and l(z). Two different algorithms are analyzed for the reciprocation of Laurent polynomials. One algorithm makes use of Graeffe's iteration which is quadratically convergent. Differently, the second algorithm directly employs evaluation/interpolation techniques at the roots of 1 and it is linearly convergent only. Algorithmic issues and numerical experiments are discussed.     

On Maillet determinant

For a positive integer m, let $\text{A = {1 ≤ a <}\text{m}\text{2}\text{| (a, m) = 1}}$ and let n = |A|. For an integer x, let R(x) be the least positive residue of x modulo m and if (x, m) = 1, let x′ be the inverse of x modulo m. If m is odd, then |R(ab′)|_a,b∈A = ?2^1?n(∏_χ(Σ_{a = 1}^{m ? 1}aχ(a))), where χ runs over all the odd Dirichlet characters modulo m.     

A Functional Equation Of J.A. Baker Involving Integral Means

The functional equation $$f(x)={1\over 2}\int^{x+1}_{x-1}f(t)\ dt\ \ \ {\rm for}\ \ \ x\ \in\ {\rm R}$$ has the linear functions ?(x) = a + bx (a, b ∈ ?) as trivial solutions. It is shown that there are two kinds of nontrivial solutions, (i) ?(x) = eλ_i ^x (i = 1, 2, …), where the λ_i∈ ? are the fixed points of the map z ? sinh z, and (ii) C^∞-solutions ? for which the values in the interval [?1,1] can be prescribed arbitrarily, but with the provision that ?^(j)(? 1) = ?^(j)(0) = ?^(j)(1) = 0 for all j = 0, 1, 2 …     

Analysis of a versatile multi-class delay-loss system with a superimposed Markovian arrival process

We analyze the behavior of a multi-class single-server delay-loss system Σ_i^xMAP_i/PH/1/m with a superposition of independent Markovian Arrival Processes as arrival stream and phase-type distributed service times. Considering the underlying finite Markov chain with its quasi-birth-and-death structure with two boundary sets, we derive a new representation of its steady-state vector by a linear combination of two matrix-geometric terms. Furthermore, we state efficient procedures to calculate the performance characteristics of this delay-loss system.     

On the g-circulant solutions to the matrix equation Am = λJ

Let g and n be positive integers and let a₁ = (g, n) and a_m = (g^m, n). If h ≡ 0 (mod $\text{na}{}_1\text{a}{}_{\mathrm{m}}$), then the g-circulant whose Hall polynomial is equal to Σ_i=0^h?1xⁱ satisfies the matrix equation A^m = λJ, where n is the size of matrix J.     

An application of the maximum principle to describe the layer behavior of large solutions and related problems

This work is devoted to the analysis of the asymptotic behavior of positive solutions to some problems of variable exponent reaction-diffusion equations, when the boundary condition goes to infinity (large solutions). Specifically, we deal with the equations ??u = u ^p(x), ??u = ?m(x)u?+?a(x)u ^p(x) where a(x)??? a ₀ >?0, p(x)??? 1 in ??, and ??u = e ^p(x) where p(x)??? 0 in ??. In the first two cases p is allowed to take the value 1 in a whole subdomain ${\Omega_c\subset \Omega}$ , while in the last case p can vanish in a whole subdomain ${\Omega_c\subset \Omega}$ . Special emphasis is put in the layer behavior of solutions on the interphase ?? _i :?= ??? _c ???. A similar study of the development of singularities in the solutions of several logistic equations is also performed. For example, we consider ???u = ?? m(x)u?a(x) u ^p(x) in ??, u = 0 on ???, being a(x) and p(x) as in the first problem. Positive solutions are shown to exist only when the parameter ?? lies in certain intervals: bifurcation from zero and from infinity arises when ?? approaches the boundary of those intervals. Such bifurcations together with the associated limit profiles are analyzed in detail. For the study of the layer behavior of solutions the introduction of a suitable variant of the well-known maximum principle is crucial.     

Successive approximation method for quasilinear impulsive differential equations with control

We introduce a technique to define successive approximations to solutions of the control problem with implulse actions on surfaces

where μ is a small positive parameter, ζ_i + θ_i + μτ_i(x(ζ_i), μ), x ϵ Rⁿ and Δx(θ) := x(θ+) − x(θ). A sequence of piecewise continuous functions with discontinuities of the first kind that converges to a solution of the above problem is constructed.     

A greedy algorithm for the optimal basis problem

The following problem is considered. Givenm+1 points {x _i }₀ ^m inR ⁿ which generate anm-dimensional linear manifold, construct for this manifold a maximally linearly independent basis that consists of vectors of the formx _i −x _j . This problem is present in, e.g., stable variants of the secant and interpolation methods, where it is required to approximate the Jacobian matrixf′ of a nonlinear mappingf by using values off computed atm+1 points. In this case, it is also desirable to have a combination of finite differences with maximal linear independence. As a natural measure of linear independence, we consider the hadamard condition number which is minimized to find an optimal combination ofm pairs {x _i ,x _j }. We show that the problem is not NP-hard, but can be reduced to the minimum spanning tree problem, which is solved by the greedy algorithm inO(m ²) time. The complexity of this reduction is equivalent to onem×n matrix-matrix multiplication, and according to the Coppersmith-Winograd estimate, is belowO(n ^2.376) form=n. Applications of the algorithm to interpolation methods are discussed. Part of the work was done while the author was visiting DIMACS, an NSF Science and Technology Center funded under contract STC-91-19999; DIMACS is a cooperative project of Rutgers University, Princeton University, AT&T Bell Laboratories and Bellcore, NJ, USA.     

Testing the equality of several covariance matrices with fewer observations than the dimension

For normally distributed data from the k populations with m×m covariance matrices Σ₁,…,Σ_k, we test the hypothesis H:Σ₁=?=Σ_k vs the alternative A≠H when the number of observations N_i, i=1,…,k from each population are less than or equal to the dimension m, N_i≤m, i=1,…,k. Two tests are proposed and compared with two other tests proposed in the literature. These tests, however, do not require that N_i≤m, and thus can be used in all situations, including when the likelihood ratio test is available. The asymptotic distributions of the test statistics are given, and the power compared by simulations with other test statistics proposed in the literature. The proposed tests perform well and better in several cases than the other two tests available in the literature.     

New minimax algorithm

The purpose of this paper is to suggest a new, efficient algorithm for the minmax problem $$\mathop {min}\limits_x \mathop {max}\limits_i f_i (x), x \in \Re ^n , i = 1, \ldots ,m,$$ wheref _i ,i=1,...,m, are real-valued functions defined on ? ⁿ . The problem is transformed into an equivalent inequality-constrained minimization problem, mint, s.t.f _i (x)?t≤0, for alli, i=1,...,m. The algorithm has these features: an active-set strategy with three types of constraints; the use of slack variables to handle inequality constraints; and a trust-region strategy taking advantage of the structure of the problem. Following Tapia, this problem is solved by an active set strategy which uses three types of constraints (called here nonactive, semiactive, and active). Active constraints are treated as equality constraints, while semiactive constraints are treated as inequality constraints and are assigned slack variables. This strategy helps to prevent zigzagging. Numerical results are provided.     

Polynomials arising in factoring generalized Vandermonde determinants II: A condition for monicity

In our previous paper [1], we observed that generalized Vandermonde determinants of the form V_n;ν(x₁,…,x_s) = |x_i^μk|, 1 ≤ i, k ≤ n, where the x_i are distinct points belonging to an interval [a, b] of the real line, the index n stands for the order, the sequence μ consists of ordered integers 0 ≤ μ₁ < μ₂ < … < μ_n, can be factored as a product of the classical Vandermonde determinant and a Schur function. On the other hand, we showed that when x = x_n, the resulting polynomial in x is a Schur function which can be factored as a two-factors polynomial: the first is the constant ∏_i=1ⁿ⁻¹ x_i^μ₁ times the monic polynomial ∏_i=1ⁿ⁻¹ (x − x_i, while the second is a polynomial P_M(x) of degree M = m_n−1 − n + 1. In this paper, we first present a typical application in which these factorizations arise and then we discuss a condition under which the polynomial P_M (x) is monic.     

Parameterisation algorithms for the integer linear programs in binary variables

In this paper we consider the integer programmiing problem: minimize z(x) = c · x subject to Ax?b,x binary.Roodman appended the objective function z(x) to the body of the constraints and presented a modified version of the Balas additive algorithm by which each fathomed partial solution is attributed to the constraint which caused the fathoming. Exploiting this information, he conducted (a) ranging analysis, i.e. calculating bounds on the values of the parameters which leave the original optimal solution unchanged, and (b) parameter change analysis, i.e. determining new optimal solutions (if any) for revised values of the parameters outside the ranging bounds.We extend Roodman's results and construct parametric functions of the following form. Let Σ be any parameter of c or b or A, and replace Σ by Σ(λ) = Σ + λ. Then, holding every other parameter of the program fixed, and varying λ in the set of real numbers we construct the parametric function $\text{z}{}^1\text{(Σ(λ))}$ which matches non-overlapping intervals of λ with optimal solutions. This replaces by exact bounds in the linear programming sense, the bounds underestimated by Roodman's ranging analysis. It also determines optimal solutions for any values of λ, rather than for a revised set of values. Finally some results of computational experience are presented.