12 ***Graphs and matrices***12.3 Spanning trees and Laplacian 12.5 Exercises

12.4 More properties of Adjacency Matrix

A subgraph $H$ of $G$ is said to be elementary if every component is a cycle or an edge. Denote by $c(H)$ and $c_{1}(H)$ the number of cycle components and edge components in a subgraph $H$ respectively.

Theorem 12.14.

detA=\sum_{\mbox{$H$ : $H$ is a sp. el. subgraph}}(-1)^{n-c_{1}(H)-c(H)}2^{c(H% )}.

Proof.

Denoting the symmetric group of permutations by $S_{n}$ , we have that

detA=\sum_{\pi\in S_{n}}(-1)^{n-|\pi|}A_{\pi};A_{\pi}:=\prod_{i=1}^{n}A_{i,\pi% (i)},

and $|\pi|$ is the number of cycles in the cycle decomposition of $\pi$ . Define the graph

H_{\pi}=\{(i,\pi(i)):i=1,\ldots,n\}=\{i\sim j:\pi(i)=j\}.

We shall sketch the proof steps here and refer to [Bapat 2010, Theorem 3.8] for the details.

Note that $A_{\pi}\in\{0,1\}$ . So, $A_{\pi}=1$ iff $i\overset{G}{\sim}\pi(i)$ for all $i$ iff $H_{\pi}$ is a elementary spanning subgraph. Since $\pi(i)\neq i$ , the spanning property of $H_{\pi}$ follows. $H_{\pi}$ is elementary because each cycle in $\pi$ corresponds to an edge component (if the cycle is a transposition) or a cycle component (if the cycle is not a transposition). One can verify that these are the only components. Thus, the argument also yields that the components in $H_{\pi}$ corresponding to the cycles in $\pi$ and since each cycle in $\pi$ corresponds to a component in $H_{\pi}$ , we have that $|\pi|=c(H)+c_{1}(H)$ .

Next note that for an elementary subgraph $H$

|\{\pi\in S_{n}:H_{\pi}=H\}|=2^{c(H)},

as reversing the orientation in a cycle of $\pi$ still yields that $H_{\pi}=H$ . Thus, the proof is complete by the determinantal formula above. ∎

Recall that the characteristic polynomial is $\phi_{\lambda}(A)=det(\lambda I-A)=\sum_{i=0}^{n}c_{i}\lambda^{n-i}$ . Note that $c_{0}=1$ . Further, we have that $c_{k}=(-1)^{k}\sum_{W\subset[n],|W|=k}det(A[W|W])$ . Observe that $A[W|W]=A(H_{W})$ where $H_{W}$ is the induced subgraph on $W$ . Thus by Theorem 12.14, we have that

det(A(H_{W}))=\sum_{\mbox{$H$ : $H$ el. sp. subgraph of $H_{W}$}}(-1)^{k-c_{1}% (H)-c(H)}2^{c(H)}

and so

c_{k}=(-1)^{k}\sum_{\mbox{$H$ : $H$ el. subgraph, $|V(H)|=k$ }}(-1)^{c_{1}(H)+% c(H)}2^{c(H)}.

Trivially, $c_{1}=0$ .

Suppose that there is $c_{3}=\ldots=c_{2k-1}=0$ . for some $k\geq 1$ .

If there is a cycle of length $3$ , then $c_{3}\neq 0$ as every elementary subgraph on $3$ vertices is a cycle. Since $c_{3}\neq 0$ , there is no cycle of length $3$ . If there is a cyle of length $5$ , then there is an induced cycle of length $3$ or $5$ but since there is no cycle of length $3$ (as $c_{3}=0$ ), we have only induced cycle of length $5$ . Thus all elementary subgraphs on $5$ vertices are induced $5$ -cycles and so $c_{5}\neq 0$ , a contradiction. Thus there are no induced $5$ -cycles.

Similarly, if there is a cycle of odd-length $l$ , there is an induced cycle of odd-length at most $l$ . But recursively applying the above argument, there are no induced odd-length cycles of length strictly smaller than $l$ and hence the induced cycle is of length $l$ . But this yields that $c_{l}\neq 0$ , a contradiction for $l\leq 2k-1$ . Thus if $c_{3}=\ldots=c_{2k-1}=0$ , there are no odd-cycles of length at most $2k-1$ .

Now, if $H$ is a elementary subgraph on $2k+1$ , then there exists an odd-cycle of length at most $(2k+1)$ . By the previous paragraph, we have that there are no odd-cycles of length at most $2k-1$ . Hence the odd-cyle is of length $2k+1$ and hence the number of induced $(2k+1)$ -cycles is $-\frac{1}{2}c_{2k+1}$ . Thus, we get the following theorem characterizing bi-partitness.

Theorem 12.15.

TFAE :

1.

$G$ is bipartite.
2.

$c_{2k+1}=0,k=0,1,\ldots$
3.

$A$ has symmetric spectrum i.e., if $\lambda$ is an e.v. of $A$ with multiplicity $k$ , so is $-\lambda$ .

Proof.

The obervations before the theorem prove that (i) is equivalent to (ii).

Assume (iii) holds. If the spectrum of $A$ is symmetric then $\phi_{A}(\lambda)=\prod_{i=1}^{m}(\lambda^{2}-a_{i}^{2})$ for some $a_{i}\in\mathbb{R}$ and thus $\phi_{A}(\lambda)$ has no odd coefficients.

Now assume (ii) holds. We need to show that $\phi_{A}(\lambda)=\lambda^{n-2k}\prod_{i=1}^{k}(\lambda^{2}-a_{i})$ . Then since eigenvalues of $A$ are real due to symmetry, $a_{i}\geq 0$ and so $\overset{-}{+}\sqrt{a_{i}},i=1,\ldots,k$ are the eigenvalues of $A$ . So, $A$ has a symmetric spectrum.

Assume that $0$ has multiplicity $n-l$ (possibly $l=n$ ). Then $\phi_{A}(\lambda)=\lambda^{n-l}g(\lambda)$ for some polynomial $g$ . By choice of $g$ , $0$ isn’t a zero of $g$ and so $g(0)\neq 0$ . Since $c_{l}=g(0)$ and $\phi_{A}(\lambda)$ has no odd coefficients, $l=2k$ for some $k\geq 0$ . Now, if $g$ has a non-zero coefficient for $\lambda^{2j+1}$ for some $j$ , then $\lambda^{n-2(k-j)+1}$ has a non-zero coefficient i.e., $c_{2(k-j)+1}\neq 0$ . This contradicts (ii) and so $g$ has non-zero coefficients only for $\lambda^{2j},j=0,\ldots,k$ . Thus $g$ is a polynomial in $\lambda^{2}$ and so $g(\lambda)=\prod_{i=1}^{k}(\lambda^{2}-a_{i})$ . Thus $\phi_{A}(\lambda)=\lambda^{n-2k}\prod_{i=1}^{k}(\lambda^{2}-a_{i})$ , as required. ∎

It is also possible to show that (i) implies (iii) directly as follows. Assume that $V=V_{1}\sqcup V_{2}$ is the bi-partition and also by adding isolated vertices if necessary, we can assume WLOG that $|V_{1}|=|V_{2}|=k$ with $n=2k$ . Note that adding isolated vertices preserves bi-partition and adds only zero eigenvalues. By relabelling vertices, we can write

A=\left[{\begin{array}[]{cc}0&B\\ B^{T}&0\\ \end{array}}\right]

for a $k\times k$ -matrix $B$ . Suppose $x$ is an eigenvector of $A$ with e.v. $\lambda$ , then we can write $x=(x^{1},x^{2})$ where $Bx^{2}=\lambda x^{1}$ and $B^{T}x^{1}=\lambda x^{2}$ . Thus, it can be easily verifies $\hat{x}=(x^{1},-x^{2})$ is an eigenvector of $B$ with eigenvalue $-\lambda$ . Furthermore if $x, y$ are linearly independent eigenvectors then so are $\hat{x},\hat{y}$ . Thus proving that if $\lambda$ is an eigenvalue of $A$ with multiplicity $k$ , then so is $-\lambda$ .