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.

We investigate the emission characteristics of a tri-atomic photonic meta-molecule with asymmetric intra-modal couplings which is uniformly excited by an incident waveform tuned to coherent virtual absorption conditions. By analyzing the dynamics of the discharged radiation, we identify a parameter domain where its directional re-emission properties are optimal.

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

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.

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.

We present examples of interesting problems that hopefully make the learning and the teaching of linear algebra enjoyable. The problems are on matrix multiplication, rank, determinants, eigenvalues and eigenvectors, and matrices and graphs. The problem solving strategies used include “look for invariants”, “check parity” and “define an energy function”.

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.

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.

In this paper, we present SciTech, the summer international research program for talented high school students, organized in the Technion — Israel Institute of Technology [1] [1] The first author of this paper is proud of founding SciTech in 1992 when he was the head of the Harry and Lou Stern Family Science and Technology Youth Center at the Technion. Information on the various activities of the Youth Center aimed at promotion of excellence and interest in mathematics, science and technology of high school students can be found in the website of the Technion ( http://www.mechina.technion.ac.il/en/index.html ) . Our major thesis is that while taking part in scientific projects under supervision by the Technion research stuff, the high school participants in SciTech are given the opportunity to work as researchers, and not just as learners. We begin with a brief discussion of the term ‘good research.’ This is followed by a description of SciTech: we outline how students are accepted to the program and what they do in it. The main part of this paper is devoted to discussion of some, not necessarily the most successful, mathematical projects, which we had the pleasure to supervise. We conclude the paper with general observations concerning the projects, based on our experience as SciTech mentors.

This article describes the following phenomenon: Gifted high school students trained in solving Olympiad-style mathematics problems experienced conflict between their conceptions of effectiveness and elegance (the EEC). This phenomenon was observed while analyzing clinical task-based interviews that were conducted with three members of the Israeli team participating in the International Mathematics Olympiad. We illustrate how the conflict between the students’ conceptions of effectiveness and elegance is reflected in their geometrical problem solving, and analyze didactical and epistemological roots of the phenomenon.

This note discusses some of the shortcomings of multiple choice tests in Mathematics given to undergraduate engineering students. Examples are presented, where the disadvantages of a multiple choice test are pointed out and suggestions how to overcome the difficulties are given.

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.