Rank of the incidence matrix of a directed graph. Can someone please help me prove that the rank of the incidence matrix of a 'simple' directed graph with $n$ nodes and $m$ edges is $n-1$? The nodes are labelled $\{1,2,...,n\}$ and the edges are labelled $\{1,2,...,m\}$.
The element $a_{ij}$ of the incidence matrix is determined in the following way,
$a_{ij}=0$ if the node $i$ is not on edge $j$.
$a_{ij}=-1$ if the edge $j$ ends on node $i$.
$a_{ij}=1$ if the edge $j$ starts on node $i$.
 A: Let $(G,E)$ refer to our simple, directed graph. Let $(G',E')$ denote the corresponding undirected graph.
One proof is as follows: begin with the case where $G'$ is a tree, which can be handled in the manner described in this post.
Now, consider the case where $G'$ is any connected graph. We use the following facts:

*

*Every undirected connected graph has a spanning tree,

*Every tree on $n$ nodes  has $n-1$ edges,

*Relabeling the nodes/edges (or equivalently, permuting the rows/columns of the incidence matrix) does not change the rank of the incidence matrix.

Relabel the edges of the graph so that the edges $1,\dots,n-1$ are the edges of our spanning tree. The first $n-1$ columns of the matrix form the incidence matrix of a tree, so these are linearly independent. It follows that the span of these $n-1$ columns is given by the subspace $S \subset \Bbb R^n$, defined by
$$
S = \{(x_1,\dots,x_n) : x_1 + \cdots + x_n = 0\}.
$$
Indeed, it suffices to observe that the span of these colums is a subspace of $S$ and that the dimension of the span is equal to that of $S$. Now, we see that the remaining columns of the incidence matrix are each elements of $S$. Thus, the column span of the entire incidence matrix of $G$ is $S$, which means that this incidence matrix has rank $n-1$.
Finally, consider the case of an arbitrary graph $G$. Let $G_1',\dots,G_k'$ denote the connected components of $G'$. Relabel the vertices so that the vertices of $G_1'$ come first, followed by the vertices of $G_2'$, and so forth. Similarly, relabel the edges so that the edges corresponding to $G_1'$ come first, followed by the edges of $G_2'$, and so forth.
I claim that the incidence matrix of $(G,E)$ (under this relabeling) has the block-diagonal form
$$
B = \pmatrix{B_1 \\ & B_2 \\ && \ddots \\ &&& B_k},
$$
where $B_j$ is the incidence matrix of $G_j$. Conclude that the rank of $B$ is the sum of the ranks of $B_1,\dots,B_k$, and is therefore given by $n - k$, where $k$ is the total number of connected components.
