The minimum rank of matrices and the equivalence class graph (Q2459958): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q1116414 |
||
Property / reviewed by | |||
Property / reviewed by: Juan Ramón Torregrosa Sánchez / rank | |||
Revision as of 13:33, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The minimum rank of matrices and the equivalence class graph |
scientific article |
Statements
The minimum rank of matrices and the equivalence class graph (English)
0 references
9 November 2007
0 references
The paper deals with the minimum rank of matrices associated with an undirected connected graph. For a given undirected connected graph \(G=(V(G),E(G))\), the minimum rank of \(G\), \(hmr(G)\), (the real symmetric minimum rank of \(G\), \(mr(G)\)) is defined to be the smallest possible rank over all hermitian (real symmetric) matrices associated with \(G\), that is, matrices \(A\) whose \((i,j)\)th entry is non-zero if and only if \(i \neq j\) and \(\{i,j\}\) is an edge in \(G\). For each vertex \(x\) in \(G\), \(N(x)\) is the set of all neighbors of \(x\). Let \(R\) be the equivalence relation on \(V(G)\) such that \[ \forall x,y \in V(G) \;\;xRy \Leftrightarrow N(x)=N(y). \] Let \(G=(V(G),E(G))\) be a graph and \(X_1, \dots, X_p\) be the equivalence classes for the relation \(R\). The equivalence class graph of \(G\) is defined as the graph \({\mathcal G}=(V({\mathcal G}),E({\mathcal G}))\) where \(V({\mathcal G})=\{X_1,\dots,X_p\}\) and \(\{X_i,X_j\}\in E(\mathcal{G})\) if, and only if, there exist \(x \in X_i\) and \(y \in X_j\) such that \(\{ x,y\}\) is an edge in \(G\). The authors study classes of undirected connected graphs \(G=(V(G),E(G))\), such that the minimum rank of \(G\) is equal to the number of equivalence classes for the relation \(R\) on \(V(G)\), \(| V(G)/R| \). Specifically, they show the following main result: Let \(G=(V(G),E(G))\) be a graph such that the equivalence class graph \({\mathcal G}\) is the path \(X_1,\dots,X_p\). Then, \[ hmr(G)=mr(G)=| V(G)/R| =p \] if, and only if, \(p\) is even and there do not exist \(i,j\) with \(1 \leq i<j \leq p\) such that \(i\) is odd, \(j\) is even and \(| X_i| =| X_j| =1\). When this is not the case \[ hmr(G)=mr(G)=p-1. \]
0 references
Hermitian matrices
0 references
undirected connected graph
0 references