El núcleo de la matriz de incidencia de un árbol es $\emptyset$

Question

Encontré lo siguiente en un documento que estoy tratando de leer:

Dejar $G=(V,E)$ ser un grafo dirigido y dejar $A \in \mathbb{R}^{\vert V \vert \times \vert E \vert}$ser su matriz de incidencia de borde de nodo definida por componentes como$$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. $$... Si el gráfico es radial (un árbol), entonces $\ker A = \emptyset$.

Me cuesta mucho tratar de visualizar por qué la última afirmación es verdadera; sé que, de manera equivalente, dice que la matriz de incidencia del borde del nodo de un árbol tiene rango completo. ¿Alguien podría mostrarme un boceto de prueba para esto? ¡Muchas gracias!

EDITAR : quise decir$\ker A$ tiene un kernel trivial, no un kernel vacío.

Answer 1

Supongo que por un "gráfico radial" o "árbol", se está refiriendo a un árbol dirigido en el sentido definido aquí .

Dicho esto, procedemos inductivamente. El caso con$|V| = 2$es trivial. Suponer que$|V| > 2$. Tenga en cuenta que cada árbol tiene un nodo con grado$1$; permutar las filas de$A$ de modo que este nodo (que etiquetamos como "$n$") corresponde a la primera fila, y permuta las columnas de modo que el borde que contiene este nodo corresponda a la primera columna. Se sigue que la matriz (permutada) $A$ se puede escribir en la forma $$ A = \pmatrix{\pm1 & 0_{1\times (|E|-1)} \\ *& A'}, $$ dónde $*$ denota algunos $(|V|-1) \times 1$ vector y $A'$ es la matriz de incidencia del gráfico que se obtiene al eliminar $n$y su borde asociado. Porque$A$ es un bloque triangular superior, vemos que $A$ tiene un núcleo trivial si y solo si $A'$ tiene un núcleo trivial.

La conclusión sigue.