A bound on the scrambling index of a primitive matrix using Boolean rank

The scrambling index of an n×n primitive matrix A is the smallest positive integer k such that A^k(A^t)^k=J, where A^t denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M=AB for some m×b Boolean matrix A and b×n Boolean matrix B. In this paper, we give an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M). Furthermore we characterize all primitive matrices that achieve the upper bound.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

Spectral Criteria of Abstract Sequences; Application to Difference Equations

We suppose that M is a closed subspace of l ^∞(J, X), the space of all bounded sequences {x(n)} _n?J ? X, where J ? {Z⁺,Z} and X is a complex Banach space. We define the M-spectrum σ_M (u) of a sequence u ? l ^∞(J,X). Certain conditions will be supposed on both M and σ_M (u) to insure the existence of u ? M. We prove that if u is ergodic, such that σ_M (u,) is at most countable and, for every λ ? σ_M (u), the sequence e^?iλnu(n) is ergodic, then u ? M. We apply this result to the operator difference equationu(n + 1) = Au(n) + ψ(n), n ? J,and to the infinite order difference equation Σ ^r _k=1 a_k (u(n + k) ? u(n)) + Σ _{s ? Z}?(n ? s)u(s) = h(n), n?J, where ψ?l ^∞(Z,X) such that ψ| _J ? M, A is the generator of a C ₀-semigroup of linear bounded operators {T(t)} _t>0 on X, h ? M, ? ? l ¹(Z) and a_k ?C. Certain conditions will be imposed to guarantee the existence of solutions in the class M.     

The Generalized <Emphasis Type="Italic">τ</Emphasis>-Bases of Primitive Non-Powerful Signed Digraphs with d Loops

Let n, k, τ, d be positive integers with 1 ≤ k, τ, d ≤ n. As natural extensions of the bases, the kth local bases, the kth upper bases and the kth lower bases of primitive non-powerful signed digraphs, we introduce a number of new, though, intimately related parameters called the generalized τ-bases of primitive non-powerful signed digraphs. Moreover, some sharp bounds for the generalized τ-bases of primitive non-powerful signed digraphs with n vertices and d loops are obtained, respectively.     

A Coding Theory Bound and Zero-Sum Square Matrices

For a code C=C(n,M) the level k code of C, denoted C _k , is the set of all vectors resulting from a linear combination of precisely k distinct codewords of C. We prove that if k is any positive integer divisible by 8, and n=k, M=k2k then there is a codeword in C _k whose weight is either 0 or at most . In particular, if <(4–2)²/48 then there is a codeword in C _k whose weight is n/2–(n). The method used to prove this result enables us to prove the following: Let k be an integer divisible by p, and let f(k,p) denote the minimum integer guaranteeing that in any square matrix over Z _p , of order f(k,p), there is a square submatrix of order k such that the sum of all the elements in each row and column is 0. We prove that lim inf f(k,2)/k<3.836. For general p we obtain, using a different approach, that f(k,p)p( ^{k / ln k )(1+ o} _k ⁽¹⁾⁾.     

Stability of Numerical Invariants in Free Groups

Let d be an odd integer, and let k be a field which contains a primitive dth root of unity. Let l ₁ and l ₂ be cyclic field extensions of k of degree d with norms n _{l 1/k} and n _{l 2/k} . Minà?'s approach which showed that quadratic Pfister forms are strongly multiplicative is applied to the form n _{l 1/k}  ? n _{l 2/k} of degree d. Let K = k(X ₁,…, X _{d ²} ). We compute polynomials which are similarity factors of a form of the kind N ? (n _{l 2/k}  ? _k K) over K, where N is the norm of a certain field extension of K of degree d. These polynomials arise by specializing certain indeterminates of the homogeneous polynomial representing the form n _{l 1/k}  ? n _{l 2/k} to be zero. Similar results are obtained for the tensor product of the norm of a cubic division algebra and a cubic norm n _{l 1/k} .     

An application of ramsey’s theorem to groups with homogeneous theory

For any integers n >m ≥ 2, we say that a complete theory T is (m, n)-homogeneous if, for each model M of T, two n-tuples [abar],[bbar] in M have the same type if the corresponding m-tuples from [abar] and [bbar] have the same type. It was conjectured by H. Kikyo that, if M is an infinite group, with possibly additional structure, then the theory of M is not (m, n)-homogeneous. We prove a general result on structures with (m, n)-homogeneous theory which implies that, if M is a counterexample to this conjecture, then there exists an integer h such that each abelian subgroup of M has at most h elements. It follows that there exist an integer k such that M ^k = 1, and an integer l such that each finite subgroup of M has at most l elements.     

On nonnegatively curved 4-manifolds with discrete symmetry

Let M be the closed, simply connected, 4-manifold with nonnegative sectional curvature, called a nonnegatively curved 4-manifold, with an effective and isometric Z _m -action for a positive integer m ≧ 61⁷. Assume that Z _m acts trivially on the homology of M. The goal of this short paper is to prove that if the fixed point set of any nontrivial element of Z _m has at most one two-dimensional component, then M is homeomorphic to S ⁴, # _i ^l =1S ² × S ², l = 1, 2, or # _j ^k = 1 ± CP ², k = 1, 2, 3, 4, 5. The main strategy of this paper is to give an upper bound of the Euler characteristic χ(M) under the homological assumption of a Z _m -action as above by using the Lefschetz fixed point formula.     

A Note on Lewin’s Problem

The parameter l(G) for a primitive digraph G introduced by Lewin is the minimum positive integer k for which there are walks of both lengths k and k + 1 from some vertex u to some vertex v. We obtain upper bounds on l(G) if G is primitive ministrong, or G is just primitive and not necessarily ministrong, or G is primitive symmetric. We also discuss the numbers attainable as l(G).AMS Subject Classification (2000): 05C20, 15A48Partially supported by the National Natural Science Foundation of China (19771040) and the Guangdong Provincial Natural Science Foundation of China (990447).     

Compositions inside a rectangle and unimodality

Let c ^k,l (n) be the number of compositions (ordered partitions) of the integer n whose Ferrers diagram fits inside a k×l rectangle. The purpose of this note is to give a simple, algebraic proof of a conjecture of Vatter that the sequence c ^k,l (0),c ^k,l (1),…,c ^k,l (kl) is unimodal. The problem of giving a combinatorial proof of this fact is discussed, but is still open.     

Polynomials and primitive roots in finite fields

The primitive elements of a finite field are those elements of the field that generate the multiplicative group of k. If f(x) is a polynomial over k of small degree compared to the size of k, then f(x) represents at least one primitive element of k. Also f(x) represents an lth power at a primitive element of k, if l is also small. As a consequence of this, the following results holds.Theorem. Let g(x) be a square-free polynomial with integer coefficients. For all but finitely many prime numbers p, there is an integer a such that g(a) is equivalent to a primitive element modulo p.Theorem. Let l be a fixed prime number and f(x) be a square-free polynomial with integer coefficients with a non-zero constant term. For all but finitely many primes p, there exist integers a and b such that a is a primitive element and f(a) ≡ b¹ modulo p.     

Improper choosability of graphs and maximum average degree

Improper choosability of planar graphs has been widely studied. In particular, ?krekovski investigated the smallest integer g_k such that every planar graph of girth at least g_k is k‐improper 2‐choosable. He proved [9] that 6 ≤ g₁ ≤ 9; 5 ≤ g₂ ≤ 7; 5 ≤ g₃ ≤ 6; and ? k ≥ 4, g_k = 5. In this article, we study the greatest real M(k, l) such that every graph of maximum average degree less than M(k, l) is k‐improper l‐choosable. We prove that if l ≥ 2 then . As a corollary, we deduce that g₁ ≤ 8 and g₂ ≤ 6, and we obtain new results for graphs of higher genus. We also provide an upper bound for M(k, l). This implies that for any fixed l, . © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 181–199, 2006     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

Power inequalities and spectral dominance of generalized matrix norms

A generalized matrix norm G dominates the spectral radius for all A?M_n(C) (i) if for some positive integer k the rule G(A^k) ? G(A)^k holds for all A?M_n(C) and (ii) if and only if for each A?M_n(C) there exists a constant γ_A such that G(A^k) ? γ_AG(A)^kfor all positive integers k. Other results and examples are also given concerning spectrally dominant generalized matrix norms.     

The first negative coefficients of symmetric square <Emphasis Type="Italic">L</Emphasis>-functions

Let n_sym²fn_{\mathrm{sym}^{2}f} be the greatest integer such that l_sym²f(n) 3 0\lambda_{\mathrm{sym}^{2}f}(n)\ge0 for all n < n_sym²fnn,N)=1, where l_sym²f(n)\lambda_{\mathrm{sym}^{2}f}(n) is the nth coefficient of the Dirichlet series representation of the symmetric square L-function L(s,sym² f) associated to a primitive form f of level N and of weight k. In this paper, we establish the subconvexity bound: n_sym²f << (k²N²)^40/113n_{\mathrm{sym}^{2}f}\ll(k^{2}N^{2})^{40/113} where the implied constant is absolute.     

ADDITIVE FAMILIES OF INVARIANTS OF SKEWSYMMETRIC TENSORS

Abstract

Let d be a positive integer and F be a field of characteristic 0. Suppose that for each positive integer n, I _n is a polynomial invariant of the usual action of GL_n (F) on Λ^d(Fⁿ), such that for t ? Λ^d(F ^k) and s ? Λ^d(F ^l), I _{k + l} (t l s) = I _k(t)I _t (s), where t ⊥ s is defined in §1.4. Then we say that {I_n} is an additive family of invariants of the skewsymmetric tensors of degree d, or, briefly, an additive family of invariants. If not all the I_n are constant we say that the family is non-trivial. We show that in each even degree d there is a non-trivial additive family of invariants, but that this is not so for any odd d. These results are analogous to those in our paper [3] for symmetric tensors. Our proofs rely on the symbolic method for representing invariants of skewsymmetric tensors. To keep this paper self-contained we expound some of that theory, but for the proofs we refer to the book [2] of Grosshans, Rota and Stein.     

Cylindricity of tangent bundles of strongly parabolic metrics and strongly parabolic surfaces

It is proved that if the intrinsic zero-index of the Sasaki metric of a tangent bundleTM ⁿ isk, thenk is even andM ⁿ is the metric product of a Riemannian manifoldM ^n–k/2 by a Euclidean spaceE ^k/2, whileTM ⁿ is the metric product ofTM ^n–k/2 byE ^k . An expression is obtained for the second fundamental forms of the imbeddingTF ^l TM ⁿ in terms of the second fundamental forms of the imbeddingF ^l M ⁿ and the curvature tensor ofM ⁿ . It is proved thatTF ^l is totally geodesic inTM ⁿ if and only ifF ^l is totally geodesic inM ⁿ .Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 12–32.     

Extremal Regular Graphs with Prescribed Odd Girth

The odd girth of a graph G gives the length of a shortest odd cycle in G. Let ƒ(k, g) denote the smallest n such that there exists a k-regular graph of order n and odd girth g. It is known that ƒ(k, g) ≥ kg/2 and that ƒ(k, g) = kg/2 if k is even. The exact values of ƒ(k, g) are also known if k = 3 or g = 5. Let x_e denote the smallest even integer no less than x, δ(g) = (−1)^{g − 1}/2, and s(k) = min {p + q | k = pq, where p and q are both positive integers}. It is proved that if k ≥ 5 and g ≥ 7 are both odd, then [formula] with the exception that ƒ(5, 7) = 20.     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.