The Minimal Polynomial of Some Matrices Via Quaternions

This work provides explicit characterizations and formulae for the minimal polynomials of a wide variety of structured 4 × 4 matrices. These include symmetric, Hamiltonian and orthogonal matrices. Applications such as the complete determination of the Jordan structure of skew-Hamiltonian matrices and the computation of the Cayley transform are given. Some new classes of matrices are uncovered, whose behaviour insofar as minimal polynomials are concerned, is remarkably similar to those of skew-Hamiltonian and Hamiltonian matrices. The main technique is the invocation of the associative algebra isomorphism between the tensor product of the quaternions with themselves and the algebra of real 4 × 4 matrices. Extensions to higher dimensions via Clifford Algebras are discussed.     

On the Computation of Particular Eigenvectors of Hamiltonian Matrix Pencils

We discuss a structure-preserving algorithm for the accurate solution of generalized eigenvalue problems for skew-Hamiltonian/Hamiltonian matrix pencils λN − ℋ. By embedding the matrix pencil λ𝒩 − ℋ into a skew-Hamiltonian/Hamiltonian matrix pencil of double size it is possible to avoid the problem of non-existence of a structured Schur form. For these embedded matrix pencils we can compute a particular condensed form to accurately compute the simple, finite, purely imaginary eigenvalues of λ𝒩 − ℋ. In this paper we describe a new method to compute also the corresponding eigenvectors by using the information contained in the condensed form of the embedded matrix pencils and associated transformation matrices. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Perturbation Analysis for the Eigenvalue Problem of a Formal Product of Matrices

We study the perturbation theory for the eigenvalue problem of a formal matrix product A ₁ ^{s 1} ··· A _p ^{s p}, where all A _k are square and s _k {–1, 1}. We generalize the classical perturbation results for matrices and matrix pencils to perturbation results for generalized deflating subspaces and eigenvalues of such formal matrix products. As an application we then extend the structured perturbation theory for the eigenvalue problem of Hamiltonian matrices to Hamiltonian/skew-Hamiltonian pencils.     

On the eigenvalues of quaternion matrices

This article is a continuation of the article [F. Zhang, Ger?gorin type theorems for quaternionic matrices, Linear Algebra Appl. 424 (2007), pp. 139–153] on the study of the eigenvalues of quaternion matrices. Profound differences in the eigenvalue problems for complex and quaternion matrices are discussed. We show that Brauer's theorem for the inclusion of the eigenvalues of complex matrices cannot be extended to the right eigenvalues of quaternion matrices. We also provide necessary and sufficient conditions for a complex square matrix to have infinitely many left eigenvalues, and analyse the roots of the characteristic polynomials for 2?×?2 matrices. We establish a characterisation for the set of left eigenvalues to intersect or be part of the boundary of the quaternion balls of Ger?gorin.     

Equiangular tight frames from complex Seidel matrices containing cube roots of unity

We derive easily verifiable conditions which characterize when complex Seidel matrices containing cube roots of unity have exactly two eigenvalues. The existence of such matrices is equivalent to the existence of equiangular tight frames for which the inner product between any two frame vectors is always a common multiple of the cube roots of unity. We also exhibit a relationship between these equiangular tight frames, complex Seidel matrices, and highly regular, directed graphs. We construct examples of such frames with arbitrarily many vectors.     

Graph covers with two new eigenvalues

A certain signed adjacency matrix of the hypercube, which Hao Huang used last year to resolve the Sensitivity Conjecture, is closely related to the unique, 4-cycle free, 2-fold cover of the hypercube. We develop a framework in which this connection is a natural first example of the relationship between group valued adjacency matrices with few eigenvalues, and combinatorially interesting covering graphs. In particular, we define a two-eigenvalue cover, to be a covering graph whose adjacency spectra differs (as a multiset) from that of the graph it covers by exactly two eigenvalues. We show that walk regularity of a graph implies walk regularity of any abelian two-eigenvalue cover. We also give a spectral characterization for when a cyclic two-eigenvalue cover of a strongly-regular graph is distance-regular.     

两个Hermitian矩阵的Hadamard乘积的特征值估计

Schur定理规定了半正定矩阵的Hadamard乘积的所有特征值的整体界限,Eric Iksoon lm在同样的条件下确定了每个特征值的特殊的界限,本文给出了Hermitian矩阵的Hadamard乘积的每个特征值的估计,改进和推广了I.Schur和Eric Iksoon Im的相应结果。     

具最小二乘谱约束的结构矩阵逼近问题及其扰动分析

从两个方面讨论具有最小二乘谱约束的对称斜哈密尔顿矩阵的逼近问题:(Ⅰ)研究使AX-XA的Frobenius范数最小的n阶实对称斜哈密尔顿矩阵A的集合C,其中X,A分别是特征向量和特征值矩阵, (Ⅱ)求(A)∈c使得‖C-(A)‖=min ‖C-A‖,这里‖·‖是Frobenius范数.给出了C的元素的一般表达式和(A)的显示表达式,分析了该最佳逼近矩阵A的扰动理论,并给出了数值实验.     

A matricial computation of rational quadrature formulas on the unit circle

A matricial computation of quadrature formulas for orthogonal rational functions on the unit circle, is presented in this paper. The nodes of these quadrature formulas are the zeros of the para-orthogonal rational functions with poles in the exterior of the unit circle and the weights are given by the corresponding Christoffel numbers. We show how these nodes can be obtained as the eigenvalues of the operator Möbius transformations of Hessenberg matrices and also as the eigenvalues of the operator Möbius transformations of five-diagonal matrices, recently obtained. We illustrate the preceding results with some numerical examples.     

On the reduction of the normal Hankel problem to two particular cases

The normal Hankel problem (NHP) is to describe complex matrices that are normal and Hankel at the same time. The available results related to the NHP can be combined into two groups. On the one hand, there are several known classes of normal Hankel matrices. On the other hand, the matrix classes that may contain normal Hankel matrices not belonging to the known classes were shown to admit a parametrization by real 2 × 2 matrices with determinant 1. We solve the NHP for the cases where the characteristic matrix W of the given class has: (a) complex conjugate eigenvalues; (b) distinct real eigenvalues. To obtain a complete solution of the NHP, it remains to analyze two situations: (1) W is the Jordan block of order two for the eigenvalue 1; (2) W is the Jordan block of order two for ?1.     

Fast transforms for high order boundary conditions in deconvolution problems

We study strategies to increase the precision in deconvolution models, while maintaining the complexity of the related numerical linear algebra procedures (matrix-vector product, linear system solution, computation of eigenvalues, etc.) of the same order of the celebrated fast Fourier transform. The key idea is the choice of a suitable functional basis to represent signals and images. Starting from an analysis of the spectral decomposition of blurring matrices associated to the antireflective boundary conditions introduced in Serra Capizzano (SIAM J. Sci. Comput. 25(3):1307–1325, 2003), we extend the model for preserving polynomials of higher degree and fast computations also in the nonsymmetric case.     

Location for the right eigenvalues of quaternion matrices

This paper aims to discuss the location for right eigenvalues of quaternion matrices. We will present some different Gerschgorin type theorems for right eigenvalues of quaternion matrices, based on the Gerschgorin type theorem for right eigenvalues of quaternion matrices (Zhang in Linear Algebra Appl. 424:139?C153, 2007), which are used to locate the right eigenvalues of quaternion matrices. We shall conclude this paper with some easily computed regions which are guaranteed to include the right eigenvalues of quaternion matrices in 4D spaces.     

Generalized minimax and interlacing theorems

We give some steps towards a unified theory of Courant-Fischer minimax-type formulas and Cauchy interlacing-type inequalities that have been obtained for the eigenvalues of Hermitian matrices, for singular values of complex matrices, and for invariant factors of integral matrices

We also unify and extend work on eigenvalues, singular values, and invariant factors of pairs of matrices and their sum or product     

On products and line graphs of signed graphs, their eigenvalues and energy

In this article we examine the adjacency and Laplacian matrices and their eigenvalues and energies of the general product (non-complete extended p-sum, or NEPS) of signed graphs. We express the adjacency matrix of the product in terms of the Kronecker matrix product and the eigenvalues and energy of the product in terms of those of the factor graphs. For the Cartesian product we characterize balance and compute expressions for the Laplacian eigenvalues and Laplacian energy. We give exact results for those signed planar, cylindrical and toroidal grids which are Cartesian products of signed paths and cycles.We also treat the eigenvalues and energy of the line graphs of signed graphs, and the Laplacian eigenvalues and Laplacian energy in the regular case, with application to the line graphs of signed grids that are Cartesian products and to the line graphs of all-positive and all-negative complete graphs.     

Additive block diagonal preconditioning for block two-by-two linear systems of skew-Hamiltonian coefficient matrices

For a class of block two-by-two systems of linear equations with certain skew-Hamiltonian coefficient matrices, we construct additive block diagonal preconditioning matrices and discuss the eigen-properties of the corresponding preconditioned matrices. The additive block diagonal preconditioners can be employed to accelerate the convergence rates of Krylov subspace iteration methods such as MINRES and GMRES. Numerical experiments show that MINRES preconditioned by the exact and the inexact additive block diagonal preconditioners are effective, robust and scalable solvers for the block two-by-two linear systems arising from the Galerkin finite-element discretizations of a class of distributed control problems.     

A new derivation of eigenvalue inequalities for the multinomial distribution

We consider the covariance matrix of the multinomial distribution. We suggest a new derivation of inequalities for the eigenvalues of this matrix using a classical result on the product of two positive semi-definite matrices.     

Maximal eigenvalue and norm of a product of Toeplitz matrices. Study of a particular case

In this paper we describe the asymptotic behaviour of the spectral norm of the product of two finite Toeplitz matrices as the matrix dimension goes to infinity. These Toeplitz matrices are generated by functions with Fisher–Hartwig singularities of negative order. If these functions are positives the product of the two matrices has positive eigenvalues and it is known that the spectral norm is also the largest eigenvalue of this product.     

A curvilinear method based on minimal-memory BFGS updates

We present a new matrix-free method for the computation of negative curvature directions based on the eigenstructure of minimal-memory BFGS matrices. We determine via simple formulas the eigenvalues of these matrices and we compute the desirable eigenvectors by explicit forms. Consequently, a negative curvature direction is computed in such a way that avoids the storage and the factorization of any matrix. We propose a modification of the L-BFGS method in which no information is kept from old iterations, so that memory requirements are minimal. The proposed algorithm incorporates a curvilinear path and a linesearch procedure, which combines two search directions; a memoryless quasi-Newton direction and a direction of negative curvature. Results of numerical experiments for large scale problems are also presented.     

A block-Lanczos method for large continuation problems

The computation of solution paths of large-scale continuation problems can be quite challenging because a large amount of computations have to be carried out in an interactive computing environment. The computations involve the solution of a sequence of large nonlinear problems, the detection of turning points and bifurcation points, as well as branch switching at bifurcation points. These tasks can be accomplished by computing the solution of a sequence of large linear systems of equations and by determining a few eigenvalues close to the origin, and associated eigenvectors, of the matrices of these systems. We describe an iterative method that simultaneously solves a linear system of equations and computes a few eigenpairs associated with eigenvalues of small magnitude of the matrix. The computation of the eigenvectors has the effect of preconditioning the linear system, and numerical examples show that the simultaneous computation of the solution and eigenpairs can be faster than only computing the solution. Our iterative method is based on the block-Lanczos algorithm and is applicable to continuation problems with symmetric Jacobian matrices. This revised version was published online in June 2006 with corrections to the Cover Date.