Classes of general H-matrices

Let M(A) denote the comparison matrix of a square H-matrix A, that is, M(A) is an M-matrix. H-matrices such that their comparison matrices are nonsingular are well studied in the literature. In this paper, we study characterizations of H-matrices with either singular or nonsingular comparison matrices. The spectral radius of the Jacobi matrix of M(A) and the generalized diagonal dominance property are used in the characterizations. Finally, a classification of the set of general H-matrices is obtained.     

An index classification of M-matrices

An M-matrix as defined by Ostrowski [5] is a matrix that can be split into A = sI ? B, where s > 0, B ? 0, with s ? r(B), the spectral radius of B. Following Plemmons [6], we develop a classification of all M-matrices. We consider v, the index of zero for A, i.e., the smallest nonnegative integer n such that the null spaces of Aⁿ and Aⁿ⁺¹ coincide. We characterize this index in terms of convergence properties of powers of s^?1B. We develop additional characterizations in terms of nonnegativity of the Drazin inverse of A on the range of A^v, extending (as conjectured by Poole and Boullion [7]) the well-known property that A^?1?0 whenever A is nonsingular.     

A theorem on products of matrices

A new result on products of matrices is proved in the following theorem: let M_i (i=1,2,…) be a bounded sequence of square matrices, and K be the l.u.b. of the spectral radii ρ(M_i). Then for any positive number ε there is a constant A and an ordering p(j) (j = 1,2,…) of the matrices such that

$\text{∏}\text{j=1}\text{n}\text{M}{}_{\mathrm{p(j)}}\text{?A·(K+ε)}{}^{\mathrm{n}}\text{(n = 1,2,…)}$

. The ordering is well defined by p(j), a one-to-one mapping on the set of positive integers. In general the inequality does not hold for any ordering p(j) (a counterexample is provided); however, some sufficient conditions are given for the result to remain true irrespective of the order of the matrices.     

Finding a positive definite linear combination of two Hermitian matrices

Let A and B be n-by-n Hermitian matrices over the complex field. A result of Au-Yeung [1] and Stewart [8] states that if

$\text{x}{}^1\text{(A + iB)x≠0}$

for all nonzero n-vectors x, then there is a linear combination of A and B which is positive definite. In this article we present an algorithm which finds such a linear combination in a finite number of steps. We also discuss the implementation of the algorithm in case A and B are real symmetric sparse matrices.     

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.     

Transposing a matrix by similarity operations

A matrix T is said to co-transpose a square matrix A if T^?1AT=A′ and T^?1A′T=A. For every n?3 there exists a real n×n matrix which cannot be co-transposed by any matrix. However, it is shown that the following classes of real matrices can be co-transposed by a symmetric matrix of order two: 2×2 matrices, normal matrices, and matrices whose square is symmetric.     

On the convergence of the symmetric successive overrelaxation method

The symmetric successive overrelaxation (SSOR) iterative method is applied to the solution of the system of linear equations $\text{A}\text{x}\text{=}\text{b}$, where A is an n×n nonsingular matrix. We give bounds for the spectral radius of the SSOR iterative matrix when A is an Hermitian positive definite matrix, and when A is a nonsingular M-matrix. Then, we discuss the convergence of the SSOR iterative method associated with a new splitting of the matrix A which extends the results of Varga and Buoni [1].     

Involutory matrices over finite commutative rings

An n × n matrix A is called involutory iff A²=I_n, where I_n is the n × n identity matrix. This paper is concerned with involutory matrices over an arbitrary finite commutative ring R with identity and with the similarity relation among such matrices. In particular the authors seek a canonical set $\text{C}$ with respect to similarity for the n × n involutory matrices over R—i.e., a set $\text{C}$ of n × n involutory matrices over R with the property that each n × n involutory matrix over R is similar to exactly on matrix in $\text{C}$. Because of the structure of finite commutative rings and because of previous research, they are able to restrict their attention to finite local rings of characteristic a power of 2, and although their main result does not completely specify a canonical set $\text{C}$ for such a ring, it does solve the problem for a special class of rings and shows that a solution to the general case necessarily contains a solution to the classically unsolved problem of simultaneously bringing a sequence A₁,…,A_v of (not necessarily involutory) matrices over a finite field of characteristic 2 to canonical form (using the same similarity transformation on each A_i). (More generally, the authors observe that a theory of similarity fot matrices over an arbitrary local ring, such as the well-known rational canonical theory for matrices over a field, necessarily implies a solution to the simultaneous canonical form problem for matrices over a field.) In a final section they apply their results to find a canonical set for the involutory matrices over the ring of integers modulo 2^m and using this canonical set they are able to obtain a formula for the number of n × n involutory matrices over this ring.     

The primitive Boolean matrices with the second largest scrambling index by Boolean rank

The scrambling index of an n × n primitive Boolean matrix A is the smallest positive integer k such that A ^k (A ^T) ^k = J, where A ^T denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M = AB for some m × b Boolean matrix A and b×n Boolean matrix B. In 2009, M. Akelbek, S. Fital, and J. Shen gave an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M), and they also characterized all primitive matrices that achieve the upper bound. In this paper, we characterize primitive Boolean matrices that achieve the second largest scrambling index in terms of their Boolean rank.     

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.     

Linear transformations which preserve fixed rank

Let M_{m, n}(F) denote the set of all m×n matrices over the algebraically closed field F. Let T denote a linear transformation, T:M_{m, n}(F)→M_{m, n}(F). Theorem: If max(m, n)?2k?2, k?1, and T preserves rank k matrices [i.e.?(A)=k implies ?(T(A))=k], then there exist nonsingular m×m and n×n matrices U and V respectively such that either (i) T:A→UAV for all A?M_{m, n}(F), or (ii) m=n and T:A→UA^tV for all A?M_n(F), where A^t denotes the transpose of A.     

Convergence in finite precision of successive iteration methods under high nonnormality

This paper is devoted to the analysis of the behaviour, in finite precision arithmetic, of the successive iteration method (SI)x ₀,x _k+1 =Ax _k +b,k ≥ 0 whereA is a real or complex matrix of ordern andx is a real or complex vector of sizen. In exact arithmetic, the behaviour of (SI) is completely understood; there is convergence for anyx ₀ if and only if ρ(A) < 1 where ρ(A) is the spectral radius ofA. When (SI) is run on a computer with finite precision arithmetic, then for certain matricesA, the convergence is not guaranteed in practice when ρ(A) < 1 is true in exact arithmetic. It is clear that the phenomenon should be attributed to the conjunction of two factors :i) the nonnormality ofA andii) the finite precision of the computer arithmetic. We perform a straightforward analysis of the convergence of (SI) in finite precision from which we try to understand the subtle interplay between factorsi) andii) which takes place inside the computer, when the iteration matrixA has a high nonnormality. Why should nonnormality be an issue in finite precision? Because only nonnormal matrices can display a significant amount of spectral instability. Therefore a small perturbation ΔA onA can result in a large perturbation of the spectrum. When the spectral instability ofA is high, it appears that a convergence condition such as ρ(A) < 1 may not be generic enough for finite precision computations.     

Über eine eigenschaft lokalfiniter,unendlicher bäume

Let A be an arbitrary locally finite, infinite tree and assume that a graph G contains for every positive integer n a system of n disjoint graphs each isomorphic to a subdivision of A. Then G contains infinitely many disjoint subgraphs each isomorphic to a subdivision of A. This sharpens a theorem of Halin [5], who proved the corresponding result for the case that A is a tree in which each vertex has degree not greater than 3.     

Asymptotic expansions for dynamic programming recursions with general nonnegative matrices

This paper is concerned with the study of the asymptotic behavior of dynamic programming recursions of the form $$x(n + 1) = \mathop {\max }\limits_{P \in \mathcal{K}} Px(n), n = 0,1,2,...,$$ where ? denotes a set of matrices, generated by all possible interchanges of corresponding rows, taken from a fixed finite set of nonnegative square matrices. These recursions arise in a number of well-known and frequently studied problems, e.g. in the theory of controlled Markov chains, Leontief substitution systems, controlled branching processes, etc. Results concerning the asymptotic behavior ofx(n), forn→∞, are established in terms of the maximal spectral radius, the maximal index, and a set of generalized eigenvectors. A key role in the analysis is played by a geometric convergence result for value iteration in undiscounted multichain Markov decision processes. A new proof of this result is also presented.     

Congruence of Hermitian matrices by Hermitian matrices

Two Hermitian matrices A,B∈M_n(C) are said to be Hermitian-congruent if there exists a nonsingular Hermitian matrix C∈M_n(C) such that B=CAC. In this paper, we give necessary and sufficient conditions for two nonsingular simultaneously unitarily diagonalizable Hermitian matrices A and B to be Hermitian-congruent. Moreover, when A and B are Hermitian-congruent, we describe the possible inertias of the Hermitian matrices C that carry the congruence. We also give necessary and sufficient conditions for any 2-by-2 nonsingular Hermitian matrices to be Hermitian-congruent. In both of the studied cases, we show that if A and B are real and Hermitian-congruent, then they are congruent by a real symmetric matrix. Finally we note that if A and B are 2-by-2 nonsingular real symmetric matrices having the same sign pattern, then there is always a real symmetric matrix C satisfying B=CAC. Moreover, if both matrices are positive, then C can be picked with arbitrary inertia.     

On a finite rational criterion for the irreducibility of a matrix

A matrix A ∈ M _n (C) is said to be irreducible if the only orthoprojectors that commute with A are the zero and unit matrices. A finite rational criterion for irreducibility is proposed. The criteria for verification of this property that can be found in the literature are neither finite nor rational.     

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.     

Spectral radius and infinity norm of matrices

Let Mn(R) be the linear space of all n×n matrices over the real field R. For any A∈Mn(R), let ρ(A) and ‖A_‖∞ denote the spectral radius and the infinity norm of A, respectively. By introducing a class of transformations φa on Mn(R), we show that, for any A∈Mn(R), ρ(A)<‖A_‖∞ if . If A∈Mn(R) is nonnegative, we prove that ρ(A)<‖A_‖∞ if and only if , and ρ(A)=‖A_‖∞ if and only if the transformation φ‖A_‖∞ preserves the spectral radius and the infinity norm of A. As an application, we investigate a class of linear discrete dynamic systems in the form of X(k+1)=AX(k). The asymptotical stability of the zero solution of the system is established by a simple algebraic method.     

Some new bounds on the spectral radius of matrices

A new lower bound on the smallest eigenvalue τ(AB) for the Fan product of two nonsingular M-matrices A and B is given. Meanwhile, we also obtain a new upper bound on the spectral radius ρ(A°B) for nonnegative matrices A and B. These bounds improve some results of Huang (2008) [R. Huang, Some inequalities for the Hadamard product and the Fan product of matrices, Linear Algebra Appl. 428 (2008) 1551-1559].     

Linear preservers of row-dense matrices

Let M_m,n be the set of all m × n real matrices. A matrix A ∈ M_m,n is said to be row-dense if there are no zeros between two nonzero entries for every row of this matrix. We find the structure of linear functions T: M_m,n → M_m,n that preserve or strongly preserve row-dense matrices, i.e., T(A) is row-dense whenever A is row-dense or T(A) is row-dense if and only if A is row-dense, respectively. Similarly, a matrix A ∈ M_n,m is called a column-dense matrix if every column of A is a column-dense vector. At the end, the structure of linear preservers (strong linear preservers) of column-dense matrices is found.