Existence of a low rank or ℋ︁‐matrix approximant to the solution of a Sylvester equation

We consider the Sylvester equation AX?XB+C=0 where the matrix C∈?^n×m is of low rank and the spectra of A∈?^n×n and B∈?^m×m are separated by a line. We prove that the singular values of the solution X decay exponentially, that means for any ε∈(0,1) there exists a matrix X? of rank k=O(log(1/ε)) such that ∥X?X?∥₂?ε∥X∥₂. As a generalization we prove that if A,B,C are hierarchical matrices then the solution X can be approximated by the hierarchical matrix format described in Hackbusch (Computing 2000; 62 : 89–108). The blockwise rank of the approximation is again proportional to log(1/ε). Copyright © 2004 John Wiley & Sons, Ltd.     

0-Minimal Quasi-ideals of Generalized Linear Transformation Semigroups

Abstract

For vector spaces V and W over a field F, L _F (V, W) denotes the set of all linear transformations α : V → W, and for a cardinal number k > 0, let L _F (V, W, k) be the set of all α ∈ L _F (V, W) of rank less than k. For θ ∈ L _F (W, V), let (L _F (V, W, k), θ) denote the semigroup L _F (V, W, k) under the operation ? defined by α ? β = αθβ for all α, β ∈ L _F (V, W, k). In this paper, all 0-minimal quasi-ideals of the semigroup (L _F (V, W, k), θ) are completely characterized. It is also shown from this characterization that every nonzero semigroup (L _F (V, W, k), θ) always has a 0-minimal quasi-ideal.     

SOME REMARKS CONCERNING THE DAUGAVET EQUATION

Abstract

We say that a normed space X has the Daugavet property (DP) if for every finite rank operator K in X the equality ∥I + T∥ = 1 + ∥T∥ holds. It is known that C[0,1] and L ₁[0,1] have DP. We prove that if X has DP then X has no unconditional basis. We also discuss anti-Daugavet property, hereditary DP-spaces and construct a strictly convex normed space having DP.     

Characterizations of new Cohen summing bilinear operators

We prove two characterizations of new Cohen summing bilinear operators. The first one is: Let X, Y and Z be Banach spaces, 1 < p < ∞, V : X × Y → Z a bounded linear operator and n ≥ 2 a natural number. Then V is new Cohen p-summing if and only if for all Banach spaces X₁,?…?, X_n and all p-summing operators U : X₁ × · · · × X_n → X, the operator V ? (U, I_Y) : X₁ × · · · × X_n × Y → Z is -summing. The second result is: Let H be a Hilbert space,, Y, Z Banach spaces and V : H × Y → Z a bounded bilinear operator and 1 < p < ∞. Then V is new Cohen p-summing if and only if for all Banach spaces E and all p-summing operators U : E → H, the operator V ? (U, I_Y) is (p, p*)-dominated.     

Operator Ideals Generalizing the Ideal of Strictly Singular Operators

It is well-known that an operator T ∈ L(E, F) is strictly singular if ∥T_x∥≧λ∥x∥ on a subspace Z ? E implies dim Z < + ∞. The present paper deals with ideals of operators defined by a condition — ∥T_x∥≧λ∥x∥ on an infinite-dimensional subspace Z ? E implies Z ? F — F being a ?quasi-injective”? class of BANACH spaces.     

Large spaces of symmetric matrices of bounded rank are decomposable ∗

Let k and n be positive integers such that kn. Let S_n (F) denote the space of all n×n symmetric matrices over the field F with char F≠2. A subspace L of S_n (F) is said to be a k-subspace if rank Ak for every A?L.

Now suppose that k is even, and write k=2r. We say a k∥-subspace of S_n (F) is decomposable if there exists in Fⁿ a subspace W of dimension n?r such that x^tAx=0 for every x?W A?L.

We show here, under some mild assumptions on k n and F, that every k∥-subspace of S_n (F) of sufficiently large dimension must be decomposable. This is an analogue of a result obtained by Atkinson and Lloyd for corresponding subspaces of F^m,n .     

The approximation of flows

Let U, V be two strongly continuous one-parameter groups of bounded operators on a Banach space $\text{X}$ with corresponding infinitesimal generators S, T. We prove the following: ∥U_t, ? V_t ∥ = O(t), t → 0, if and only if U = V; ∥U_t ? V_t∥ = O(t^α), t → 0; with 0 ? α ? 1, if and only if $\text{S = Ω(T + P)Ω}{}^{\mathrm{?1}}$, where Ω, P, are bounded operators on $\text{X}$ such that $\text{∥U}{}_{\mathrm{t}}\text{Ω ? ΩU}{}_{\mathrm{t}}\text{∥ = O(t}{}^{\mathrm{\alpha }}\text{), ∥U}{}_{\mathrm{t}}\text{P ? PU}{}_{\mathrm{t}}\text{∥ = ?O(t}{}^{\mathrm{\alpha }}\text{), t → 0; ∥U}{}_{\mathrm{t}}\text{? V}{}_{\mathrm{t}}\text{∥ = O(t)}$ if and only if $\text{S}{}^1\text{? T}{}^1$ has a bounded extension to $\text{X}$¹. Further results of this nature are inferred for semigroups, reflexive spaces, Hilbert spaces, and von Neumann algebras.     

Special orthogonal splittings of<Emphasis Type="Italic">L</Emphasis><Stack><Subscript>1</Subscript><Superscript>2<Emphasis Type="Italic">k</Emphasis></Superscript></Stack>

We show that for each positive integerk there is ak×k matrixB with ±1 entries such that puttingE to be the span of the rows of thek×2k matrix [√kI _k,B], thenE,E ^⊥ is a Kashin splitting: TheL ₁ ^2k and theL ₂ ^2k are universally equivalent on bothE andE ^⊥. Moreover, the probability that a random ±1 matrix satisfies the above is exponentially close to 1. Supported by the Israel Science Foundation.     

On the Schur multiplier norm of matrices

The Schur product of two n×n complex matrices A=(a_ij), B=(b_ij) is defined by A°B=(a_ijb_ij. By a result of Schur [2], the algebra of n×n matrices with Schur product and the usual addition is a commutative Banach algebra under the operator norm (the norm of the operator defined on $\text{C}$ⁿ by the matrix). For a fixed matrix A, the norm of the operator B?A°B on this Banach algebra is called the Schur multiplier norm of A, and is denoted by ∥A∥^m. It is proved here that $\text{∥A∥=∥U}{}^1\text{AU∥}{}_{\mathrm{m}}$ for all unitary U (where ∥·∥ denotes the operator norm) iff A is a scalar multiple of a unitary matrix; and that ∥A∥_m=∥A∥ iff there exist two permutations P, Q, a p×p (1?p?n) unitary U, an (n?p)×(n?p)1 contraction C, and a nonnegative number λ such that

$\text{A=λP}\text{U}\text{0}\text{0}\text{C}\text{Q;}$

and this is so iff $\text{∥A°}\text{A}\text{?}\text{∥=∥A∥}{}^2$, where ā is the matrix obtained by taking entrywise conjugates of A.     

Bessel functions and representation theory. I

In this paper a general theory of operator-valued Bessel functions is presented. These functions arise naturally in representation theory in the context of metaplectic representations, discrete series, and limits of discrete series for certain semi-simple Lie groups. In general, Bessel functions J_λ are associated to the action by automorphisms of a compact group U on a locally compact abelian group X, and are indexed by the irreducible representations λ of U that appear in the primary decomposition of the regular representation of U on L²(X). Then on the λ-primary constituent of L²(X), the Fourier transform is described by the Hankel transform corresponding to J_λ. More detailed information is available in the case in which (U, X) is an orthogonal transformation group which possesses a system of polar coordinates. In particular, when X=$\text{F}$^k×n,$\text{F}$ a real finite-dimensional division algebra, with k ? 2n and $\text{O}$(k, $\text{F}$), the representations λ of U are induced in a certain sense from representations π of GL(n, $\text{F}$). This leads to a characterization of J_λ as a reduced Bessel function defined on the component of 1 in GL(n, $\text{F}$) and to the connection between metaplectic representations and holomorphic discrete series for the group of biholomorphic automorphisms of the Siegel upper half-plane in the complexification of $\text{F}$^{n × n}.     

Distributions of orientations on Stiefel manifolds

The Riemann space whose elements are m × k (m k) matrices X, i.e., orientations, such that X′X = I_k is called the Stiefel manifold V_k,m. The matrix Langevin (or von Mises-Fisher) and matrix Bingham distributions have been suggested as distributions on V_k,m. In this paper, we present some distributional results on V_k,m. Two kinds of decomposition are given of the differential form for the invariant measure on V_k,m, and they are utilized to derive distributions on the component Stiefel manifolds and subspaces of V_k,m for the above-mentioned two distributions. The singular value decomposition of the sum of a random sample from the matrix Langevin distribution gives the maximum likelihood estimators of the population orientations and modal orientation. We derive sampling distributions of matrix statistics including these sample estimators. Furthermore, representations in terms of the Hankel transform and multi-sample distribution theory are briefly discussed.     

Direct products of cyclic semigroups an unions of groups

We consider direct productsS×U_eεE G _e=S ₁×…×S _n × U_eεE G _e of non-group finite cyclic semigroupsS _i, 1 ≤i ≤n, and finite unions of finite groups U_eεE G _e We prove that if such a semigroup is isomorphic to another of the same form, sayT×U _fεF H _f =T ₁×…×U _fεF H _f , whereT _j are non-group cyclic semigroups, 1≤j≤l, and U _fεF H _f is a union of groups, thenS is isomorphic toT and U_eεE G _e is isomorphic to U_fεF H _f . We then determine when a finite semigroup has such a decomposition and show how the direct factors can be found.     

Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

Given a graph G = (V, E), a weight function w: E → R⁺, and a parameter k, we consider the problem of finding a subset U  V of size k that maximizes: Max-Vertex Cover_k: the weight of edges incident with vertices in U,Max-Dense Subgraph_k: the weight of edges in the subgraph induced by U,Max-Cut_k: the weight of edges cut by the partition (U, V\U),Max-Uncut_k: the weight of edges not cut by the partition (U, V\U).For each of the above problems we present approximation algorithms based on semidefinite programming and obtain approximation ratios better than those previously published. In particular we show that if a graph has a vertex cover of size k, then one can select in polynomial time a set of k vertices that covers over 80% of the edges.     

Density Estimation on the Stiefel Manifold

This paper develops the theory of density estimation on the Stiefel manifoldV_{k, m}, whereV_{k, m}is represented by the set ofm×kmatricesXsuch thatX′X=I_k, thek×kidentity matrix. The density estimation by the method of kernels is considered, proposing two classes of kernel density estimators with small smoothing parameter matrices and for kernel functions of matrix argument. Asymptotic behavior of various statistical measures of the kernel density estimators is investigated for small smoothing parameter matrix and/or for large sample size. Some decompositions of the Stiefel manifoldV_{k, m}play useful roles in the investigation, and the general discussion is applied and examined for a special kernel function. Alternative methods of density estimation are suggested, using decompositions ofV_{k, m}.     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

On the maximum number of edges in a hypergraph whose linegraph contains no cycle

Soit H = (X,F) un hypergraphe h-uniforme avec ∥X∥ = n et soit L_h±1(H) le graphe dont les sommets représentent les arêtes de H. deux sommets étant relíes si et seulement si les arétes qu'ils représentent intersectent en h ± 1 sommets. Nous montrons que si L_h±1(H) ne contient pas de cycle, alors $\text{∥F∥<(}{}^{\mathrm{n}}{}_{\mathrm{h\pm 1}}\text{)/h±1}$. la borne étant exacte pour h = 2 et pour des valeurs de H pour h = 3. Ce probl`eme mène á une conjecture sur les “presque systèmes de Steine.”Let H = (X, F) be a h-uniform hypergraph, with ∥X∥ = n and let L_h±1(H) be the graph whose vertices are the edges of H, two vertices being joined if and only if the edges they represent intersect in h ±1 vertices. We prove that, if L_h±1H contains no cycle, then $\text{∥F∥(}{}^{\mathrm{n}}{}_{\mathrm{h\pm 1}}\text{)/h±1}$; moreover the bound is exact for h = 2 and with some values of n for h = 3. This problem leads to a conjecture on “almost Steiner systems”.     

Paranormal Elements in Normed Algebra

For a normed algebra A and natural numbers k we introduce and investigate the ∥ · ∥ closed classes P _k (A). We show that P₁(A) is a subset of P _k (A) for all k. If T in P₁(A), then Tⁿ lies in P₁(A) for all natural n. If A is unital, U, V ∈ A are such that ∥U∥ = ∥V∥ = 1, VU = I and T lies in P _k (A), then UTV lies in P _k (A) for all natural k. Let A be unital, then 1) if an element T in P₁(A) is right invertible, then any right inverse element T^?1 lies in P₁(A); 2) for ßßIßß = 1 the class P₁(A) consists of normaloid elements; 3) if the spectrum of an element T, T ∈ P₁(A) lies on the unit circle, then ∥TX∥ = ∥X∥ for all X ∈ A. If A = B(H), then the class P₁(A) coincides with the set of all paranormal operators on a Hilbert space H.     

Low Rank Approximation of a Hankel Matrix by Structured Total Least Norm

The structure preserving rank reduction problem arises in many important applications. The singular value decomposition (SVD), while giving the closest low rank approximation to a given matrix in matrix L ₂ norm and Frobenius norm, may not be appropriate for these applications since it does not preserve the given structure. We present a new method for structure preserving low rank approximation of a matrix, which is based on Structured Total Least Norm (STLN). The STLN is an efficient method for obtaining an approximate solution to an overdetermined linear system AX B, preserving the given linear structure in the perturbation [E F] such that (A + E)X = B + F. The approximate solution can be obtained to minimize the perturbation [E F] in the L _p norm, where p = 1, 2, or . An algorithm is described for Hankel structure preserving low rank approximation using STLN with L _p norm. Computational results are presented, which show performances of the STLN based method for L ₁ and L ₂ norms for reduced rank approximation for Hankel matrices.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

High dimensional limit theorems and matrix decompositions on the Stiefel manifold

The main purpose of this paper is to investigate high dimensional limiting behaviors, as m becomes infinite (m → ∞), of matrix statistics on the Stiefel manifold V_{k, m}, which consists of m × k (m ≥ k) matrices X such that X′X = I_k. The results extend those of Watson. Let X be a random matrix on V_{k, m}. We present a matrix decomposition of X as the sum of mutually orthogonal singular value decompositions of the projections P X and P X, where and are each a subspace of R^m of dimension p and their orthogonal compliment, respectively (p ≥ k and m ≥ k + p). Based on this decomposition of X, the invariant measure on V_{k, m} is expressed as the product of the measures on the component subspaces. Some distributions related to these decompositions are obtained for some population distributions on V_{k, m}. We show the limiting normalities, as m → ∞, of some matrix statistics derived from the uniform distribution and the distributions having densities of the general forms f(P X) and f(m^1/2P X) on V_{k, m}. Subsequently, applications of these high dimensional limit theorems are considered in some testing problems.