Linearly independent vertices and minimum semidefinite rank

Philip Hackney; Benjamin Harris; Margaret Lay; Lon H. Mitchell; Sivaram K. Narayan; Amanda Pascoe

doi:10.1016/j.laa.2009.03.030

Linearly independent vertices and minimum semidefinite rank

Philip Hackney, Benjamin Harris, Margaret Lay, Lon H. Mitchell, Sivaram K. Narayan^*, Amanda Pascoe

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

39 Citations (Scopus)

Abstract

We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex. (C) 2009 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	1105-1115
Number of pages	11
Journal	Linear Algebra and Its Applications
Volume	431
Issue number	8
DOIs	https://doi.org/10.1016/j.laa.2009.03.030
Publication status	Published - 1 Sept 2009
Externally published	Yes

Keywords

Minimum semidefinite rank
Join
Linearly independent vertices
GRAPHS
REPRESENTATIONS
MATRICES

Access to Document

10.1016/j.laa.2009.03.030

Cite this

@article{1c68c670637943c49fd5ab5fc518811f,

title = "Linearly independent vertices and minimum semidefinite rank",

abstract = "We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex. (C) 2009 Elsevier Inc. All rights reserved.",

keywords = "Minimum semidefinite rank, Join, Linearly independent vertices, GRAPHS, REPRESENTATIONS, MATRICES",

author = "Philip Hackney and Benjamin Harris and Margaret Lay and Mitchell, {Lon H.} and Narayan, {Sivaram K.} and Amanda Pascoe",

year = "2009",

month = sep,

day = "1",

doi = "10.1016/j.laa.2009.03.030",

language = "English",

volume = "431",

pages = "1105--1115",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier",

number = "8",

}

TY - JOUR

T1 - Linearly independent vertices and minimum semidefinite rank

AU - Hackney, Philip

AU - Harris, Benjamin

AU - Lay, Margaret

AU - Mitchell, Lon H.

AU - Narayan, Sivaram K.

AU - Pascoe, Amanda

PY - 2009/9/1

Y1 - 2009/9/1

N2 - We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex. (C) 2009 Elsevier Inc. All rights reserved.

AB - We study the minimum semidefinite rank of a graph using vector representations of the graph and of certain subgraphs. We present a sufficient condition for when the vectors corresponding to a set of vertices of a graph must be linearly independent in any vector representation of that graph, and conjecture that the resulting graph invariant is equal to minimum semidefinite rank. Rotation of vector representations by a unitary matrix allows us to find the minimum semidefinite rank of the join of two graphs. We also improve upon previous results concerning the effect on minimum semidefinite rank of the removal of a vertex. (C) 2009 Elsevier Inc. All rights reserved.

KW - Minimum semidefinite rank

KW - Join

KW - Linearly independent vertices

KW - GRAPHS

KW - REPRESENTATIONS

KW - MATRICES

U2 - 10.1016/j.laa.2009.03.030

DO - 10.1016/j.laa.2009.03.030

M3 - Article

SN - 0024-3795

VL - 431

SP - 1105

EP - 1115

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 8

ER -

Linearly independent vertices and minimum semidefinite rank

Abstract

Keywords

Access to Document

Fingerprint

Cite this