On the Schur multiplier norm of matrices

The Schur product of two n×n complex matrices A=(a_ij), B=(b_ij) is defined by A°B=(a_ijb_ij. By a result of Schur [2], the algebra of n×n matrices with Schur product and the usual addition is a commutative Banach algebra under the operator norm (the norm of the operator defined on $\text{C}$ⁿ by the matrix). For a fixed matrix A, the norm of the operator B?A°B on this Banach algebra is called the Schur multiplier norm of A, and is denoted by ∥A∥^m. It is proved here that $\text{∥A∥=∥U}{}^1\text{AU∥}{}_{\mathrm{m}}$ for all unitary U (where ∥·∥ denotes the operator norm) iff A is a scalar multiple of a unitary matrix; and that ∥A∥_m=∥A∥ iff there exist two permutations P, Q, a p×p (1?p?n) unitary U, an (n?p)×(n?p)1 contraction C, and a nonnegative number λ such that

$\text{A=λP}\text{U}\text{0}\text{0}\text{C}\text{Q;}$

and this is so iff $\text{∥A°}\text{A}\text{?}\text{∥=∥A∥}{}^2$, where ā is the matrix obtained by taking entrywise conjugates of A.     

Semisimilarity for matrices over a division ring

Two square matrices A and B over a ring R are semisimilar, written A$\text{?}$B, if YAX=B and XBY=A for some (possibly rectangular) matrices X, Y over R. We show that if A and B have the same dimension, and if the ring is a division ring $\text{D}$, then A$\text{?}$B if and only if A² is similar to B² and rank(A^k)=rank(B^k), k=1,2,…     

Transcendental continued fractions

In two previous papers Nettler proved the transcendence of the continued fractions $\text{A := a}{}_1\text{+}\text{1}\text{a}{}_2\text{+}\text{1}\text{a}{}_3\text{+ ?}$, $\text{B := b}{}_1\text{+}\text{1}\text{b}{}_2\text{+}\text{1}\text{b}{}_3\text{+ ?}$ as well as the transcendence of the numbers A + B, A ? B, AB, $\text{A}\text{B}$ where the a's and b's are positive integers satisfying a certain mutual growth condition. In the present paper even the algebraic independence of A and B is proved under almost the same condition and furthermore a result concerning the transcendency of A^B is established.     

Extension de quelques theoremes sur les densites de series d'elements de n a des series de sous-ensembles finis de n

For a sequence A = {A_k} of finite subsets of N we introduce: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{n}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$, where A(m) is the number of subsets A_k ? {1, 2, …, m}.The collection of all subsets of {1, …, n} together with the operation $\text{a ∪ b, (a ∩ b), (a 1 b = a ∪ b ? a ∩ b)}$ constitutes a finite semi-group N^∪ (semi-group N^∩) (group $\text{N}{}^1$). For N^∪, N^∩ we prove analogues of the Erdös-Landau theorem: δ(A+B) ? δ(A)(1+(2λ)^?1(1?δ(A>))), where B is a base of N of the average order λ. We prove for $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ analogues of Schnirelmann's theorem (that δ(A) + δ(B) > 1 implies δ(A + B) = 1) and the inequalities λ ? 2h, where h is the order of the base.We introduce the concept of divisibility of subsets: a|b if b is a continuation of a. We prove an analog of the Davenport-Erdös theorem: if d(A) > 0, then there exists an infinite sequence {A_kr}, where A_kr | A_kr+1 for r = 1, 2, …. In Section 6 we consider for $\text{N∪, N∩, N1}$ analogues of Rohrbach inequality: $\text{2n}\text{? g(n) ? 2}\text{n}$, where g(n) = min k over the subsets {a₁ < … < a_k} ? {0, 1, 2, …, n}, such that every m? {0, 1, 2, …, n} can be expressed as m = a_i + a_j.Pour une série A = {A_k} de sous-ensembles finis de N on introduit les densités: $\text{δ(A) =}\text{inf}{}_{\mathrm{m?n}}\text{A(m)}\text{2}{}^{\mathrm{m}}$, $\text{d(A) =}\text{lim inf}{}_{\mathrm{n\to \infty }}\text{A(n)}\text{2}{}^{\mathrm{n}}$ où A(m) est le nombre d'ensembles A_k ? {1, 2, …, m}. L'ensemble de toutes les parties de {1, 2, …, n} devient, pour les opérations $\text{a ∪ b, a ∩ b, a 1 b = a ∪ b ? a ∩ b}$, un semi-groupe fini N^∪, N^∩ ou un groupe N¹ respectivement. Pour N^∪, N^∩ on démontre l'analogue du théorème de Erdös-Landau: δ(A + B) ? δ(A)(1 + (2λ)^?1(1?δ(A))), où B est une base de N d'ordre moyen λ. On démontre pour $\text{N}{}^{\mathrm{\cup }}\text{, N}{}^{\mathrm{\cap }}\text{, N}{}^1$ l'analogue du théorème de Schnirelmann (si δ(A) + δ(B) > 1, alors δ(A + B) = 1) et les inégalités λ ? 2h, où h est l'ordre de base. On introduit le rapport de divisibilité des enembles: a|b, si b est une continuation de a. On démontre l'analogue du théorème de Davenport-Erdös: si d(A) > 0, alors il existe une sous-série infinie {A_kr}, où A_kr|A_kr+1, pour r = 1, 2, … . Dans le Paragraphe 6 on envisage pour N^∪, $\text{N}{}^{\mathrm{\cap }}\text{, N}{}^1$ les analogues de l'inégalité de Rohrbach: $\text{2n}\text{? g(n) ? 2}\text{n}$, où g(n) = min k pour les ensembles {a₁ < … < a_k} ? {0, 1, 2, …, n} tels que pour tout m? {0, 1, 2, …, n} on a m = a_i + a_j.     

Transcendental continued fractions

In a previous paper it was proven that given the continued fractions

$\text{A = a}{}_1\text{+}\text{1}\text{a}{}_2\text{+}\text{1}\text{a}{}_3\text{+… and B = b}{}_1\text{+}\text{1}\text{b}{}_2\text{+}\text{1}\text{b}{}_3\text{+…}$

where the a's and b's are positive integers, then A, B, A ± B, $\text{A}\text{B}$ and AB are irrational numbers if $\text{a}{}_{\mathrm{n}}\text{2}\text{> b}{}_{\mathrm{n}}\text{> a}{}_{\mathrm{n?1}}{}^{\mathrm{5n}}$ for all n sufficiently large, and transcendental numbers if for all n sufficiently large. Using a more direct approach it is proven in this paper that A, B, A ± B, $\text{A}\text{B}$ and AB are transcendental numbers if a_n > b_n > a_n?1^(n?1)2 for all n sufficiently large.     

On the convergence of the Neumann series in interval analysis

Let $\text{A}$ be a real or complex n × n interval matrix. Then it is shown that the Neumann series $\text{Σ}{}^{\mathrm{\infty }}{}_{\mathrm{k=0}}\text{A}{}^{\mathrm{k}}$ is convergent iff the sequence {$\text{A}$^k} converges to the null matrix $\text{O}$, i.e., iff the spectral radius of the real comparison matrix $\text{B}$ constructed in [2] is less than one.     

Nonnegative factorization of completely positive matrices

Let A be a real symmetric n × n matrix of rank k, and suppose that A = BB′ for some real n × m matrix B with nonnegative entries (for some m). (Such an A is called completely positive.) It is shown that such a B exists with $\text{m?}\text{1}\text{2}\text{k(k+1)?N}$, where 2N is the maximal number of (off-diagonal) entries which equal zero in a nonsingular principal submatrix of A. An example is given where the least m which works is $\text{(k+1)}{}^2\text{4}$ (k odd),$\text{k(k+2)}\text{4}$ (k even).     

Un contre-exemple pour les formes invariantes sur un corps fini

Let A be a Jordan algebra over the reals which is a Banach space with respect to a norm satisfying the requirements: (i) ∥ a ° b ∥ ≤ ∥ a ∥ ∥ b ∥, (ii) ∥ a² ∥ = ∥ a ∥², (iii) ∥ a² ∥ ≤ ∥ a² + b² ∥ for a, b?A. It is shown that A possesses a unique norm closed Jordan ideal J such that $\text{A}\text{J}$ has a faithful representation as a Jordan algebra of self-adjoint operators on a complex Hilbert space, while every “irreducible” representation of A not annihilating J is onto the exceptional Jordan algebra M₃⁸.     

On the convergence of powers of interval matrices

We give a necessary and sufficient condition for the sequence {$\text{A}$^k}of the powers of an interval matrix $\text{A}$ to converge to the null matrix $\text{O}$. We construct a point matrix $\text{B}$ which has spectral radius ? ($\text{B}$) less than one if {$\text{A}$^k}converges.     

A global genericity theorem for bifurcations in variational problems

Let C be a Banach space, H a Hilbert space, and let F(C,H) be the space of C^∞ functions f: C × H → R having Fredholm second derivative with respect to x at each (c, x) ?C × H for which $\text{D?}{}_{\mathrm{c}}\text{(x) = 0}$; here we write $\text{?}{}_{\mathrm{c}}\text{(x)}$ for $\text{?(c, x)}$. Say ? is of standard type if at all critical points of ?_c it is locally equivalent (as an unfolding) to a quadratic form Q plus an elementary catastrophe on the kernel of Q. It is proved that if f?F (A × B, H) satisfies a certain ‘general position’ condition, and dim B ? 5, then for most a?A the function f_o?F(B,H) is of standard type. Using this it is shown that those f?F(B,H) of standard type form an open dense set in F(B,H) with the Whitney topology. Thus both results are Hilbert-space versions of Thom's theorem for catastrophes in $\text{R}$ⁿ.     

Relaxed very asymmetric coloring games

This paper investigates a competitive version of the coloring game on a finite graph G. An asymmetric variant of the (r,d)-relaxed coloring game is called the (r,d)-relaxed (a,b)-coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph G, using colors from a set X, with |X|=r. On each turn Alice colors a vertices and Bob colors b vertices. A color α∈X is legal for an uncolored vertex u if by coloring u with color α, the subgraph induced by all the vertices colored with α has maximum degree at most d. Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The d-relaxed (a,b)-game chromatic number, denoted by , of G is the least r for which Alice has a winning strategy in the (r,d)-relaxed (a,b)-coloring game.The (r,d)-relaxed (1,1)-coloring game has been well studied and there are many interesting results. For the (r,d)-relaxed (a,1)-coloring game, this paper proves that if a graph G has an orientation with maximum outdegree k and a≥k, then for all d≥k²+2k; If a≥k³, then (a,1)- for all d≥2k+1.     

Conditions under which the order of two non-negative Hermitian matrices is preserved when taking integral powers

Let A and B be two n×n non-negative matrices. We write A ? B iff

$\text{u}{}^1\text{(A ? B)u ? 0}$

for all column vectors u in Cⁿ. Here u¹ is the conjugate transpose of u. In this paper are stated equivalent conditions under which A^k ? B^k for all natural numbers k. The result is then generalized to Hermitian operators in a Hilbert space.     

Cyclic quartic fields and genus theory of their subfields

Let k = $\text{Q}$(√u) (u ≠ 1 squarefree), K any possible cyclic quartic field containing k. A close relation is established between K and the genus group of k. In particular: (1) Each K can be written uniquely as K = $\text{Q}$(√vwη), where η is fixed in k and satisfies η ? 1, (η) = $\text{U}$²√u, |$\text{U}$²| = |(√u)|, (v, u) = 1, v ∈ $\text{Z}$ is squarefree, w|u, 0 < w < √u. Thus if u ≠ a² + b², there is no K ? k. If u = a² + b² then for each fixed v there are 2^{g ? 1}K ? k, where g is the number of prime divisors of u. (2) $\text{K}\text{k}$ has a relative integral basis (RIB) (i.e., O_K is free over O_k) iff N(ε₀) = ?1 and w = 1, where ε₀ is the fundamental unit of k, (or, equivalently, iff K = $\text{Q}$(√vε₀√u), (v, u) = 1). (3) A RIB is constructed explicitly whenever it exists. (4) disc(K) is given. In particular, the following results are special cases of (2): (i) Narkiewicz showed in 1974 that $\text{K}\text{k}$ has a RIB if u is a prime; (ii) Edgar and Peterson (J. Number Theory12 (1980), 77–83) showed that for u composite there is at least one K ? k having no RIB. Besides, it follows from (4) that the classification and integral basis of K given by Albert (Ann. of Math.31 (1930), 381–418) are wrong.     

Restoring rank and consistency by orthogonal projection

Let A₀x=b₀ be a consistent (but possibly unknown) linear algebraic system of m equations in n unknowns, with rank(A₀)=k (likewise possibly unknown). Let Ax=b be a known (but possibly inconsistent) nearby system. Procedures for “solving” Ax=b usually replace it (at least in principle) by a nearby consistent system $\text{A}\text{?}\text{x=}\text{b}\text{?}$ of (hopefully) rank k, and solve that one instead. We consider consistent systems $\text{A}\text{?}\text{x=}\text{b}\text{?}$ with rank$\text{(}\text{A}\text{?}\text{)=k}$ such that (Ã,b?) is the orthogonal projection of (A,b) on span(Ã) [i.e., the columns of (Ã┆b?) are the projections of those of (A ┆ b)]. Under suitable circumstances the rank k pair (Ã,b?) nearest to (A,b) in the sense of minimizing $\text{6(}\text{A}\text{?}\text{┆}\text{b}\text{?}\text{) ? (}\text{A}\text{?}\text{┆}\text{b}\text{?}\text{)6}{}_{\mathrm{F}}$ belongs to this class, as well as the pair delivered by the ordinary least squares method (if k=n?m) or, more generally, the pair delivered by a well-known algorithm (viz. HFTI). If $\text{?:= |(A┆b)?(A}{}_0\text{┆b}{}_0\text{)6}{}_{\mathrm{F}}$, then the minimum length solutions of all systems $\text{A}\text{?}\text{x=}\text{b}\text{?}$ so related to (A,b) are shown to differ mutually only by O(?²). This means, e.g., that itwill usually not pay to compute the solution of the nearest system.     

3×3 Orthostochastic matrices and the convexity of generalized numerical ranges

Let $\text{U}$₃ be the set of all 3 × 3 unitary matrices, and let A and B be two 3 × 3 complex nor?al matrices. In this note, the authors first give a necessary and sufficient condition for a 3 × 3 doubly stochastic matrix to be orthostochastic and then use this result to consider the structure of the sets $\text{W}$ (A) = {Diag UAU¹ : U ∈ $\text{U}$₃} and W(A,B) = {Tr UAU¹B: U ∈ $\text{U}$₃}, where ¹ denotes the transpose conjugate.     

On the fair coin tossing process

Let Ω = {1, 0} and for each integer n ≥ 1 let $\text{Ω}{}_{\mathrm{n}}\text{= Ω × Ω × … × Ω}$ (n-tuple) and $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}\text{= {(a}{}_1\text{, a}{}_2\text{, …, a}{}_{\mathrm{n}}\text{)|(a}{}_1\text{, a}{}_2\text{, … , a}{}_{\mathrm{n}}\text{) ? Ω}{}_{\mathrm{n}}\text{and}\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{a}{}_{\mathrm{i}}\text{= k}}$ for all k = 0,1,…,n. Let {Y_m}_m≥1 be a sequence of i.i.d. random variables such that $\text{P(Y}{}_1\text{= 0) = P(Y}{}_1\text{= 1) =}\text{1}\text{2}$. For each A in $\text{Ω}{}_{\mathrm{n}}$, let T_A be the first occurrence time of A with respect to the stochastic process {Y_m}_m≥1. R. Chen and A.Zame (1979, J. Multivariate Anal. 9, 150–157) prove that if n ≥ 3, then for each element A in $\text{Ω}{}_{\mathrm{n}}$, there is an element B in $\text{Ω}{}_{\mathrm{n}}$ such that the probability that T_B is less than T_A is greater than $\text{1}\text{2}$. This result is sharpened as follows: (I) for n ≥ 4 and 1 ≤ k ≤ n ? 1, each element A in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$, there is an element B also in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$ such that the probability that T_B is less than T_A is greater than $\text{1}\text{2}$; (II) for n ≥ 4 and 1 ≤ k ≤ n ? 1, each element A = (a₁, a₂,…,a_n) in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$, there is an element C also in $\text{Ω}{}_{\mathrm{n}}{}^{\mathrm{k}}$ such that the probability that T_A is less than T_C is greater than $\text{1}\text{2}$ if n ≠ 2m or n = 2m but a_i = a_{i + 1} for some 1 ≤ i ≤ n?1. These new results provide us with a better and deeper understanding of the fair coin tossing process.     

Barring rectangles from the plane

The problem of what proportion of squares of an infinite checkerboard must be barred so as to bar all a × b rectangles from the board is considered. If a ? b is assumed, a complete answer is obtained except when the fractional part of $\text{b}\text{a}$ is $\text{?(}\text{1}\text{3}\text{,}\text{1}\text{2}\text{)}$ and $\text{b}\text{a}\text{> 2}$.     

On multiple sum and product sets of finite sets of integers

Let $\text{A?}\text{Z}$ be a finite set of integers of cardinality |A|=N?2. Given a positive integer k, denote kA (resp. A^(k)) the set of all sums (resp. products) of k elements of A. We prove that for all b>1, there exists k=k(b) such that max(|kA|,|A^(k)|)>N^b. This answers affirmably questions raised in Erd?s and Szemerédi (Stud. Pure Math., 1983, pp. 213–218), Elekes et al. (J. Number Theory 83 (2) (2002) 194–201) and recently, by S. Konjagin (private communication). The method is based on harmonic analysis techniques in the spirit of Chang (Ann. Math. 157 (2003) 939–957) and combinatorics on graphs. To cite this article: J. Bourgain, M.-C. Chang, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Resolvable perfect cyclic designs

Let k, λ, and υ be positive integers. A perfect cyclic design in the class PD(υ, k, λ) consists of a pair (Q, B) where Q is a set with |Q| = υ and B is a collection of cyclically ordered k-subsets of Q such that every ordered pair of elements of Q are t apart in exactly λ of the blocks for t = 1, 2, 3,…, k?1. To clarify matters the block [a₁, a₂, …, a_k] has cyclic order a₁ < a₂ < a₃ … < a_k < a₁ and a_i and a_i+1 are said to be t apart in the block where i + t is taken mod k. In this paper we are interested only in the cases where λ = 1 and υ ≡ 1 mod k. Such a design has $\text{υ(υ ? 1)}\text{k}$ blocks. If the blocks can be partitioned into υ sets containing $\text{(υ ? 1)}\text{k}$ pairwise disjoint blocks the design is said to be resolvable, and any such partitioning of the blocks is said to be a resolution. Any set of $\text{υ ? 1)}\text{k}$ pairwise disjoint blocks together with a singleton consisting of the only element not in one of the blocks is called a parallel class. Any resolution of a design yields υ parallel classes. We denote by RPD(υ, k, 1) the class of all resolvable perfect cyclic designs with parameters υ, k, and 1. Associated with any resolvable perfect cyclic design is an orthogonal array with k + 1 columns and υ rows with an interesting conjugacy property. Also a design in the class RPD(υ, k, 1) is constructed for all sufficiently large υ with υ ≡ 1 mod k.