Search

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

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

In this paper we describe an experiment in a linear algebra course. The aim of the experiment was to promote the students' understanding of the studied concepts focusing on their definitions. It seems to be a given that students should understand concepts’ definitions before working substantially with them. Unfortunately, in many cases they do not. Influenced by their high school experience they concentrate in learning patterns for problem solving without deep understanding of the relevant concepts. In order to educate the students to appreciate the importance of understanding definitions, we changed the homework problems and the didactical contract with the students. We discuss the positive outcomes of these changes from theoretical and educational points of view. We chose to try our approach in a linear algebra course since it is probably the most abstract course for first semester students. We hope that our approach can be useful in teaching other undergraduate courses.

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.

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.

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.

The relationships between heuristic literacy development and mathematical achievements of middle school students were explored during a 5-month classroom experiment in two 8th grade classes (N = 37). By heuristic literacy we refer to an individual’s capacity to use heuristic vocabulary in problem-solving discourse and to approach scholastic mathematical problems by using a variety of heuristics. During the experiment the heuristic constituent of curriculum-determined topics in algebra and geometry was gradually revealed and promoted by means of incorporating heuristic vocabulary in classroom discourse and seizing opportunities to use the same heuristics in different mathematical contexts. Students’ heuristic literacy development was indicated by means of individual thinking-aloud interviews and their mathematical achievements – by means of the Scholastic Aptitude Test. We found that heuristic literacy development and changes in mathematical achievements are correlated yet distributed unequally among the students. In particular, the same students, who progressed with respect to SAT scores, progressed also with respect to their heuristic literacy. Those students, who were weaker with respect to SAT scores at the beginning of the intervention, demonstrated more significant progress regarding both measures.

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.

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

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.

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.

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

Necessary and sufficient conditions for D-stability of acyclic matrices are given. Special cases of this characterization are recent results on tridiagonal matrices.

The relationship between inverse M-matrices and matrices whose graph is transitive is studied. The results are applied to obtain a new proof of the characterization, due to M. Lewin and M. Neumann, of (0,1) inverse M-matrices.

Results on ω- and τ-matrices are surveyed. The question whether an ω-matrix with positive leading principal minors is a τ-matrix is answered negatively. Other open questions are discussed. New conjectures and questions are introduced.

The concept of a regular splitting of a real nonsingular matrix, introduced by R. Varga, is used in iterative methods for solving linear systems. The purpose of this paper is to extend this concept to rectangular linear systems \[ ( * )\qquad Ax = b, \] in two directions. Firstly, this is accomplished by replacing $A^{ - 1} $ by $A^\dag $, the Moore–Penrose inverse of A, and, secondly, by considering matrices that leave a cone invariant.Let $A \in R^{m \times n} $. The splitting $A = M - N$ is called proper if $R(A) = R(M)$ and $N(A) = N(M)$. Such is the case when A and M are nonsingular. Consider the iteration \[ ( * * )\qquad x^{i + 1} = M^ \dag Nx^i + M^ \dag b. \] It is shown that for a proper splitting, $\rho (M^ \dag N)$ (the spectral radius of $M^ \dag N$) is less than l, if and only if the iteration (**) converges to $A^ \dag b$, the best least squares approximate solution of the system (*). This approach has the advantage of avoiding the normal system $A^T Ax = A^T b$ in solving (*). Necessary an...

The paper is a collection of results on the linear complementarity problem (q, M). The results are stated in terms of the matrix M.

Control theoretic problems concerning controllable sets are analyzed through matrix theoretic problems involving essential nonnegativity, irreducibility, and M - matrices. These problems are solved via linear programming and graph theoretic methods.

An n × n sign pattern admits a matrix with zero-line-sums and rank n −1 if and only if it is fully indecomposable and every arc of an associated directed bipartite graph lies on a circuit. This proves a conjecture of Fiedler and Grone made in the study of sign patterns of inverse-positive matrices.

The complementarity problem is defined and studied for cases where the constraints involve convex cones, thus extending the real and complex complementarity problems. Special cases of the problem are equivalent to dual, linear or quadratic, programs over polyhedral cones.

Proper splittings $A = M - N$ of a rectangular matrix A of ${\poeratorname{rank}}r$ are characterized in terms of splittings $A_{11} = M_{11} - N_{11} $, where $A_{11} $ is a nonsingular submatrix ...

A sufficient condition for complete positivity of a matrix, in terms of complete positivity of smaller matrices, is given. Those patterns for which this condition is also necessary are characterized. These results are used to characterize complete positivity of matrices under some acyclicity assumptions on their graph. The exact value of the factorization index is given for acyche matrices.

For each of several S ⊆ R n , n , those linear transformations L : R n,n → R n,n which map S onto S are characterized. Each class is a familiar one which generalizes the notion of positivity to matrices. The classes include: the matrices with nonnegative principal minors, the M -matrices, the totally nonnegative matrices, the D -stable matrices, the matrices with positive diagonal Lyapunov solutions, and the H -matrices, as well as other related classes. The set of transformations is somewhat different from case to case, but the strategy of proof, while differing in detail, is similar.

Complementary subspaces consistency between the linear system \[ ( * )\qquad Ax = b \] and the linear system $Bx = c$ is defined and studied. This concept is applied to the consideration of iterative schemes for solving (*) obtained through various splittings of the matrix A.

The length of a (0, 1) matrix (a bigraph) is defined and studied.

A real matrix A is called S-monotone if S is a complementary subspace of N(A) and if Ax⩾0, x∈S → x⩾0 . A is called almost monotone if it is S-monotone for every such S. These types of monotonicity appear in the study of regular splittings for iterative methods. Almost and S-monotonicity are characterized here and are related to six other types of monotonicity.

Necessary and sufficient conditions are given for the pencil generated by two, or more, Hermitian matrices to contain a positive definite matrix.

The solvability of linear equations with solutions in the interior of a closed convex cone is characterized. Corollaries include Lyapunov's theorem characterizing stable matrices and a generalization of Stiemke's theorem of the alternative for complex linear inequalities.