טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMichal Dina
SubjectSpectrally Arbitrary Patterns
DepartmentDepartment of Mathematics
Supervisors Professor Emeritus Berman Abraham
Professor Emeritus Hershkowitz Daniel
Full Thesis textFull thesis text - English Version


Abstract

A sign pattern matrix is a matrix which has + ,- or 0 as its entries.

If S = (sij) is an  n×n sign pattern matrix then the sign pattern class of S is

Q(S) = { A = (aij) in Mn(R) : sgn(aij) = sij for all i,j }, where Mn(R) is the set of all n×n matrices over R and sgn(aij) is the sign of the number aij.

An n×n sign pattern matrix S, where n≥2, is called spectrally arbitrary pattern (SAP) if given any monic polynomial p(x) of degree n with real coefficients, there is a matrix A in Q(S) such that the characteristic polynomial of A is p(x).

A sign pattern B = (bij) is a superpattern of a sign pattern A = (aij) if bij = aij whenever aij≠0.

A sign pattern A is minimally spectrally arbitrary pattern (MSAP) if it is spectrally arbitrary but is not spectrally arbitrary if any nonzero entry of A is replaced by zero.

Two sign patterns A and B are equivalent if B may be obtained from A by some combination of negation, transposition, permutation similarity and signature similarity. It is known that if A and B are two equivalent sign patterns then A is a SAP iff B is a SAP.

A combinatorially symmetric sign pattern matrix is a square sign pattern matrix A where aij ≠ 0 iff aji ≠ 0.

A tree sign pattern (t.s.p.) matrix is a combinatorially symmetric sign pattern matrix whose undirected graph is a tree (possibly with loops).


In the thesis we describe the Nilpotent-Jacobian Method which is used for proving that a certain sign pattern, as well as all of its superpatterns, are SAPs and give an overview of the sign patterns which are known to be SAPs/MSAPs.

We then refer to the tree sign patterns. We give basic properties of the spectrally arbitrary tree sign patterns and give an overview of the classification of the 2×2, 3×3 and 4×4 spectrally arbitrary t.s.p..

The new results in the thesis are:

• New patterns are proven to be SAPs. In order to verify that those patterns are not equivalent to any of the known SAPs, I use a new result which enables us to verify that two sign patterns are not equivalent.

• A classification of all the 5×5 spectrally arbitrary tridiagonal t.s.p., excluding three patterns. The concept of Grobner Bases is used in this classification.