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.     

Minimum norm problems over transportation polytopes

We consider the problem of updating input-output matrices, i.e., for given (m,n) matrices A ? 0, W ? 0 and vectors u ? $\text{R}$^m, v?$\text{R}$ⁿ, find an (m,n) matrix X ? 0 with prescribed row sums Σⁿ_j=1X_ij = u_i (i = 1,…,m) and prescribed column sums Σ^m_i=1X_ij = v_j (j = 1,…,n) which fits the relations X_ij = A_ij + λ_iW_ij + W_ij + W_ijμ_j for all i,j and some λ?$\text{R}$^m, μ?$\text{R}$ⁿ. Here we consider the question of existence of a solution to this problem, i.e., we shall characterize those matrices A, W and vectors u,v which lead to a solvable problem. Furthermore we outline some computational results using an algorithm of [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 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.     

Canonical row-column-exchangeable arrays

Consider a standard row-column-exchangeable array X = (X_ij : i,j ≥ 1), i.e., X_ij = f(a, ξ_i, η_j, λ_ij) is a function of i.i.d. random variables. It is shown that there is a canonical version of X, X′, such that X′, and α′, ξ′₁, ξ′₂,…, η′₁, η′₂,…, are conditionally independent given ∩_{n ≥ 1}σ(X′_ij : max(i,j) ≥ n). This result is quite a bit simpler to prove than the analogous result for the original array X, which is due to Aldous.     

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.     

On Ochoa's special matrices in matrix classes

It is well known that the ideal classes of an order Z[μ], generated over Z by the integral algebraic number μ, are in a bijective correspondence with certain matrix classes, that is, classes of unimodularly equivalent matrices with rational integer coefficients. If the degree of μ is ?3, we construct explicitly a particularly simple ideal matrix for an ideal which is a product of different prime ideals of degree 1. We obtain the following special n×n matrix (c_ij) in the matrix class corresponding to the ideal class of our ideal: c_i+1,_i=1(i=1,…,n?2); c_ij=0(?i?n, 1?j?n? 2, and i≠j+1); c_nj=0(j)=2,…,n?1). The remaining coefficients are given as explicit polynomials in an integer z which depends on the ideal. It is shown that the matrix class of every regular ideal class of Z[μ] contains a special matrix of this kind.     

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.     

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.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

Mean matrices and infinite divisibility

We consider matrices M with entries m_ij = m(λ_i, λ_j) where λ₁, … ,λ_n are positive numbers and m is a binary mean dominated by the geometric mean, and matrices W with entries w_ij = 1/m (λ_i, λ_j) where m is a binary mean that dominates the geometric mean. We show that these matrices are infinitely divisible for several much-studied classes of means.     

On constant discrete programming problems

Let H be a subset of the set S_n of all permutations

$\text{1}\text{2}\text{???}\text{n}\text{s(1)}\text{s(2)}\text{???}\text{s(n)}$

C=6c_ij6 a real n?n matrix L_c(s)=c_1s(1)+c_2s(2)+???+c_ns(n) for s ? H. A pair (H, C) is the existencee of reals a₁,b₁,a₂,b₂,…a_n,b_n, for which c_ij=a₁+b_j if (i,j)?D(H), where D(H)={(i,j):(?h?H)(j=h(i))}.For a pair (H,C) the specifity of it is proved in the case, when H is either a special cyclic class of permutations or a special union of cyclic classes. Specific pairs with minimal sets H are in some sense described.     

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.     

On a Conjecture of E. Dittert

Let K_n denote the set of all n X n nonnegative matrices whose entries have sum n, and let φ be a real valued function defined on K_n by φ(X) = π_iⁿ⁼¹ n, + π_j=1^c_j⁻ⁿ per X for X E K_n with row sum vector (r₁,…, r_n) and column sum vector (c_l,hellip;, c_n). For the same X, let φ_ij(X)= π_k≠ir_k + π_1≠jc₁ - per X(i| j). A ϵK_n is called a φ-maximizing matrix if φ(A) > φ(X) for all X ϵ K_n. Dittert's conjecture asserts that J_n = [1/n]_n×n is the unique (φ-maximizing matrix on K_n. In this paper, the following are proved: (i) If A = [a_ij] is a φ-maximizing matrix on K_n then φ_ij(A) = φ (A) if a_ij > 0, and φ_ij (A) ⩽ φ (A)if aij = 0. (ii) The conjecture is true for n = 3.     

Distribution exacte du score local,cas markovien

Given a sequence $\text{X}\text{=(X}{}_{\mathrm{k}}\text{)}{}_{\mathrm{k?1}}$ of random variables taking values in {?v,…,0,…,+u}, let's define the local score of the sequence by H_n=max_1?i?j?n(∑_k=i^jX_k). The local score is used to analyze biological sequences pointing out regions of the sequences with interesting biological properties. In order to separate randomly events from really interesting segments, we establish here the distribution of the local score of H_n when the sequence $\text{X}$ is a Markov chain of order 1. To cite this article: S. Mercier, C. Hassenforder, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

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.     

Sign-nonsingular matrices and even cycles in directed graphs

A sign-nonsingular matrix or L-matrix A is a real m× n matrix such that the columns of any real m×n matrix with the same sign pattern as A are linearly independent. The problem of recognizing square L-matrices is equivalent to that of finding an even cycle in a directed graph. In this paper we use graph theoretic methods to investigate L-matrices. In particular, we determine the maximum number of nonzero elements in square L-matrices, and we characterize completely the semicomplete L-matrices [i.e. the square L-matrices (a_ij) such that at least one of a_ij and a_ij is nonzero for any i,j] and those square L-matrices which are combinatorially symmetric, i.e., the main diagonal has only nonzero entries and a_ij=0 iff a_ji=0. We also show that for any n×n L-matrix there is an i such that the total number of nonzero entries in the ith row and ith column is less than n unless the matrix has a completely specified structure. Finally, we discuss the algorithmic aspects.     

A note on a conjecture on permanents

Let Kn denote the set of all n × n nonnegative matrices whose entries have sum n, and let ϕ be a real function on K_n defined by ϕ (X) = Πⁿ_i=1Σⁿ_j=1x_ij + Πⁿ_j=1Σⁿ_i=1x_ij − per X for X = [x_ij] ϵ K_n. A matrix A ϵ K_n is called a ϕ -maximizing matrix on K_n if ϕ (A) ⩾ ϕ (X) for all X ϵ K_n. It is conjectured that J_n = [1/n]_{n × n} is the unique ϕ-maximizing matrix on K_n. In this note, the following are proved: (i) If A is a positive ϕ-maximizing matrix, then A = J_n. (ii) If A is a row stochastic ϕ-maximizing matrix, then A = J_n. (iii) Every row sum and every column sum of a ϕ-maximizing matrix lies between 1 − √2·n!/nⁿ and 1 + (n − 1)√2·n!/nⁿ. (iv) For any p.s.d. symmetric A ϵ K_n, ϕ (A) ⩽ 2 − n!/nⁿ with equality iff A = J_n. (v) ϕ attains a strict local maximum on K_n at J_n.     

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′}.