Max algebraic powers of irreducible matrices in the periodic regime: An application of cyclic classes

In max algebra it is well known that the sequence of max algebraic powers A^k, with A an irreducible square matrix, becomes periodic after a finite transient time T(A), and the ultimate period γ is equal to the cyclicity of the critical graph of A.In this connection, we study computational complexity of the following problems: (1) for a given k, compute a periodic power A^r with and r?T(A), (2) for a given x, find the ultimate period of {A^l⊗x}. We show that both problems can be solved by matrix squaring in O(n³logn) operations. The main idea is to apply an appropriate diagonal similarity scaling A?X^-1AX, called visualization scaling, and to study the role of cyclic classes of the critical graph.     

Two cores of a nonnegative matrix

We prove that the sequence of eigencones (i.e., cones of nonnegative eigenvectors) of positive powers A^k$A^k$ of a nonnegative square matrix A is periodic both in max algebra and in nonnegative linear algebra. Using an argument of Pullman, we also show that the Minkowski sum of the eigencones of powers of A is equal to the core of A defined as the intersection of nonnegative column spans of matrix powers, also in max algebra. Based on this, we describe the set of extremal rays of the core.     

Construction and nonnegativity of sign idempotent sign pattern matrices

In this paper, we modify Eschenbach’s algorithm for constructing sign idempotent sign pattern matrices so that it correctly constructs all of them. We find distinct classes of sign idempotent sign pattern matrices that are signature similar to an entrywise nonnegative sign pattern matrix. Additionally, if for a sign idempotent sign pattern matrix A there exists a signature matrix S such that SAS is nonnegative, we prove such S is unique up to multiplication by -1 if the signed digraph D(A) is not disconnected.     

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.     

A max version of the generalized spectral radius theorem

Let Ψ be a bounded set of n × n nonnegative matrices in max algebra. In this paper we propose the notions of the max algebra version of the generalized spectral radius μ(Ψ) of Ψ, and the max algebra version of the joint spectral radius η(Ψ) of Ψ. The max algebra version of the generalized spectral radius theorem μ(Ψ) = η(Ψ) is established. We propose the relationship between the generalized spectral radius ρ(Ψ) of Ψ (in the sense of Daubechies and Lagarias) and its max algebra version μ(Ψ). Moreover, a generalization of Elsner and van den Driessche’s lemma is presented as well.     

Max-algebraic attraction cones of nonnegative irreducible matrices

It is known that the max-algebraic powers A^r of a nonnegative irreducible matrix are ultimately periodic. This leads to the concept of attraction cone Attr(A, t), by which we mean the solution set of a two-sided system λ^t(A)A^r⊗x=A^r+t⊗x, where r is any integer after the periodicity transient T(A) and λ(A) is the maximum cycle geometric mean of A. A question which this paper answers, is how to describe Attr(A,t) by a concise system of equations without knowing T(A). This study requires knowledge of certain structures and symmetries of periodic max-algebraic powers, which are also described. We also consider extremals of attraction cones in a special case, and address the complexity of computing the coefficients of the system which describes attraction cone.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

A conforming decomposition theorem,a piecewise linear theorem of the alternative,and scalings of matrices satisfying lower and upper bounds

A scaling of a nonnegative matrixA is a matrixXAY ^?1, whereX andY are nonsingular, nonnegative diagonal matrices. Some condition may be imposed on the scaling, for example, whenA is square,X=Y or detX=detY. We characterize matrices for which there exists a scaling that satisfies predetermined upper and lower bound. Our principal tools are a piecewise linear theorem of the alternative and a theorem decomposing a solution of a system of equations as a sum of minimal support solutions which conform with the given solutions.     

Reduction of variance for Gaussian densities via restriction to convex sets

Let X be a random vector with values in $\text{R}$ⁿ and a Gaussian density f. Let Y be a random vector whose density can be factored as k · f, where k is a logarithmically concave function on $\text{R}$ⁿ. We prove that the covariance matrix of X dominates the covariance matrix of Y by a positive semidefinite matrix. When k is the indicator function of a compact convex set A of positive measure the difference is positive definite. If A and X are both symmetric Var(a · X) is bounded above by an expression which is always strictly less than Var(a · X) for every a ∈ $\text{R}$ⁿ. Finally some counterexamples are given to show that these results cannot be extended to the general case where f is any logarithmically concave density.     

The sum of unitary similarity orbits containing only special operators

Let B(H) be the algebra of bounded linear operator acting on a Hilbert space H (over the complex or real field). Characterization is given to A₁,…,A_k∈B(H) such that for any unitary operators is always in a special class S of operators such as normal operators, self-adjoint operators, unitary operators. As corollaries, characterizations are given to A∈B(H) such that complex, real or nonnegative linear combinations of operators in its unitary orbit U(A)={U^∗AU:Uunitary} always lie in S.     

Quadratic Lyapunov functions for systems with state-dependent switching

In this paper, we consider the existence of quadratic Lyapunov functions for certain types of switched linear systems. Given a partition of the state-space, a set of matrices (linear dynamics), and a matrix-valued function A(x) constructed by associating these matrices with regions of the state-space in a manner governed by the partition, we ask whether there exists a positive definite symmetric matrix P such that A(x)^TP+PA(x) is negative definite for all x(t). For planar systems, necessary and sufficient conditions are given. Extensions for higher order systems are also presented.     

Equalities and inequalities for inertias of hermitian matrices with applications

The inertia of a Hermitian matrix is defined to be a triplet composed of the numbers of the positive, negative and zero eigenvalues of the matrix counted with multiplicities, respectively. In this paper, we show some basic formulas for inertias of 2×2 block Hermitian matrices. From these formulas, we derive various equalities and inequalities for inertias of sums, parallel sums, products of Hermitian matrices, submatrices in block Hermitian matrices, differences of outer inverses of Hermitian matrices. As applications, we derive the extremal inertias of the linear matrix expression A-BXB^∗ with respect to a variable Hermitian matrix X. In addition, we give some results on the extremal inertias of Hermitian solutions to the matrix equation AX=B, as well as the extremal inertias of a partial block Hermitian matrix.     

Some closer bounds of Perron root basing on generalized Perron complement

This paper is concerned with the bounds of the Perron root ρ(A) of a nonnegative irreducible matrix A. Two new methods utilizing the relationship between the Perron root of a nonnegative irreducible matrix and its generalized Perron complements are presented. The former method is efficient because it gives the bounds for ρ(A) only by calculating the row sums of the generalized Perron complement P_t(A/A[α]) or even the row sums of submatrices A[α],A[β],A[α,β] and A[β,α]. And the latter gives the closest bounds (just in this paper) of ρ(A). The results obtained by these methods largely improve the classical bounds. Numerical examples are given to illustrate the procedure and compare it with others, which shows that these methods are effective.     

Google PageRanking problem: The model and the analysis

The spectral and Jordan structures of the Web hyperlink matrix G(c)=cG+(1−c)ev^T have been analyzed when G is the basic (stochastic) Google matrix, c is a real parameter such that 0<c<1, v is a nonnegative probability vector, and e is the all-ones vector. Typical studies have relied heavily on special properties of nonnegative, positive, and stochastic matrices. There is a unique nonnegative vector y(c) such that y(c)^TG(c)=y(c)^T and y(c)^Te=1. This PageRank vector y(c) can be computed effectively by the power method.We consider a square complex matrix A and nonzero complex vectors x and v such that Ax=λx and v^∗x=1. We use standard matrix analytic tools to determine the eigenvalues, the Jordan blocks, and a distinguished left λ-eigenvector of A(c)=cA+(1−c)λxv^∗ as a function of a complex variable c. If λ is a semisimple eigenvalue of A, there is a uniquely determined projection N such that lim_c→1y(c)=Nv for all v; this limit may fail to exist for some v if λ is not semisimple. As a special case of our results, we obtain a complex analog of PageRank for the Web hyperlink matrix G(c) with a complex parameter c. We study regularity, limits, expansions, and conditioning of y(c) and we propose algorithms (e.g., complex extrapolation, power method on a modified matrix etc.) that may provide an efficient way to compute PageRank also with c close or equal to 1. An interpretation of the limit vector Nv and a related critical discussion on the model, on its adherence to reality, and possible ways for its improvement, represent the contribution of the paper on modeling issues.     

Characterizations of rectangular totally and strictly totally positive matrices

An n×m real matrix A is said to be totally positive (strictly totally positive) if every minor is nonnegative (positive). In this paper, we study characterizations of these classes of matrices by minors, by their full rank factorization and by their thin QR factorization.     

On the inverse mean first passage matrix problem and the inverse M-matrix problem

The inverse mean first passage time problem is given a positive matrix M∈R^n,n, then when does there exist an n-state discrete-time homogeneous ergodic Markov chain C, whose mean first passage matrix is M? The inverse M-matrix problem is given a nonnegative matrix A, then when is A an inverse of an M-matrix. The main thrust of this paper is to show that the existence of a solution to one of the problems can be characterized by the existence of a solution to the other. In so doing we extend earlier results of Tetali and Fiedler.     

Hoffman polynomials of nonnegative irreducible matrices and strongly connected digraphs

For a nonnegative n × n matrix A, we find that there is a polynomial f(x)∈R[x] such that f(A) is a positive matrix of rank one if and only if A is irreducible. Furthermore, we show that the lowest degree such polynomial f(x) with tr f(A) = n is unique. Thus, generalizing the well-known definition of the Hoffman polynomial of a strongly connected regular digraph, for any irreducible nonnegative n × n matrix A, we are led to define its Hoffman polynomial to be the polynomial f(x) of minimum degree satisfying that f(A) is positive and has rank 1 and trace n. The Hoffman polynomial of a strongly connected digraph is defined to be the Hoffman polynomial of its adjacency matrix. We collect in this paper some basic results and open problems related to the concept of Hoffman polynomials.     

On the spectral radius and the spectral norm of Hadamard products of nonnegative matrices

We prove the spectral radius inequality ρ(A₁°A₂°?°A_k)?ρ(A₁A₂?A_k) for nonnegative matrices using the ideas of Horn and Zhang. We obtain the inequality ‖A°B‖?ρ(A^TB) for nonnegative matrices, which improves Schur’s classical inequality ‖A°B‖?‖A‖‖B‖, where ‖·‖ denotes the spectral norm. We also give counterexamples to two conjectures about the Hadamard product.