Do incidence matrices fully characterize a graph? In other words, is it sufficient to retain the incidence matrix of a graph in order to know everything about it, namely, its connectivity (edge set), vertex set and underlying topology? As opposed to e.g. the degree matrix, which does not contain complete information on how the nodes are wired or directed in case of a digraph.
Incidence matrix of a graph
algebraic-graph-theorygraph theorylinear algebramatrices
Related Solutions
First off, the kernel of a matrix is never empty as it always contains the zero vector. If the kernel of the matrix $M$ consists only of the zero vector, then it is common to write (with a slight abuse of notation) $\ker(M) = 0$; you should not confuse this with $\ker(M) = \varnothing$.
Second, there are two typos in the proof. Taken from the errata page of the book:
In the first line of the proof we should have "null space of $D^T$". In the second sentence of the proof, on the next line, we should have "$z^TD=0$".
So to address your confusion: if the underlying graph of the graph is a tree, then indeed $\ker(D) = 0$, but $\ker(D^T) = 1$. Since $D$ is an $n \times (n-1)$ matrix, both observations are equivalent to $rank(D) = n-1$.
For the general case, note the following simple principle. For a vector $x$, write $\text{supp}(x) = \{i \mid x_i \neq 0\}$.
1. Proposition. Let $A$ be a normal matrix, and let $x$ and $y$ be non-negative eigenvectors corresponding to different eigenvalues of $A$. Then $\text{supp}(x) \cap \text{supp}(y) = \varnothing$.
Proof. By non-negativity we have $x_iy_i \geq 0$ for all $i$. Furthermore, since $A$ is normal, the eigenspaces of $A$ are pairwise orthogonal. Therefore we have $$ 0 = \langle x,y\rangle = \sum_i x_iy_i \geq 0, $$ so we must have equality throughout. Thus, for every $i$ we have $x_iy_i = 0$, hence $i \notin \text{supp}(x) \cap \text{supp}(y)$. $\quad\Box$
In particular, if $A$ has a strictly positive eigenvector with eigenvalue $\lambda$, then $A$ does not have a non-negative eigenvector with eigenvalue $\mu \neq \lambda$. Conversely, if the $\lambda$-eigenspace of $A$ contains a non-negative eigenvector but not a strictly positive vector, then $A$ does not have a strictly positive eigenvector.
For the remainder of this answer, I will focus on your more specific question.
First we look at eigenvectors with eigenvalue $0$. Here we show that a non-negative eigenvector exists if and only if $G$ has a directed cycle, and a similar statement for strictly positive eigenvectors (see Proposition 3 below). For this we use the following lemma.
2. Lemma. For every real matrix $A$, one has $\ker(A^TA) = \ker(A)$.
Proof. Clearly $\ker(A) \subseteq \ker(A^TA)$. Conversely, suppose that $A^TAx = 0$. Then $\lVert Ax \rVert^2 = x^TA^TAx = 0$, hence $Ax = 0$. $\quad\Box$
3. Proposition. Let $G$ be a directed graph. Then:
There is a non-negative vector in $\ker(BVB^T) \setminus \{0\}$ if and only if $G$ has a directed cycle.
There is a strictly positive vector in $\ker(BVB^T)$ if and only if every arc of $G$ belongs to a directed cycle.
Proof. Let $V^{1/2}$ denote the unique positive semidefinite square root of $V$. (Of course, this is just the entry-wise square root, since $V$ is diagonal.) It follows from Lemma 2 that $$ \ker(BVB^T) = \ker(BV^{1/2}V^{1/2}B^T) = \ker\big((V^{1/2}B^T)^TV^{1/2}B^T\big) = \ker(V^{1/2}B^T). $$ Since the diagonal entries of $V^{1/2}$ are positive, $V^{1/2}$ is invertible, so we have $\ker(V^{1/2}B^T) = \ker(B^T)$. Therefore $\ker(BVB^T) = \ker(B^T)$ is the flow space (or circulation space) of $G$. Now the statements of the proposition follow easily:
If $G$ has a directed cycle $C$, then the unsigned characteristic vector $\mathbb{1}_C$ of $C$ is a non-negative vector in $\ker(B^T)$. Conversely, if $G$ is acyclic, then every non-zero flow must traverse at least one arc in the negative direction, so now $\ker(B^T)$ does not contain a non-negative vector (apart from $0$).
If every arc belongs to a directed cycle, then the sum of the characteristic vectors of all directed cycles yields a strictly positive vector in $\ker(B^T)$. Conversely, if the arc $(v,w)$ does not lie on a directed cycle, then every circulation which is non-zero on $(v,w)$ must go in the negative direction on some other arc, so there is no strictly positive vector in $\ker(B^T)$. $\quad\Box$
4. Corollary. Let $G$ be a directed graph. If $G$ has a directed cycle, but also has an arc which is not contained in a directed cycle, then $BVB^T$ has no strictly positive eigenvectors.
Proof. By Proposition 3, the $0$-eigenspace contains a non-negative eigenvector, but not a strictly positive vector. Therefore it follows from Proposition 1 that there is no strictly positive eigenvector. $\quad\Box$
Second, we look at eigenvectors with non-zero eigenvalue. Here things are the other way around: we show that a strictly positive eigenvector can only exist if $G$ is acyclic (see Proposition 7 below). For this we use the following lemma.
5. Lemma. Let $A$ be an $m \times n$ matrix, let $B$ be an $n \times m$ matrix, and let $\lambda \neq 0$. Then the map $y \mapsto By$ defines an isomorphism from the $\lambda$-eigenspace of $AB$ to the $\lambda$-eigenspace of $BA$.
Proof. See this answer. $\quad\Box$
6. Corollary. Every eigenvector $x$ of $BVB^T$ with non-zero eigenvalue is of the form $x = By$ for some eigenvector $y$ of $VB^TB$.
Proof. Apply Lemma 5 with $A = VB^T$. $\quad\Box$
7. Proposition. Let $G$ be a directed graph. If $x$ is a non-negative eigenvector of $BVB^T$ with eigenvalue $\lambda \neq 0$, then $x_a = 0$ for every arc which belongs to a directed cycle. In particular, if $BVB^T$ has a strictly positive eigenvector with non-zero eigenvalue, then $G$ is acyclic.
First proof. By Corollary 6, we may write $x = By$ for some $y \in \mathbb{R}^{V(G)}$. For every arc $a = (v,w)$ we have $y(w) - y(v) = x(a) \geq 0$, so $y(v) \leq y(w)$. Therefore if $C$ is a directed cycle, then all arcs in $C$ must have the same $y$-value, so it follows that $x(a) = 0$ for all such arcs. $\quad\Box$
Second proof. For every directed cycle $C$, the characteristic vector $\mathbb{1}_C$ of $C$ is a non-negative eigenvector with eigenvalue $0$, by Proposition 3. Hence it follows from Proposition 1 that $\text{supp}(x) \cap \text{supp}(\mathbb{1}_C) = \varnothing$, so $x(a) = 0$ whenever $a$ belongs to a directed cycle. $\quad\Box$
Next, we make a slight change of perspective. Henceforth, we let $G$ be an undirected graph with Laplacian $\Delta$, and we will look at all possible orientations of the edges of $G$.
8. Definition. Given an undirected graph $G$ and an orientation $o$ of the edges of $G$, we say that a vector $y \in \mathbb{R}^{V(G)}$ is:
weakly compatible with $o$ if $y(v) \leq y(w)$ for every edge oriented from $v$ to $w$;
strongly compatible with $o$ if $y(v) < y(w)$ for every edge oriented from $v$ to $w$.
9. Proposition. Let $G$ be an undirected graph with Laplacian $\Delta$, let $o$ be an orientation of the edges of $G$, and let $B$ be the incidence matrix with respect to the orientation $o$. Then $BVB^T$ has a non-negative (resp. strictly positive) eigenvector with eigenvalue $\lambda \neq 0$ if and only if $V\Delta$ has an eigenvector with eigenvalue $\lambda$ which is weakly compatible (resp. strongly compatible) with the orientation $o$.
Proof. Recall that $\Delta = B^TB$, regardless of the orientation. Hence it follows from Lemma 5 (with $A = VB^T$) that the map $y \mapsto By$ defines an isomorphism from the $\lambda$-eigenspace of $V\Delta = VB^TB$ to the $\lambda$-eigenspace of $BVB^T$. To complete the proof, note that $By$ is non-negative (resp. strictly positive) if and only if $y$ is weakly compatible (resp. strongly compatible) with $o$. $\quad\Box$
If the orientation $o$ is fixed, then it is unclear whether or not there exists a compatible eigenvector of $V\Delta$. However, note that $V\Delta$ only depends on the undirected graph, and not on the orientation. If we choose a fixed eigenvector of $V\Delta$, then it is easy to see which orientations are compatible.
The following heuristic argument suggests that $BVB^T$ does not have a non-negative eigenvector for “most” orientations of $G$. If $V\Delta$ is sufficiently generic (specifically, if it has has $n$ different eigenvalues and if each eigenvector has $n$ different entries), then $G$ has at most $2n$ different acyclic orientations which admit a compatible eigenvector of $V\Delta$. (An eigenvector $y$ with $n$ different entries admits exactly one compatible orientation, and $-y$ is compatible with the reverse orientation. Different eigenvectors might give rise to the same orientation.) The following result of Linial shows that the total number of acyclic orientations is much larger than $2n$:
10. Theorem (Linial). Let $G$ be an undirected graph with $n$ vertices and $m$ edges, and write $m = \binom{k}{2} + \ell$ with $k > \ell \geq 0$. Then the number of acyclic orientations of $G$ is at least $k!(\ell + 1)$.
Proof. Combine Theorem 4 and Theorem 5 from [Lin86].
This suggests that “most” directed acyclic graphs do not have a non-negative eigenvector of $BVB^T$. (This argument is heuristic in the sense that it relies on genericity of $V\Delta$. If some eigenspace of $V\Delta$ has dimension $\geq 2$, then there are infinitely many eigenvectors, so there might be many more acyclic orientations which are compatible with some eigenvector of $V\Delta$.)
References.
[Lin86]: N. Linial, Legal colorings of graphs, Combinatorica 6(1) (1986) 49–54.
Best Answer
If you are talking about a simple, undirected graph, then the answer is "yes." From the incidence matrix we can easily construct the adjacency matrix, which clearly fully determines the graph. If graph is directed, the incidence matrix also determines it, since the signs give the orientation of the edges. This works even if there are parallel edges.
If the graph has loops, then the incidence matrix does not determine it. We can tell that an edge is a loop, since the corresponding column is all $0$'s, but we can tell which vertex it is incident on. It would be easy to fix this, by just making the relevant entry $1$ instead of $0$ say, but this is not the usual way of defining the incidence matrix, so far as I am aware.