M.Sc Thesis | |

M.Sc Student | Bank Efrat |
---|---|

Subject | Symmetric Matrices with a Given Graph |

Department | Department of Mathematics |

Supervisor | PROFESSOR EMERITUS Raphael Loewy |

Full Thesis text |

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 *S*_{F}(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 *S*_{F}(G) are allowed to be any element
from the field. Let *mr*_{F}(G) be the minimum rank of all the
matrices in *S*_{F}(G). The parameter *mr*_{F}(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, *mr*_{F}(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 *S*_{F}(T) with* rank*(A) = *mr*_{F}(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 *mr*_{F}(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.