Partition of a directed bipartite graph into two directed cycles

Let D = (V₁, V₂; A) be a directed bipartite graph with |V₁| = |V₂| = n 2. Suppose that d_D(x) + d_D(y) 3n + 1 for all x ε V₁ and y ε V₂. Then D contains two vertex-disjoint directed cycles of lengths 2n₁ and 2n₂, respectively, for any positive integer partition n = n₁ + n₂. Moreover, the condition is sharp for even n and nearly sharp for odd n.     

On Lyapunov scaling factors of real symmetric matrices

A necessary and sufficient condition for the identity matrix to be the unique Lyapunov scaling factor of a given real symmetric matrix A is given. This uniqueness is shown to be equivalent to the uniqueness of the identity matrix as a scaling D for which the kernels of A and AD are identical.     

Flat portions on the boundary of the numerical ranges of certain Toeplitz matrices

We give criterions for a flat portion to exist on the boundary of the numerical range of a matrix. A special type of Teoplitz matrices with flat portions on the boundary of its numerical range are constructed. We show that there exist 2 × 2 nilpotent matrices A₁,A₂, an n  × n nilpotent Toeplitz matrix N_n, and an n  × n cyclic permutation matrix S_n(s) such that the numbers of flat portions on the boundaries of W(A₁⊕N_n) and W(A₂⊕S_n(s)) are, respectively, 2(n - 2) and 2n.     

A characterization on n-critical economical generalized tic-tac-toe games

There is a so called generalized tic-tac-toe game playing on a finite set X with winning sets A₁, A₂,…, A_m. Two players, F and S, take in turn a previous untaken vertex of X, with F going first. The one who takes all the vertices of some winning set first wins the game. Erd s and Selfridge proved that if |A₁|=|A₂|==|A_m|=n and m<2ⁿ⁻¹, then the game is a draw. This result is best possible in the sense that once m=2ⁿ⁻¹, then there is a family A₁, A₂,…, A_m so that F can win. In this paper we characterize all those sets A₁,…, A_2n−1 so that F can win in exactly n moves. We also get similar result in the biased games.     

On controllability of partially prescribed matrices

Let A₁and A₂be matrices of sizes m×m and m×n, respectively. Suppose that some of the entries under the main diagonal of A₁ are unknown and all the other entries of [A₁ A₂] are constant. We study the existence of a completely controllable completion of (A₁,A₂) and generalize a previous result on the same problem.     

Ranks of Solutions of the Matrix Equation AXB = C

The purpose of this article is to solve two problems related to solutions of a consistent complex matrix equation AXB = C : (I) the maximal and minimal ranks of solution to AXB = C , and (II) the maximal and minimal ranks of two real matrices X₀ and X₁ in solution X = X₀ + iX₁ to AXB = C . As applications, the maximal and minimal ranks of two real matrices C and D in generalized inverse (A + iB)^- = C + iD of a complex matrix A + iB are also examined.     

Equality of higher numerical ranges of matrices and a conjecture of Kippenhahn on Hermitian pencils

Let M_n be the algebra of all n × n complex matrices. For 1 k n, the kth numerical range of A M_n is defined by W_k(A) = (1/k)∑_j^k=1x_j^*Ax_j : x₁, …, x_k is an orthonormal set in ⁿ]. It is known that tr A/n = W_n(A) W_n−1(A) W₁(A). We study the condition on A under which W_m(A) = W_k(A) for some given 1 m < k n. It turns out that this study is closely related to a conjecture of Kippenhahn on Hermitian pencils. A new class of counterexamples to the conjecture is constructed, based on the theory of the numerical range.     

On the fourth power moment of Fourier coefficients of cusp form

Let a(n)be the Fourier coefficients of a holomorphic cusp form of weightκ=2n≥12 for the full modular group and A(x)=∑_(n≤x)a(n).In this paper,we establish an asymptotic formula of the fourth power moment of A(x)and prove that ∫T1A~4(x)dx=3/(64κπ~4)s_4;2()T~(2κ)+O(T~(2κ-δ_4+ε))with δ_4=1/8,which improves the previous result.     

Generalized equivalence of pairs of matrices

Pairs (A₁B₁) and (A₂B₂) of matrices over a principal ideal domain R are called the generalized equivalent pairs if A₂=UA₁V₁B₂=UB₁V₂ for some invertible matrices UV₁V₂ over R. A special form is established to which a pair of matrices can be reduced by means of generalized equivalent transformations. Besides necessary and sufficient conditions are found, under which a pair of matrices is generalized equivalent to a pair of diagonal matrices. Applications are made to study the divisibility of matrices and multiplicative property of the Smith normal form.     

A theorem of the alternatives for the equation Ax + B|x| = b

The following theorem is proved: given square matrices A, D of the same size, D nonnegative, then either the equation Ax + B|x| = b has a unique solution for each B with |B| ≤ D and for each b, or the equation Ax + B₀|x| = 0 has a nontrivial solution for some matrix B₀ of a very special form, |B₀| ≤ D; the two alternatives exclude each other. Some consequences of this result are drawn. In particular, we define a λ to be an absolute eigenvalue of A if |Ax| = λ|x| for some x ≠ 0, and we prove that each square real matrix has an absolute eigenvalue.     

Pancyclic orderings of in-tournaments

An in-tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. In this paper, pancyclic orderings of a strong in-tournament D are investigated. This is a labeling, say x₁,x₂,…,x_n, of the vertex set of D such that D[{x₁,x₂,…,x_t}] is Hamiltonian for t=3,4,…,n. Moreover, we consider the related problem on weak pancyclic orderings, where the same holds for t4 and x₁ belongs to an arbitrary oriented 3-cycle. We present sharp lower bounds for the minimum indegree ensuring the existence of a pancyclic or a weak pancyclic ordering in strong in-tournaments.     

The solvability of two linear matrix equations

The solvability conditions of the following two linear matrix equations (i)A₁X₁B₁+A₂X₂B₂+A₃X₃B₃=C,(ii) A₁XB₁=C₁A₂XB₂=C₂ are established using ranks and generalized inverses of matrices. In addition, the duality of the three types of matrix equations

(iii) A₁X₁B₁+A₂X₂B₂+A₃X₃B₃+A₄X₄B₄=C, (iv) A₁XB₁=C₁A₂XB₂=C₂A₃XB₃=C₃A₄XB₄=C₄, (v) AXB+CXD=E are also considered.     

Gowers norms and pseudorandom measures of subsets

Let $A \subset {{\Bbb Z}_N}$, and ${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$ We define the pseudorandom measure of order k of the subset A as follows, P_k(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$f_A(n + c₁)f_A(n + c₂) … f_A(n + c_k)|, where the maximum is taken over all D = (c₁, c₂, . . . , c_k) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c₁ < c₂ < … < c_k ≤ N - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if P_k(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4, and lcm(a₁, a₂, . . . , a_l) denotes the least common multiple of a₁, a₂, . . . , a_l.     

On generalized Boolean functions II

This cycle of papers is based on the concept of generalized Bolean functions introduced by the author in the first article of the series. Every generalized Boolean function f:Bⁿ→B can be written in a manner similar to the canonical disjunctive form using some function defined on A×B, where A is a finite subset of B containing 0 and 1. The set of those functions f is denoted by GBF_n[A]. In this paper the following questions are presented: (1) What is the relationship between GBF_n[A₁] and GBF_n[A₂] when A₁A₂. (2) What can be said about GBF_n[A₁∩A₂] and GBF_n[A₁A₂] in comparison with GBF_n[A₁]∩GBF_n[A₂] and GBF_n[A₁]GBF_n[A₂], respectively.     

Krylov subspace methods for eigenvalues with special properties and their analysis for normal matrices

In this paper we propose a general approach by which eigenvalues with a special property of a given matrix A can be obtained. In this approach we first determine a scalar function ψ: C → C whose modulus is maximized by the eigenvalues that have the special property. Next, we compute the generalized power iterations uinj + 1 = ψ(A)u_j, j = 0, 1,…, where u₀ is an arbitrary initial vector. Finally, we apply known Krylov subspace methods, such as the Arnoldi and Lanczos methods, to the vector u_n for some sufficiently large n. We can also apply the simultaneous iteration method to the subspace span{x⁽ⁿ⁾₁,…,x⁽ⁿ⁾_k} with some sufficiently large n, where x^(j+1)_m = ψ(A)x^(j)_m, j = 0, 1,…, m = 1,…, k. In all cases the resulting Ritz pairs are approximations to the eigenpairs of A with the special property. We provide a rather thorough convergence analysis of the approach involving all three methods as n → ∞ for the case in which A is a normal matrix. We also discuss the connections and similarities of our approach with the existing methods and approaches in the literature.     

Bounds on codes over an alphabet of five elements

We consider the problem of finding bounds and exact values of A₅(n,d) — the maximum size of a code of length n and minimum distance d over an alphabet of 5 elements. Using a wide variety of constructions and methods, a table of bounds on A₅(n,d) for n11 is obtained.     

Loopless generation of up–down permutations

An up–down permutation P=(p₁,p₂,…,p_n) is a permutation of the integers 1 to n which satisfies constraints specified by a sequence C=(c₁,c₂,…,c_n−1) of U's and D's of length n−1. If c_i is U then p_i<p_i+1 otherwise p_i−1>p_i. A loopless algorithm is developed for generating all the up–down permutations satisfying any sequence C. Ranking and unranking algorithms are discussed.     

A matrix problem associated with computing Cohen-Macaulay type

Suppose A∈M_n×m(F), B∈M_n×t(F) for some field F. Define Г(AB) to be the set of n×n diagonal matrices D such that the column space of DA is contained in the column space of B. In this paper we determine dim Г(AB). For matrices AB of the same rank we provide an algorithm for computing dim Г(AB).     

On Mills's conjecture on matroids with many common bases

In this paper, we shall prove a conjecture of Mills: for two (k+1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n₁ circuit-hyperplanes and from the other by relaxing n₂ circuit-hyperplanes, where n₁ and n₂ are non-negative integers such that n₁+n₂k