Block tridiagonal reduction of perturbed normal and rank structured matrices

It is well known that if a matrix A∈C^n×n$A\in {\mathbb{C}}^{n\times n}$ solves the matrix equation f(A,A^H)=0$f(A,A^H)=0$, where f(x,y)$f(x,y)$ is a linear bivariate polynomial, then A is normal; A   and A^H$A^H$ can be simultaneously reduced in a finite number of operations to tridiagonal form by a unitary congruence and, moreover, the spectrum of A is located on a straight line in the complex plane. In this paper we present some generalizations of these properties for almost normal matrices which satisfy certain quadratic matrix equations arising in the study of structured eigenvalue problems for perturbed Hermitian and unitary matrices.     

Note on structured indefinite perturbations to Hermitian matrices

In a recent paper, Overton and Van Dooren have considered structured indefinite perturbations to a given Hermitian matrix. We extend their results to skew-Hermitian, Hamiltonian and skew-Hamiltonian matrices. As an application, we give a formula for computation of the smallest perturbation with a special structure, which makes a given Hamiltonian matrix own a purely imaginary eigenvalue.     

Eigenvalue perturbation theory of classes of structured matrices under generic structured rank one perturbations

udy the perturbation theory of structured matrices under structured rank one perturbations, and then focus on several classes of complex matrices. Generic Jordan structures of perturbed matrices are identified. It is shown that the perturbation behavior of the Jordan structures in the case of singular J-Hamiltonian matrices is substantially different from the corresponding theory for unstructured generic rank one perturbation as it has been studied in [18, 28, 30, 31]. Thus a generic structured perturbation would not be generic if considered as an unstructured perturbation. In other settings of structured matrices, the generic perturbation behavior of the Jordan structures, within the confines imposed by the structure, follows the pattern of that of unstructured perturbations.     

Lagrange's formula for tangential interpolation with application to structured matrices

Lagrange's interpolation formula is generalized to tangential interpolation. This includes interpolation by vector polynomials and by rational vector functions with prescribed pole characteristics. The formula is applied to obtain representations of the inverses of Cauchy-Vandermonde matrices generalizing former results.     

A generalized unitary Hessenberg matrix

This paper describes the use of a generalized isometric Arnoldi algorithm to reduce a unitary matrix, via unitary similarity, to a product of elementary reflectors and permutations. The computation is analogous to the reduction of a unitary matrix to a unitary Hessenberg matrix using the isometric Arnoldi algorithm. In the case in which A is a shift matrix, the reduction provides a novel recurrence for the factor R in the QR factorization of a Toeplitz-like matrix.     

Backward errors for eigenproblem of two kinds of structured matrices

In this paper, we consider backward errors in the eigenproblem of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices. By making use of the properties of symmetric centrosymmetric and symmetric skew-centrosymmetric matrices, we derive explicit formulae for the backward errors of approximate eigenpairs.     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of M_m×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.     

Drazin inverse of partitioned matrices in terms of Banachiewicz-Schur forms

Let be a partitioned matrix, where A and D are square matrices. Denote the Drazin inverse of A by A^D. The purpose of this paper is twofold. Firstly, we develop conditions under which the Drazin inverse of M having generalized Schur complement, S=D-CA^DB, group invertible, can be expressed in terms of a matrix in the Banachiewicz-Schur form and its powers. Secondly, we deal with partitioned matrices satisfying rank(M)=rank(A^D)+rank(S^D), and give conditions under which the group inverse of M exists and a formula for its computation.     

Structured mixed and componentwise condition numbers of some structured matrices

Structured matrices, such as Cauchy, Vandermonde, Toeplitz, Hankel, and circulant matrices, are considered in this paper. We apply a Kronecker product-based technique to deduce the structured mixed and componentwise condition numbers for the matrix inversion and for the corresponding linear systems.     

A complete unitary similarity invariant for unicellular matrices

We present necessary and sufficient conditions for an n×n complex matrix B to be unitarily similar to a fixed unicellular (i.e., indecomposable by similarity) n×n complex matrix A.     

The nullity and rank of linear combinations of idempotent matrices

Baksalary and Baksalary [J.K. Baksalary, O.M. Baksalary, Nonsingularity of linear combinations of idempotent matrices, Linear Algebra Appl. 388 (2004) 25-29] proved that the nonsingularity of P₁ + P₂, where P₁ and P₂ are idempotent matrices, is equivalent to the nonsingularity of any linear combinations c₁P₁ + c₂P₂, where c₁, c₂ ≠ 0 and c₁ + c₂ ≠ 0. In the present note this result is strengthened by showing that the nullity and rank of c₁P₁ + c₂P₂ are constant. Furthermore, a simple proof of the rank formula of Groß and Trenkler [J. Groß, G. Trenkler, Nonsingularity of the difference of two oblique projectors, SIAM J. Matrix Anal. Appl. 21 (1999) 390-395] is obtained.     

Approximate iterations for structured matrices

Important matrix-valued functions f (A) are, e.g., the inverse A ⁻¹, the square root and the sign function. Their evaluation for large matrices arising from pdes is not an easy task and needs techniques exploiting appropriate structures of the matrices A and f (A) (often f (A) possesses this structure only approximately). However, intermediate matrices arising during the evaluation may lose the structure of the initial matrix. This would make the computations inefficient and even infeasible. However, the main result of this paper is that an iterative fixed-point like process for the evaluation of f (A) can be transformed, under certain general assumptions, into another process which preserves the convergence rate and benefits from the underlying structure. It is shown how this result applies to matrices in a tensor format with a bounded tensor rank and to the structure of the hierarchical matrix technique. We demonstrate our results by verifying all requirements in the case of the iterative computation of A ⁻¹ and . This work was performed during the stay of the third author at the Max-Planck-Institute for Mathematics in the Sciences (Leipzig) and also supported by the Russian Fund of Basic Research (grants 05-01-00721, 04-07-90336) and a Priority Research Grant of the Department of Mathematical Sciences of the Russian Academy of Sciences.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Bijective linear rank preservers for spaces of matrices over antinegative semirings

We classify the bijective linear operators on spaces of matrices over antinegative commutative semirings with no zero divisors which preserve certain rank functions such as the symmetric rank, the factor rank and the tropical rank. We also classify the bijective linear operators on spaces of matrices over the max-plus semiring which preserve the Gondran-Minoux row rank or the Gondran-Minoux column rank.     

Relative perturbation bounds for the unitary polar factor

LetB be anm×n (m≥n) complex (or real) matrix. It is known that there is a uniquepolar decomposition B=QH, whereQ*Q=I, then×n identity matrix, andH is positive definite, providedB has full column rank. Existing perturbation bounds suggest that in the worst case, for complex matrices the change inQ be proportional to the reciprocal ofB's least singular value, or the reciprocal of the sum ofB's least and second least singular values if matrices are real. However, there are situations where this unitary polar factor is much more accurately determined by the data than the existing perturbation bounds would indicate. In this paper the following question is addressed: how much mayQ change ifB is perturbed to $\tilde B = D_1^* BD_2 $ , whereD ₁ andD ₂ are nonsingular and close to the identity matrices of suitable dimensions? It is shown that for a such kind of perturbation, the change inQ is bounded only by the distances fromD ₁ andD ₂ to identity matrices and thus is independent ofB's singular values. Such perturbation is restrictive, but not unrealistic. We show how a frequently used scaling technique yields such a perturbation and thus scaling may result in better-conditioned polar decompositions.     

On nonsingularity of block two-by-two matrices

We derive necessary and sufficient conditions for guaranteeing the nonsingularity of a block two-by-two matrix by making use of the singular value decompositions and the Moore–Penrose pseudoinverses of the matrix blocks. These conditions are complete, and much weaker and simpler than those given by Decker and Keller [D.W. Decker, H.B. Keller, Multiple limit point bifurcation, J. Math. Anal. Appl. 75 (1980) 417–430], and may be more easily examined than those given by Bai [Z.-Z. Bai, Eigenvalue estimates for saddle point matrices of Hermitian and indefinite leading blocks, J. Comput. Appl. Math. 237 (2013) 295–306] from the computational viewpoint. We also derive general formulas for the rank of the block two-by-two matrix by utilizing either the unitarily compressed or the orthogonally projected sub-matrices.     

Accurate computations with Said-Ball-Vandermonde matrices

A generalization of the Vandermonde matrices which arise when the power basis is replaced by the Said-Ball basis is considered. When the nodes are inside the interval (0,1), then those matrices are strictly totally positive. An algorithm for computing the bidiagonal decomposition of those Said-Ball-Vandermonde matrices is presented, which allows us to use known algorithms for totally positive matrices represented by their bidiagonal decomposition. The algorithm is shown to be fast and to guarantee high relative accuracy. Some numerical experiments which illustrate the good behaviour of the algorithm are included.