Grinberg-Introduction-Graph-Theory · Problem 3.6

Multigraphs

Mathematics — Graph Theory · multigraph-incidence-matrix-rank

Problem

Let FF be any field. (For instance, FF can be Q\mathbb{Q} or R\mathbb{R} or C\mathbb{C}.) Let G=(V,E,φ)G = (V, E, \varphi) be a multigraph, where V={1,2,…,n}V = \{1, 2, \ldots, n\} for some n∈Nn \in \mathbb{N}. For each edge e∈Ee \in E, we construct a column vector χe∈Fn\chi_e \in F^n (that is, a column vector with nn entries) as follows: • If ee is a loop, then we let χe\chi_e be the zero vector. • Otherwise, we let uu and vv be the two endpoints of ee, and we let χe\chi_e be the column vector that has a 11 in its uu-th position, a −1-1 in its vv-th position, and 00s in all other positions. (This depends on which endpoint we call uu and which endpoint we call vv, but we just make some choice and stick with it. The result will be true no matter how we choose.) Let MM be the n×∣E∣n \times |E|-matrix over FF whose columns are the column vectors χe\chi_e for all e∈Ee \in E (we order them in some way; the exact order doesn't matter). Prove that rank⁡M=∣V∣−conn⁡G,\operatorname{rank} M = |V| - \operatorname{conn} G, where conn⁡G\operatorname{conn} G denotes the number of components of GG. [Remark: The claim of the exercise can be restated as follows: The span of the vectors χe\chi_e for all e∈Ee \in E has dimension ∣V∣−conn⁡G|V| - \operatorname{conn} G. Topologists will recognize the matrix MM as (a matrix that represents) the boundary operator ∂:C1(G)→C0(G)\partial : C_1(G) \to C_0(G), where GG is viewed as a CW-complex.]

Related theory

Browse the problem library