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.     

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.     

Linear operators preserving unitarily invariant norms of matrices

Let F_{m × n} be the set of all m × n matrices over the field F = C or R Denote by U_n(F) the group of all n × n unitary or orthogonal matrices according as F = C or F-R. A norm N() on Fm ×n, is unitarily invariant if N(UAV) = N(A): for all A ∈ F _m×n U ∈ U_m(F). and V ∈ U_n(F). We characterize those linear operators TF_{m × n} → F_{m × n}which satisfy N (T(A)) = N(A)for all A ∈ F_{m × n}

for a given unitarily invariant norm N(). It is shown that the problem is equivalent to characterizing those operators which preserve certain subsets in F_{m × n} To develop the theory we prove some results concerning unitary operators on F_{m × n} which are of independent interest.     

Intersections of nest algebras in finite dimensions

If are maximal nests on a finite-dimensional Hilbert space H, the dimension of the intersection of the corresponding nest algebras is at least dim H. On the other hand, there are three maximal nests whose nest algebras intersect in the scalar operators. The dimension of the intersection of two nest algebras (corresponding to maximal nests) can be of any integer value from n to n(n+1)/2, where n=dim H. For any two maximal nests there exists a basis {f₁,f₂,…,f_n} of H and a permutation π such that and where M_i=  span{f₁,f₂,…,f_i} and N_i= span{f_π(1),f_π(2),…,f_π(i)}. The intersection of the corresponding nest algebras has minimum dimension, namely dim H, precisely when π(j)=n−j+1,1jn. Those algebras which are upper-triangular matrix incidence algebras, relative to some basis, can be characterised as intersections of certain nest algebras.     

L2-approximation of real-valued functions with interpolatory constraints

We construct the polynomial p_m,n^* of degree m which interpolates a given real-valued function f L²[a, b] at pre-assigned n distinct nodes and is the best approximant to f in the L₂-sense over all polynomials of degree m with the same interpolatory character. It is shown that the L₂-error p_m,n^* − f → 0 as m → ∞ if f C[a, b].     

A note on linearization of actions of finitely semisimple Hopf algebras on local algebras

Let H be a Hopf algebra over a field k and let H A → A, h a → h.a, be an action of H on a commutative local Noetherian kalgebra (A, m). We say that this action is linearizable if there exists a minimal system x₁, …, x_n of generators of the maximal ideal m such that h.x_i ε kx₁ + …+ kx_n for all h ε H and i = 1, …, n. In the paper we prove that the actions from a certain class are linearizable (see Theorem 4), and we indicate some consequences of this fact.     

A class of solutions to the gossip problem, part III

We complete the study of NOHO-graphs, begun in Parts I and II of this paper. NOHO- graphs correspond to solutions to the gossip problem where No One Hears his Own information. These are graphs with a linear ordering on their edges such that an increasing path exists from each vertex to every other, but from no vertex to itself. We discard the two such graphs with no 2-valent vertices. In Part I, we translated these graphs into quadruples of integer sequences. In Part II, we characterized and enumerated the realizable quadruples and various subclasses of them. In Part III, we eliminate the overcounting of isomorphic graphs and obtain recurrence relations and generating functions to enumerate the non-isomorphic NOHO-graphs. If u_m=(1,1,2,…) satisfies u_m=3u_m-1–u_m-3, then the number of non-isomorphic NOHO- graphs on 2m+2 vertices is (u_m + u_[m/2]+1 + u_[m/2]+1 - u_[m/2]). We also examine some re lated questions.     

Some explicit formulas for the polynomial decomposition of the matrix exponential and applications

This paper is devoted to the study of some formulas for polynomial decomposition of the exponential of a square matrix A. More precisely, we suppose that the minimal polynomial M_A(X) of A is known and has degree m. Therefore, e^tA is given in terms of P₀(A),…,P_m−1(A), where the P_j(A) are polynomials in A of degree less than m, and some explicit analytic functions. Examples and applications are given. In particular, the two cases m=5 and m=6 are considered.     

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.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.     

Compatibilité entre structures d''intervalles et relations d''orde

Compatibility between interval structures and partial orderings.

If H=(X,E) is a hypergraph, n the cardinality of X,I_n the ordered set {1..n} and < an order relation on X, we call F(X,<) the set of the one-to-one functions from X to I_n which are compatible with <. If AI_n we denote by (A) the length of the smallest interval of I_n which contains A.

We first deal with the following problem: Find ƒF(X,<) which minimise . The a_e, eR are positive coefficients.

This problem can be understood as a scheduling problem and is checked to be NP-complete. We learn how to recognize in polynomial time those hypergraphs H=(X,E) which induce an optimal value of z min equal to .

Next we work on a dual question which arises about interval graphs, when some partial orderings on the vertex set of these graphs intend to represent inclusion, overlapping or anteriority relations between closed intervals of the real line.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

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.     

ContributionsTriangular embeddings of Kn−Km with unboundedly large m

The author has proposed methods of constructing index 2 and 3 current graphs generating triangular embeddings of graphs K_n−K_m with unboundedly large m (as n increases). As a result, triangular embeddings of graphs of many families of graphs K_n−K_m with unboundedly large m were constructed. The paper gives a survey of these results and a short explanation of the methods.     

Almost perfect matchings in random uniform hypergraphs

We consider the following model H_r(n, p) of random r-uniform hypergraphs. The vertex set consists of two disjoint subsets V of size | V | = n and U of size | U | = (r − 1)n. Each r-subset of V × (_r−1^U) is chosen to be an edge of H ε H_r(n, p) with probability p = p(n), all choices being independent. It is shown that for every 0 < < 1 if P = (C ln n)/n^r−1 with C = C() sufficiently large, then almost surely every subset V₁ V of size | V₁ | = (1 − )n is matchable, that is, there exists a matching M in H such that every vertex of V₁ is contained in some edge of M.     

Induced subgraphs of given sizes

We say (n, e) → (m, f), an (m, f) subgraph is forced, if every n-vertex graph of size e has an m-vertex spanned subgraph with f edges. For example, as Turán proved, (n,e)→(k,(^k₂)) for e> t_{k − 1}(n) and (n,e) (^k₂)), otherwise. We give a number of constructions showing that forced pairs are rare. Using tools of extremal graph theory we also show infinitely many positive cases. Several problems remain open.     

Weight distribution of the bases of a binary matroid

Let M be a weighted binary matroid and w₁ < … < w_m be the increasing sequence of all possible distinct weights of bases of M. We give a sufficient condition for the property that w₁, …, w_m is an arithmetical progression of common difference d. We also give conditions which guarantee that w_i+1 − w_i ≤ d, 1 ≤ i ≤ m −1. Dual forms for these results are given also.     

The space localization of unbounded boundary perturbations in nonlinear heat conduction with transfer

We consider the nonlinear parabolic equation u_t = (k(u)u_x)_x + b(u)_x, where u = u(x, t, x ε R¹, t > 0; k(u) ≥ 0, b(u) ≥ 0 are continuous functions as u ≥ 0, b (0) = 0; k, b > 0 as u > 0. At t = 0 nonnegative, continuous and bounded initial value is prescribed. The boundary condition u(0, t) = Ψ(t) is supposed to be unbounded as t → +∞. In this paper, sufficient conditions for space localization of unbounded boundary perturbations are found. For instance, we show that nonlinear equation u_t = (uⁿu_x)_x + (u^β)_x, n ≥ 0, β >; n + 1, exhibits the phenomenon of “inner boundedness,” for arbitrary unbounded boundary perturbations.