The inverse M-matrix problem

One aspect of the inverse M-matrix problem can be posed as follows. Given a positive n × n matrix A=(a_ij) which has been scaled to have unit diagonal elements and off-diagonal elements which satisfy 0 < y ? a_ij ? x < 1, what additional element conditions will guarantee that the inverse of A exists and is an M-matrix? That is, if A^?1=B=(b_ij), then b_ii> 0 and b_ij ? 0 for i≠_j. If n=2 or x=y no further conditions are needed, but if n ? 3 and y < x, then the following is a tight sufficient condition. Define an interpolation parameter s via x²=sy+(1?s)y²; then B is an M-matrix if s^?1 ? n?2. Moreover, if all off-diagonal elements of A have the value y except for a_ij=a_jj=x when i=n?1, n and 1 ? _j ? n?2, then the condition on both necessary and sufficient for B to be an M-matrix.     

On a problem of P. Erdös

Let n be a positive integer and let A = {a₁,…, a_s}, B = {b₁,…, b_t} be two sets of positive integers such that the product set consists of st distinct numbers. Then, for a certain positive constant c, $\text{st ≤ c}\text{n}{}^2\text{log}\text{n}$, establishing a conjecture made by P. Erdös.     

An upper bound for Cubicity in terms of Boxicity

An axis-parallel b-dimensional box is a Cartesian product R₁×R₂×?×R_b where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,b_i] on the real line. The boxicity of any graph G, is the minimum positive integer b such that G can be represented as the intersection graph of axis-parallel b-dimensional boxes. A b-dimensional cube is a Cartesian product R₁×R₂×?×R_b, where each R_i (for 1≤i≤b) is a closed interval of the form [a_i,a_i+1] on the real line. When the boxes are restricted to be axis-parallel cubes in b-dimension, the minimum dimension b required to represent the graph is called the cubicity of the graph (denoted by ). In this paper we prove that , where n is the number of vertices in the graph. We also show that this upper bound is tight.Some immediate consequences of the above result are listed below:

1.

Planar graphs have cubicity at most 3⌈log₂n⌉.

2.

Outer planar graphs have cubicity at most 2⌈log₂n⌉.

3.

Any graph of treewidth tw has cubicity at most (tw+2)⌈log₂n⌉. Thus, chordal graphs have cubicity at most (ω+1)⌈log₂n⌉ and circular arc graphs have cubicity at most (2ω+1)⌈log₂n⌉, where ω is the clique number.

The above upper bounds are tight, but for small constant factors.     

On diagonal products of doubly stochastic matrices

The following result is proved: If A and B are distinct n × n doubly stochastic matrices, then there exists a permutation σ of {1, 2,…, n} such that ∏_ia_iσ(i) > ∏_ib_iσ(i).     

Block partitions of sequences

Given a sequence A = (a ₁, …, a _n ) of real numbers, a block B of A is either a set B = {a _i , a _i+1, …, a _j } where i ≤ j or the empty set. The size b of a block B is the sum of its elements. We show that when each a _i ∈ [0, 1] and k is a positive integer, there is a partition of A into k blocks B ₁, …, B _k with |b _i ?b _j | ≤ 1 for every i, j. We extend this result in several directions.     

Singular values, norms, and commutators

Let and X_i, i=1,…,n, be bounded linear operators on a separable Hilbert space such that X_i is compact for i=1,…,n. It is shown that the singular values of are dominated by those of , where ‖·‖ is the usual operator norm. Among other applications of this inequality, we prove that if A and B are self-adjoint operators such that a₁?A?a₂ and b₁?B?b₂ for some real numbers and b₂, and if X is compact, then the singular values of the generalized commutator AX-XB are dominated by those of max(b₂-a₁,a₂-b₁)(X⊕X). This inequality proves a recent conjecture concerning the singular values of commutators. Several inequalities for norms of commutators are also given.     

Construction of a Jacobi matrix from spectral data

A proof is given for the existence and uniqueness of a correspondence between two pairs of sequences {a},{b} and {ω},{μ}, satisfying b_i>0 for i=1,…,n?1 and ω₁<μ₁<?<μ_n?1<ω_n, under which the symmetric Jacobi matrices J(n,a,b) and J(n?1,a,b) have eigenvalues {ω} and {μ} respectively. Here J(m,a,b) is symmetric and tridiagonal with diagonal elements a_i (i=1,…,m) and off diagonal elements b_i (i=1,…,m?1). A new concise proof is given for the known uniqueness result. The existence result is new.     

A note on scheduling identical coupled tasks in logarithmic time

The coupled tasks problem consists in scheduling n jobs on a single machine. Each job i is made of two operations with processing times a_i and b_i and a fixed required delay L_i between them. Operations cannot overlap in time but operations of different jobs can be interleaved. The objective is to minimize the makespan of the schedule. In this note we show that the problem with identical jobs (∀i,a_i=a,b_i=b,L_i=L) can be solved in O(logn) time when a,b,L are fixed. This problem is motivated by radar scheduling applications where tasks corresponding to transmitting radiowaves and listening to potential echoes are coupled.     

On bounds for eigenvalues of real symmetric matrices

Let A=(a_ij) be a real symmetric matrix of order n. We characterize all nonnegative vectors x=(x₁,...,x_n) and y=(y₁,...,y_n) such that any real symmetric matrix B=(b_ij), with b_ij=a_ij, i≠jhas its eigenvalues in the union of the intervals [b_ij?y_i, b_ij+ x_i]. Moreover, given such a set of intervals, we derive better bounds for the eigenvalues of B using the 2n quantities {b_ii?y, b_ii+x_i}, i=1,..., n.     

Approximating reversal distance for strings with bounded number of duplicates

For a string A=a₁…a_n, a reversalρ(i,j), 1?i?j?n, transforms the string A into a string A^′=a₁…a_i-1a_ja_j-1…a_ia_j+1…a_n, that is, the reversal ρ(i,j) reverses the order of symbols in the substring a_i…a_j of A. In the case of signed strings, where each symbol is given a sign + or -, the reversal operation also flips the sign of each symbol in the reversed substring. Given two strings, A and B, signed or unsigned, sorting by reversals (SBR) is the problem of finding the minimum number of reversals that transform the string A into the string B.Traditionally, the problem was studied for permutations, that is, for strings in which every symbol appears exactly once. We consider a generalization of the problem, k-SBR, and allow each symbol to appear at most k times in each string, for some k?1. The main result of the paper is an O(k²)-approximation algorithm running in time O(n). For instances with , this is the best known approximation algorithm for k-SBR and, moreover, it is faster than the previous best approximation algorithm.     

Least squares solutions to AX = B for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation

A matrix A∈R^n×n is called a bisymmetric matrix if its elements a_i,j satisfy the properties a_i,j=a_j,i and a_i,j=a_n-j+1,n-i+1 for 1?i,j?n. This paper considers least squares solutions to the matrix equation AX=B for A under a central principal submatrix constraint and the optimal approximation. A central principal submatrix is a submatrix obtained by deleting the same number of rows and columns in edges of a given matrix. We first discuss the specified structure of bisymmetric matrices and their central principal submatrices. Then we give some necessary and sufficient conditions for the solvability of the least squares problem, and derive the general representation of the solutions. Moreover, we also obtain the expression of the solution to the corresponding optimal approximation problem.     

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.     

Fast canonization of circular strings

A circular string A = (a₁,…,a_n) is a string that has n equivalent linear representations A_i = a_i,…,a_n,a₁,…,a_i?1 for i = 1,…,n. The a_i's are assumed to be well ordered. We say that A_i < A_j if the word a_i…a_na₁…a_i?1 precedes the word a_j…a_na₁…a_j?1 in the lexicographic order, A_i ? A_j if either A_i < A_j or A_i = A_j. A_i0 is a minimal representation of A if A_i0 ? A_i for all 1 ≤ i ≤ n. The index i₀ is called a minimal starting point (m.s.p.). In this paper we discuss the problem of finding m.s.p. of a given circular string. Our algorithm finds, in fact, all the m.s.p.'s of a given circular string A of length n by using at most $\text{n + ?}\text{d}\text{2}\text{?}$ comparisons. The number d denotes the difference between two successive m.s.p.'s (see Lemma 1.1) and is equal to n if A has a unique m.s.p. Our algorithm improves the result of 3n comparisons given by K. S. Booth. Only constant auxiliary storage is used.     

On a question of Sárközy on gaps of product sequences

Motivated by a question of Sárközy, we study the gaps in the product sequence B = A · A = {b ₁ < b ₂ < …} of all products a _i a _j with a _i , a _j ∈ A when A has upper Banach density α > 0. We prove that there are infinitely many gaps b _n+1 ? b _n ? α ^?3 and that for t ≥ 2 there are infinitely many t-gaps b _n+t ? b _n ? t ² α ^?4. Furthermore, we prove that these estimates are best possible.We also discuss a related question about the cardinality of the quotient set A/A = {a _i /a _j , a _i , a _j ∈ A} when A ? {1, …, N} and |A| = αN.     

Quasi sure quadratic variation of local times of smooth semimartingales

In this paper, we prove that the process of the quadratic variation of local times of smooth semimartingales can be constructed as the quasi sure limit of the form ∑_Δn(L_t^a_i+1n−L_t^a_in)², where Δ_n=(a_iⁿ,a_i+1ⁿ) is a sequence of subdivisions of [a,b], a_iⁿ=i(b−a)/2ⁿ+a, i=0,1,…,2ⁿ.     

Asymptotic behavior of solutions of the functional differential equation x′(t) = Ax(λt) + Bx(t), λ>0

The author discusses the asymptotic behavior of the solutions of the functional differential equation x′(t) = Ax(λt) + Bx(t), λ>0 (1) where x(t) is an n-dimensional column vector and A, B are n × n matrices with complex constant entries. He obtains the following results for the case 0 < λ < 1: (i) If B is diagonalizable with eigenvalues b_i such that Re b_i < 0 for all i, then there is a constant α such that every solution of (1) is O(t^α) as t → ∞. (ii) If B is diagonalizable with eigenvalues b_i such that 0 < Re b₁ ? Re b₂ ? ··· ? Re b_n and λ times Re b_n < Re b₁, then every solution of (1) is O(e^bn^t) as t → ∞. For the case λ>1, he has the following results: (i) If B is diagonalizable with eigenvalues b_i such that Re b_i>0 for all i, then there is a constant α such that no solution x(t) of (1), except the identically zero solution, is 0(t^α) as t → ∞. (ii) If B is diagonalizable with eigenvalues b_i such that Re b₁ ? Re b₂ ? ··· ? Re b_n < 0 and λ Re b_n < Re b₁, then no solution x(t) of (1), except the identically zero solution, is 0(e^b1^t) as t → ∞.     

The characteristic polynomial of a principal subpencil of a Hermitian matrix pencil

Given n-square Hermitian matrices A,B, let A_i,B_i denote the principal (n?1)- square submatrices of A,B, respectively, obtained by deleting row i and column i. Let μ, λ be independent indeterminates. The first main result of this paper is the characterization (for fixed i) of the polynomials representable as det(μA_i?λB_i) in terms of the polynomial det(μA?λB) and the elementary divisors, minimal indices, and inertial signatures of the pencil μA?λB. This result contains, as a special case, the classical interlacing relationship governing the eigenvalues of a principal sub- matrix of a Hermitian matrix. The second main result is the determination of the number of different values of i to which the characterization just described can be simultaneously applied.     

Small divisors of Bernoulli sums

Let ?= {?_i,i ≥1} be a sequence of independent Bernoulli random variables (P{?_i = 0} = P{?_i = 1 } = 1/2) with basic probability space (Ω, A, P). Consider the sequence of partial sums B_n=?₁+...+?_n, n=1,2..... We obtain an asymptotic estimate for the probability P{P^-(B_n) > >} for >≤n^{e/log log n}, c a positive constant.     

An all-substrings common subsequence algorithm

Given two strings A and B of lengths n_a and n_b, n_a?n_b, respectively, the all-substrings longest common subsequence (ALCS) problem obtains, for every substring B^′ of B, the length of the longest string that is a subsequence of both A and B^′. The ALCS problem has many applications, such as finding approximate tandem repeats in strings, solving the circular alignment of two strings and finding the alignment of one string with several others that have a common substring. We present an algorithm to prepare the basic data structure for ALCS queries that takes O(n_an_b) time and O(n_a+n_b) space. After this preparation, it is possible to build a matrix of size that allows any LCS length to be retrieved in constant time. Some trade-offs between the space required and the querying time are discussed. To our knowledge, this is the first algorithm in the literature for the ALCS problem.