Search

The stability and inertia of sign pattern matrices with entries in { + , − , 0 } associated with dynamical systems of second-order ordinary differential equations x ¨ = A x ˙ + B x are studied, where A and B are real matrices of order n. An equivalent system of first-order differential equations has coefficient matrix C = [ A B I O ] of order 2n, and eigenvalue properties are considered for sign patterns C = [ A B D O ] of order 2n, where A , B are the sign patterns of A , B respectively, and D is a positive diagonal sign pattern. For given sign patterns A and B where one of them is a negative diagonal sign pattern, results are determined concerning the potential stability and sign stability of C , as well as the refined inertia of C . Applications include the stability of such dynamical systems in which only the signs rather than the magnitudes of entries of the matrices A and B are known.

A unified approach to the determination of eigenvalues and eigenvectors of specific matrices associated with directed graphs is presented. Matrices studied include the new distance matrix, with natural extensions to the distance Laplacian and distance signless Laplacian, in addition to the new adjacency matrix, with natural extensions to the Laplacian and signless Laplacian. Various sums of Kronecker products of nonnegative matrices are introduced to model the Cartesian and lexicographic products of digraphs. The Jordan canonical form is applied extensively to the analysis of spectra and eigenvectors. The analysis shows that Cartesian products provide a method for building infinite families of transmission regular digraphs with few distinct distance eigenvalues.

A unified approach to the determination of eigenvalues and eigenvectors of specific matrices associated with directed graphs is presented. Matrices studied include the distance matrix, distance Laplacian, and distance signless Laplacian, in addition to the adjacency matrix, Laplacian, and signless Laplacian. Various sums of Kronecker products of nonnegative matrices are introduced to model the Cartesian and lexicographic products of digraphs. The Jordan canonical form is applied extensively to the analysis of spectra and eigenvectors. The analysis shows that Cartesian products provide a method for building infinite families of transmission regular digraphs with few distinct distance eigenvalues.

The enhanced principal rank characteristic sequence (epr-sequence) of an $n\x n$ matrix is a sequence $\ell_1 \ell_2 \cdots \ell_n$, where each $\ell_k$ is ${\tt A}$, ${\tt S}$, or ${\tt N}$ according as all, some, or none of its principal minors of order $k$ are nonzero. There has been substantial work on epr-sequences of symmetric matrices (especially real symmetric matrices) and real skew-symmetric matrices, and incidental remarks have been made about results extending (or not extending) to (complex) Hermitian matrices. A systematic study of epr-sequences of Hermitian matrices is undertaken; the differences with the case of symmetric matrices are quite striking. Various results are established regarding the attainability by Hermitian matrices of epr-sequences that contain two ${\tt N}$s with a gap in between. Hermitian adjacency matrices of mixed graphs that begin with ${\tt NAN}$ are characterized. All attainable epr-sequences of Hermitian matrices of orders $2$, $3$, $4$, and $5$, are listed with justifications.

The enhanced principal rank characteristic sequence (epr-sequence) of a symmetric n × n matrix is a sequence l 1 l 2 ⋯ l n where l k is A , S , or N according as all, some, or none of its principal minors of order k are nonzero. Such sequences give more information than the (0,1) pr-sequences previously studied (where basically the k th entry is 0 or 1 according as none or at least one of its principal minors of order k is nonzero). Various techniques including the Schur complement are introduced to establish that certain subsequences such as NAN are forbidden in epr-sequences over fields of characteristic not two. Using probabilistic methods over fields of characteristic zero, it is shown that any sequence of A s and S s ending in A is attainable, and any sequence of A s and S s followed by one or more N s is attainable; additional families of attainable epr-sequences are constructed explicitly by other methods. For real symmetric matrices of orders 2, 3, 4, and 5, all attainable epr-sequences are listed with justifications.

[EN] We study matrices A is an element of C-n x n such that A(s+1)R = RA* where R-k = I-n, and s, k are nonnegative integers with k >= 2; such matrices are called {R, s+1, k, *}-potent matrices. The s = 0 case corresponds to matrices such that A = RA* R-1 with R-k = I-n, and is studied using spectral properties of the matrix R. For s >= 1, various characterizations of the class of {R, s + 1, k, *}-potent matrices and relationships between these matrices and other classes of matrices are presented. (C) 2018 Elsevier Inc. All rights reserved., The second and fourth authors have been partially supported by Ministerio de Economia y Competitividad of Spain (Grant MTM2013-43678-P and Red de Excelencia Grant MTM2017-90682-REDT).

Given an n × n matrix, its principal rank characteristic sequence is a sequence of length n + 1 of 0s and 1s where, for k = 0 , 1 , … , n , a 1 in the kth position indicates the existence of a principal submatrix of rank k and a 0 indicates the absence of such a submatrix. The principal rank characteristic sequences for symmetric matrices over various fields are investigated, with all such attainable sequences determined for all n over any field with characteristic 2. A complete list of attainable sequences for real symmetric matrices of order 7 is reported.

Given a graph [math] , the tree cover number of the graph, denoted [math] , is the minimum number of vertex disjoint simple trees occurring as induced subgraphs that cover all the vertices of G. This graph parameter was introduced in 2011 as a tool for studying the maximum positive semidefinite nullity of a graph, and little is known about it. It is conjectured that the tree cover number of a graph is at most the maximum positive semidefinite nullity of the graph. ¶ In this paper, we establish bounds on the tree cover number of a graph, characterize when an edge is required to be in some tree of a minimum tree cover, and show that the tree cover number of the [math] -dimensional hypercube is 2 for all [math] .

A necessary and sufficient condition for the existence of the group inverse of a certain bipartite matrix is given, and an explicit formula is obtained for the group inverse in terms of its block submatrices. This form is used to derive a graph–theoretic description of the entries of the group inverse of some examples of such a matrix, including those corresponding to broom graphs. If the group inverse of a nonnegative matrix corresponding to a broom graph exists, then it is shown that this group inverse is signed. An open question about group inverses of more general bipartite matrices is posed and a summary of cases for which its answer is known is given.

An n × n sign pattern matrix has entries in { + , - , 0 } . This paper surveys the following problems concerning spectral properties of sign pattern matrices: sign patterns that allow all possible spectra (spectrally arbitrary sign patterns); sign patterns that allow all inertias (inertially arbitrary sign patterns); sign patterns that allow nilpotency (potentially nilpotent sign patterns); and sign patterns that allow stability (potentially stable sign patterns). Relationships between these four classes of sign patterns are given, and several open problems are identified.

In earlier works, authors such as Varga, Micchelli and Willoughby, Ando, and Fiedler and Schneider have studied and characterized functions which preserve the M-matrices or some subclasses of the M-matrices, such as the Stieltjes matrices. Here we characterize functions which either preserve the inverse M-matrices or map the inverse M-matrices to the M-matrices. In one of our results we employ the theory of Pick functions to show that if A and B are inverse M-matrices such that B −1 ≤ A −1, then (B+tI)−1 ≤ (A+tI)−1, for all t ≥ 0.

Let V∈ R m,n be a nonnegative matrix. The nonnegative matrix factorization (NNMF) problem consists of finding nonnegative matrix factors W∈ R m,r and H ∈ R r , n such that V ≈ WH . Lee and Seung proposed two algorithms, one of which finds nonnegative W and H such that ∥ V − WH ∥ F is minimized. After examining the case in which r =1 about which a complete characterization of the solution is possible, we consider the case in which m = n and V is symmetric. We focus on questions concerning when the best approximate factorization results in the product WH being symmetric and on cases in which the best approximation cannot be a symmetric matrix . Finally, we show that the class of positive semidefinite symmetric nonnegative matrices V generated via a Soules basis admit for every 1⩽ r ⩽rank( V ), a nonnegative factorization WH which coincides with the best approximation in the Frobenius norm to V in R n,n of rank not exceeding r . An example of applications in which NNMF factorizations for nonnegative symmetric matrices V arise is video and other media summarization technology where V is obtained from a distance matrix.

An n × n diamond alternating sign matrix (ASM) is a (0, +1, −1)-matrix with ±1 entries alternatingand arranged in a diamond-shaped pattern. The explicit inverse (for n even) or generalized inverse (for nodd) of a diamond ASM is derived. The eigenvalues of diamond ASMs are considered and when n is even, thecharacteristic polynomial, which involves signed binomial coefficients, is determined.

Barrett et al. asked in [W. Barrett et al. Minimum rank of edge subdivisions of graphs. Electronic Journal of Linear Algebra, 18:530–563, 2009.], whether the maximum nullity is equal to the zero forcing number for all complete subdivision graphs. We prove that this equality holds. Furthermore, we compute the value of M(F, G) = Z(G) by introducing the bridge tree of a connected graph. Since this equality is valid for all fields, G has field independent minimum rank, and we also show that G has a universally optimal matrix.

We introduce the study of potentially eventually exponentially positive (PEEP) sign patterns and establish several results using the connections between these sign patterns and the potentially eventually positive (PEP) sign patterns. It is shown that the problem of characterizing PEEP sign patterns is not equivalent to that of characterizing PEP sign patterns. A characterization of all [math] and [math] PEEP sign patterns is given.

A simple digraph describes the off-diagonal zero-nonzero pattern of a family of (not necessarily symmetric) matrices. Minimum rank of a simple digraph is the minimum rank of this family of matrices; maximum nullity is defined analogously. The simple digraph zero forcing number is an upper bound for maximum nullity. Cut-vertex reduction formulas for minimum rank and zero forcing number for simple digraphs are established. The effect of deletion of a vertex on minimum rank or zero forcing number is analyzed, and simple digraphs having very low or very high zero forcing number are characterized.

A formula for the Drazin inverse of a block k-cyclic (k � 2) matrix A with nonzeros only in blocks Ai,i+1, for i = 1,...,k (mod k) is presented in terms of the Drazin inverse of a smaller order product of the nonzero blocks of A, namely Bi = Ai,i+1 ···Ai 1,i for some i. Bounds on the index of A in terms of the minimum and maximum indices of these Bi are derived. Illustrative examples and special cases are given.

A new class of sign patterns contained in the class of sign patterns that allow eventual nonnegativity is introduced and studied. A sign pattern is potentially strongly eventually nonnegative (PSEN) if there is a matrix with this sign pattern that is eventually nonnegative and has some power that is both nonnegative and irreducible. Using Perron-Frobenius theory and a matrix perturbation result, it is proved that a PSEN sign pattern is either potentially eventually positive or r-cyclic. The minimum number of positive entries in an n× n PSEN sign pattern is shown to be n, and PSEN sign patterns of orders 2 and 3 are characterized.

The zero forcing number, maximum nullity and path cover number of a (simple, undirected) graph are parameters that are important in the study of minimum rank problems. We investigate the effects on these graph parameters when an edge is subdivided to obtain a so-called edge subdivision graph. An open question raised by Barrett et al. is answered in the negative, and we provide additional evidence for an affirmative answer to another open question in that paper [W. Barrett, R. Bowcutt, M. Cutler, S. Gibelyou, and K. Owens. Minimum rank of edge subdivisions of graphs. Electronic Journal of Linear Algebra, 18:530–563, 2009.]. It is shown that there is an independent relationship between the change in maximum nullity and zero forcing number caused by subdividing an edge once. Bounds on the effect of a single edge subdivision on the path cover number are presented, conditions under which the path cover number is preserved are given, and it is shown that the path cover number and the zero forcing number of a complete subdivision graph need not be equal.

Potentially eventually positive (PEP) sign patterns were introduced in \Sign patterns that allow eventual positivity," Electronic Journal of Linear Algebra, 19 (2010): 108{120, where it was noted thatA is PEP if its positive part is primitive, and an example was given of a 3 3 PEP sign pattern with reducible positive part. We extend these results by constructing n n PEP sign patterns with reducible positive part, for every n 3.

Block representations of the Drazin inverse of a bipartite matrix A = 0 B C 0 in terms of the Drazin inverse of the smaller order block product BC or CBare presented. Relationships between the index of A and the index of BC are determined, and examples are given to illustrate all such possible relationships.

Several necessary or sufficient conditions for a sign patternto allow eventual posi- tivity are established. It is also shown that certain families of sign patterns do not allow eventual positivity. These results are applied to show that for n � 2, the minimum number of positive entries in an n×n sign pattern that allows eventual positivity is n+1, and to classify all 2×2 and 3×3 sign patterns as to whether or not the pattern allows eventual positivity. A 3 × 3 matrix is presented to demonstrate that the positive part of an eventually positive matrix need not be primitive, answering negatively a question of Johnson and Tarazaga.

A matrix A is power-positive if some positive integer power of A is entrywise positive. A sign pattern A is shown to require power-positivity if and only if either A or A is nonnegative and has a primitive digraph, or equivalently, either A or A requires eventual positivity. A sign pattern A is shown to be potentially power-positive if and only if A or A is potentially eventually positive.

A simple formula for the group inverse of a 2 × 2 block matrix with a bipartite digraph is given in terms of the block matrices. This formula is used to give a graph-theoretic description of the group inverse of an irreducible tridiagonal matrix of odd order with zero diagonal (which is singular). Relations between the zero/nonzero structures of the group inverse and the Moore-Penrose inverse of such matrices are given. An extension of the graph-theoretic description of the group inverse to singular matrices with tree graphs is conjectured.

In this paper we connect, generalize, and broaden properties of matrices related to (i) the triangular inequality for mean first passage times in finite homogeneous ergodic Markov chains, (ii) the triangle inequality for proximities in Laplacian matrices of undirected weighted graphs, and (iii) the Metzler property of the column entrywise diagonal dominance of inverses of diagonally dominant M-matrices.

Recently D. Higham showed that the small-world phenomenon arising in a ring network of N nodes can be modelled by a Markov chain which depends on a parameter ϵ of the form ϵ = K / N α , where K ⩾ 0 and α > 1. The parameter can be viewed as a transitional factor interpolating between the completely local and completely global configurations of the network. Higham analyzed the Markov chain model by a combination of matrix perturbation theory and finite difference approximations to an underlying boundary value problem. Using such tools he obtained asymptotic results for the limiting case when N is sufficiently large. Furthermore, for large N , Higham verified the small-world phenomenon on the network in the case when α = 3. Motivated by Higham’s work, we show that the Markov chain of the small-world model can be investigated more completely by direct matrix-theoretic methods which produces exact results for all N and for all ϵ . Our results therefore allow a fuller examination of the behavior of the small-world phenomenon in the Markov chain model for small to moderate values of N and for all α > 1.