Symmetrizers of matrices

A symmetrizer of a given pair of matrices, A and B, is defined as a matrix X for which the product AXB is symmetric. Right and left symmetrizers of a given matrix A are defined accordingly. The main results of the paper are general representations of all three types of symmetrizers. The problem considered arose in connection with certain questions pertaining to admissible linear estimation in a Gauss-Markoff model.     

Two theorems on integral matrices

The following two results are proved: (1) For a positive definite integral symmetric matrix S of rank (S) < 7 or when rank (S) = 8, S has an odd entry in its diagonal, there is an integral matrix A satisfying AA^t = Sif there is a rational matrix R with RR^t = S (2) Given an integral matrix A of size r×n such that AA^t = mI_r there is then always an integral completion matrix B of size n×n satisfying BB^t = mI_r whenever n-r is less than or equal to 7. This threshold number 7 is the best possible. (Here m, n satisfy the obvious necessary conditions.)     

The Well-Posedness Issue in Sobolev Spaces for Hyperbolic Systems with Zygmund-Type Coefficients

In this paper we study the well-posedness of the Cauchy problem for first order hyperbolic systems with constant multiplicities and with low regularity coefficients depending just on the time variable. We consider Zygmund and log-Zygmund type assumptions, and we prove well-posedness in H^∞ respectively without loss and with finite loss of derivatives. The key to obtain the results is the construction of a suitable symmetrizer for our system, which allows us to recover energy estimates (with or without loss) for the hyperbolic operator under consideration. This can be achievied, in contrast with the classical case of systems with smooth (say Lipschitz) coefficients, by adding one step in the diagonalization process, and building the symmetrizer up to the second order.     

Zero‐sum flows in designs

Let D be a t ‐ ( v, k , λ) design and let N _i (D) , for 1 ≤ i ≤ t , be the higher incidence matrix of D , a ( 0 , 1 )‐matrix of size , where b is the number of blocks of D . A zero‐sum flow of D is a nowhere‐zero real vector in the null space of N ₁ ( D ). A zero‐sum k‐flow of D is a zero‐sum flow with values in { 1 , …, ±( k ? 1 )}. In this article, we show that every non‐symmetric design admits an integral zero‐sum flow, and consequently we conjecture that every non‐symmetric design admits a zero‐sum 5‐flow. Similarly, the definition of zero‐sum flow can be extended to N _i ( D ), 1 ≤ i ≤ t . Let be the complete design. We conjecture that N _t ( D ) admits a zero‐sum 3‐flow and prove this conjecture for t = 2 . © 2011 Wiley Periodicals, Inc. J Combin Designs 19:355‐364, 2011     

A nonsymmetric matrix with integer eigenvalues

A nonsymmetric N?×?N matrix with elements as certain simple functions of N distinct real or complex numbers r ₁, r ₂, …, r_N is presented. The matrix is special due to its eigenvalues???the consecutive integers 0,1,2, …, N?1. Theorems are given establishing explicit expressions of the right and left eigenvectors and formulas for recursive calculation of the right eigenvectors. A special case of the matrix has appeared in sampling theory where its right eigenvectors, if properly normalized, give the inclusion probabilities of the conditional Poisson sampling design.     

Fast approximate truncated SVD

This paper presents a new method for the computation of truncated singular value decomposition (SVD) of an arbitrary matrix. The method can be qualified as deterministic because it does not use randomized schemes. The number of operations required is asymptotically lower than that using conventional methods for nonsymmetric matrices and is at a par with the best existing deterministic methods for unstructured symmetric ones. It slightly exceeds the asymptotical computational cost of SVD methods based on randomization; however, the error estimate for such methods is significantly higher than for the presented one. The method is one‐pass, that is, each value of the matrix is used just once. It is also readily parallelizable. In the case of full SVD decomposition, it is exact. In addition, it can be modified for a case when data are obtained sequentially rather than being available all at once. Numerical simulations confirm accuracy of the method.     

On some structured inverse eigenvalue problems

This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problems (SIEP). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (JIEP): given some constraints on two sets of reals, find a Jacobi matrix J (real, symmetric, tridiagonal, with positive off-diagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm which is based on a special Euclid–Sturm algorithm (Householder's terminology) and has been rediscovered several times. The matrix algorithm which is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix ensures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the nonsymmetric case. This is the second SIEP to be considered: the Tridiagonal Inverse Eigenvalue Problem (TIEP). Possible breakdowns may occur in the polynomial algorithm as it may happen with the nonsymmetric Lanczos algorithm. The connection between the two algorithms exhibits a similarity transformation from the classical Frobenius companion matrix to the tridiagonal matrix. This result is used to illustrate the fact that, when computing the eigenvalues of a matrix, the nonsymmetric Lanczos algorithm may lead to a slow convergence, even for a symmetric matrix, since an outer eigenvalue of the tridiagonal matrix of order n − 1 can be arbitrarily far from the spectrum of the original matrix. This revised version was published online in August 2006 with corrections to the Cover Date.     

The solvability conditions for inverse eigenproblem of symmetric and anti‐persymmetric matrices and its approximation

The problem of generating a matrix A with specified eigen‐pair, where A is a symmetric and anti‐persymmetric matrix, is presented. An existence theorem is given and proved. A general expression of such a matrix is provided. We denote the set of such matrices by ??????_Eⁿ. The optimal approximation problem associated with ??????_Eⁿ is discussed, that is: to find the nearest matrix to a given matrix A* by A∈??????_Eⁿ. The existence and uniqueness of the optimal approximation problem is proved and the expression is provided for this nearest matrix. Copyright © 2002 John Wiley & Sons, Ltd.     

Generating orthogonal matrix polynomials satisfying second order differential equations from a trio of triangular matrices

The method developed in [A.J. Durán, F.A. Grünbaum, Orthogonal matrix polynomials satisfying second order differential equations, Int. Math. Res. Not. 10 (2004) 461–484] led us to consider matrix polynomials that are orthogonal with respect to weight matrices W(t) of the form , , and (1−t)^α(1+t)^βT(t)T^*(t), with T satisfying T^′=(2Bt+A)T, T(0)=I, T^′=(A+B/t)T, T(1)=I, and T^′(t)=(−A/(1−t)+B/(1+t))T, T(0)=I, respectively. Here A and B are in general two non-commuting matrices. We are interested in sequences of orthogonal polynomials (P_n)_n which also satisfy a second order differential equation with differential coefficients that are matrix polynomials F₂, F₁ and F₀ (independent of n) of degrees not bigger than 2, 1 and 0 respectively. To proceed further and find situations where these second order differential equations hold, we only dealt with the case when one of the matrices A or B vanishes.The purpose of this paper is to show a method which allows us to deal with the case when A, B and F₀ are simultaneously triangularizable (but without making any commutativity assumption).     

Error-free matrix symmetrizers and equivalent symmetric matrices

A symmetrizer of the matrix A is a symmetric solution X that satisfies the matrix equation XA=AX. An exact matrix symmetrizer is computed by obtaining a general algorithm and superimposing a modified multiple modulus residue arithmetic on this algorithm. A procedure based on computing a symmetrizer to obtain a symmetric matrix, called here an equivalent symmetric matrix, whose eigenvalues are the same as those of a given real nonsymmetric matrix is presented.Supported by CSIR.     

Computing a matrix symmetrizer exactly using modified multiple modulus residue arithmetic

A symmetric solution X satisfying the matrix equation XA = A^tX is called a symmetrizer of the matrix A. A general algorithm to compute a matrix symmetrizer is obtained. A new multiple-modulus residue arithmetic called floating-point modular arithmetic is described and implemented on the algorithm to compute an error-free matrix symmetrizer.     

Fast and Stable Reduction of Diagonal Plus Semi-Separable Matrices to Tridiagonal and Bidiagonal Form

A two-way chasing algorithm to reduce a diagonal plus a symmetric semi-separable matrix to a symmetric tridiagonal one and an algorithm to reduce a diagonal plus an unsymmetric semi-separable matrix to a bidiagonal one are considered. Both algorithms are fast and stable, requiring a computational cost of N ², where N is the order of the considered matrix.     

Extending the eigCG algorithm to nonsymmetric Lanczos for linear systems with multiple right‐hand sides

The technique that was used to build the eigCG algorithm for sparse symmetric linear systems is extended to the nonsymmetric case using the BiCG algorithm. We show that, similar to the symmetric case, we can build an algorithm that is capable of computing a few smallest magnitude eigenvalues and their corresponding left and right eigenvectors of a nonsymmetric matrix using only a small window of the BiCG residuals while simultaneously solving a linear system with that matrix. For a system with multiple right‐hand sides, we give an algorithm that computes incrementally more eigenvalues while solving the first few systems and then uses the computed eigenvectors to deflate BiCGStab for the remaining systems. Our experiments on various test problems, including Lattice QCD, show the remarkable ability of eigBiCG to compute spectral approximations with accuracy comparable with that of the unrestarted, nonsymmetric Lanczos. Furthermore, our incremental eigBiCG followed by appropriately restarted and deflated BiCGStab provides a competitive method for systems with multiple right‐hand sides. Copyright © 2013 John Wiley & Sons, Ltd.     

The generalized centro‐symmetric and least squares generalized centro‐symmetric solutions of the matrix equation AYB + CYTD = E

An n×n real matrix P is said to be a symmetric orthogonal matrix if P = P^?1 = P^T. An n × n real matrix Y is called a generalized centro‐symmetric with respect to P, if Y = PYP. It is obvious that every matrix is also a generalized centro‐symmetric matrix with respect to I. In this work by extending the conjugate gradient approach, two iterative methods are proposed for solving the linear matrix equation and the minimum Frobenius norm residual problem over the generalized centro‐symmetric Y, respectively. By the first (second) algorithm for any initial generalized centro‐symmetric matrix, a generalized centro‐symmetric solution (least squares generalized centro‐symmetric solution) can be obtained within a finite number of iterations in the absence of round‐off errors, and the least Frobenius norm generalized centro‐symmetric solution (the minimal Frobenius norm least squares generalized centro‐symmetric solution) can be derived by choosing a special kind of initial generalized centro‐symmetric matrices. We also obtain the optimal approximation generalized centro‐symmetric solution to a given generalized centro‐symmetric matrix Y₀ in the solution set of the matrix equation (minimum Frobenius norm residual problem). Finally, some numerical examples are presented to support the theoretical results of this paper. Copyright © 2011 John Wiley & Sons, Ltd.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

Roux-type constructions for covering arrays of strengths three and four

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t-sets of component interactions. Recursive constructions for covering arrays of strengths 3 and 4 are developed, generalizing many “Roux-type” constructions. A numerical comparison with current construction techniques is given through existence tables for covering arrays.      

Pivoting strategy for rank-one modification ofLDM t-like factorization

The rank-one modification algorithm of theLDM ^t factorization was given by Bennett [1]. His method, however, could break down even when the matrix is nonsingular and well-conditioned. We introduce a pivoting strategy for avoiding possible break-down as well as for suppressing error growth in the modification process. The method is based on a symbolic formula of the rank-one modification of the factorization of a possibly singular nonsymmetric matrix. A new symbolic formula is also obtained for the inverses of the factor matrices. Repeated application of our method produces theLDM ^t-like product form factorization of a matrix. A numerical example is given to illustrate our pivoting method. An incomplete factorization algorithm is also introduced for updating positive definite matrix useful in quasi-Newton methods, in which the Fletcher and Powell algorithm [2] and the Gill, Murray and Saunders algorithm [4] are usually used.This paper is presented at the Japan SIAM Annual Meeting held at University of Tokyo, Japan, October 7–9, 1991.     

Minimal harmoniously colorable designs

A graph G is minimal harmoniously colorable if it has a proper vertex coloring in which each pair of colors occurs exactly once on an edge. In particular, if D is a 2-design we consider the graph G whose vertices are the points and blocks of D and where two vertices of G are adjacent if and only if the corresponding elements of D are incident. It will be shown that if D is symmetric then G is minimal harmoniously colorable if and only if D is a Hadamard design with corresponding Hadamard matrix of a certain form. We obtain some results if D is nonsymmetric, and construct two classes of nonsymmetric minimal harmoniously colorable designs. © 1994 John Wiley & Sons, Inc.     

Some examples of orthogonal matrix polynomials satisfying odd order differential equations

It is well known that if a finite order linear differential operator with polynomial coefficients has as eigenfunctions a sequence of orthogonal polynomials with respect to a positive measure (with support in the real line), then its order has to be even. This property no longer holds in the case of orthogonal matrix polynomials. The aim of this paper is to present examples of weight matrices such that the corresponding sequences of matrix orthogonal polynomials are eigenfunctions of certain linear differential operators of odd order. The weight matrices are of the form

W(t)=t^αe^-te^Att^Bt^B*e^A*t,