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.     

Classification des Objets Galoisiens de U q (𝔤) à Homotopie PrèS

Pour toute algèbre enveloppante quantique U_q(𝔤) de Drinfeld–Jimbo et toute famille λ = (λ_ij)1≤i ∈ k^? d'éléments inversibles du corps de base, nous construisons explicitement par générateurs et relations un objet galoisien A_λ de U_q(𝔤) et nous montrons que tout objet galoisien de U_q(𝔤) est homotope à un unique objet de la forme A_λ.

For any Drinfeld–Jimbo quantum enveloping algebra U_q(𝔤) and for any family λ = (λ_ij)_{1≤i ∈ k^? of invertible elements of the base field, we explicitly construct a Galois object Aλ of Uq(𝔤) by generators and relations and we prove that any Galois object of Uq(𝔤) is homotopic to a unique object of type Aλ.}     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

On the h-triangles of sequentially (S r ) simplicial complexes via algebraic shifting

Recently, Haghighi, Terai, Yassemi, and Zaare-Nahandi introduced the notion of a sequentially (S _r ) simplicial complex. This notion gives a generalization of two properties for simplicial complexes: being sequentially Cohen–Macaulay and satisfying Serre’s condition (S _r ). Let Δ be a (d?1)-dimensional simplicial complex with Γ(Δ) as its algebraic shifting. Also let (h _i,j (Δ))_{0≤j≤i≤d} be the h-triangle of Δ and (h _i,j (Γ(Δ)))_{0≤j≤i≤d} be the h-triangle of Γ(Δ). In this paper, it is shown that for a Δ being sequentially (S _r ) and for every i and j with 0≤j≤i≤r?1, the equality h _i,j (Δ)=h _i,j (Γ(Δ)) holds true.     

A weighted geometric regularity from order restricted statistical inference

In Euclideank-space, the cone of vectors x = (x ₁,x ₂,...,x _k ) satisfyingx ₁ ≤x ₂ ≤ ... ≤x _k and $\sum\nolimits_{j = 1}^k {x_j } = 0$ is generated by the vectorsv _j = (j ?k, ...,j ?k,j, ...,j) havingj ?k’s in its firstj coordinates andj’s for the remainingk ?j coordinates, for 1 ≤j <k. In this equal weights case, the average angle between v _i and v _j over all pairs (i, j) with 1 ≤i <j <k is known to be 60°. This paper generalizes the problem by considering arbitrary weights with permutations.     

The use of the tetrachoric series for evaluating multivariate normal probabilities

The tetrachoric series is a technique for evaluating multivariate normal probabilities frequently cited in the statistical literature. In this paper we have examined the convergence properties of the tetrachoric series and have established the following. For orthant probabilities, the tetrachoric series converges if $\text{|;?}{}_{\mathrm{ij}}\text{|; <}\text{1}\text{(k ? 1)}$, 1 ≤ i < j ≤ k, where ?_ij are the correlation coefficients of a k-variate normal distribution. The tetrachoric series for orthant probabilities diverges whenever k is even and $\text{?}{}_{\mathrm{ij}}\text{>}\text{1}\text{(k ? 1)}$ or k is odd and $\text{?}{}_{\mathrm{ij}}\text{>}\text{1}\text{(k ? 2)}$, 1 ≤ i < j ≤ k. Other specific results concerning the convergence or divergence of this series are also given. The principal point is that the assertion that the tetrachoric series converges for all k ≥ 2 and all ?_ij such that the correlation matrix is positive definite is false.     

Δ-Monotone arrangements of real numbers

Given a set of M × N real numbers, can these always be labeled as x_i,j; i = 1,…, M; j = 1,…, N; such that x_i+1,j+1 ? x_i+1,j ? x_i,j+1 + x_ij ≥ 0, for every (i, j) where 1 ≤ i ≤ M ? 1, 1 ≤ j ≤ N ? 1? For M = N = 3, or smaller values of M, N it is shown that there is a “uniform” rule. However, for max(M, N) > 3 and min(M, N) ≥ 3, it is proved that no uniform rule can be given. For M = 3, N = 4 a way of labeling is demonstrated. For general M, N the problem is still open although, for a special case where all the numbers are 0's and 1's, a solution is given.     

Symposium on combinatorial mathematics and optimal design

Let A₁,A₂,…,A_n be finite sets such that A_i?A_j for all i≠j. Let F be an intersecting family consisting of sets contained in some A_i, i=1,2,…,n. Chvátal conjectured that among the largest intersecting families, there is always a star. In this paper, we obtain another proof of a result of Schönheim: If A₁∩A₂∩?∩A_n≠?, then the conjecture is true. We also prove that if A_i∩A_jA_k = ? for all i≠j≠k≠i or if the independent system satisfies a hereditary tree structure, then the conjecture is also true.     

Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

On B(4, 13) 2-Groups

A group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j  | 1 ≤ i, j ≤ n}| ≤k. In this article, we give a complete characterization of B(4, 13) 2-groups, and then obtain a complete characterization of B(4, 13) groups.     

A general form of certain mean field models for spin glasses

Given numbers a _ij ≥ 0 for 1 ≤ i  <  j ≤ N, and given numbers b _i ≥ 0, i ≤ N, we consider the random Hamiltonian $\sum_{i,j \le N} \sqrt{a_{ij}} g_{ij} \sigma_i \sigma_j + \sum_{i \le N} \sqrt{b_i} g_i \sigma_i$ , where g _i , g _ij denote independent standard normal r.v., and where σ _i = ± 1. We give sufficient conditions on the coefficients a _ij for the system governed by this Hamiltonian to exhibit “high-temperature behavior”. There results extend known facts concerning the behavior of the Sherrington-Kirkpatrick model at “very high-temperature”. In a similar manner we give a general form of the “perceptron model”.     

Sperner systems consisting of pairs of complementary subsets

It was proved by Erdös, Ko, and Radó (Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser.12 (1961), 313–320.) that if $\text{A}$ = {;A₁,…, A_l}; consists of k-subsets of a set with n > 2k elements such that A_i ∩ A_j ≠ ? for all i, j then l ? (_k?1^n?1). Schönheim proved that if A₁, …, A_l are subsets of a set S with n elements such that A_i ? A_j, A_i ∩ A_j ≠ ø and A_i ∪ A_j ≠ S for all i ≠ j then $\text{l ? (}{}_{\mathrm{<mtext>[</mtext><mtext>n</mtext><mtext>2</mtext><mtext>]\; ?\; 1</mtext>}}{}^{\mathrm{n\; ?\; 1}}\text{)}$. In this note we prove a common strengthening of these results.     

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.     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Block partitions of sequences

Given a sequence A = (a ₁, …, a _n ) of real numbers, a block B of A is either a set B = {a _i , a _i+1, …, a _j } where i ≤ j or the empty set. The size b of a block B is the sum of its elements. We show that when each a _i ∈ [0, 1] and k is a positive integer, there is a partition of A into k blocks B ₁, …, B _k with |b _i ?b _j | ≤ 1 for every i, j. We extend this result in several directions.     

On quadruples of Griffiths points

Tabov (Math Mag 68:61–64, 1995) has proved the following theorem: if points A ₁, A ₂, A ₃, A ₄ are on a circle and a line l passes through the centre of the circle, then four Griffiths points G ₁, G ₂, G ₃, G ₄ corresponding to pairs (Δ _i ,l) are on a line (Δ _i denotes the triangle A _j A _k A _l , j,k,l ≠ i). In this paper we present a strong generalisation of the result of Tabov. An analogous property for four arbitrary points A ₁, A ₂, A ₃, A ₄, is proved, with the help of the computer program “Mathematica”.     

Paths and edge-connectivity in graphs III. Six-terminalk paths

Suppose thatk ≥ 1 is an odd integer, (s ₁,t ₁),..., (s _k> ,t _k ) are pairs of vertices of a graphG andλ(s _i ,t _i ) is the maximal number of edge-disjoint paths betweens _i andt _i . We prove that ifλ(s _i ,t _i )≥ k (1≤ i ≤ k) and |{s ₁,...s _k ,t ₁,...,t _k }| ≤ 6, then there exist edge-disjoint pathsP ₁,...,P _k such thatP _i has endss _i andt _i (1≤ i ≤ k).     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

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).