Glossary: Spectra of matrices: terminology

Click on the word to edit or delete.   Or you can add a new entry.

To print, use the PDF version.

The html version (which you are viewing right now) is only intended to help with the creation and editing of the glossary. Use the pdf version to read or print the glossary. You may notice some anomalies with the formulas in the html version: the pdf file is the "official" version. (These anomalies have a variety of causes, such as your browser caching images of the formulas).

 

$ 2$ -connected
A graph of order at least 3 that does not have a cut-vertex.
$ (3,\ell)$ -whirl ( $ \ell \geq 1$ )
The tree on $ n=6\ell+4$ vertices with 6 pendant paths $ \alpha_{i}, \beta_{i}, \gamma_{i}$ , each with $ \ell$ vertices, for $ i=1,2$ .
acyclic
A graph that does not contain any cycles. Also a matrix $ A$ whose graph $ {\mathcal G}(A)$ is acyclic.
allows singularity
Graph $ G$ allows singularity if there exists $ B\in{\mathcal S}^\ell(G)$ that is singular.
appropriate
A vertex $ v$ of $ T$ is appropriate if $ T-v$ has at least two components that are pendent paths.
center
The unique high degree vertex in a generalized star or pendent generalized star (if one exists).

chordal
A graph that does not contain an induced cycle on four or more vertices.

chromatic number
The smallest number of color classes of any vertex coloring of $ G$ (provided $ G$ does not have loops), denoted $ \chi(G)$ .
clique
An induced subgraph $ G'$ of a graph $ G$ that has an edge between every pair of vertices of $ G'$ (i.e., $ G'$ is isomorphic to $ K_n$ where $ n=\vert{G'}\vert$ ).
clique covering
A set of subgraphs of $ G$ , each of which is a clique and such that every edge of $ G$ is contained in at least one of these cliques.
clique covering number
The smallest number of cliques in a clique covering of $ G$ , denoted $ \theta(G)$ .
coclique
A set of vertices $ S$ of graph $ G$ such that the induced subgraph $ G[S]$ has no edges.
Colin de Verdiere parameters $ \mu, \nu=\nu^{\mathbb{R}}, \nu^{\mathbb{C}}$
$ \mu(G)$ is the maximum multiplicity of 0 as an eigenvalue among matrices $ L$ that satisfy:
  • $ L$ is a generalized Laplacian matrix of $ G$ ,
  • $ L$ has exactly one negative eigenvalue (of multiplicity 1),
  • $ L$ satisfies the Strong Arnold Hypothesis.

$ \nu(G)$ is defined to be the maximum multiplicity of 0 as an eigenvalue among matrices $ A$ that satisfy:

  • $ A \in {\mathcal S}(G)$ ,
  • $ A$ is positive semidefinite,
  • $ A$ satisfies the Strong Arnold Hypothesis.

$ \nu^{\mathbb{C}}(G)$ is defined to be the maximum multiplicity of 0 as an eigenvalue among matrices $ A$ that satisfy:

  • $ A \in {\mathcal H}(G)$ ,
  • $ A$ is positive semidefinite,
  • $ A$ satisfies the complex Strong Arnold Hypothesis.
Colin de Verdiere type-parameter $ \xi$
$ \xi(G)$ is the maximum multiplicity of 0 as an eigenvalue among matrices $ A$ that satisfy:
  • $ A \in {\mathcal S}(G)$
  • $ A$ satisfies the Strong Arnold Hypothesis.
color class
One of the cocliques in a vertex coloring.

complete subgraph
See clique.
complex Strong Arnold Hypothesis
A Hermitian matrix $ M$ satifies the complex Strong Arnold Hypothesis provided there does not exist a nonzero Hermitian matrix $ X$ satisfying:
  • $ MX = \0$ .
  • $ M\circ X = \0$ .
  • $ I\circ X=\0$ .
component
A maximum connected (induced) subgraph. Same as connected component.

connected
There is a path from any vertex to any other vertex. (A graph of order one is connected whether or not it has a loop.)

connected component
A maximum connected (induced) subgraph.

contraction
A graph obtained from $ G$ by identifying two adjacent vertices of $ G$ , suppressing any loops or multiple edges that arise in this process.
cut-vertex
A vertex $ v$ of a connected simple graph $ G$ such that $ G - v$ is disconnected. More generally, $ v$ is a cut-vertex of a graph $ G$ if $ v$ is a cut-vertex of a component of $ G$ .
decomposable
A graph that can be expressed as a sequence of unions and joins of isolated vertices.

degree sequence
Let $ G$ be a graph having vertices $ v_1,\dots,v_n$ of degrees $ d_1\le d_2\le\dots\le d_n$ . The degree sequence of $ G$ is $ (d_1,d_2,\dots,d_n)$ .
delete (vertex or set of vertices)
The result of deleting vertex $ v$ of $ G$ and its incident edges, denoted $ G-v$ . If $ S\subset V$ , $ G-S$ is the result of deleting all vertices of $ S$ and their incident edges from $ G$ .
diameter
$ {\rm diam}(G)$ is the maximum distance between any two vertices of G.
disconnected
Not connected.

distance (between two vertices)
The number of edges in a shortest path between the vertices.

double generalized star
A tree that can be constructed from two generalized stars by joining their centers by an edge.

double path
A tree that can be constructed from two paths $ T_1$ and $ T_2$ each of order $ \ge 3$ by joining a vertex of degree two in $ T_1$ to a vertex of degree two in $ T_2$ by an edge.
dual
The dual of a plane embedding of a planar graph $ G$ is obtained as follows: Place a new vertex in each face of the embedding; these are the vertices of the dual. Two dual vertices are adjacent if and only if the two faces of $ G$ share an edge of $ G$ .

Note that the dual of a planar graph is not well-defined in general: the graph can have two embeddings with different duals.

energy of a graph
The sum of the absolute values of the eigenvalues of the adjacency matrix of the graph.
generalized Laplacian matrix
(of simple $ G$ ) A symmetric matrix $ L$ such that $ {\mathcal G}(L)=G$ and all off-diagonal entries of $ L$ are non-positive.
generalized star
A tree that has at most one high degree vertex.

geometric multiplicity
(of $ {\lambda}$ as an eigenvalue of $ B$ ) The dimension of ker( $ B-{\lambda} I$ ), denoted $ {\rm gmult}_B({\lambda})$ .
graph
A set of vertices and a set of edges joining vertices. A {graph} may allow multiple edges and/or loops. A simple graph allows neither. Most graphs under discussion are simple.

graph (of $ B\in{S_n}$ )
The simple graph with vertices $ \{1,\dots,n \}$ and edges $ \{ \{i,j \} \vert b_{ij} \ne 0$    and $ i \ne j \}$ , denoted $ {\mathcal G}(B)$ . Note that the diagonal of $ B$ is ignored in determining $ {\mathcal G}(B)$ .
$ H$ -free
A subgraph $ G_1$ of $ G$ is $ H$ -free if $ G_1$ has no vertex in $ H$ ( $ H\subset V(G)$ ).
Hermitian minimum rank
$ {{\rm hmr}}(G)=\min\{ {\rm rank}(B) : B \in {{\mathcal H}}(G) \}$ . ($ G$ is simple.)
Hermitian positive semidefinite minimum rank
$ {\rm hmr}^+(G)=\min\{ {\rm rank}(B): B \in {\mathcal H}^+(G) \}$ . ($ G$ is simple.)
high degree vertex
A vertex of degree at least 3. The set of high degree vertices of $ G$ is denoted $ H(G)$ .
hyperenergetic graph
A simple graph with $ n$ vertices whose energy is greater than the energy of the complete graph $ K_n$ .
independent set of vertices
A set of vertices $ S$ of graph $ G$ such that the induced subgraph $ G[S]$ has no edges.
induced subgraph
The subgraph $ G[S]$ of $ G=(V,E)$ induced by $ S\subset V$ is the subgraph with vertex set $ S$ and edge set $ \{\{i,j\} \in E \mid i,j \in S\}$ .
Inverse Eigenvalue Problem of a graph (IEP-G)
To characterize the possible spectra of matrices in $ {\mathcal S}(G)$ . ($ G$ is simple.)
linear $ 2$ -tree
A $ 2$ -connected graph $ G$ that can be embedded in the plane such that the graph obtained from the dual of $ G$ after deleting the vertex corresponding to the infinite face is a path.
loop-tree
The graph $ T$ is a loop-tree if $ {\widehat T}$ is a (simple) tree.
low degree vertex
A vertex of degree less than 3.

matrix
The rank-spread of simple graph $ G$ at vertex $ v$ is $ r_{v}(G)={\rm mr}(G)-{\rm mr}(G-v)$ .
matrix of indeterminates
For a loop-tree $ T$ , define it its matrix of indeterminates $ X_T$ as follows:
For $ i\le j, i,j\in V(T), ij\in E(T)$ , let $ x_{ij}$ be independent indeterminates and $ (X_T)_{ij}=x_{ij}$ and $ (X_T)_{ji}=x_{ij}$ , and let the entries that do not correspond to edges be 0.
maximum multiplicity
$ M(G) = \max\{{\rm mult}_B({\lambda}) : B \in {\mathcal S}(G), {\lambda}\in{\mathbb{R}} \}$ (over $ {\mathbb{R}}$). Over field $ F$, $ M^F(G) = \max\{{\rm mult}_B({\lambda}) : B \in {\mathcal S}^F(G), {\lambda}\in\sigma(B)) \}.$ $ gM^F(G) = \max\{{\rm gmult}_B({\lambda}) : B \in {\mathcal S}^F(G), {\lambda}\in\sigma(B)).\}$ ($ G$ is a simple graph.)
minimum number of distinct eigenvalues
(of simple graph $ G$ ) $ q(G)=\min\{q(B):B\in{\mathcal S}(G)\}$ where $ q(B)$ denotes the number of distinct eigenvalues of $ B$ .
minimum rank
$ {\rm mr}(G)=\min\{ {\rm rank} (B) : B \in {\mathcal S}(G) \}$ (over $ {\mathbb{R}}$ ). Over field $ F$ , $ {\rm mr}^F(G)=\min\{ {\rm rank}(B) : B \in {\mathcal S}^F(G) \}.$ ($ G$ is a simple graph.)
minimum rank problem
Determine the minimum rank among real symmetric matrices whose zero-nonzero pattern of off-diagonal entries is described by a given simple graph $ G$ .
minimum vector rank
For any graph $ G$ , the minimum rank over all vector representations of $ G$ , denoted by $ {\rm mvr}(G)$ .
minor
A graph obtained from $ G$ by performing a series of deletions of edges, deletions of isolated vertices, and/or contraction of edges.
minor monotone
A graph parameter $ \zeta$ such that for any minor $ G'$ of $ G$ , $ \zeta(G') \le \zeta(G)$ .
monotone on induced subgraphs
A graph parameter $ \zeta$ such that for any induced subgraph $ H$ of $ G$ , $ \zeta(H) \le \zeta(G)$ .
multiplicity
(of eigenvalue $ {\lambda}$ of square matrix $ B$ ) The multiplicity of $ {\lambda}$ as a root of the characteristic polynomial of $ B$ (i.e., the algebraic multiplicity of $ {\lambda}$ ), denoted $ {\rm mult}_B({\lambda})$ .
order
The order of $ G$ , denoted $ \vert{G}\vert$ , is the number of vertices of $ G$ . All graphs are finite (finite number of vertices and finite number of edges).
ordered multiplicity list
$ (m_1,\dots,m_q)$ where the distinct eigenvalues of $ B\in{S_n}$ are $ \breve{\beta}_1 < \cdots < \breve{\beta}_q$ with multiplicities $ m_1,\dots,m_q$ .
Parter-Wiener (PW) vertex
Vertex $ k$ is a Parter-Wiener (PW) vertex of $ B$ for eigenvalue $ {\lambda}$ if
$ {\rm mult}_{B(k)}({\lambda}) = {\rm mult}_B({\lambda}) + 1$ .
path cover number
The minimum number of vertex disjoint paths occurring as induced subgraphs of simple graph $ G$ that cover all the vertices of $ G$ , of $ G$ , denoted $ P(G)$ .
pendent generalized star
A connected induced subgraph $ S$ of $ G$ such that:
  • There is exactly one vertex $ v$ of $ S$ that is a high degree vertex of $ G$ ,
  • $ G - v$ has $ k+1$ components and exactly $ k$ of the components of $ G - v$ are pendent paths of $ v$ ,
  • $ S$ is induced by the vertices of the $ k$ pendent paths and $ v$ .
pendent path
A path $ P$ in $ G$ is a pendent path of vertex $ v$ if $ P$ is a component of $ G - v$ and (in $ G$ ) $ P$ is connected to $ v$ by one of its end-points.
positive semidefinite
A real symmetric matrix $ B$ such that for all $ {\bf x}\in{\mathbb{R}}^n, {\bf x}^TB{\bf x}\ge 0$ . More generally, a matrix $ B\in{{\mathbb{C}}^{n\times n}}$ such that for all $ {\bf x}\in{\mathbb{C}}^n, {\bf x}^TB{\bf x}\ge 0$ (a complex positive semidefinite matrix is necessarily Hermitian).
positive semidefinite minimum rank
$ {\rm mr}^+(G)=\min\{ {\rm rank}(B): B \in {\mathcal S}^+(G) \}.$ ($ G$ is simple.)
principal submatrix
If $ R \subseteq \{1,2,\ldots, n\}$ and $ B\in{F^{n\times n}}$ , then the principal submatrix of $ B$ defined by $ R$ is the submatrix of $ B$ whose rows and columns are indexed by $ R$ , denoted $ B[R]$ . $ B(R)$ denotes the complementary principal submatrix obtained from $ B$ by deleting the rows and columns indexed by $ R$ .
rank
(of vector representation $ \vec{W} =\{{\bf w}_1, \dots, {\bf w}_n\} \subset \mathbb{C}^m$ ) $ \dim{\rm Span}(W)$ .
rank-strong
A vertex $ v$ of $ G$ is rank-strong if $ {\rm mr}(G)={\rm mr}(G-v)+2$ .
SAP
Spectrally Arbitrary Pattern
set of Hermitian matrices (of simple graph $ G$ )
$ {\mathcal H}(G) = \{ B : B$    is a Hermitian $ n\times n$    matrix over $ {\mathbb{C}}$    and $ {\mathcal G}(B) = G\}.$
set of symmetric matrices (of simple graph $ G$ )
$ {\mathcal S}(G) = \{ B \in {S_n} : {\mathcal G}(B) = G\}$ (over $ {\mathbb{R}}$ ).

Over a field $ F$ , $ {\mathcal S}^F(G) = \{ B : B$    is a symmetric $ n\times n$    matrix over $ F$    and $ {\mathcal G}(B) = G\}$ .

simple graph
A graph that does not have multiple edges or loops.
spectrum
For a matrix $ A\in{F^{n\times n}}$ , the multiset of the $ n$ roots of the characteristic polynomial in the algebraic closure of $ F$ , denoted $ \sigma(A)$ .
Strong Arnold Hypothesis
A symmetric real matrix $ M$ is said to satisfy the Strong Arnold Hypothesis provided there does not exist a nonzero symmetric matrix $ X$ satisfying:
  • $ MX = {\bf0}$ .
  • $ M\circ X = {\bf0}$ .
  • $ I\circ X={\bf0}$ .
strong PW vertex
Vertex $ k$ is a strong PW vertex of $ B$ for $ {\lambda}$ if $ k$ is a PW vertex of $ B$ for $ {\lambda}$ and $ {\lambda}$ is an eigenvalue of at least three components of $ {\mathcal G}(B) - k$ .
tree
A tree is a connected acyclic simple graph.

typical
A vertex $ v$ of $ G$ is typical if $ v$ has at least two low-degree neighbors.
vector representation
(of graph $ G$ ) A set $ \vec{W} =\{{\bf w}_1, \dots, {\bf w}_n\} \subset \mathbb{C}^m$ , where none of the $ {\bf w}_i$ is the zero vector and for $ i \neq j$ , $ \langle {\bf w}_i, {\bf w}_j \rangle \neq 0$ if vertices $ i$ and $ j$ are connected and $ \langle {\bf w}_i, {\bf w}_j \rangle =0$ if $ i$ and $ j$ are not connected.
vertex coloring
A partition of the vertex set into cocliques.

vertex independence number
The largest number $ k$ for which a coclique of $ G$ with $ k$ vertices exists, denoted by $ \alpha(G)$ .



Click on the word to edit or delete.   Or you can add a new entry.