Some remarks on the perturbation of polar decompositions for rectangular matrices

In this article we focus on perturbation bounds of unitary polar factors in polar decompositions for rectangular matrices. First we present two absolute perturbation bounds in unitarily invariant norms and in spectral norm, respectively, for any rectangular complex matrices, which improve recent results of Li and Sun (SIAM J. Matrix Anal. Appl. 2003; 25 :362–372). Secondly, a new absolute bound for complex matrices of full rank is given. When ‖A ? Ã‖₂ ? ‖A ? Ã‖_F, our bound for complex matrices is the same as in real case. Finally, some asymptotic bounds given by Mathias (SIAM J. Matrix Anal. Appl. 1993; 14 :588–593) for both real and complex square matrices are generalized. Copyright © 2005 John Wiley & Sons, Ltd.     

Generalized induced norms

Let ‖·‖ be a norm on the algebra ?_n of all n × n matrices over ?. An interesting problem in matrix theory is that “Are there two norms ‖·‖₁ and ‖·‖₂ on ?_n such that ‖A‖ = max|‖Ax‖₂: ‖x‖₁ = 1} for all A ∈ ?_n?” We will investigate this problem and its various aspects and will discuss some conditions under which ‖·‖₁ = ‖·‖₂.     

The inverse problem of bisymmetric matrices with a submatrix constraint

An n×n real matrix A is called a bisymmetric matrix if A=A^T and A=S_nAS_n, where S_n is an n×n reverse unit matrix. This paper is mainly concerned with solving the following two problems: Problem I Given n×m real matrices X and B, and an r×r real symmetric matrix A₀, find an n×n bisymmetric matrix A such that where A([1: r]) is a r×r leading principal submatrix of the matrix A. Problem II Given an n×n real matrix A^*, find an n×n matrix  in S_E such that where ∥·∥ is Frobenius norm, and S_E is the solution set of Problem I. The necessary and sufficient conditions for the existence of and the expressions for the general solutions of Problem I are given. The explicit solution, a numerical algorithm and a numerical example to Problem II are provided. Copyright © 2003 John Wiley & Sons, Ltd.     

Unitary invariance and spectral variation

We call a norm on operators or matrices weakly unitarily invariant if its value at operator A is not changed by replacing A by U1AU, provided only that U is unitary. This class includes such norms as the numerical radius. We extend to all such norms an inequality that bounds the spectral variation when a normal operator A is replaced by another normal B in terms of the arclength of any normal path from A to B, computed using the norm in question. Related results treat the local metric geometry of the “manifold” of normal operators. We introduce a representation for weakly unitarily invariant matrix norms in terms of function norms over the unit ball, and identify this correspondence explicitly in certain cases.     

On a characterization of irreducibility of a non-negative matrix

Let A denote an n×n matrix with all its elements real and non-negative, and let r_i be the sum of the elements in the ith row of A, i=1,…,n. Let B=A?D(r₁,…,r_n), where D(r₁,…,r_n) is the diagonal matrix with r_i at the position (i,i). Then it is proved that A is irreducible if and only if rank B=n?1 and the null space of B^T contains a vector d whose entries are all non-null.     

On the condition numbers associated with the polar factorization of a matrix

We are interested in the calculation of explicit formulae for the condition numbers of the two factors of the polar decomposition of a full rank real or complex m × n matrix A, where m ≥ n. We use a unified presentation that enables us to compute such condition numbers in the Frobenius norm, in cases where A is a square or a rectangular matrix subjected to real or complex perturbations. We denote by σ₁ (respectively σ _n) the largest (respectively smallest) singular value of A, and by K(A) = σ₁/σ _n the generalized condition number of A. Our main results are that the absolute condition number of the Hermitian polar factor is √2(1 + K(A)²)^1/2/(1 + K(A)) and that the absolute condition number of the unitary factor of a rectangular matrix is 1/σ _n. Copyright © 2000 John Wiley & Sons, Ltd.     

Balancing vectors and Gaussian measures of n-dimensional convex bodies

Let ‖·‖ be the Euclidean norm on R ⁿ and γ_n the (standard) Gaussian measure on R ⁿ with density (2π)^−n/2e. It is proved that there is a numerical constant c>0 with the following property: if K is an arbitrary convex body in R ⁿ with γ_n(K)≥1/2, then to each sequence u₁,…,u_m∈ R ⁿ with ‖u₁‖,…,‖u_m‖≤c there correspond signs ε₁,…,ε_m=±1 such that ∑^m_i=1ε_iu_i∈K. This improves the well-known result obtained by Spencer [Trans. Amer. Math. Soc. 289 , 679–705 (1985)] for the n-dimensional cube. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12: 351–360, 1998     

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 F m ×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 T F _{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.     

Approximating minimum norm solutions of rank-deficient least squares problems

In this paper we consider the solution of linear least squares problems min_x∥Ax - b∥²₂ where the matrix A ∈ R ^{m × n} is rank deficient. Put p = min{m, n}, let σ_i, i = 1, 2,…, p, denote the singular values of A, and let u_i and v_i denote the corresponding left and right singular vectors. Then the minimum norm solution of the least squares problem has the form x* = ∫^r_{i = 1}(u^T_ib/σ_i)v_i, where r ≤ p is the rank of A. The Riley–Golub iteration, x_{k + 1} = arg min_x{∥Ax - b∥²₂ + λ∥x − x_k∥²₂} converges to the minimum norm solution if x₀ is chosen equal to zero. The iteration is implemented so that it takes advantage of a bidiagonal decomposition of A. Thus modified, the iteration requires only O(p) flops (floating point operations). A further gain of using the bidiagonalization of A is that both the singular values σ_i and the scalar products u^T_ib can be computed at marginal extra cost. Moreover, we determine the regularization parameter, λ, and the number of iterations, k, in a way that minimizes the difference x* − x_k with respect to a certain norm. Explicit rules are derived for calculating these parameters. One advantage of our approach is that the numerical rank can be easily determined by using the singular values. Furthermore, by the iterative procedure, x* is approximated without computing the singular vectors of A. This gives a fast and reliable method for approximating minimum norm solutions of well-conditioned rank-deficient least squares problems. Numerical experiments illustrate the viability of our ideas, and demonstrate that the new method gives more accurate approximations than an approach based on a QR decomposition with column pivoting. © 1998 John Wiley & Sons, Ltd.     

Monotonicity of the matrix geometric mean

An attractive candidate for the geometric mean of m positive definite matrices A ₁, . . . , A _m is their Riemannian barycentre G. One of its important operator theoretic properties, monotonicity in the m arguments, has been established recently by Lawson and Lim. We give an elementary proof of this property using standard matrix analysis and some counting arguments. We derive some new inequalities for G. One of these says that, for any unitarily invariant norm, ||| G ||| is not bigger than the geometric mean of |||A ₁|||, . . . , |||A _m |||.     

The eigenvalues of the sum of matrices with prescribed invariant polynomials *

Let A and B be n×n matrices over a field F, and c ₁,…,c_n ∈F. We give a sufficient condition for the existence of matrices A' and B' similar to A and B, respectively, such that A' + B' has eigenvalues c ₁,…,c_n .     

A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

How good can polynomial interpolation on the sphere be?

This paper explores the quality of polynomial interpolation approximations over the sphere S ^r−1⊂R ^r in the uniform norm, principally for r=3. Reimer [17] has shown there exist fundamental systems for which the norm ‖Λ _n ‖ of the interpolation operator Λ _n , considered as a map from C(S ^r−1) to C(S ^r−1), is bounded by d _n , where d _n is the dimension of the space of all spherical polynomials of degree at most n. Another bound is d _n ^1/2(λ_avg/λ_min)^1/2, where λ_avg and λ_min are the average and minimum eigenvalues of a matrix G determined by the fundamental system of interpolation points. For r=3 these bounds are (n+1)² and (n+1)(λ_avg/λ_min)^1/2, respectively. In a different direction, recent work by Sloan and Womersley [24] has shown that for r=3 and under a mild regularity assumption, the norm of the hyperinterpolation operator (which needs more point values than interpolation) is bounded by O(n ^1/2), which is optimal among all linear projections. How much can the gap between interpolation and hyperinterpolation be closed?

For interpolation the quality of the polynomial interpolant is critically dependent on the choice of interpolation points. Empirical evidence in this paper suggests that for points obtained by maximizing λ_min, the growth in ‖Λ _n ‖ is approximately n+1 for n<30. This choice of points also has the effect of reducing the condition number of the linear system to be solved for the interpolation weights. Choosing the points to minimize the norm directly produces fundamental systems for which the norm grows approximately as 0.7n+1.8 for n<30. On the other hand, ‘minimum energy points’, obtained by minimizing the potential energy of a set of (n+1)² points on S ², turn out empirically to be very bad as interpolation points.

This paper also presents numerical results on uniform errors for approximating a set of test functions, by both interpolation and hyperinterpolation, as well as by non-polynomial interpolation with certain global basis functions.

     

Characterizing optimal sampling of binary contingency tables via the configuration model

A binary contingency table is an m × n array of binary entries with row sums r = (r₁, …, r_m) and column sums c = (c₁, …, c_n). The configuration model generates a contingency table by considering r_i tokens of type 1 for each row i and c_j tokens of type 2 for each column j, and then taking a uniformly random pairing between type‐1 and type‐2 tokens. We give a necessary and sufficient condition so that the probability that the configuration model outputs a binary contingency table remains bounded away from 0 as \begin{align*}N=\sum_{i=1}^m r_i=\sum_{j=1}^n c_j\end{align*} goes to ∞. Our finding shows surprising differences from recent results for binary symmetric contingency tables. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Domination theorems in non-commutativeC *-Algebras

LetA be a Banach algebra with unite. Ifu, v ₁, …,v _n are elements ofA thenu is said to be dominated byv ₁, …,v _n if there is γ>O such that for everyx∈A we have ‖ux‖≤γ(‖v ₁ x‖+…+‖v _n x‖). It is shown that for everyx∈A we have ‖ux‖≤γ(‖v ₁ x‖+…+‖v _n x‖). it is shown for finite-dimensional algebras that the above condition is sufficient foru to belong to the left ideal generated byv ₁, …,v _n in some superalgebra ofA. A similar result is proved for subalgebras of the algebra of all bounded operators on a Hilbert space.     

Unitarily invariant norms related to the numerical radius

We determine the maximum in the class of unitarily invariant norms ∥·∥ such that w(A) ? ∥A∥ for all n-square matrices A. Here w(A) denotes the numerical radius of A.     

Adjacency preserving functions on symmetric elements and linear preservers of non-zero decomposable symmetric tensors

Let A be a non-empty set and m be a positive integer. Let ≡ be the equivalence relation defined on A ^m such that (x ₁, …, x _m ) ≡ (y ₁, …, y _m ) if there exists a permutation σ on {1, …, m} such that y _σ(i) = x _i for all i. Let A ^(m) denote the set of all equivalence classes determined by ≡. Two elements X and Y in A ^(m) are said to be adjacent if (x ₁, …, x _m?1, a) ∈ X and (x ₁, …, x _m?1, b) ∈ Y for some x ₁, …, x _m?1 ∈ A and some distinct elements a, b ∈ A. We study the structure of functions from A ^(m) to B ⁽ⁿ⁾ that send adjacent elements to adjacent elements when A has at least n + 2 elements and its application to linear preservers of non-zero decomposable symmetric tensors.     

Tracial gauge norms on finite von Neumann algebras satisfying the weak Dixmier property

In this paper we set up a representation theorem for tracial gauge norms on finite von Neumann algebras satisfying the weak Dixmier property in terms of Ky Fan norms. Examples of tracial gauge norms on finite von Neumann algebras satisfying the weak Dixmier property include unitarily invariant norms on finite factors (type II₁ factors and Mn(C)) and symmetric gauge norms on L^∞[0,1] and Cn. As the first application, we obtain that the class of unitarily invariant norms on a type II₁ factor coincides with the class of symmetric gauge norms on L^∞[0,1] and von Neumann's classical result [J. von Neumann, Some matrix-inequalities and metrization of matrix-space, Tomsk. Univ. Rev. 1 (1937) 286-300] on unitarily invariant norms on Mn(C). As the second application, Ky Fan's dominance theorem [Ky Fan, Maximum properties and inequalities for the eigenvalues of completely continuous operators, Proc. Natl. Acad. Sci. USA 37 (1951) 760-766] is obtained for finite von Neumann algebras satisfying the weak Dixmier property. As the third application, some classical results in non-commutative Lp-theory (e.g., non-commutative Hölder's inequality, duality and reflexivity of non-commutative Lp-spaces) are obtained for general unitarily invariant norms on finite factors. We also investigate the extreme points of N(M), the convex compact set (in the pointwise weak topology) of normalized unitarily invariant norms (the norm of the identity operator is 1) on a finite factor M. We obtain all extreme points of N(M₂(C)) and some extreme points of N(Mn(C)) (n?3). For a type II₁ factor M, we prove that if t (0?t?1) is a rational number then the Ky Fan tth norm is an extreme point of N(M).