Error bounds on the power method for determining the largest eigenvalue of a symmetric, positive definite matrix

Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ₁. We consider the power method, i.e. that of choosing a vector v₀ and setting v_k = A^kv₀; then the Rayleigh quotients R_k = (Av_k, v_k)/(v_k, v_k) usually converge to λ₁ as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close R_k is to λ₁. They are both based on a bound on λ₁ − R_k involving the difference of two consecutive Rayleigh quotients and a quantity ω_k. While we do not know how to directly calculate ω_k, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ₁ − R_k which is proportional to (λ₂/λ₁)^2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ).     

The Hoffman number of a graph

For a connected graph G with n vertices, let {λ₁,λ₂,…,λ_r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ(G) of G is defined by μ(G)=λ₁λ₂…λ_r/n. In this paper, we study some properties and applications of the Hoffman number.     

Changing cofinalities and collapsing cardinals in models of set theory

If a˜cardinal κ₁, regular in the ground model M, is collapsed in the extension N to a˜cardinal κ₀ and its new cofinality, ρ, is less than κ₀, then, under some additional assumptions, each cardinal λ>κ₁ less than cc(P(κ₁)/[κ₁]^<κ₁) is collapsed to κ₀ as well. If in addition N=M[f], where f : ρ→κ₁ is an unbounded mapping, then N is a˜|λ|=κ₀-minimal extension. This and similar results are applied to generalized forcing notions of Bukovský and Namba.     

Poisson evolution in word selection

This paper presents the finding that the invocation of new words in human language samples is governed by a slowly changing Poisson process. The time dependent rate constant for this process has the form

λ(t) = λ₁(1−λ₂t)e^-λ₂t+λ₃(1−λ₄t)e^-λ₄t+λ₅

, where

λ_i > 0, I=1,…,5

.

This form implies that there are opening, middle and final phases to the introduction of new words, each distinguished by a dominant rate constant, or equivalently, rate of decay. With the occasional exception of the phase transition from beginning to middle, the rate λ(t) decays monotonically. Thus, λ(t) quantifies how the penchant of humans to introduce new words declines with the progression of their narratives, written or spoken.     

Two theorems on Euclidean distance matrices and Gale transform

We present a characterization of those Euclidean distance matrices (EDMs) D which can be expressed as D=λ(E−C) for some nonnegative scalar λ and some correlation matrix C, where E is the matrix of all ones. This shows that the cones

where is the elliptope (set of correlation matrices) and is the (closed convex) cone of EDMs.

The characterization is given using the Gale transform of the points generating D. We also show that given points , for any scalars λ₁,λ₂,…,λ_n such that

∑_j=1ⁿλ_jp^j=0, ∑_j=1ⁿλ_j=0,

we have

∑_j=1ⁿλ_jpⁱ−p^j2= forall i=1,…,n,

for some scalar independent of i.     

A two-sided estimate in the Hsu-Robbins-Erdös law of large numbers

Let X₁, X₂, … be independent identically distributed random variables. Then, Hsu and Robbins (1947) together with Erdös (1949, 1950) have proved that

,

if and only if E[X²₁] < ∞ and E[X₁] = 0. We prove that there are absolute constants C₁, C₂ (0, ∞) such that if X₁, X₂, … are independent identically distributed mean zero random variables, then

c₁λ⁻² E[X₁²·1_{|X1|λ}]S(λ)C₂λ⁻² E[X₁²·1_{|X1|λ}]

,

for every λ > 0.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

The reflection length of a transformation in the unitary group over a finite field

Let U be the unitary group over a finite field K where [K]≠3 and char K≠2. Every transformation π in U with detπ = ±1 is a product of reflections. We determine the length t of every such transformation π i.e. for each π we find reflections σ_i in U such that π=σ₁ σ_t and so that no factorization of π into fewer than t reflections exists.     

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.     

Oscillation criteria for a class of nonlinear system of differential equations

Using the integral average method, we establish some oscillation criteria of Kamenev type and Yan type for the nonlinear system of differential equation

where the functions b_i(t) (i = 1, 2) are nonnegative and summable on each finite segment of the interval Z0, ∞), λ_i > 0 (i = 1,2) with λ₁ λ₂ = 1.     

ContributionsSign-balanced covering matrices

A q × n array with entries from 0, 1,…,q − 1 is said to form a difference matrix if the vector difference (modulo q) of each pair of columns consists of a permutation of [0, 1,… q − 1]; this definition is inverted from the more standard one to be found, e.g., in Colbourn and de Launey (1996). The following idea generalizes this notion: Given an appropriate δ (-[−1, 1]^t, a λq × n array will be said to form a (t, q, λ, Δ) sign-balanced matrix if for each choice C₁, C₂,…, C_t of t columns and for each choice = (₁,…,_t) Δ of signs, the linear combination ∑_j=1^t _jC_j contains (mod q) each entry of [0, 1,…, q − 1] exactly λ times. We consider the following extremal problem in this paper: How large does the number k = k(n, t, q, λ, δ) of rows have to be so that for each choice of t columns and for each choice (₁, …, _t) of signs in δ, the linear combination ∑_j=1^t _jC_j contains each entry of [0, 1,…, q t- 1] at least λ times? We use probabilistic methods, in particular the Lovász local lemma and the Stein-Chen method of Poisson approximation to obtain general (logarithmic) upper bounds on the numbers k(n, t, q, λ, δ), and to provide Poisson approximations for the probability distribution of the number W of deficient sets of t columns, given a random array. It is proved, in addition, that arithmetic modulo q yields the smallest array - in a sense to be described.     

Constructions of (q, K, λ, t, Q) almost difference families

The concept of a (q, k, λ, t) almost difference family (ADF) has been introduced and studied by C. Ding and J. Yin as a useful generalization of the concept of an almost difference set. In this paper, we consider, more generally, (q, K, λ, t, Q)-ADFs, where K = {k₁, k₂, ..., k_r} is a set of positive integers and Q = (q₁, q₂,..., q_r) is a given block-size distribution sequence. A necessary condition for the existence of a (q, K, λ, t, Q)-ADF is given, and several infinite classes of (q, K, λ, t, Q)-ADFs are constructed.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

Sometimes slow growing is fast growing

The slow growing hierarchy is commonly defined as follows: G₀(x) = 0, G_x−1(x) := G_x(x) + 1 and G_λ(x) := G_λ[x](x) where λ<₀ is a limit and ·[·]:₀∩ Lim × ω → ₀ is a given assignment of fundamental sequences for the limits below ₀. The first obvious question which is encountered when one looks at this definition is: How does this hierarchy depend on the choice of the underlying system of fundamental sequences? Of course, it is well known and easy to prove that for the standard assignment of fundamental sequence the hierarchy (G_x)_x<0 is slow growing, i.e. each G_x is majorized by a Kalmar elementary recursive function.

It is shown in this paper that the slow growing hierarchy (G_x)_x<0 — when it is defined with respect to the norm-based assignment of fundamental sequences which is defined in the article by Cichon (1992, pp. 173–193) — is actually fast growing, i.e. each PA-provably recursive function is eventually dominated by G_x for some <₀. The exact classification of this hierarchy, i.e. the problem whether it is slow or fast growing, has been unsolved since 1992. The somewhat unexpected result of this paper shows that the slow growing hierarchy is extremely sensitive with respect to the choice of the underlying system of fundamental sequences.

The paper is essentially self-contained. Only little knowledge about ordinals less than ₀ — like the existence of Cantor normal forms, etc. and the beginnings of subrecursive hierarchy theory as presented, for example, in the 1984 textbook of Rose — is assumed.     

New constructions of divisible designs

A construction is given for a (p^2a(p+1),p²,p^2a+1(p+1),p^2a+1,p^2a(p+1)) (p a prime) divisible difference set in the group H×Z²_pa+1 where H is any abelian group of order p+1. This can be used to generate a symmetric semi-regular divisible design; this is a new set of parameters for λ₁≠0, and those are fairly rare. We also give a construction for a (p^a−1+p^a−2+…+p+2,p^a+2, p^a(p^a+p^a−1+…+p+1), p^a(p^a−1+…+p+1), p^a−1(p^a+…+p²+2)) divisible difference set in the group H×Z_p2×Z^a_p. This is another new set of parameters, and it corresponds to a symmetric regular divisible design. For p=2, these parameters have λ₁=λ₂, and this corresponds to the parameters for the ordinary Menon difference sets.     

An extremal problem on potentially Kr,s-graphic sequences

We consider a variation of a classical Turán-type extremal problem (F. Chung, R. Graham, Erd s on Graphs: His Legacy of Unsolved Problems, AK Peters Ltd., Wellesley, 1998, Chapter 3) as follows: Determine the smallest even integer σ(K_r,s,n) such that every n-term graphic sequence π=(d₁,d₂,…,d_n) with term sum σ(π)=d₁+d₂++d_nσ(K_r,s,n) is potentially K_r,s-graphic, where K_r,s is a r×s complete bipartite graph, i.e., π has a realization G containing K_r,s as its subgraph. In this paper, we first give sufficient conditions for a graphic sequence being potentially K_r,s-graphic, and then we determine σ(K_r,r,n) for r=3,4.     

On the minor-minimal 2-connected graphs having a fixed minor

Let H be a graph with κ₁ components and κ₂ blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ₁−1)+β(κ₂−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.     

Strong equality of domination parameters in trees

We study the concept of strong equality of domination parameters. Let P₁ and P₂ be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P₂ also has property P₁. Let ψ₁(G) and ψ₂(G), respectively, denote the minimum cardinalities of sets with properties P₁ and P₂, respectively. Then ψ₁(G)ψ₂(G). If ψ₁(G)=ψ₂(G) and every ψ₁(G)-set is also a ψ₂(G)-set, then we say ψ₁(G) strongly equals ψ₂(G), written ψ₁(G)≡ψ₂(G). We provide a constructive characterization of the trees T such that γ(T)≡i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T)=γ_t(T), where γ_t(T) denotes the total domination number of T, is also presented.     

On the area of the intersection of disks in the plane

Let C₁,…, C_n and C′₁,…, C′_n be two collections of equal disks in the plane, with centers c₁,…, c_n and c′₁,…, c′_n. According to a well-known conjecture of Klee and Wagon (1991), if |c_i − c_j| ≥ |c′_i − c′_j| for all i, j, then Area(∩_i C_i) ≤ Area(∩_i C′_i).

We prove this statement in the special case when there is a continuous contraction of {c₁,…, c_n} onto {c′₁,…, c′_n}.