12 ***Graphs and matrices***12 ***Graphs and matrices***12.2 Laplacian Matrix

12.1 Incidence matrix and connectivity

Let $n=|V|,m=|E|$ . We shall assign an orientation to every edge $e\in E$ and call $\overrightarrow{E}$ this set of oriented edges. The orientation can be arbitrary.

Definition 12.1 (Incidence matrix ).

$\partial_{1}$ is a $n\times m$ matrix with $\partial_{1}(i,j)=\chi_{e_{j}}(v_{i})$ where $\chi_{e}(v)=\mathbf{1}[v=e^{+}]-\mathbf{1}[v=e^{-}]$ for $e=(e^{-},e^{+})\in\overrightarrow{E},v\in V.$

\bordermatrix{\leavevmode\nobreak\ \partial_{1}(i,j)&e_{1}&e_{2}&\ldots&e_{m}% \cr v_{1}&-1&0&\ldots&0\cr v_{2}&1&-1&\ldots&1\cr\vdots&\vdots&\vdots&\ddots&% \vdots\cr v_{n}&0&0&\ldots&-1}

We set $\partial_{0}=[1,\ldots,1]$ as a $1\times n$ -matrix.

Remark 12.2.

We consider the matrices as a real matrices and our matrix algebra will be with respect to $\mathbb{R}$ . One can consider any other field $\mathbb{F}$ instead of $\mathbb{R}$ as well.

Further set ${\mathcal{C}}_{j}=\{0\},j\leq-2,{\mathcal{C}}_{-1}=\mathbb{R}$ , ${\mathcal{C}}_{0}=\{\sum_{i=1}^{n}a_{i}v_{i}:a_{i}\in\mathbb{R}\},{\mathcal{C}% }_{1}==\{\sum_{i=1}^{m}a_{i}e_{i}:a_{i}\in\mathbb{R},e_{i}\in\overrightarrow{E% }\},$ where the sums are to be considered as a formal sum. Observe that ${\mathcal{C}}_{0},{\mathcal{C}}_{1}$ are $\mathbb{R}$ - vector spaces and note that ${\mathcal{C}}_{0}\cong\mathbb{R}^{V},{\mathcal{C}}_{1}\cong\mathbb{R}^{% \overrightarrow{E}}.$ The canonical basis for ${\mathcal{C}}_{0}$ is $\{v_{1},\ldots,v_{n}\}$ and for ${\mathcal{C}}_{1}$ is $\{e_{i}:e_{i}\in\overrightarrow{E}\}$ . Here, we think of $v_{1}=v_{1}+0v_{2}+\ldots+0v_{n},e_{1}=e_{1}+0e_{2}+\ldots+0e_{m}$ and similarly for other $v_{i}$ ’s and $e_{j}$ ’s.

We shall view $\partial_{0},\partial_{1}$ as linear maps in the following sense :

\partial_{0}:{\mathcal{C}}_{0}\to{\mathcal{C}}_{-1},\,\,\,z=\sum_{i=1}^{n}a_{i% }v_{i}\to\sum_{i}a_{i}=\partial_{0}[a_{1},\ldots,a_{n}]^{t},

\partial_{1}:{\mathcal{C}}_{1}\to{\mathcal{C}}_{0},\,\,\,z=\sum_{i=1}^{m}a_{i}% e_{i}\to\sum_{i}a_{i}(e_{i}^{+}-e_{i}^{-}).

Suppose we represent $\partial_{1}z=\sum_{i=1}^{n}b_{i}v_{i}$ then $(b_{1},\ldots,b_{n})^{t}=\partial_{1}[a_{1},\ldots,a_{m}]^{t}$ . Further if the columns of $\partial_{1}$ matrix are $Co_{1},\ldots,Co_{m}$ then $(b_{1},\ldots,b_{n})^{t}=\sum_{i=1}^{m}a_{i}Co_{i}$ .

Assume that $G\neq\emptyset$ . We set ${\mathcal{B}}_{i}=Im(\partial_{i+1}),{\mathcal{Z}}_{i}=Ker(\partial_{i}).$

Remark 12.3.

The above abstraction of representing ${\mathcal{C}}_{0},{\mathcal{C}}_{1}$ as formal sums seems a little unnecessary as we could have also represented ${\mathcal{C}}_{0},{\mathcal{C}}_{1}$ as functions from $V\to\mathbb{R}$ and $\overrightarrow{E}\to\mathbb{R}$ respectively. However, this representation will be notationally convenient and is borrowed from algebraic topology where one considers richer structures giving rise to further vector spaces such as ${\mathcal{C}}_{2},{\mathcal{C}}_{3},\ldots$ . Further, if we choose $\mathbb{Z}$ -coefficients instead of $\mathbb{R}$ -coefficients, ${\mathcal{C}}_{0},{\mathcal{C}}_{1}$ are modules and not vector spaces. Thus, the above representation allows us to carry over similar algebraic operations even in such a case. As an exercise, the algebraically inclined students can try to repeat the proofs with $\mathbb{Z}$ -coefficients. See [Edelsbrunner 2010] for an accessible introduction to algebraic topology and [Munkres 2018] for more details.

Trivially, we have that ${\mathcal{B}}_{-1}={\mathcal{C}}_{-1}=\mathbb{R}$ . Thus by the fundamental theorem of algebra, we have that $r({\mathcal{Z}}_{0})=n-1$ where by $r(.)$ we denote the rank of matrix/dimension of a vector space. It is easy to see that $v_{i}-v_{j}\in{\mathcal{Z}}_{0},\forall i\neq j.$ Further, we have that $v_{1}-v_{i},i=2,\ldots,n$ are linearly independent and hence form a basis for ${\mathcal{Z}}_{0}$ . Here linear independence means that if $\sum_{j=2}^{n}a_{j}(v_{j}-v_{0})=0$ then $a_{j}=0,j=2,\ldots,n$ . Observe that for $z=\sum_{i=1}^{m}b_{i}e_{i}$ ,

\partial_{0}\partial_{1}z=\partial_{0}(\sum_{i=1}^{m}b_{i}(e_{i}^{+}-e_{i}^{-}% ))=\sum_{i=1}^{m}b_{i}(\partial_{0}e_{i}^{+}-\partial_{0}e_{i}^{-})=0,

where in the first and third equalities we have used the definition of $\partial_{1},\partial_{0}$ respectively and in the second equality, the linearity of $\partial_{0}$ . Thus, we have that $\partial_{0}\partial_{1}=0$ and in other words ${\mathcal{B}}_{0}\subset{\mathcal{Z}}_{0}$ . The same can also be deduced by noting that as matrix product $\partial_{0}\partial_{1}$ is nothing but sum of rows of $\partial_{1}$ and hence $0$ .

Now, if we can understand $r({\mathcal{B}}_{0})$ then we can understand all the ranks involved. Observe that ${\mathcal{B}}_{0}$ is nothing but the column space of of $\partial_{1}$ i.e., denoting the columns of the matrix $\partial_{1}$ by $Co_{1},\ldots,Co_{m}$ , we have that

{\mathcal{B}}_{0}\cong\{\sum_{i=1}^{m}a_{i}Co_{i}:a_{i}\in\mathbb{R}\}.

Hence $r({\mathcal{B}}_{0})$ is nothing but the maximum number of linearly independent column vectors.

Suppose $e_{1},\ldots,e_{k}$ denote the edges corresponding to the linearly independent columns. Assume that the subgraph $H=e_{1}\cup\ldots\cup e_{k}$ is connected. Let $V(H)=\{v_{1},\ldots,v_{l}\}$ . Consider the incidence matrix restricted to $\{v_{1},\ldots,v_{l}\}\times\{e_{1},\ldots,e_{k}\}$ . Call it $\partial_{1}^{\prime}$ . Since the non-trivial entries of $e_{i}$ ’s are on $v_{1},\ldots,v_{l}$ , the columns of $\partial_{1}^{\prime}$ are also linearly independent and so the column rank of $\partial_{1}^{\prime}=k$ and since $H$ is connected, $k\geq l-1$ . Let $R_{1},\ldots,R_{l}$ be the rows of the matrix $\partial_{1}^{\prime}$ . Since every column has exactly one $+1$ and one $-1$ , we have that $\sum_{i}R_{i}=0$ and thus the row rank of $\partial_{1}^{\prime}\leq l-1$ . Since the row rank $=$ column rank, we have that $k=l-1$ i.e., $H$ is a tree.

Thus, we have proved that if $e_{1},\ldots,e_{k}$ denote the edges corresponding to the linearly independent columns, then every component of $e_{1}\cup\ldots\cup e_{k}$ is a tree i.e., $e_{1}\cup\ldots\cup e_{k}$ is a forest or acyclic subgraph. We show the converse and determine the basis for ${\mathcal{B}}_{0}$ .

Proposition 12.4.

Let $Co_{i}$ be the columns corresponding to $e_{i}$ in $\partial_{1}$ . Then $e_{1}\cup\ldots\cup e_{k}$ is acyclic iff $Co_{1},\ldots,Co_{k}$ are linearly independent.

Proof.

We have shown the ‘if’ part. We will show the ‘only if’ part. Suppose that $H=e_{1}\cup\ldots\cup e_{k}$ is acyclic. We will show that $Co_{1},\ldots,Co_{k}$ are linearly independent by induction. The conclusion holds trivially for $k=1$ . Suppose it holds for all $l<k$ . WLOG assume that $e_{k}$ is a leaf edge with $deg_{H}(e_{k}^{+})=1$ . Thus $e_{k}^{+}\notin e_{1}\cup\ldots\cup e_{k-1}$ . If $\sum_{i=1}^{k}a_{i}Co_{i}=0$ then since $e_{k}^{+}\in e_{k}$ only, we have that $a_{k}=0$ . Thus $\sum_{i=1}^{k-1}a_{i}Co_{i}=0$ and since $e_{1}\cup\ldots\cup e_{k-1}$ are acyclic and hence by induction hypothesis, we have that $Co_{1},\ldots,Co_{k-1}$ are linearly independent i.e., $a_{i}=0,1\leq i\leq k$ . ∎

From the previous proposition, the following theorem follows easily.

Theorem 12.5.

1.

Let $e_{1}\cup\ldots\cup e_{k}$ be the (maximal) spanning forest in $G$ . Then

${\mathcal{B}}_{0}=\{\sum_{i=1}^{k}a_{i}\partial_{1}(e_{i}):a_{i}\in\mathbb{R}\}.$
2.

$r({\mathcal{B}}_{0})=n-\beta_{0}(G),r({\mathcal{Z}}_{0})-r({\mathcal{B}}_{0})=% \beta_{0}(G)-1$ .
3.

$G$ is connected iff ${\mathcal{B}}_{0}={\mathcal{Z}}_{0}$ .

By the rank-nullity theorem, we have that $r({\mathcal{Z}}_{1})=m-n+\beta_{0}(G)$ which is nothing but the number of excess edges i.e., edges added after forming a (maximal) spanning forest. Let $e_{1}e_{2}\ldots,e_{k}$ form a cycle, denoting the reversal of an edge by $\widehat{e}$ , set

z_{C}:=\sum_{i=1}^{k}\mathbf{1}[e_{i}\in\overrightarrow{E}]e_{i}-\mathbf{1}[% \widehat{e_{i}}\in\overrightarrow{E}]\widehat{e_{i}}.

Thus, it is easy to verify that $\partial_{1}z_{C}=0$ i.e., since $\partial_{1}e_{i}=-\partial_{1}\widehat{e_{i}}=e_{i}^{+}-e_{i}^{-}$ ,

\partial_{1}z_{C}=\sum_{i=1}^{k}e_{i}^{+}-e_{i}^{-}=0,

where the last equality is because $e_{1}\ldots e_{k}$ is a cycle. Hence $z_{c}\in{\mathcal{Z}}_{1}$ . We can extend this further.

Exercise(A) 12.6.

Let $F$ be a maximal spanning forest in $G$ and $e_{1},\ldots,e_{l}\in\overrightarrow{E}-E(F)$ where $l=m-n+\beta_{0}(G)$ . Let $C_{1},\ldots,C_{l}$ be the cycles in $F\cup e_{1},\ldots,F\cup e_{l}$ respectively. Then $z_{C_{1}},\ldots,z_{C_{l}}$ form a basis for ${\mathcal{Z}}_{1}$ .

Remark 12.7.

Another challenging exercise : In terms of matrices, the linear transformation $\partial_{0},\partial_{1}$ represent right multiplication i.e., we have that

\{0\}\stackrel{{\scriptstyle\partial_{2}}}{{\to}}{\mathcal{C}}_{1}\stackrel{{% \scriptstyle\partial_{1}}}{{\to}}{\mathcal{C}}_{0}\stackrel{{\scriptstyle% \partial_{0}}}{{\to}}\mathbb{R}\stackrel{{\scriptstyle\partial_{-1}}}{{\to}}\{% 0\}.

But we could have considered left multiplication and in which case we will have linear transformations $\delta_{i}$ ’s as follows :

\{0\}\stackrel{{\scriptstyle\delta_{2}}}{{\leftarrow}}{\mathcal{C}}_{1}% \stackrel{{\scriptstyle\delta_{1}}}{{\leftarrow}}{\mathcal{C}}_{0}\stackrel{{% \scriptstyle\delta_{0}}}{{\leftarrow}}\mathbb{R}\stackrel{{\scriptstyle\delta_% {-1}}}{{\leftarrow}}\{0\}.

Can you compute the ranks and characterize connectivity as we did above with $\partial_{0},\partial_{1}$ ’s ?

See [Bapat 2010, Chapter 2] for more on incidence matrices.

We shall define the $0-1$ incidence matrix $M$ as follows : $M(i,j)=1[v_{i}\in e_{j}]$ . In other words, $M$ is the unoriented incidence matrix. The following result explains the importance of considering orientations in the incidence matrix.

Theorem 12.8.

Let $G$ be a connected graph. Then $r(M)=n-1$ if $G$ is bi-partite and $r(M)=n$ otherwise.

See [Bapat 2010, Lemma 2.17] for a proof.