A balancing strategy

Suppose x₁, x₂,…, is a sequence of vectors in R^k, 6X_n6⩽1, where 6(x₁,…,x_k)6 = max_j|x_j|. An algorithm is given for choosing a corresponding sequence ε₁, ε₂,…, of numbers, ε_n = ±1, so that 6ε₁x₁+ … +ε_nx_n6 remains small.     

An improved upper bound in the maximum dispersal problem

For integral? m?2, let x₁,…, x_m be any unit vectors in R_n, the real Euclidean space of n dimensions. We obtain an upper bound for the quantity min_i≠j|x_i-x_j| which, though not as simple, is uniformly sharper than one recently obtained by the author. The result has application to the so-called maximum-dispersal problem, an open problem recently popularized by Klee.     

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

A characterization of the multivariate normal distribution

Let X_j (j = 1,…,n) be i.i.d. random variables, and let Y′ = (Y₁,…,Y_m) and X′ = (X₁,…,X_n) be independently distributed, and A = (a_jk) be an n × n random coefficient matrix with a_jk = a_jk(Y) for j, k = 1,…,n. Consider the equation U = AX, Kingman and Graybill [Ann. Math. Statist.41 (1970)] have shown U ～ N(O,I) if and only if X ～ N(O,I). provided that certain conditions defined in terms of the a_jk are satisfied. The task of this paper is to delete the identical assumption on X₁,…,X_n and then generalize the results to the vector case. Furthermore, the condition of independence on the random components within each vector is relaxed, and also the question raised by the above authors is answered.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

Arithmetic-progression-weighted subsequence sums

Let G be an abelian group, let s be a sequence of terms s ₁, s ₂, …, s _n ∈ G not all contained in a coset of a proper subgroup of G, and let W be a sequence of n consecutive integers. Let $$W \odot S = \left\{ {w_1 s_1 + \cdots + w_n s_n :w_i a term of W,w_i \ne w_j for i \ne j} \right\},$$ which is a particular kind of weighted restricted sumset. We show that |W ⊙ S| ≥ min{|G| ? 1, n}, that W ⊙ S = G if n ≥ |G| + 1, and also characterize all sequences S of length |G| with W ⊙ S ≠ G. This result then allows us to characterize when a linear equation $$a_1 x_1 + \cdots + a_r x_r \equiv \alpha mod n,$$ where α, a ₁, …, a _r ∈ ? are given, has a solution (x ₁, …, x _r ) ∈ ? ^r modulo n with all x _i distinct modulo n. As a second simple corollary, we also show that there are maximal length minimal zero-sum sequences over a rank 2 finite abelian group $G \cong C_{n_1 } \oplus C_{n_2 }$ (where n ₁ |n ₂ and n ₂ ≥ 3) having k distinct terms, for any k ε [3, min{n ₁ + 1, exp(G)}]. Indeed, apart from a few simple restrictions, any pattern of multiplicities is realizable for such a maximal length minimal zero-sum sequence.     

Decomposable bilinear numerical radii

Let A be an n-square normal matrix over $\text{C}$, and Q_{m, n} be the set of strictly increasing integer sequences of length m chosen from 1,…, n. For α,β∈Q_{m, n} denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k∈{0,1,…,m} write z.sfnc;α∩β|=k if there exists a rearrangement of 1,…,m, say i₁,…,i_k, i_k+1,…,i_m, such that α(i_j)=β(i_j), j=1,…,k, and {α(i_k+1),…,α(i_m)};∩{β(i_k+1),…,β(i_m)}=ø. Let

be the group of n-square unitary matrices. Define the nonnegative number

$\text{?}{}_{\mathrm{k}}\text{(A)=}\text{max}\text{U∈}\textcolor{red}{}\text{|}\text{det}\text{(U}{}^1\text{AU) [α|β]|}$

, where |α∩β|=k. Theorem 1 establishes a bound for ?_k(A), 0?k<m?1, in terms of a classical variational inequality due to Fermat. Let A be positive semidefinite Hermitian, n?2m. Theorem 2 leads to an interlacing inequality which, in the case n=4, m=2, resolves in the affirmative the conjecture that

$\text{?}{}_{\mathrm{m}}\text{(A)??}{}_{\mathrm{m?1}}\text{(A)????}{}_0\text{(A)}$

.     

On the chromatic number of certain highly symmetric graphs

For 1 ⩽ k ⩽ n, let V(n, k) denote the set of n(n − 1) … (n − k + 1) sequences of k distinct elements from {1, …, n}. Let us define the graph Γ(n, k) on the vertex set V(n, k) by joining two sequences if they differ at exactly one place. We investigate the chromatic number and another related parameter of these graphs. We give a sharp answer for some infinite families, using the theory of sharply transitive permutation groups. The problems discussed are related to a question of Henkin, Monk and Tarski in mathematical logic.     

On maximal antichains containing no set and its complement

Let 1?k₁?k₂?…?k_n be integers and let S denote the set of all vectors x = (x₁, …, x_n with integral coordinates satisfying 0?x_i?k_i, i = 1,2, …, n; equivalently, S is the set of all subsets of a multiset consisting of k_i elements of type i, i = 1,2, …, n. A subset X of S is an antichain if and only if for any two vectors x and y in X the inequalities x_i?y_i, i = 1,2, …, n, do not all hold. For an arbitrary subset H of S, (i)H denotes the subset of H consisting of vectors with component sum i, i = 0, 1, 2, …, K, where K = k₁ + k₂ + …k_n. |H| denotes the number of vectors in H, and the complement of a vector x?S is (k₁-x₁, k₂-x₂, …, k_n -x_n). What is the maximal cardinality of an antichain containing no vector and its complement? The answer is obtained as a corollary of the following theorem: if X is an antichain, K is even and$\text{|(}\text{1}\text{2}\text{K)X|}$ does not exceed the number of vectors in $\text{(}\text{1}\text{2}\text{K)S}$ with first coordinate different from k₁, then

$\text{∑}\text{i=0}\text{K}\text{i≠}\text{1}\text{2}\text{K}\text{|(i)X|}\text{|(i)S|}\text{+}\text{|(}\text{1}\text{2}\text{K)X|}\text{|(}\text{1}\text{2}\text{K-1)S|}\text{?1}$

.     

Divisibility and structure constraints on automorphism groups of almost perfect 1-factorizations of

Let G be a permutation group acting on a set with N elements such that every permutation with more than m fixed points is the identity. It is easy to verify that |G| divides N(N − 1) ··· (N − m). We show that if gcd(|G|, m!) = 1, then |G| divides (N − i)(N − j) for some i and j satisfying 0 ≤ i < j ≤ m. We use this to show that any almost perfect 1-factorization of K_2n has an automorphism group whose cardinality divides (2n − i)(2n − j) for some i and j with 0 ≤ i < j ≤ 2 as long as n is odd. An almost perfect 1-factorization (or APOF) is a 1-factorization in which the union of any three distinct 1-factors is connected. This result contrasts with an example of an APOF on K₁₂ given by Cameron which has PSL(2, ℤ₁₁) as its automorphism group [with cardinality 12(11)(5)]. When n is even and the automorphism group is solvable, we show that either G acts vertex transitively and n is a power of two, or |G| divides 2n − 2^a for some integer a with 2^a dividing 2n, or else |G| divides (2n − i)(2n − j) for some i and j with 0 ≤ i < j ≤ 2. We also give a number of structure results concerning these automorphism groups. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 355–380, 1998     

On a problem of Katona on minimal completely separating systems with restrictions

Let S be a set of n elements, and k a fixed positive integer $\text{<}\text{1}\text{2}\text{n}$. Katona's problem is to determine the smallest integer m for which there exists a family $\text{A}$ = {A₁, …, A_m} of subsets of S with the following property: |_i| ? k (i = 1, …, m), and for any ordered pair x_i, x_i ∈ S (i ≠ j) there is A₁ ∈ $\text{A}$ such that x_i ∈ A₁, x_j ? A₁. It is given in this note that $\text{m = ?}\text{2n}\text{k}\text{?}\text{if}\text{1}\text{2}\text{k}{}^2\text{? 2}$.     

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 an inequality of Tosio Kato for degenerate-elliptic operators

Let Ω be a domain in Rⁿ and T = ∑_{j,k = 1}ⁿ(?_j ? ib_j(x)) a_jk(x)(?_k ? ib_k(x)), where the a_jk and the b_j are real valued functions in $\text{C}{}^1\text{(Ω)}$, and the matrix (a_jk(x)) is symmetric and positive definite for every $\text{x ? Ω}$. If T₀ is the same as T but with b_j = 0, j = 1,…, n, and if u and Tu are in $\text{L}{}_{\mathrm{<mtext>loc</mtext>}}{}^1\text{(Ω)}$, then T. Kato has established the distributional inequality $\text{T}{}_0\text{¦ u ¦ ?}\text{Re[(sign}$ ū) Tu]. He then used this result to obtain selfadjointness results for perturbed operators of the form T ? q on Rⁿ. In this paper we shall obtain Kato's inequality for degenerate-elliptic operators with real coefficients. We then use this to get selfadjointness results for second order degenerate-elliptic operators on Rⁿ.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Intersection properties of finite sets

Let X₁, X₂, …, X_m be finite sets. The present paper is concerned with the m² ? m intersection numbers |X_i ∩ X_j| (i ≠ j). We prove several theorems on families of sets with the same prescribed intersection numbers. We state here one of our conclusions that requires no further terminology. Let T₁, T₂, …, T_m be finite sets and let m ? 3. We assume that each of the elements in the set union T₁ ∪ T₂ ∪ … ∪ T_m occurs in at least two of the subsets T₁, T₂, …, T_m. We further assume that every pair of sets T_i and T_j (i ≠ j) intersect in at most one element and that for every such pair of sets there exists exactly one set T_k (k ≠ i, k ≠ j) such that T_k intersects both T_i and T_j. Then it follows that the integer m = 2m′ + 1 is odd and apart from the labeling of sets and elements there exist exactly m′ + 1 such families of sets. The unique family with the minimal number of elements is {1}, {2}, …, {m′}, {1}, {2}, …, {m′}, {1, 2, …, m′}.     

On discount residue classes

It is shown that, whenever m₁, m₂,…, m_n are natural numbers such that the pairwise greatest common divisors, d_ij=(m_i, m_j), i≠j are distinct and different from 1, then there exist integers a₁, a₂,…,a_n such that the solution sets of the congruences x≡_i (modm_i), i= 1,2,…,n are disjoint.     

Extensions of band matrices with band inverses

Let R_ij be a given set of μ_i× μ_j matrices for i, j=1,…, n and |i?j| ?m, where 0?m?n?1. Necessary and sufficient conditions are established for the existence and uniqueness of an invertible block matrix =[F_ij], i,j=1,…, n, such that F_ij=R_ij for |i?j|?m, F admits either a left or right block triangular factorization, and (F^?1)_ij=0 for |i?j|>m. The well-known conditions for an invertible block matrix to admit a block triangular factorization emerge for the particular choice m=n?1. The special case in which the given R_ij are positive definite (in an appropriate sense) is explored in detail, and an inequality which corresponds to Burg's maximal entropy inequality in the theory of covariance extension is deduced. The block Toeplitz case is also studied.     

An existence theorem for antichains

Let k₁, k₂,…, k_n be given integers, 1 ? k₁ ? k₂ ? … ? k_n, and let S be the set of vectors x = (x₁,…, x_n) with integral coefficients satisfying 0 ? x_i ? k_i, i = 1, 2, 3,…, n. A subset H of S is an antichain (or Sperner family or clutter) if and only if for each pair of distinct vectors x and y in H the inequalities x_i ? y_i, i = 1, 2,…, n, do not all hold. Let |H| denote the number of vectors in H, let K = k₁ + k₂ + … + k_n and for 0 ? l ? K let (l)H denote the subset of H consisting of vectors h = (h₁, h₂,…, h_n) which satisfy h₁ + h₂ + … + h_n = l. In this paper we show that if H is an antichain in S, then there exists an antichain H′ in S for which |(l)H′| = 0 if $\text{l <}\text{K}\text{2}$, $\text{|(}\text{K}\text{2}\text{)H′| = |(}\text{K}\text{2}\text{)H|}$ if K is even and |(l)H′| = |(l)H| + |(K ? l)H| if $\text{l>}\text{K}\text{2}$.     

A note on a special case of the Frobenius problem

For a set of positive and relative prime integers A = {a ₁…,a _k }, let Γ(A) denote the set of integers of the form a ₁ x ₁+…+a _k x _k with each x _j ≥ 0. Let g(A) (respectively, n(A) and s(A)) denote the largest integer (respectively, the number of integers and sum of integers) not in Γ(A). Let S*(A) denote the set of all positive integers n not in Γ(A) such that n + Γ(A) \ {0} ? Γ((A)\{0}. We determine g(A), n(A), s(A), and S*(A) when A = {a, b, c} with a | (b + c).     

The periods of the sequences generated by some symmetric shift registers

E_k(x₂,…, x_n) is defined by E_k(a₂,…, a_n) = 1 if and only if ∑_i=2ⁿa_i = k. We determine the periods of sequences generated by the shift registers with the feedback functions x₁ + E_k(x₂,…, x_n) and x₁ + E_k(x₂,…, x_n) + E_k+1(x₂,…, x_n) over the field GF(2).