Numerical enclosure for each eigenvalue in generalized eigenvalue problem

An algorithm for enclosing all eigenvalues in generalized eigenvalue problem Ax=λBx is proposed. This algorithm is applicable even if A∈C^n×n is not Hermitian and/or B∈C^n×n is not Hermitian positive definite, and supplies nerror bounds while the algorithm previously developed by the author supplies a single error bound. It is proved that the error bounds obtained by the proposed algorithm are equal or smaller than that by the previous algorithm. Computational cost for the proposed algorithm is similar to that for the previous algorithm. Numerical results show the property of the proposed algorithm.     

Hermitian‐type generalized singular value decomposition with applications

For a pair of given Hermitian matrix A and rectangular matrix B with the same row number, we reformulate a well‐known simultaneous Hermitian‐type generalized singular value decomposition (HGSVD) with more precise structure and parameters and use it to derive some algebraic properties of the linear Hermitian matrix function A?BXB* and Hermitian solution of the matrix equation BXB* = A, and the canonical form of a partitioned Hermitian matrix and some optimization problems on its inertia and rank. Copyright © 2012 John Wiley & Sons, Ltd.     

More on extremal ranks of the matrix expressions A − BX ± X*B* with statistical applications

Through a Hermitian‐type (skew‐Hermitian‐type) singular value decomposition for pair of matrices (A, B) introduced by Zha (Linear Algebra Appl. 1996; 240 :199–205), where A is Hermitian (skew‐Hermitian), we show how to find a Hermitian (skew‐Hermitian) matrix X such that the matrix expressions A ? BX ± X^*B^* achieve their maximal and minimal possible ranks, respectively. For the consistent matrix equations BX ± X^*B^* = A, we give general solutions through the two kinds of generalized singular value decompositions. As applications to the general linear model {y, Xβ, σ²V}, we discuss the existence of a symmetric matrix G such that Gy is the weighted least‐squares estimator and the best linear unbiased estimator of Xβ, respectively. Copyright © 2007 John Wiley & Sons, Ltd.     

Some New Bounds for Singular Values and Eigenvalues of Matrix Products

For two Hermitian matrices A and B, at least one of which is positive semidefinite, we give upper and lower bounds for each eigenvalue of AB in terms of the eigenvalues of A and B. For two complex matrices A,B with known singular values, upper and lower bounds are deduced for each singular value of AB.     

Fast enclosure for all eigenvalues in generalized eigenvalue problems

A fast method for enclosing all eigenvalues in generalized eigenvalue problems Ax=λBx is proposed. Firstly a theorem for enclosing all eigenvalues, which is applicable even if A is not Hermitian and/or B is not Hermitian positive definite, is presented. Next a theorem for accelerating the enclosure is presented. The proposed method is established based on these theorems. Numerical examples show the performance and property of the proposed method. As an application of the proposed method, an efficient method for enclosing all eigenvalues in polynomial eigenvalue problems is also sketched.     

When is a matrix unitary or Hermitian plus low rank?

Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low‐rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low‐rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low‐rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew‐Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low‐rank perturbation. Numerical tests prove that this straightforward algorithm is effective.     

The computation of Kronecker's canonical form of a singular pencil

We develop stable algorithms for the computation of the Kronecker structure of an arbitrary pencil. This problem can be viewed as a generalization of the well-known eigenvalue problem of pencils of the type λI?A. We first show that the elementary divisors (λ ? α)ⁱ of a regular pencil λB?A can be retrieved with a deflation algorithm acting on the expansion (λ ? α)B ? (A ? αB). This method is a straightforward generalization of Kublanovskaya's algorithm for the determination of the Jordan structure of a constant matrix. We also show how to use this method to determine the structure of the infinite elementary divisors of λB?A. In the case of singular pencils, the occurrence of Kronecker indices—containing the singularity of the pencil—somewhat complicates the problem. Yet our algorithm retrieves these indices with no additional effort, when determining the elementary divisors of the pencil. The present ideas can also be used to separate from an arbitrary pencil a smaller regular pencil containing only the finite elementary divisors of the original one. This is shown to be an effective tool when used together with the QZ algorithm.     

Linear preservers and quantum information science

In this article, a brief survey of recent results on linear preserver problems and quantum information science is given. In addition, characterization is obtained for linear operators φ on mn?×?mn Hermitian matrices such that φ(A???B) and A???B have the same spectrum for any m?×?m Hermitian A and n?×?n Hermitian B. Such a map has the form A???B???U(?₁(A)????₂(B))U* for mn?×?mn Hermitian matrices in tensor form A???B, where U is a unitary matrix, and for j?∈?{1,?2}, ? _j is the identity map?X???X or the transposition map?X???X ^t . The structure of linear maps leaving invariant the spectral radius of matrices in tensor form A???B is also obtained. The results are connected to bipartite (quantum) systems and are extended to multipartite systems.     

Pertubation bounds for the definite generalized eigenvalue problem

Let A and B be Hermitian matrices, and let c(A, B) = inf{|x^H(A + iB)x|:6 = 1}. The eigenvalue problem Ax = λBx is called definite if c(A, B)>0. It is shown that a definite problem has a complete system of eigenvectors and that its eigenvalues are real. Under pertubations of A and B, the eigenvalues behave like the eigenvalues of a Hermitian matrix in the sense that there is a 1-1 pairing of the eigenvalues with the perturbed eigenvalues and a uniform bound for their differences (in this case in the chordal metric). Pertubation bounds are also developed for eigenvectors and eigenspaces.     

On Additive Decomposition of the Hermitian Solution of the Matrix Equation AXA* = B

The decomposition of a Hermitian solution of the linear matrix equation AXA* = B into the sum of Hermitian solutions of other two linear matrix equations A₁X₁A^*₁ = B₁{A_{1}X_{1}A^{*}_{1} = B_{1}} and A₂X₂A^*₂ = B₂{A_{2}X_{2}A^*_{2} = B_{2}} are approached. As applications, the additive decomposition of Hermitian generalized inverse C ⁻ = A ⁻ + B ⁻ for three Hermitian matrices A, B and C is also considered.     

Least‐squares solutions and least‐rank solutions of the matrix equation AXA* = B and their relations

A Hermitian matrix X is called a least‐squares solution of the inconsistent matrix equation AXA^* = B, where B is Hermitian. A^* denotes the conjugate transpose of A if it minimizes the F‐norm of B ? AXA^*; it is called a least‐rank solution of AXA^* = B if it minimizes the rank of B ? AXA^*. In this paper, we study these two types of solutions by using generalized inverses of matrices and some matrix decompositions. In particular, we derive necessary and sufficient conditions for the two types of solutions to coincide. Copyright © 2012 John Wiley & Sons, Ltd.     

A fast algorithm for computing the smallest eigenvalue of a symmetric positive‐definite Toeplitz matrix

Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive‐definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008 ). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R^?1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd.     

A Structured Kronecker form for the Palindromic Eigenvalue Problem

We consider a structured generalized eigenvalue problem of the form Ax = λ (–A^T )x, called palindromic eigenvalue problem. We will explain this name and give applications. To characterize the spectral properties of this problem we introduce a structured version of the Kronecker canonical form. As an application we present a characterization of the set of pencils B + λC that are equivalent to a palindromic pencil A + λA^T . (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Simultaneous iteration for the matrix eigenvalue problem

Let B be a given positive definite Hermitian matrix, and assume the matrix P satisfies the “normality” condition PB^?1P^HB=B^?1P^HBP, where P^H denotes the Hermitian of P. In this paper, we develop an accelerated version of simultaneous iteration for partial solution of the eigenproblem Px=λx. Convergence together with sharp error bounds is obtained. The results are then applied to the solution of the symmetric eigenproblem Ax=λBx, where the algorithms are shown to be improvements over existing techniques.     

A note on Stewart's theorem for definite matrix pairs

Let A and B be n×n Hermitian matrices. The matrix pair (A, B) is called definite pair and the corresponding eigenvalue problem βAx = αBx is definite if c(A, B) ≡ inf_{6x6= 1}{|^H(A+iB)x|} > 0. In this note we develop a uniform upper bound for differences of corresponding eigenvalues of two definite pairs and so improve a result which is obtained by G.W. Stewart [2]. Moreover, we prove that this upper bound is a projective metric in the set of n × n definite pairs.     

On the optimality and sharpness of Laguerre’s lower bound on the smallest eigenvalue of a symmetric positive definite matrix

Lower bounds on the smallest eigenvalue of a symmetric positive definite matrix A ∈ R ^m×m play an important role in condition number estimation and in iterative methods for singular value computation. In particular, the bounds based on Tr(A ^?1) and Tr(A ^?2) have attracted attention recently, because they can be computed in O(m) operations when A is tridiagonal. In this paper, we focus on these bounds and investigate their properties in detail. First, we consider the problem of finding the optimal bound that can be computed solely from Tr(A ^?1) and Tr(A ^?2) and show that the so called Laguerre’s lower bound is the optimal one in terms of sharpness. Next, we study the gap between the Laguerre bound and the smallest eigenvalue. We characterize the situation in which the gap becomes largest in terms of the eigenvalue distribution of A and show that the gap becomes smallest when {Tr(A ^?1)}²/Tr(A ^?2) approaches 1 or m. These results will be useful, for example, in designing efficient shift strategies for singular value computation algorithms.     

Improving projection‐based eigensolvers via adaptive techniques

We consider subspace iteration (or projection‐based) algorithms for computing those eigenvalues (and associated eigenvectors) of a Hermitian matrix that lie in a prescribed interval. For the case that the projector is approximated with polynomials, we present an adaptive strategy for selecting the degree of these polynomials such that convergence is achieved with near‐to‐optimum overall work without detailed a priori knowledge about the eigenvalue distribution. The idea is then transferred to the approximation of the projector by numerical integration, which corresponds to FEAST algorithm proposed by E. Polizzi in 2009. [E. Polizzi: Density‐matrix‐based algorithm for solving eigenvalue problems. Phys. Rev. B 2009; 79 :115112]. Here, our adaptation controls the number of integration nodes. We also discuss the interaction of the method with search space reduction methods.     

Singular M-matrices and inverse positivity

For a matrix decomposable as A=sI?B, where B?0, it is well known that A^?1?0 if and only if the spectral radius ρ(B)>s. An extension of this result to the singular case ρ(B)=s is made by replacing A^?1 by [A+t(I?AA^D)]^?1, where A^D is the Drazin generalized inverse.     

Perturbation analysis for the generalized Schur complement of a positive semi‐definite matrix

Let and S=C?B^HA^?B be the generalized Schur complement of A?0 in P. In this paper, some perturbation bounds of S are presented which generalize the result of Stewart (Technical Report TR‐95‐38, University of Maryland, 1995) and enrich the perturbation theory for the Schur complement. Also, an error estimate for the smallest perturbation of C, which lowers the rank of P, is discussed. Copyright © 2007 John Wiley & Sons, Ltd.     

Global optimal approximate solutions

Given non-void subsets A and B of a metric space and a non-self mapping T:A? B{T:A\longrightarrow B}, the equation T x = x does not necessarily possess a solution. Eventually, it is speculated to find an optimal approximate solution. In other words, if T x = x has no solution, one seeks an element x at which d(x, T x), a gauge for the error involved for an approximate solution, attains its minimum. Indeed, a best proximity point theorem is concerned with the determination of an element x, called a best proximity point of the mapping T, for which d(x, T x) assumes the least possible value d(A, B). By virtue of the fact that d(x, T x) ≥ d(A, B) for all x in A, a best proximity point minimizes the real valued function x? d(x, T x){x\longrightarrow d(x, T\,x)} globally and absolutely, and therefore a best proximity in essence serves as an ideal optimal approximate solution of the equation T x = x. The aim of this article is to establish a best proximity point theorem for generalized contractions, thereby producing optimal approximate solutions of certain fixed point equations. In addition to exploring the existence of a best proximity point for generalized contractions, an iterative algorithm is also presented to determine such an optimal approximate solution. Further, the best proximity point theorem obtained in this paper generalizes the well-known Banach’s contraction principle.