Equivalence constants for certain matrix norms II

We give an almost complete solution of a problem posed by Klaus and Li [A.-L. Klaus, C.-K. Li, Isometries for the vector (p, q) norm and the induced (p, q) norm, Linear and Multilinear Algebra 38 (1995) 315–332]. Klaus and Li’s problem, which arose during their investigations of isometries, was to relate the Frobenius (or Hilbert–Schmidt) norm of a matrix to various operator norms of that matrix. Our methods are based on earlier work of Feng [B.Q. Feng, Equivalence constants for certain matrix norms, Linear Algebra Appl. 374 (2003) 247–253] and Tonge [A. Tonge, Equivalence constants for matrix norms: a problem of Goldberg, Linear Algebra Appl. 306 (2000) 1–13], but introduce as a new ingredient some techniques developed by Hardy and Littlewood [G.H. Hardy, J.E. Littlewood, Bilinear forms bounded in space [p, q], Quart. J. Math. (Oxford) 5 (1934) 241–254].     

Linear circulant matricesover a finite field

Rings of polynomials R_N = Z_p[x]/x^N − 1 which are isomorphic to Z_P^N are studied, where p is prime and N is an integer. If I is an ideal in R_N, the code K whose vectors constitute the isomorphic image of I is a linear cyclic code. If I is a principle ideal and K contains only the trivial cycle 0 and one nontrivial cycle of maximal least period N, then the code words of K/ 0 obtained by removing the zero vector can be arranged in an order which constitutes a linear circulant matrix, C. The distribution of the elements of C is such that it forms the cyclic core of a generalized Hadamard matrix over the additive group of Z_Pp. A necessary condition that C = K/ 0 be linear circulant is that for each row vector v of C, the periodic infinite sequence a(v) produced by cycling the elements of v be period invariant under an arbitrary permutation of the elements of the first period. The necessary and sufficient condition that C be linear circulant is that the dual ideal generated by the parity check polynomial h(χ) of K be maximal (a nontrivial, prime ideal of R_N), with N = p^k − 1 and k = deg (h(χ)).     

The location of zeros of polynomials

Let A be a complex n×n matrix. p an equilibrated vectonal norm and x(A) the spectrial abscissa of A. Then, it is known [5] x(A)≤x(γ_p(A)) where γp is the matricial logarithmic derivative induced by p. We will make use of the above inequality to obtain regions in the plane which contain the zeros of complex polynomials.     

A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree

Given an edge-weighted tree T and an integer p1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2−2/(p+1))-approximation algorithm which runs in O(p^p−1n^p−1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p−1)!·n) time.     

On the maximum density of 0–1 matrices with no forbidden rectangles

This note provides bounds for the maximal number of ones allowed in an N × N 0–1 matrix, N=2ⁿ, in which there are no ‘forbidden rectangles’ of a special type.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Loopless generation of up–down permutations

An up–down permutation P=(p₁,p₂,…,p_n) is a permutation of the integers 1 to n which satisfies constraints specified by a sequence C=(c₁,c₂,…,c_n−1) of U's and D's of length n−1. If c_i is U then p_i<p_i+1 otherwise p_i−1>p_i. A loopless algorithm is developed for generating all the up–down permutations satisfying any sequence C. Ranking and unranking algorithms are discussed.     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.     

On neighborhood condition for graphs to have [a,b]-factors

Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |N_G(x₁)N_G(x₂)N_G(x_k)|an/(a+b) for any independent subset {x₁,x₂,…,x_k} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.     

Wiener–Hopf factorization for a group of exponentials of nilpotent matrices

A complete study of the generalized factorization for a group of 2×2 matrix functions of the form G=I+γN, where , I denotes the 2×2 identity matrix and N represents a rational nilpotent matrix function, is presented. A closely related class involving the same matrix N is also studied. The canonical and non-canonical factorizations are considered and explicit formulas are obtained for the partial indices and the factors in such factorizations. It is shown in particular that only one of the columns in the factors needs to be determined, as a solution to a homogeneous linear Riemann–Hilbert problem, the other column being expressed in terms of the first. Necessary and sufficient conditions for existence of a canonical factorization within the same class are established, as well as explicit formulas for the factors in this case.     

New constructions of divisible designs

A construction is given for a (p^2a(p+1),p²,p^2a+1(p+1),p^2a+1,p^2a(p+1)) (p a prime) divisible difference set in the group H×Z²_pa+1 where H is any abelian group of order p+1. This can be used to generate a symmetric semi-regular divisible design; this is a new set of parameters for λ₁≠0, and those are fairly rare. We also give a construction for a (p^a−1+p^a−2+…+p+2,p^a+2, p^a(p^a+p^a−1+…+p+1), p^a(p^a−1+…+p+1), p^a−1(p^a+…+p²+2)) divisible difference set in the group H×Z_p2×Z^a_p. This is another new set of parameters, and it corresponds to a symmetric regular divisible design. For p=2, these parameters have λ₁=λ₂, and this corresponds to the parameters for the ordinary Menon difference sets.     

The thermal equilibrium state of semiconductor devices

The thermal equilibrium state of two oppositely charged gases confined to a bounded domain , m = 1,2 or m = 3, is entirely described by the gases' particle densities p, n minimizing the total energy (p, n). it is shown that for given P, N > 0 the energy functional admits a unique minimizer in {(p, n) ε L²(Ω) x L ²(Ω) : p, n ≥ 0, _Ωp = P, _Ωn = N} and that p, n ε C(Ω) ∩ L^∞(Ω).

The analysis is applied to the hydrodynamic semiconductor device equations. These equations in general possess more than one thermal equilibrium solution, but only the unique solution of the corresponding variational problem minimizes the total energy. It is equivalent to prescribe boundary data for electrostatic potential and particle densities satisfying the usual compatibility relations and to prescribe V^e and P, N for the variational problem.     

Superfast algorithms for Cauchy-like matrix computations and extensions

An effective algorithm of [M. Morf, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974; in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954–959; R.R. Bitmead and B.D.O. Anderson, Linear Algebra Appl. 34 (1980) 103–116] computes the solution to a strongly nonsingular Toeplitz or Toeplitz-like linear system , a short displacement generator for the inverse T⁻¹ of T, and det T. We extend this algorithm to the similar computations with n×n Cauchy and Cauchy-like matrices. Recursive triangular factorization of such a matrix can be computed by our algorithm at the cost of executing O(nr²log³ n) arithmetic operations, where r is the scaling rank of the input Cauchy-like matrix C (r=1 if C is a Cauchy matrix). Consequently, the same cost bound applies to the computation of the determinant of C, a short scaling generator of C⁻¹, and the solution to a nonsingular linear system of n equations with such a matrix C. (Our algorithm does not use the reduction to Toeplitz-like computations.) We also relax the assumptions of strong nonsingularity and even nonsingularity of the input not only for the computations in the field of complex or real numbers, but even, where the algorithm runs in an arbitrary field. We achieve this by using randomization, and we also show a certain improvement of the respective algorithm by Kaltofen for Toeplitz-like computations in an arbitrary field. Our subject has close correlation to rational tangential (matrix) interpolation under passivity condition (e.g., to Nevanlinna–Pick tangential interpolation problems) and has further impact on the decoding of algebraic codes.     

A note on the stationarity of a threshold first-order bilinear process

In the present note we study the threshold first-order bilinear model

X(t)=aX(t−1)+(b₁1_{X(t−1)<c}+b₂1_{X(t−1)c})X(t−1)e(t−1)+e(t), tεN

where {e(t), tεN} is a sequence of i.i.d. absolutely continuous random variables, X(0) is a given random variable and a, b₁, b₂ and c are real numbers. Under suitable conditions on the coefficients and lower semicontinuity of the densities of the noise sequence, we provide sufficient conditions for the existence of a stationary solution process to the present model and of its finite moments of order p.     

First passage time for some stationary processes

For a 1-dependent stationary sequence {X_n} we first show that if u satisfies p₁=p₁(u)=P(X₁>u)0.025 and n>3 is such that 88np₁³1, then

P{max(X₁,…,X_n)u}=ν·μⁿ+O{p₁³(88n(1+124np₁³)+561)}, n>3,

where

ν=1−p₂+2p₃−3p₄+p₁²+6p₂²−6p₁p₂,μ=(1+p₁−p₂+p₃−p₄+2p₁²+3p₂²−5p₁p₂)⁻¹

with

p_k=p_k(u)=P{min(X₁,…,X_k)>u}, k1

and

|O(x)||x|.

From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Y_s}, a similar, in terms of P{max_0skTY_s<u}, k=1,2 formula for P{max_0stY_su}, t>3T and apply this formula to the process Y_s=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.     

On the number of irreducible coverings by edges of complete bipartite graphs

In this paper it is proved that the exponential generating function of the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite graphs K_p,q equals exp(xe^y + ye^x − x − y − xy) − 1.     

On meromorphic solutions of a certain type of nonlinear differential equations

We consider transcendental meromorphic solutions with N(r,f) = S(r,f) of the following type of nonlinear differential equations:f~n + Pn-2(f) = p1(z)e~(α1(z)) +p2(z)e~(α2(z)),where n≥ 2 is an integer, Pn-2(f) is a differential polynomial in f of degree not greater than n-2 with small functions of f as its coefficients, p1(z), p2(z) are nonzero small functions of f, and α1(z), α2(z)are nonconstant entire functions. In particular, we give out the conditions for ensuring the existence of meromorphic solutions and their possible forms of the above equation. Our results extend and improve some known results obtained most recently.     

Commutativity preserving linear maps and Lie automorphisms of strictly triangular matrix space

In this paper we classify linear maps preserving commutativity in both directions on the space N(F) of strictly upper triangular (n+1)×(n+1) matrices over a field F. We show that for n3 a linear map on N(F) preserves commutativity in both directions if and only if =^′+f where ^′ is a product of standard maps on N(F) and f is a linear map of N(F) into its center.     

Convex 4-valent polytopes

Let {p_k}_k≥3 be a sequence of nonnegative integers which satisfies 8 + Σ_k≥3 (k-4) p_k = 0 and p₄ ≥ p₃. Then there is a convex 4-valent polytope P in E³ such that P has exactly p_k k-gons as faces. The inequality p₄ ≥ p₃ is the best possible in the sense that for c < 1 there exist sequences that are not 4-realizable that satisfy both 8 + Σ_{k ≥3} (k - 4) p_k = 0 and p₄ > cp₃. When Σ_{k ≥ 5} p_k ≠ 1, one can make the stronger statement that the sequence {p_k} is 4-reliazable if it satisfies 8 + Σ_{k ≥ 3} (k - 4) p_k = 0 and p₄ ≥ 2Σ_{k ≥ 5} p_k + max{k ¦ p_k ≠ 0}.     

Profile minimization on triangulated triangles

Given graph G=(V,E) on n vertices, the profile minimization problem is to find a one-to-one function f:V→{1,2,…,n} such that ∑_vV(G){f(v)−min_xN[v] f(x)} is as small as possible, where N[v]={v}{x: x is adjacent to v} is the closed neighborhood of v in G. The trangulated triangle T_l is the graph whose vertices are the triples of non-negative integers summing to l, with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two coordinates. This paper provides a polynomial time algorithm to solve the profile minimization problem for trangulated triangles T_l with side-length l.