Glossary: Spectra of matrices: notation

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).

 

$ A(R)$
$ \=A[ \overline{R}]$ .
$ A[R]$
The principal submatrix of $ A$ whose rows and columns are indexed by $ R$ (where $ R \subseteq \{1,2,\ldots, n\}$ .)
$ A(v)$
$ =A(\{v\})$ .
$ \alpha(G)$
The vertex independence number of $ G$ , i.e., the largest number $ k$ for which a coclique with $ k$ vertices exists.
$ c_{\lambda}(Q)$
If $ T$ is a loop-tree and $ Q \subseteq V(T)$ , $ c_{\lambda}(Q)$ is the number of components of $ T(Q)$ that allow eigenvalue $ \lambda$ .
$ C_\lambda(T)$
$ C_\lambda(T) = \max \{c_\lambda(Q) - \vert Q\vert~ : Q \subseteq V(T)\}.$
$ C_n$
Cycle on $ n$ vertices.
$ \chi(G)$
The chromatic number of $ G$ (provided $ G$ does not have loops), i.e., the smallest number of color classes of any vertex coloring of $ G$ .
$ \Delta(G)$
$ \Delta(G) =\max\{p-q$ : there is a set of $ q$ vertices whose deletion leaves $ p$ paths.} (Note that an isolated vertex is a path of order 1 and $ G$ is simple.)
$ {\rm diam}(G)$
The diameter of $ G$ , i.e., the maximum distance between any two vertices of G.
$ E(G)$
The energy of the simple graph $ G$ .
$ \eta(G)$
$ \eta(G)=\min\{{\rm rank}(B): B\in{\mathcal S}_\eta^F(G), F$    any field$ \}$ ($ G$ simple.)
$ {\mathcal G}(A)$
The simple graph of symmetric matrix $ A$ , i.e., the simple graph with vertices $ \{1,\dots,n \}$ and edges $ \{ \{i,j \} \vert b_{ij} \ne 0$    and $ i \ne j \}$ . Note that the diagonal of $ B$ is ignored in determining $ {\mathcal G} (B)$ .
$ G-S$
The result of deleting all vertices of $ S\subset V$ and their incident edges from $ G$ .
$ G-v$
The result of deleting a vertex $ v$ of $ G$ and its incident edges.
$ \overline G$
The complement of simple graph $ G$ , i.e., $ \overline G=(V,\overline E)$ .
$ G[S]$
The subgraph induced by $ S\subset V$ , the subgraph with vertex set $ S$ and edge set $ \{\{i,j\} \in E \mid i,j \in S\}$ .
$ \vert G\vert$
The order of $ G$ . The number of vertices in $ G$ .
$ \widehat G$
The simple graph obtained from $ G$ by removing all loops from $ G$ .
$ G=(V,E)$
A graph, usually on $ \{1,\dots,n\}$ .

$ V$ is the set of vertices, $ E$ is the set of edges. $ G$ is allowed to have loops and/or multiple edges.

$ gM^F(G)$
$ gM^F(G) = \max\{{\rm gmult}_B({\lambda}) : B \in {\mathcal S}^F(G), {\lambda}\in\sigma(B)) \}.$
$ {\rm gmult}_A({\lambda})$
The geometric multiplicity of $ {\lambda}$ as an eigenvalue of $ A$ (i.e., the dimension of ker( $ A-{\lambda} I$ )).
$ H(G)$
The set of high degree vertices of simple graph $ G$ , i.e., the set of vertices of degree at least 3.
$ {\mathcal H}(G)$
$ {\mathcal H}(G) = \{ B : B$    is a Hermitian $ n\times n$    matrix over $ {\mathbb{C}}$    and $ {\mathcal G}(B) = G\}.$ ($ G$ is simple.)
$ {\mathcal H}^+(G)$
$ {\mathcal H}^+(G) = \{ B \in {\mathcal H}(G) : B$    is positive semidefinite$ \}.$ ($ G$ is simple.)
$ {{\rm hmr}}(G)$
$ {{\rm hmr}}(G)=\min\{ {\rm rank}(B) : B \in {{\mathcal H}}(G) \}.$ ($ G$ is simple.)
$ {\rm hmr}^+(G)$
$ {\rm hmr}^+(G)=\min\{ {\rm rank}(B): B \in {\mathcal H}^+(G) \}.$
$ K_n$
The complete (simple) graph on $ n$ vertices.
$ K_{p,q}$
The complete (simple) bipartite graph on $ p$ and $ q$ vertices.
$ M(G)$
The maximum multiplicity of simple $ G$ , i.e.,
$ M(G) = \max\{{\rm mult}_A({\lambda}) :~A \in {\mathcal S}(G), {\lambda}\in{\mathbb{R}} \}.$
$ M^F(G)$
$ M^F(G) = \max\{{\rm mult}_B({\lambda}) : B \in {\mathcal S}^F(G), {\lambda}\in\sigma(B)) \}.$ ($ G$ simple.)
$ M^+_{\lambda}(G)$
$ M^+_{\lambda}(G) = \max\{{\rm mult}_B({\lambda}): B \in {\mathcal S}^+(G), {\lambda}\in\sigma(B)) \}.$ ($ G$ simple.)
$ M_{{\lambda}}^\ell(G)$
$ M_{{\lambda}}^\ell(G) = \max\{{\rm mult}_B({\lambda}) : B \in {\mathcal S}^\ell(G), {\lambda}\in\sigma(B)) \}.$ (It is necessary to distinguish between zero from nonzero eigenvalues because translation is no longer possible.)
$ {\rm mr}(G)$
The minimum rank of simple graph $ G$ , i.e., $ {\rm mr}(G)=\min\{ {\rm rank} (A) : A \in {\mathcal S}(G) \}.$
$ {\rm mr}^\ell(G)$
$ {\rm mr}^\ell(G)=\min\{{\rm rank}(B) : B \in {\mathcal S}^\ell(G) \}.$
$ {\rm mr}^F(G)$
$ {\rm mr}^F(G)=\min\{ {\rm rank}(B) : B \in {\mathcal S}^F(G) \}.$ ($ G$ is simple.)
$ {\rm mr}^+(G)$
$ {\rm mr}^+(G)=\min\{ {\rm rank}(B): B \in {\mathcal S}^+(G) \}.$ ($ G$ is simple.)
$ \mu(G)$
The Colin de Verdière number $ \mu(G)$ of simple graph $ 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.
$ {\rm mult}_A({\lambda})$
The multiplicity of $ {\lambda}$ as a root of the characteristic polynomial of $ A$ (i.e., the algebraic multiplicity of $ {\lambda}$ if $ {\lambda}$ is an eigenvalue of $ A$ and 0 otherwise).
The rank-spread of simple graph $ G$ at vertex $ v$ is $ r_{v}(G)={\rm mr}(G)-{\rm mr}(G-v)$ .
The rank-spread of simple graph $ G$ at vertex $ v$ is $ r_{v}(G)={\rm mr}(G)-{\rm mr}(G-v)$ .
$ \nu(G)$
The parameter $ \nu(G)$ of simple graph $ 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)$
The parameter $ \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$ satisfies the complex Strong Arnold Hypothesis.
$ \nu^{\mathbb{R}}(G)$
Same as $ \nu(G)$
$ P(G)$
The path cover number of simple graph $ G$ , i.e., the minimum number of vertex disjoint paths occurring as induced subgraphs of $ G$ that cover all the vertices of $ G$ .
$ P_n$
The path on $ n$ vertices.
$ \overline R$
The complement of $ R$ (universe may be set of edges in a graph or index set $ \{1,\dots,n\}).$
$ r_{v}(G)$
$ r_{v}(G)={\rm mr}(G)-{\rm mr}(G-v)$ , the rank-spread of simple graph $ G$ at vertex $ v$ .
$ {\mathcal S}(G)$
The set of symmetric matrices of simple graph $ G$ , i.e.,
$ {\mathcal S}(G) = \{ A \in {S_n} :~{\mathcal G}(A) = G\}.$
$ {\mathcal S}^\ell(G)$
$ {\mathcal S}^\ell(G) = \{ B \in {S_n} : b_{ij}\ne 0$    if and only if $ ij\in E(G). \}$ Note $ G$ may have loops and the diagonal zero-nonzero pattern is restricted by $ G$ .
$ {\mathcal S}^F(G)$
$ {\mathcal S}^F(G) = \{ B : B$    is a symmetric $ n\times n$    matrix over $ F$    and $ {\mathcal G}(B) = G\}.$
$ {\mathcal S}^+(G)$
$ {\mathcal S}^+(G) = \{ B \in {\mathcal S}(G) : B$    is positive semidefinite$ \}.$ ($ G$ is simple.)
$ {\mathcal S}_\eta^F(G)$
$ {\mathcal S}_\eta^F(G) = \{ B\in{F^{n\times n}} : B$    is a symmetric matrix over $ $ F    , if $ ij\notin E(G)$   , then $ b_{ij}=0$    and $ \forall i, b_{ii}\ne 0\}.$ ($ G$ is simple and no requirement that the entry corresponding to an edge be nonzero.)
$ S_n$
The set of real symmetric $ n \times n$ matrices.
$ \sigma(A)$
The spectrum of $ A$ , i.e., the multiset of the $ n$ roots of the characteristic polynomial in the algebraic closure of $ F$ , where $ A\in{F^{n\times n}}$ .
$ \theta(G)$
Clique covering number of $ G$ . The smallest number of cliques in a clique covering of $ G$ .
$ X_T$
The matrix of indeterminates for a loop-tree $ T$ , i.e., 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.
$ \xi(G)$
The parameter $ \xi(G)$ of simple graph $ 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.



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