Row Stochastic Matrices Similar to Doubly Stochastic Matrices

The problem of determining which row stochastic n-by-n matrices are similar to doubly stochastic matrices is considered. That not all are is indicated by example, and an abstract characterization as well as various explicit sufficient conditions are given. For example, if a row stochastic matrix has no entry smaller than (n+1)^-1 it is similar to a doubly stochastic matrix.

Relaxing the nonnegativity requirement, the real matrices which are similar to real matrices with row and column sums one are then characterized, and it is observed that all row stochastic matrices have this property. Some remarks are then made on the nonnegative eigenvalue problem with respect to i) a necessary trace inequality and ii) removing zeroes from the spectrum.     

Essentially doubly stochastic matrices

In this paper we extend the general theory of essentially doubly stochastic (e.d.s.) matrices begun in earlier papers in this series. We complete the investigation in one direction by characterizing all of the algebra isomorphisms between the algebra of e.d.s. matrices of order n over a field F,E_n(F), and the total algebra of matrices of order n - 1over F,M_n-1(F) We then develop some of the theory when Fis a field with an involution. We show that for any e,f§Fof norm 1,e≠f every e.d.s. matrix in E_n(F) is a unique e.d.s. sum of an e.d.s. e-hermitian matrix and an e.d.s. f-hermitian matrix in E_n(F) Next, we completely determine the cases for which there exists an above-mentioned matrix algebra isomorphism preserving adjoints. Finally, we consider cogredience in E_n(F) and show that when such an adjoint-preserving isomorphism exists and char M_n(F) two e.d.s. e-hermitian matrices which are cogredient in M_n(F) are also cogredient in E_n(F). Using this result, we obtain simple canonical forms for cogredience of e.d.s. e-hermitian matrices in E_n(F) when Fsatisfies special conditions. This ncludes the e.d.s. skew-symmetric matrices, where the involution is trivial and E = -1.     

Column Ranks and Their Preservers of Matrices Over Max Algebra

The column rank of an m by n matrix A over max algebra is the weak dimension of the column space of A. We compare the column rank with rank of matrices over max algebra. We also characterize the linear operators which preserve the column rank of matrices over max algebra.     

Common eigenvectors of two matrices

A computable criterion is given for two square matrices to possess a common eigenvector, as well as a criterion for one matrix to have an eigenvector lying in a given subspace. Some applications are discussed.     

A tensor product matrix approximation problem in quantum physics

We consider a matrix approximation problem arising in the study of entanglement in quantum physics. This notion represents a certain type of correlations between subsystems in a composite quantum system. The states of a system are described by a density matrix, which is a positive semidefinite matrix with trace one. The goal is to approximate such a given density matrix by a so-called separable density matrix, and the distance between these matrices gives information about the degree of entanglement in the system. Separability here is expressed in terms of tensor products. We discuss this approximation problem for a composite system with two subsystems and show that it can be written as a convex optimization problem with special structure. We investigate related convex sets, and suggest an algorithm for this approximation problem which exploits the tensor product structure in certain subproblems. Finally some computational results and experiences are presented.     

A bound for the condition of a hyperbolic eigenvector matrix

The hyperbolic eigenvector matrix is a matrix X which simultaneously diagonalizes the pair (H,J), where H is Hermitian positive definite and J = diag(±1) such that X*HX = Δ and X*JX = J. We prove that the spectral condition of X, κ(X), is bounded byK(X)√minK(D^*HD), where the minimum is taken over all non-singular matrices D which commute with J. This bound is attainable and it can be simply computed. Similar results hold for other signature matrices J, like in the discretized Klein—Gordon equation.     

Newton's method for the common eigenvector problem

In El Ghazi et al. [Backward error for the common eigenvector problem, CERFACS Report TR/PA/06/16, Toulouse, France, 2006], we have proved the sensitivity of computing the common eigenvector of two matrices A and B, and we have designed a new approach to solve this problem based on the notion of the backward error.If one of the two matrices (saying A) has n eigenvectors then to find the common eigenvector we have just to write the matrix B in the basis formed by the eigenvectors of A. But if there is eigenvectors with multiplicity >1, the common vector belong to vector space of dimension >1 and such strategy would not help compute it.In this paper we use Newton's method to compute a common eigenvector for two matrices, taking the backward error as a stopping criteria.We mention that no assumptions are made on the matrices A and B.     

Computing an Eigenvector of a Monge Matrix in Max-Plus Algebra

The problem of finding one eigenvector of a given Monge matrix A in a max-plus algebra is considered. For a general matrix, the problem can be solved in O(n ³) time by computing one column of the corresponding metric matrix Δ(A _λ), where λ is the eigenvalue of A. An algorithm is presented, which computes an eigenvector of a Monge matrix in O(n ²) time.     

A new differential equation method for finding the Perron root of a positive matrix

A basic problem in linear algebra is the determination of the largest eigenvalue (Perron root) of a positive matrix. In the present paper a new differential equation method for finding the Perron root is given. The method utilizes the initial value differential system developed in a companion paper for individually tracking the eigenvalue and corresponding right eigenvector of a parametrized matrix.     

Finding all essential terms of a characteristic maxpolynomial

Let us denote ab=max(a,b) and ab=a+b for and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n²(m+n log n)) algorithm for finding all essential terms of the max-algebraic characteristic polynomial of an n×n matrix over with m finite elements. In the cases when all terms are essential, this algorithm also solves the following problem: Given an n×n matrix A and k{1,…,n}, find a k×k principal submatrix of A whose assignment problem value is maximum.     

Analysis of sensitivity of reciprocal matrices

We develop a method based on the Hadamard Product of matrices to analyze the sensitivity of reciprocal matrices. We show that this type of matrices can be decomposed into the Hadamard Product of a consistent matrix and an inconsistent matrix. The consistent matrix has the same principal eigenvector as the original matrix, and the inconsistent matrix has the same principal eigenvalue as the original one. We use this decomposition in the analysis of sensitivity to compute the principle eigenvector of a perturbed reciprocal matrix.     

Some generators for the algebra of n×n matrices

In this note, we show how the algebra of n×n matrices over a field can be generated by a pair of matrices AB, where A is an arbitrary nonscalar matrix and B can be chosen so that there is the maximum degree of linear independence between the higher commutators of B with A.     

Self-duality results for unitary and hermitian matrices

It is known that, if T is an n × n complex matrix such that every characteristic root of UT has modulus I for every n × n unitary matrix U then T must be unitary. This paper generalizes this result in two directions, one of which provides a proof of a 1971 conjecture of M. Marcus. An analogous self-duaiity result is given for hermitian matrices, and several additional results of self-duality type are given concerning hermitian matrices and real matrices, using the trace and the determinant.     

Lie products in incidence algebras

We give conditions when a strictly upper triangular element of an incidence algebra over a commutative ring is the Lie commutator of two elements of the incidence algebra, one of which is strictly upper triangular. In particular, it follows that this is the case for the ring of n × n upper triangular matrices, where n is either finite or infinite.     

Partly zero eigenvectors

This paper is concerned with the forced presence or absence of zero components in an eigenvector. Relative to a fixed matrix Awith eigenvalue λ, we characterize the strictly nonzero part of a partly zero eigenvector associated with λ. We also give a sufficient condition for a fixed matrix to have a partly zero eigenvector, and discuss several examples in which a matrix has one or more partly zero eigenvectors. Our main results, however, are qualitative in nature. We associate a zero/nonzero pattern class of matrices with a digraph, and characterize the set of pattern classes which requires all eigenvectors to be strictly nonzero. A sufficient condition is also given that identifies the components of a partly zero eigenvector which may be nonzero.     

MATRIX EQUATION AXB = E WITH PX = sXP CONSTRAINT

The matrix equation AXB = E with the constraint PX=sXP is considered,where P is a given Hermitian matrix satisfying p~2=I and s=±1.By an eigenvalue decomposition of P,the constrained problem can be equivalently transformed to a well-known unconstrained problem of matrix equation whose coefficient matrices contain the corresponding eigenvector, and hence the constrained problem can be solved in terms of the eigenvectors of P.A simple and eigenvector-free formula of the general solutions to the constrained problem by generalized inverses of the coefficient matrices A and B is presented.Moreover,a similar problem of the matrix equation with generalized constraint is discussed.     

Matrix realizations of littlewood—richardson sequences

In this paper we consider the problem of characterizing the invariant factors of three matrices AB, and C, such that AB — C Our matrices have entries over a principal ideal domain or over a local domain. In Section 2 we show that this problem is localizablc

The above problem lias a well-known solution in terms of Littlewood-Richardson sequences. We introduce the concept of a matrix realization of a Littlewood-Richardson sequence. The main result is an explicit construction of a sequence of matrices which realizes a previously given Littlewood Richardson sequence. Our methods offer a matrix theoretical proof of a well-known result of T, Klein on extensions of p-modules.     

On Eigenvector Bounds

We show under very general assumptions that error bounds for an individual eigenvector of a matrix can be computed if and only if the geometric multiplicity of the corresponding eigenvalue is one. Basically, this is true if not computing exactly like in computer algebra methods. We first show, under general assumptions, that nontrivial error bounds are not possible in case of geometric multiplicity greater than one. This result is also extended to symmetric, Hermitian and, more general, to normal matrices. Then we present an algorithm for the computation of error bounds for the (up to normalization) unique eigenvector in case of geometric multiplicity one. The effectiveness is demonstrated by numerical examples.This revised version was published online in October 2005 with corrections to the Cover Date.     

On the derivative of the Perron vector whose infinity norm is fixed

In the recent paper the authors studied the derivaties of the Perron vector at an n × n essentially nonnegative and irreducible matrix A when the Perron vector is subjected to the normalization that one of its components is held a fixed constant in a neighbourhood of A or that the pth norm of the of the eigenvector is held a fixed constant in such a neighborhood. The Perron vector subject to the normalization that its infinity norm is held a fixed constant in a neighborhood of A does not necessarily imply that it is differentiable at A. In this paper we give formulas for the first derivative of this Perron vector where it is differentiable. Our formulas also accommodate left and right derivatives of the eigenvector.     

Nonsingularity of some classes of matrices, and minimal solutions of Silverman''s game on discrete sets

We establish the irreducibility of each game in four infinite three-parameter families of even order Silverman games, and the major step in doing so is to prove that certain matrices A, related in a simple way to the payoff matrices, are nonsingular for all relevant values of the parameters. This nonsingularity is established by, in effect, producing a matrix D such that AD is known to be nonsingular. The elements of D are polynomials from six interrelated sequences of polynomials closely related to the Chebyshev polynomials of the second kind. Each of these sequences satisfies a second order recursion, and consequently has many Fibonacci-like properties, which play an essential role in proving that the product AD is what we claim it is. The matrices D were found experimentally, by discovering patterns in low order cases worked out with the help of some computer algebra systems. The corresponding results for four families of odd order games were reported in an earlier paper.