Spelling suggestions: "subject:"diagonal entry restrictions"" "subject:"diagonal entry estrictions""
1 |
The Minimum Rank of Schemes on GraphsSexton, William Nelson 01 March 2014 (has links)
Let G be an undirected graph on n vertices and let S(G) be the class of all real-valued symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let V = {1, 2, . . . , n} be the vertex set of G. A scheme on G is a function f : V → {0, 1}. Given a scheme f on G, there is an associated class of matrices Sf (G) = {A ∈ S(G)|aii = 0 if and only if f(i) = 0}. A scheme f is said to be constructible if there exists a matrix A ∈ Sf (G) with rank A = min{rank M|M ∈ S(G)}. We explore properties of constructible schemes and give a complete classification of which schemes are constructible for paths and cycles. We also consider schemes on complete graphs and show the existence of a graph for which every possible scheme is constructible.
|
2 |
Diagonal Entry Restrictions in Minimum Rank Matrices, and the Inverse Inertia and Eigenvalue Problems for GraphsNelson, Curtis G. 11 June 2012 (has links) (PDF)
Let F be a field, let G be an undirected graph on n vertices, and let SF(G) be the set of all F-valued symmetric n x n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let MRF(G) be defined as the set of matrices in SF(G) whose rank achieves the minimum of the ranks of matrices in SF(G). We develop techniques involving Z-hat, a process termed nil forcing, and induced subgraphs, that can determine when diagonal entries corresponding to specific vertices of G must be zero or nonzero for all matrices in MRF(G). We call these vertices nil or nonzero vertices, respectively. If a vertex is not a nil or nonzero vertex, we call it a neutral vertex. In addition, we completely classify the vertices of trees in terms of the classifications: nil, nonzero and neutral. Next we give an example of how nil vertices can help solve the inverse inertia problem. Lastly we give results about the inverse eigenvalue problem and solve a more complex variation of the problem (the λ, µ problem) for the path on 4 vertices. We also obtain a general result for the λ, µ problem concerning the number of λ’s and µ’s that can be equal.
|
Page generated in 0.0834 seconds