Transition matrices for well-conditioned Markov chains

Let T∈R^n×n be an irreducible stochastic matrix with stationary distribution vector π. Set A = I − T, and define the quantity , where A_j, j = 1, … , n, are the (n − 1) × (n − 1) principal submatrices of A obtained by deleting the jth row and column of A. Results of Cho and Meyer, and of Kirkland show that κ₃ provides a sensitive measure of the conditioning of π under perturbation of T. Moreover, it is known that .In this paper, we investigate the class of irreducible stochastic matrices T of order n such that , for such matrices correspond to Markov chains with desirable conditioning properties. We identify some restrictions on the zero-nonzero patterns of such matrices, and construct several infinite classes of matrices for which κ₃ is as small as possible.     

The case of equality in the Dobrushin-Deutsch-Zenger bound

Suppose that A=(a_i,j) is an n×n real matrix with constant row sums μ. Then the Dobrushin-Deutsch-Zenger (DDZ) bound on the eigenvalues of A other than μ is given by . When A a transition matrix of a finite homogeneous Markov chain so that μ=1,Z(A) is called the coefficient of ergodicity of the chain as it bounds the asymptotic rate of convergence, namely, , of the iteration , to the stationary distribution vector of the chain.In this paper we study the structure of real matrices for which the DDZ bound is sharp. We apply our results to the study of the class of graphs for which the transition matrix arising from a random walk on the graph attains the bound. We also characterize the eigenvalues λ of A for which |λ|=Z(A) for some stochastic matrix A.     

OMC for scalar multiples of unitaries

We establish the following case of the Determinantal Conjecture of Marcus [M. Marcus, Derivations, Plücker relations and the numerical range, Indiana Univ. Math. J. 22 (1973) 1137-1149] and de Oliveira [G.N. de Oliveira, Research problem: Normal matrices, Linear and Multilinear Algebra 12 (1982) 153-154]. Let A and B be unitary n × n matrices with prescribed eigenvalues a₁, … , a_n and b₁, … , b_n, respectively. Then for any scalars t and s

     

Preservers of spectral radius, numerical radius, or spectral norm of the sum on nonnegative matrices

Let be the set of entrywise nonnegative n×n matrices. Denote by r(A) the spectral radius (Perron root) of . Characterization is obtained for maps such that r(f(A)+f(B))=r(A+B) for all . In particular, it is shown that such a map has the form

     

Eigenvalues and degree deviation in graphs

Let G be a graph with n vertices and m edges and let μ(G) = μ₁(G) ? ? ? μ_n(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑_u∈V(G)∣d(u)-2m/n∣. We prove that

     

A note on the perturbation of positive matrices by normal and unitary matrices

In a recent paper, Neumann and Sze considered for an n × n nonnegative matrix A, the minimization and maximization of ρ(A + S), the spectral radius of (A + S), as S ranges over all the doubly stochastic matrices. They showed that both extremal values are always attained at an n × n permutation matrix. As a permutation matrix is a particular case of a normal matrix whose spectral radius is 1, we consider here, for positive matrices A such that (A + N) is a nonnegative matrix, for all normal matrices N whose spectral radius is 1, the minimization and maximization problems of ρ(A + N) as N ranges over all such matrices. We show that the extremal values always occur at an n × n real unitary matrix. We compare our results with a less recent work of Han, Neumann, and Tastsomeros in which the maximum value of ρ(A + X) over all n × n real matrices X of Frobenius norm was sought.     

Laplacian energy of a graph

Let G be a graph with n vertices and m edges. Let λ₁, λ₂, … , λ_n be the eigenvalues of the adjacency matrix of G, and let μ₁, μ₂, … , μ_n be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences.     

A note on complex matrices that are unitarily congruent to real matrices

Every square complex matrix is known to be consimilar to a real matrix. Unitary congruence is a particular type of consimilarity. We prove that a matrix A∈M_n(C) is unitarily congruent to a real matrix if and only if A is unitarily congruent to via a symmetric unitary matrix. It is shown by an example that there exist matrices that are congruent, but not unitarily congruent, to real matrices.     

Low rank perturbation of regular matrix polynomials

Let A(λ) be a complex regular matrix polynomial of degree ? with g elementary divisors corresponding to the finite eigenvalue λ₀. We show that for most complex matrix polynomials B(λ) with degree at most ? satisfying rank the perturbed polynomial (A+B)(λ) has exactly elementary divisors corresponding to λ₀, and we determine their degrees. If does not exceed the number of λ₀-elementary divisors of A(λ) with degree greater than 1, then the λ₀-elementary divisors of (A+B)(λ) are the elementary divisors of A(λ) corresponding to λ₀ with smallest degree, together with rank(B(λ)-B(λ₀)) linear λ₀-elementary divisors. Otherwise, the degree of all the λ₀-elementary divisors of (A+B)(λ) is one. This behavior happens for any matrix polynomial B(λ) except those in a proper algebraic submanifold in the set of matrix polynomials of degree at most ?. If A(λ) has an infinite eigenvalue, the corresponding result follows from considering the zero eigenvalue of the perturbed dual polynomial.     

Large matchings from eigenvalues

We find lower bounds on the difference between the spectral radius λ₁ and the average degree of an irregular graph G of order n and size e. In particular, we show that, if n ? 4, then

     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

The Dirichlet Markov Ensemble

We equip the polytope of n×n Markov matrices with the normalized trace of the Lebesgue measure of Rⁿ². This probability space provides random Markov matrices, with i.i.d. rows following the Dirichlet distribution of mean (1/n,…,1/n). We show that if is such a random matrix, then the empirical distribution built from the singular values of tends as n→∞ to a Wigner quarter-circle distribution. Some computer simulations reveal striking asymptotic spectral properties of such random matrices, still waiting for a rigorous mathematical analysis. In particular, we believe that with probability one, the empirical distribution of the complex spectrum of tends as n→∞ to the uniform distribution on the unit disc of the complex plane, and that moreover, the spectral gap of is of order when n is large.     

On approximately simultaneously diagonalizable matrices

A collection A₁, A₂, …, A_k of n × n matrices over the complex numbers C has the ASD property if the matrices can be perturbed by an arbitrarily small amount so that they become simultaneously diagonalizable. Such a collection must perforce be commuting. We show by a direct matrix proof that the ASD property holds for three commuting matrices when one of them is 2-regular (dimension of eigenspaces is at most 2). Corollaries include results of Gerstenhaber and Neubauer-Sethuraman on bounds for the dimension of the algebra generated by A₁, A₂, …, A_k. Even when the ASD property fails, our techniques can produce a good bound on the dimension of this subalgebra. For example, we establish for commuting matrices A₁, …, A_k when one of them is 2-regular. This bound is sharp. One offshoot of our work is the introduction of a new canonical form, the H-form, for matrices over an algebraically closed field. The H-form of a matrix is a sparse “Jordan like” upper triangular matrix which allows us to assume that any commuting matrices are also upper triangular. (The Jordan form itself does not accommodate this.)     

A link between the Perron-Frobenius theorem and Perron’s theorem for difference equations

Let A_n,n∈N, be a sequence of k×k matrices which converge to a matrix A as n→∞. It is shown that if x_n,n∈N, is a sequence of nonnegative nonzero vectors such that

     

Reduction of the c-numerical range to the classical numerical range

Let A be an n×n complex matrix and c=(c₁,c₂,…,c_n) a real n-tuple. The c-numerical range of A is defined as the set

     

Numerical ranges of weighted shift matrices

We show that if A is an n-by-n (n?3) matrix of the form

     

Isospectral flows that preserve matrix structure

The matrix A = (a_ij) ∈ S_n is said to lie on a strict undirected graph G if a_ij = 0 (i ≠ j) whenever (i, j) is not in E(G). If S is skew-symmetric, the isospectral flow maintains the spectrum of A. We consider isospectral flows that maintain a matrix A(t) on a given graph G. We review known results for a graph G that is a (generalised) path, and construct isospectral flows for a (generalised) ring, and a star, and show how a flow may be constructed for a general graph. The analysis may be applied to the isospectral problem for a lumped-mass finite element model of an undamped vibrating system. In that context, it is important that the flow maintain other properties such as irreducibility or positivity, and we discuss whether they are maintained.     

Some relations between rank of a graph and its complement

Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that .     

No eigenvalues outside the support of the limiting empirical spectral distribution of a separable covariance matrix

We consider a class of matrices of the form , where X_n is an n×N matrix consisting of i.i.d. standardized complex entries, is a nonnegative definite square root of the nonnegative definite Hermitian matrix A_n, and B_n is diagonal with nonnegative diagonal entries. Under the assumption that the distributions of the eigenvalues of A_n and B_n converge to proper probability distributions as , the empirical spectral distribution of C_n converges a.s. to a non-random limit. We show that, under appropriate conditions on the eigenvalues of A_n and B_n, with probability 1, there will be no eigenvalues in any closed interval outside the support of the limiting distribution, for sufficiently large n. The problem is motivated by applications in spatio-temporal statistics and wireless communications.