Kernel of the incidence matrix of a tree is $\emptyset$

I came upon the following in a paper I'm trying to read:

Let $$G=(V,E)$$ be a directed graph and let $$A \in \mathbb{R}^{\vert V \vert \times \vert E \vert}$$ be its node-edge incidence matrix defined component-wise as $$A_{ke} = \left\{ \begin{array}{cl} 1 & \text{if node } k \text{ is the source node of edge }e\\ -1 & \text{if node } k \text{ is the sink node of edge }e\\ 0 & \text{otherwise} \end{array} \right.$$... If the graph is radial (a tree), then $$\ker A = \emptyset$$.

I'm having a hard time trying to visualize why the last statement is true -- I know equivalently it says the node-edge incidence matrix of a tree is full rank. Could anyone show me a proof sketch for this? Thanks a lot!

EDIT: I meant $$\ker A$$ has a trivial kernel, not an empty kernel.

• It is never true that the kernel of a matrix is $\emptyset$. The kernel will always at least contain the zero vector Aug 20, 2020 at 6:28
• What do you mean when you say that a directed graph is a tree? Aug 20, 2020 at 6:30

With that said, we proceed inductively. The case with $$|V| = 2$$ is trivial. Suppose that $$|V| > 2$$. Note that every tree has a node with degree $$1$$; permute the rows of $$A$$ so that this node (which we label as "$$n$$") corresponds to the first row, and permute the columns so that the edge containing this node corresponds to the first column. It follows that the (permuted) matrix $$A$$ can be written in the form $$A = \pmatrix{\pm1 & 0_{1\times (|E|-1)} \\ *& A'},$$ where $$*$$ denotes some $$(|V|-1) \times 1$$ vector and $$A'$$ is the incidence matrix of the graph obtained by deleting $$n$$ and its associated edge. Because $$A$$ is block upper-triangular, we see that $$A$$ has a trivial kernel if and only if $$A'$$ has a trivial kernel.
• @user The important thing from my perspective was that each edge has only one direction. That is, we never have an edge both from $v_1$ to $v_2$ and from $v_2$ to $v_1$. This was not clear from the problem statement Aug 22, 2020 at 19:41