0
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

I assume that by a "radial graph" or "tree", you are referring to a directed tree in the sense defined here.

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.

The conclusion follows.

$\endgroup$
3
  • $\begingroup$ Thank you for the reply! You're right, the original statement didn't specify a directed graph, but I didn't think the source and sink nodes made sense if it is undirected, so yes, I believe it meant a polytree as you pointed out. $\endgroup$
    – user594147
    Aug 22, 2020 at 19:11
  • $\begingroup$ @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 $\endgroup$ Aug 22, 2020 at 19:41
  • $\begingroup$ Yes, I believe that assumption is valid. And I think only finite, simple graphs are considered. $\endgroup$
    – user594147
    Aug 23, 2020 at 2:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .