Matrix realizations of littlewood—richardson sequences

In this paper we consider the problem of characterizing the invariant factors of three matrices A B, and C, such that AB — C Our matrices have entries over a principal ideal domain or over a local domain. In Section 2 we show that this problem is localizablc

The above problem lias a well-known solution in terms of Littlewood-Richardson sequences. We introduce the concept of a matrix realization of a Littlewood-Richardson sequence. The main result is an explicit construction of a sequence of matrices which realizes a previously given Littlewood Richardson sequence. Our methods offer a matrix theoretical proof of a well-known result of T, Klein on extensions of p-modules.     

The admissible interval for the invariant factors of a product of matrices

It is well known that Littlewood-Richardson sequences give a combinatorial characterization for the invariant factors of a product of two matrices over a principal ideal domain. Given partitions a and c, let LR(a,c) be the set of partitions b for which at least one Littlewood - Richardson sequence of type (a,b,c) exists. I. Zaballa has shown in [20] that LR(a, c) has a minimal element w and a maximal element n, with respect to the order bf majorization, depending only on a and c;. In generalLR(a, c) is not the whole interval [w, n]. Here a combinatorial algorithm is provided for constructing all the elements of LR(a, c). This algorithm consists in starting with the minimal Littlewood-Richardson sequence of shape c/a and successively modifying it until the maximal Littlewood - Richardson sequence of shape c/a is achieved. Also explicit bijections between Littlewood - Richardson sequences of conjugate shape and weight and between Littlewood - Richardson sequences of dual shape and equal weight are presented. The bijections are denned by means of permutations of Littlewood - Richardson sequences.     

Note on a paper of thompson: the congruence numerical range

Given n×n Complex matrices A, Cdefine the C-congruence numerical range of A to be the set [ILM0001]. R.C. Thompson has characterized R_C(A) when [ILM0002] are fixed complex numbers. In this note. we obtain some analogous results about R_t(A) when C is skew symmmetric and a simple proof of the result of Thompson is given.Moreover, we characterize a certain set of partial off diagonals under congruence unitary transformation.     

On the stationary Lp-approximation power to derivatives by radial basis function interpolation

In this paper, we consider approximation to derivatives of a function by using radial basis function interpolation. Most of well-known theories for this problem provide error analysis in terms of the so-called native space, say C_φ. However, if a basis function φ is smooth, the space C_φ is extremely small. Thus, the purpose of this study is to extend this result to functions in the homogenous Sobolev space.     

New upper and lower bounds on the channel capacity of read/write isolated memory

In this paper, we refine upper and lower bounds for the channel capacity of a serial, binary rewritable medium in which no consecutive locations may store 1's and no consecutive locations may be altered during a single rewriting pass. This problem was originally examined by Cohn (Discrete. Appl. Math. 56 (1995) 1) who proved that C, the channel capacity of the memory, in bits per symbol per rewrite, satisfies

0.50913C0.56029 .

In this paper, we show how to model the problem as a constrained two-dimensional binary matrix problem and then modify recent techniques for dealing with such matrices to derive improved bounds of

0.53500C0.55209 .

     

Block matrices over a valuation ring

A result of W. E. Roth, generalized by W. H. Gustafson connecting the matrix equation AX - XB - C, with block diagonal matrices, is adapted to matrices over a complete Valuation Ring. A necessary and sufficient condition for the similarity of a full matrix to a block diagonal matrix is proved.     

Cycle-saturated graphs of minimum size

A graph G is called C_k-saturated if G contains no cycles of length k but does contain such a cycle after the addition of any new edge. Bounds are obtained for the minimum number of edges in C_k-saturated graphs for all k ≠ 8 or 10 and n sufficiently large. In general, it is shown that the minimum is between n + c₁n/k and n + c₂n/k for some positive constants c₁ and C₂. Our results provide an asymptotic solution to a 15-year-old problem of Bollobás.     

Enumeration of irreducible binary words

Overlap free words over two letters are called irreducible binary words. Let d(n) denote the number of irreducible binary words of length n. In this paper we show that there are positive constants C₁ and C₂ such that C₁n^1.155<d(n)<C₂n^1.587 holds for all n>0.     

Some recent results on drazin monotonicty of property n martices

If a square matrix has a nonnegarive power it is called a property-n matrix. In a recent paper [12] Werner derived some interesting necessary and sufficient conditions for a property n property-n matrix to be Drazin-montone. In particular, it was shown that a property -n matrix with ind(A) = k is Drazin-monotone if and only if A^2k+1 is weak-r-monotone. Our principal aim here is to show how this result can he strengthened considerably. To tackle this problem we also present several further results on the structure of Drazin-monotone (property-n) matrices.     

Superfast algorithms for Cauchy-like matrix computations and extensions

An effective algorithm of [M. Morf, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974; in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954–959; R.R. Bitmead and B.D.O. Anderson, Linear Algebra Appl. 34 (1980) 103–116] computes the solution to a strongly nonsingular Toeplitz or Toeplitz-like linear system , a short displacement generator for the inverse T⁻¹ of T, and det T. We extend this algorithm to the similar computations with n×n Cauchy and Cauchy-like matrices. Recursive triangular factorization of such a matrix can be computed by our algorithm at the cost of executing O(nr²log³ n) arithmetic operations, where r is the scaling rank of the input Cauchy-like matrix C (r=1 if C is a Cauchy matrix). Consequently, the same cost bound applies to the computation of the determinant of C, a short scaling generator of C⁻¹, and the solution to a nonsingular linear system of n equations with such a matrix C. (Our algorithm does not use the reduction to Toeplitz-like computations.) We also relax the assumptions of strong nonsingularity and even nonsingularity of the input not only for the computations in the field of complex or real numbers, but even, where the algorithm runs in an arbitrary field. We achieve this by using randomization, and we also show a certain improvement of the respective algorithm by Kaltofen for Toeplitz-like computations in an arbitrary field. Our subject has close correlation to rational tangential (matrix) interpolation under passivity condition (e.g., to Nevanlinna–Pick tangential interpolation problems) and has further impact on the decoding of algebraic codes.     

How many maxima can there be?

Let C be a planar region. Choose n points p₁,,p_nI.I.D. from the uniform distribution over C. Let M^C_n be the number of these points that are maximal. If C is convex it is known that either E(M^C_n)=Θ(√n)> or E(M^C_n)=O(log n). In this paper we will show that, for general C, there is very little that can be said, a-priori, about E(M^C_n). More specifically we will show that if g is a member of a large class of functions then there is always a region C such that E(M^C_n)=Θ(g(n)). This class contains, for example, all monotically increasing functions of the form g(n)= nln^βn, where 0<<1 and β0. This class also contains nondecreasing functions like g(n)=ln^*n. The results in this paper remain valid in higher dimensions.     

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.     

Sarason's Toeplitz Product Problem on the Fock–Sobolev Space

The Sarason's Toeplitz product problem asks when the Toeplitz product operator Tu T_v,with analytic symbols u and v, is bounded on Hilbert space of analytic functions. In this paper, we deal with this problem on the Fock–Sobolev space and have a complete solution that u = e~q, v = Ce~(-q),where q is a linear complex polynomial and C is a nonzero constant.     

An extremal problem for positive defintie matrices

A problem studied by Flanders (1975) is minimize the function f(R)=tr(SR+TR^-1) over the set of positive definite matrices R, where S and T are positive semi-definite matrices. Alternative proofs that may have some intrinsic interest are provided. The proofs explicitly yield the infimum of f(R). One proof is based on a convexity argument and the other on a sequence of reductions to a univariate problem.     

An extremal result on convex lattice polygons

The diameter of a convex set C is the length of the longest segment in C, and the local diameter at a point p is the length of the longest segment which contains p. It is easy to see that the local diameter at any point equals at least half of the diameter of C.

This paper looks at the analogous question in a discrete setting; namely we look at convex lattice polygons in the plane. The analogue of Euclidean diameter is lattice diameter, defined as the maximal number of collinear points from a figure. In this setting, lattice diameter and local lattice diameter need not be related. However, for figures of a certain size, the local lattice diameter at any point must equal at least (n − 2)/2, where n is the lattice diameter of the figure. The exact minimal size for which this result holds is determined, as a special case of an exact combinatorial formula.     

Positive and real-positive solutions to the equation axa*=c in C*-algebras

We obtain new representations for the general positive and real-positive solutions of the equation axa*=c in a C*-algebra using the characterization of positivity based on a matrix representation of an element and the generalized Schur complement. Applications to the equation AXA*=C for operators between Hilbert spaces and for finite matrices are given.     

Geometric dilation of closed planar curves: New lower bounds

Given two points on a closed planar curve, C, we can divide the length of a shortest connecting path in C by their Euclidean distance. The supremum of these ratios, taken over all pairs of points on the curve, is called the geometric dilation of C. We provide lower bounds for the dilation of closed curves in terms of their geometric properties, and prove that the circle is the only closed curve achieving a dilation of π/2, which is the smallest dilation possible. Our main tool is a new geometric transformation technique based on the perimeter halving pairs of C.     

The countability index of the endomorphism semigroup of a vector space

The countability index C(S) of a semigroup S is the least positive integer n, if such an integer exists, with the property that every countable subset of S is contained in a subsemigroup with n generators. If no such integer exists. C(S) is defined to be infinite. Let V be a vector space over a field F and denote by End V the endomorphism semigroup of V. In the two main results, it is determined precisely when C(End V)=2 and when C(End V)=x SpecificallyC(End V)=2 if and only if V is infinite dimensional or dim V=1 and F is finite and C(End V)=x if and only if F is infinite and dim V is an integer N≥1.     

Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

Decompositions of positive self-dual boolean functions

A coterie, which is used to realize mutual exclusion in distributed systems, is a family C of subsets such that any pair of subsets in C has at least one element in common, and such that no subset in C contains any other subset in C. Associate with a family of subsets C a positive Boolean function f_c such that f_c(x) = 1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f_c is dual-minor, and is a non-dominated (ND) coterie if and only if f_c is self-dual. We study in this paper the decomposition of a positive self-dual function into smaller positive self-dual functions, as it explains how to represent and how to construct the corresponding ND coterie. A key step is how to decompose a positive dual-minor function f into a conjunction of positive self-dual functions f₁,f₂,…, f_k. In addition to the general condition for this decomposition, we clarify the condition for the decomposition into two functions f₁, and f₂, and introduce the concept of canonical decomposition. Then we present an algorithm that determines a minimal canonical decomposition, and a very simple algorithm that usually gives a decomposition close to minimal. The decomposition of a general self-dual function is also discussed.