Search

Completely positive matrices are matrices that can be decomposed as $$BB^T$$ , where B is an entrywise nonnegative matrix. These matrices have many applications, including applications to optimization. This article is a survey of some results in the theory of completely positive matrices that involve matrices whose graph contains no triangles.

We model the Lights Out game on general simple graphs in the framework of linear algebra over the field F2. Based upon a version of the Fredholm alternative, we introduce a separating invariant of the game, i.e., an initial state can be transformed into a final state if and only if the values of the invariant of both states agree. We also investigate certain states with particularly interesting properties. Apart from the classical version of the game, we propose several variants, in particular a version with more than only two states (light on, light off), where the analysis relies on systems of linear equations over the ring Zn. Although it is easy to find a concrete solution of the Lights Out problem, we show that it is NP-hard to find a minimal solution. We also propose electric circuit diagrams to actually realize the Lights Out game., Mathematische Semesterberichte, 68 (2)

Let G be a connected, bipartite graph. Let Gw denote the weighted graph obtained from G by assigning weights to its edges using the positive weight function w : E(G) ! (0;1). In this article we consider a class Hnmc of bipartite graphswith unique perfect matchings and the family WG of weight functions with weight 1 on the matching edges, and characterize all pairs G in Hnmc and w in WG such that Gw is strongly self-inverse.

It is known that complete multipartite graphs are determined by their distance spectrum but not by their adjacency spectrum. The Seidel spectrum of a graph $G$ on more than one vertex does not determine the graph, since any graph obtained from $G$ by Seidel switching has the same Seidel spectrum. We consider $G$ to be determined by its Seidel spectrum, up to switching, if any graph with the same spectrum is switching equivalent to a graph isomorphic to $G$. It is shown that any graph which has the same spectrum as a complete $k$-partite graph is switching equivalent to a complete $k$-partite graph, and if the different partition sets sizes are $p_1,\ldots, p_l$, and there are at least three partition sets of each size $p_i$, $i=1,\ldots, l$, then $G$ is determined, up to switching, by its Seidel spectrum. Sufficient conditions for a complete tripartite graph to be determined by its Seidel spectrum are discussed, and a conjecture is made on complete tripartite graphs on more than 18 vertices., 12 page 2 figures

This paper was presented as an invited talk in the 6th International Conference on Matrix Analysis and Applications, Duy Tan University, Da Nang City, Vietnam, June 15–18, 2017. All the matrices in the paper are real. We survey known results and present some new problems. The paper has six parts.

An SPN matrix is a matrix which is the sum of a real positive semidefinite matrix and a symmetric nonnegative one. We solve the SPN completion problem: we show that the SPN completable graphs are the graphs in which every odd cycle induces a complete subgraph.

A graph G is nonsingular (singular) if its adjacency matrix A ( G ) is nonsingular (singular). In this article, we consider the nonsingularity of block graphs, i.e., graphs in which every block is a clique. Extending the problem, we characterize nonsingular vertex-weighted block graphs in terms of reduced vertex-weighted graphs resulting after successive deletion and contraction of pendant blocks. Special cases where nonsingularity of block graphs may be directly determined are discussed.

Let $F_{p,q}$ be the generalized friendship graph $K_1\bigvee (pK_q)$ on $pq+1$ vertices obtained by joining a vertex to all vertices of $p$ disjoint copies of the complete graph $K_q$ on $q$ vertices. In this paper, we prove that $F_{p,q}$ is determined by its normalized Laplacian spectrum if and only if $q\ge 2$, or $q=1$ and $p\le 2$., 10 pages, Linear Algebra and its Applications, 2018

We show how to separate a doubly nonnegative matrix, which is not completely positive and has a triangle-free graph, from the completely positive cone. This method can be used to compute cutting planes for semidefinite relaxations of combinatorial problems. We illustrate our approach by numerical tests on the stable set problem.

H-matrices (matrices whose comparison matrix is an M-matrix) are well studied in matrix theory and have numerous applications, e.g., linear complementarity problems and iterative methods for solving systems of linear equations. In this article we establish some properties of their tensor counterparts: strong H -tensors and (general) H -tensors.

In this paper we describe a method for teaching students to prove some mathematical statements independently, by using specially designed auxiliary assignments. The assignments are designed as homework problems and can be adapted for online learning. We illustrate our method using examples from calculus and differential equations.

In this article, a general notion of common diagonal Lyapunov matrix is formulated for a collection of n × n matrices A 1, … , A s , and cones k 1, … , k s in ℝ n . Necessary and sufficient conditions are derived for the existence of a common diagonal Lyapunov matrix in this setting. The conditions are similar to and extend the well-known criteria for the case s = 1, k 1 = ℝ n .

Let μ ( G ) and ω ( G ) be the Colin de Verdiere and clique numbers of a graph G, respectively. It is well-known that μ ( G ) ⩾ ω ( G ) - 1 for all graphs. Our main results include μ ( G ) ⩽ ω ( G ) for all chordal graphs; μ ( G ) ⩽ tw ( G ) + 1 for all graphs (where tw is the tree-width), and a characterization of those split ( ⊆ chordal) graphs for which μ ( G ) = ω ( G ) . The bound μ ( G ) ⩽ tw ( G ) + 1 improves a result of Colin de Verdiere by a factor of 2.

In this article we describe the process of studying the assumptions and the conclusion of a theorem. We tried to provide the students with exercises and problems where we discuss the following questions: What are the assumptions of a theorem and what are the conclusions? What is the geometrical meaning of a theorem? What happens when one or more of the theorem's assumptions are not fulfiled? What assumptions are necessary and which are sufficient? According to the students' opinion and the test results the developed approach was successful.

Let A be an n × n real matrix. A is called {0,1}-cp if it can be factorized as A = BB T with bij =0 or 1. The smallest possible number of columns of B in such a factorization is called the {0,1}-rank of A. A {0,1}-cp matrix A is called minimal if for every nonzero nonnegative n × n diagonal matrix D, A-D is not {0,1}-cp, and r-uniform if it can be factorized as A=BB T, where B is a (0, 1) matrix with r 1s in each column. In this article, we first present a necessary condition for a nonsingular matrix to be {0,1}-cp. Then we characterize r-uniform {0,1}-cp matrices. We also obtain some necessary conditions and sufficient conditions for a matrix to be minimal {0,1}-cp, and present some bounds for {0,1}-ranks.

The purpose of this note is to address the computational question of determining whether or not a square nonnegative matrix (over the reals) is completely positive and finding its CP-rank when it is. We show that these questions can be resolved by finite algorithms and we provide (non-polynomial) complexity bounds on the number of arithmetic/Boolean operations that these algorithms require. We state several open questions including the existence of polynomial algorithms to resolve the above problems and availability of algorithms for addressing complete positivity over the rationals and over {0, 1} matrices.

We consider a convex combination of matrices that arise in the study of communication networks and the corresponding convex combination of Kronecker squares of these matrices. We show that the spectrum of the first convex combination is contained in the spectrum of the second set and that the second largest eigenvalues coincide.

Let S be a subset of the set of real numbers R. A is called S-factorizable if it can be factorized as A=BBT with bij∈S. The smallest possible number of columns of B in such factorization is called the S-rank of A and is denoted by rankSA. If S is a set of nonnegative numbers, then A is called S-cp. The aim of this work is to study {0,1}-cp matrices. We characterize {0,1}-cp matrices of order less than 4, and give a necessary and sufficient condition for a matrix of order 4 with some zero entries, to be {0,1}-cp. We show that a nonnegative integral Jacobi matrix is {0,1}-cp if and only if it is diagonally dominant, and obtain a necessary condition for a 2-banded symmetric nonnegative integral matrix to be {0,1}-cp. We give formulae for the exact value of the {0,1}-rank of integral symmetric nonnegative diagonally dominant matrices and some other {0,1}-cp matrices.

We study the spectrum of a positive matrix that arises in the study of certain communication networks. Bounds are given on the rate of convergence of the networks to the equilibrium condition.

We study the problem of determining whether a given 5 × 5 matrix is completely positive, by investigating the number of negative entries of a Schur complement of A . We show that if this number is not 4, then A is completely positive, and present some sufficient conditions for A to be cp when this number is 4. We also show that the complete positivity of an elementwise positive doubly nonnegative 5 × 5 matrix is equivalent to the complete positivity of a related 5 × 5 doubly nonnegative matrix that is not elementwise positive.

Let Φ k be the maximal cp-rank of all rank k completely positive matrices. We prove that Φ k = k ( k +1)/2−1 for k ⩾2. In particular we furnish a procedure to produce, for k ⩾2, completely positive matrices with rank k and cp-rank k ( k +1)/2−1.

We first obtain the exact value for bipartite density of a cubic line graph on n vertices. Then we give an upper bound for the bipartite density of cubic graphs in terms of the smallest eigenvalue of the adjacency matrix. In addition, we characterize, except in the case n = 20, those graphs for which the upper bound is obtained.

Symmetry is an important mathematical concept which plays an extremely important role as a problem-solving technique. Nevertheless, symmetry is rarely used in secondary school in solving mathematical problems. Several investigations demonstrate that secondary school mathematics teachers are not aware enough of the importance of this elegant problem-solving tool. In this paper we present examples of problems from several branches of mathematics that can be solved using different types of symmetry. Teachers' attitudes and beliefs regarding the use of symmetry in the solutions of these problems are discussed.

This note proves a conjecture of Merris that the minimal value of entries of the doubly stochastic matrix of the degree antiregular graph En of order n ≥ 3 is equal to (l/2(n + l)).

This note considers some examples of how multiple choice examinations can be used to check the understanding of engineering students of some theoretical parts of their course.

The paper consists of several remarks on complete positivity. The main result is that if the comparison matrix of an n × n completely positive matrix A is an M-matrix, then A has a support 3 rank 1 representation with at most terms.

Consider the functional f (U) = ∑n i=1 maxj{(UMjU)ii} over orthogonal matrices U , where the collection of n -byn symmetric matrices Mj are pairwise commutative, and thus simultaneously diagonalizable. Selecting an orthogonal matrix U which maximizes f (U) has applications in adaptive optics. A proof is given here that any orthogonal matrix Q which simultaneously diagonalizes the Mj maximizes the function f . Mathematics subject classification (1991): 15A27, 15A45, 15A51, 15A90.

In this article we prove the strict monotonicity of the spectral radius of weakly irreducible nonnegative tensors. As an application, we give a necessary and sufficient condition for an interval hull of tensors to be contained in the set of all strong $\mathcal{M}$-tensors. We also establish some properties of $\mathcal{M}$-tensors. Finally, we consider some problems related to interval hull of positive (semi)definite tensors and $P(P_0)$-tensors., Comment: 10 pages

The inertia-preservers of several sets of matrices are identified. The sets include: all real matrices, all complex matrices, triangular matrices, real symmetric matrices and Hermitian matrices.

Copositive and completely positive matrices play an increasingly important role in Applied Mathematics, namely as a key concept for approximating NP-hard optimization problems. The cone of copositive matrices of a given order and the cone of completely positive matrices of the same order are dual to each other with respect to the standard scalar product on the space of symmetric matrices. This paper establishes some new relations between orthogonal pairs of such matrices lying on the boundary of either cone. As a consequence, we can establish an improvement on the upper bound of the cp-rank of completely positive matrices of general order, and a further improvement for such matrices of order six., Comment: 15 pages; Following a minor revision: improved set notations, phrasing of some proofs (Cor. 2.1, Prop. 4.2)

We introduce a new variant of zero forcing - signed zero forcing. The classical zero forcing number provides an upper bound on the maximum nullity of a matrix with a given graph (i.e. zero-nonzero pattern). Our new variant provides an analo- gous bound for the maximum nullity of a matrix with a given sign pattern. This allows us to compute, for instance, the maximum nullity of a Z-matrix whose graph is L(K_{n}), the line graph of a clique.

It is shown that a matrix can be strongly inertia preserving without being diagonally stable.

Let G be a weighted graph on n vertices. Letn 1(G) be the second largest eigenvalue of the Laplacian of G. For n� 3, it is proved thatn 1(G)� dn 2(G), where dn 2(G) is the third largest degree of G. An upper bound for the second smallest eigenvalue of the signless Laplacian of G is also obtained. 1. Introduction. Let G = E(G),V (G) � be a simple graph (a graph without loops or multiple edges) with |V (G)| = n. We say that G is a weighted graph if it has a weight (a positive number) associated with each edge. The weight of an edge � i,j � ∈ E(G) will be denoted by wij. We define the adjacency matrix A(G) of G to be a symmetric matrix which satisfies

We complete the proof that a graph G is completely positive (every doubly nonnegative matrix A , with G ( A )= G , is completely positive) if and only if it has no odd cycle of length greater than 4.

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 real matrix A is inertia preserving if in $AD = \operatorname{in} D$, for every invertible diagonal matrix D. This class of matrices is a subset of the D-stable matrices and contains the diagonally stable matrices.In order to study inertia-preserving matrices, matrices that have no imaginary eigenvalues are characterized. This is used to characterize D-stability of stable matrices. It is also shown that irreducible, acyclic D-stable matrices are inertia preserving.

Let G be a weighted graph. Let v be a vertex of G and let Gω denote the graph obtained by adding a vertex u and an edge {v, u} with weight ω to G. Then the algebraic connectivity μ(Gω) of G v ω is a nondecreasing function of ω and is bounded by the algebraic connectivity μ(G) of G. The question of when lim ω→∞ v ω) is equal to μ(G) is considered and answered in the case that G is a tree.

Nonnegative nilpotent lower triangular completions of a nonnegative nilpotent matrix are studied. It is shown that for every natural number between the index of the matrix and its order, there exists a completion that has this number as its index. A similar result is obtained for the rank. However, unlike the case of complex completions of complex matrices, it is proved that for every nonincreasing sequence of nonnegative integers whose sum is n, there exists an n n nonnegative nilpotent matrix A such that for every nonnegative nilpotent lower triangular completion, B, of A, B 6= A, ind(B) > ind(A). AMS(MOS) subject classi cation. 15A21, 15A48

The paper describes a qualitative study of completely positive matrices. The main result is

The prefix “m” stands for “many” (“M” stands for “Minkowski”), and the purpose of this chapter is to demonstrate that M-matrices are very useful. We shall describe, or at least mention, some of their applications to ecology, numerical analysis, probability, mathematical programming, game theory, control theory, and matrix theory.