M.Sc Thesis
M.Sc Student Bank Efrat Symmetric Matrices with a Given Graph Department of Mathematics Professor Emeritus Raphael Loewy

Abstract

The main theme of this thesis is the interplay between graphs and matrices.

Let G = (V, E) be a finite undirected graph on n vertices without loops or multiple edges.  For every field F, associate with G the set SF(G) - the set of all n-by-n symmetric matrices over F whose nonzero off-diagonal entries occur in exactly the same positions corresponding to the edges of G. The diagonal entries of any matrix A in SF(G) are allowed to be any element from the field.  Let mrF(G) be the minimum rank of all the matrices in SF(G). The parameter mrF(G) is called the minimum rank of G and is the main subject of this thesis.

We begin by providing the necessary definitions and basic results.  Then we survey some of the recent results.

Our first result provides a way to compute the minimum rank of forests.  For a graph G we define the path cover number of G to be the minimum size of a set of disjoint induced paths that cover the vertices of G. We generalize a known result about the connection between the path cover number and the minimum rank of forests, to obtain, mrF(T) = n - p where T is a forest on n vertices with path cover number p, and F is an arbitrary field.  We present a way of constructing a matrix A in SF(T) with rank(A) = mrF(T) .

The next result deals with graphs that contain a complete graph as an induced subgraph.  The goal is to find an upper bound for the minimum rank over some field F.  This upper bound depends on the size of the graph G and the size of the maximum induced complete graph.  We obtain that  mrF(G) b n - q +1, where G is a graph on n vertices, which contains the complete graph on q vertices as a maximal clique and F is a field with at least q - 1 elements.  Some special cases deal with a graph G on  n vertices which contains the complete graph on 2, 3 or n - 1, n - 2 vertices.  These are distinct cases, since the size of the field may be smaller than q - 1 where q is the size of the maximum clique.

Finally, we present a variant of the minimum rank and find a relation between this variant and symmetric k-diagonal matrices.