|
|
|
Minimum
Rank/Eigenvalues of Symmetric Matrices of a Graph or Sign pattern
The graph G(A) of a real symmetric matrix A has vertices {1,...,n},
and as edges the unordered pairs {i,j} such that ai j
is nonzero (with distinct i, j). In recent years there has been a
great deal of interest in the possible eigenvalues of a real symmetric
matrix whose nonzero entries are described by a given graph or by the
pattern
of the signs of the entries, especially a tree (i.e., a connected graph
with no cycles). An example of an application of an
algorithm
that produces a 0,1-matrix B wuth G(B) = T and rank B = mr(T) is shown
below.
For a sign pattern, the matrices need not be symmetric (the pattern
itself need not be symmetric. There is interest in psetrcally
arbitary
patterns, i.e., those that allow any spectrum.
The Nonnegative P0-Matrix
Completion
Problem
(Choi, DeAlba, Hogben, Kivunge,
Nordstrom, Shedenhelm)
Electronic
Journal of Linear Algebra 10 (2003): 46-59
In this paper the nonnegative P 0 -matrix completion
problem
is considered. It is shown that a pattern for 4 x 4 matrices that
includes all diagonal positions has nonnegative P 0
-completion
if and only if its digraph has the property that the induced subdigraph
of any 4-cycle is a clique.It is also shown that any positionally
symmetric
pattern that includes all diagonal positions and whose graph is an n
-cycle
has nonnegative P 0 -completion if and only if n =4. [PDF
]
The (Weakly) Sign Symmetric
P-Matrix
Completion Problems
(DeAlba, Hardy, Hogben, Wangsness)
Electronic
Journal of Linear Algebra 10 (2003): 257-271
In this paper we show that a partial sign symmetric P-matrix, whose
graph of specified entries is an n-cycle with n >= 6, can be
completed
to a sign symmetric P-matrix. The analogous completion property is also
established for a partial weakly sign symmetric P-matrix and for a
partial
weakly sign symmetric P0-matrix. We show that a partial
(weakly)
sign symmetric P-matrix, whose digraph of specified entries is an
asymmetric
n-cycle with n >= 4, can be completed to a (weakly) sign symmetric
P-matrix.
We also classify patterns of entries for 4 x 4 matrices as to whether
or
not a partial (weakly) sign symmetric P- or weakly sign symmetric P0-matrix
specifying the pattern must have completion to the same type of matrix.
We also examine the relationship between the weakly sign symmetric P-
and
sign symmetric P-matrix completion problems. [PDF
]
On completion problems for
various
classes of P-matrices (Bowers, Evers,
Hogben, Shaner, Snider, Wangsness) Linear
Algebra and Its Applications
413 (2006) 342-354.
A pattern of positions in an n x n real matrix is said to have P-completion
if every partial P-matrix which specifies
that
pattern can be completed to a P-matrix.
A Fischer matrix is a P-matrix that satisfies Fischer's inequality for
all principal submatrices. In this paper, all patterns of
positions
of size up through 4 are classified as to whether or not every partial
P-matrix
can be completed to a P-matrix
for
P
any of the classes positive P-, nonnegative
P-, or Fischer matrices. Also, all symmetric patterns
up through size 5 are classified as to whether or not they have Fischer
completion, and all but 2 such patterns are classified as to whether or
not they have positive P- or nonnegative P-completion. We also
show
that any pattern whose digraph contains a minimally chordal
symmetric-Hamiltonian
induced subdigraph does not have $\Pi$-completion for P
any
of the classes positive P-, nonnegative P-, Fischer matrices. [
PDF preprint ]
Minimum Rank and Maximum
Eigenvalue
Multiplicity of Symmetric Tree Sign Patterns
(DeAlba,
Hardy, Hentzel, Hogben, Wangsness), Linear
Algebra and Its
Applications 418 (2006)
389-415 pdf
preprint.
The set of real matrices described by a
sign
pattern (a square matrix whose entries are elements of {+,
-, 0}) has been studied
extensively. A simple graph has been associated
with the set of symmetric matrices having a zero-nonzero pattern of
off-diagonal
entries described by the graph. In this
paper, we present a unified approach to the study
of the set of symmetric matrices described by a sign pattern and
the set of matrices associated with a graph allowing loops, with the
presence
or absence of loops describing the zero-nonzero pattern of the
diagonal.
We call any family of matrices having a common graph a
cohort.
For a cohort whose graph is a tree, we provide an algorithm for the
calculation
of the maximum of the multiplicities of eigenvalues of any matrix
in the cohort. For a
symmetric tree sign pattern or tree that allows
loops, this algorithm allows exact computation of maximum multiplicity
and minimum rank, and can be used to
obtain a symmetric integer matrix realizing
minimum
rank.
Rational Realization of
Maximum
Eigenvalue Multiplicity of Symmetric Tree Sign Patterns
(Chowdhury,
Hogben, Melancon, Mikkelson), Linear
Algebra and
Its
Applications 418 (2006)
380-393, pdf preprint.
A sign pattern is a matrix
whose entries are elements of {+, -,0} and describes the family
of
real matrices whose entries have the signs in the pattern. A graph
(that
allows loops but not multiple edges) describes the set of
symmetric
matrices having a zero-nonzero pattern of entries determined
by
the absence or presence of edges in the graph. DeAlba, Hardy, Hentzel,
Hogben, Wangsness (above)
gave
algorithms for the computation of maximum multiplicity and minimum rank
of matrices associated with a tree sign pattern or tree, and an
algorithm
to obtain an integer matrix realizing minimum rank. We extend
these
results by giving algorithms to obtain a symmetric rational matrix
realizing
the maximum multiplicity of a rational eigenvalue among symmetric
matrices
associated with a symmetric tree
sign pattern or tree.
Spectrally Arbitrary Patterns: Reducibility and the 2n Conjecture (with DeAlba,
Hentzel, McDonald, Mikkelson, Pryporova, Shader, Vander Meulen) Linear
Algebra and
Its
Applications, 423 (2007) 262-276. [PDF
preprint
]
A
sign pattern $Z$ (a matrix whose entries are elements
of $\{+, -, 0\}$) is spectrally arbitrary if for any self-conjugate
spectrum there is a real matrix with sign pattern $Z$ having the given
spectrum. Spectrally arbitrary sign patterns were introduced in
\cite{specArbPat}, where it was (incorrectly) stated that if a sign
pattern $Z$ is reducible and each of its irreducible components is a
spectrally arbitrary sign pattern, then $Z$ is a spectrally arbitrary
sign pattern, and it was conjectured that the converse is true as well;
we present counterexamples to both of these statements. In
\cite{BMO04} it was conjectured that any $n\times n$ spectrally
arbitrary sign pattern must have at least $2n$ nonzero entries; we
establish that this conjecture is true for $5\times 5$ sign
patterns. We also establish analogous results for nonzero patterns.
Minimum Rank
of a Tree over an Arbitrary Field (with Nathan L. Chenette,
Sean V. Droms, Rana Mikkelson and Olga Pryporova)
Electronic Journal of
Linear
Algebra 16 (2007): 183-186.
For a field $F$ and graph $G$ of order $n$, the
minimum rank of $G$ over $F$ is defined to be the smallest possible
rank over all symmetric matrices $A\in\Fnn$ whose $(i,j)$th entry (for
$i\neq j$) is nonzero whenever $\{i,j\}$ is an edge in $G$
and is zero otherwise. We show that the minimum rank of a
tree is independent of the field.
| Leslie Hogben's Homepage |    |
30-July-07 |