Il nocciolo della matrice di incidenza di un albero è $\emptyset$
In un articolo che sto cercando di leggere mi sono imbattuto in quanto segue:
Permettere $G=(V,E)$ sii un grafico diretto e lascia $A \in \mathbb{R}^{\vert V \vert \times \vert E \vert}$essere la sua matrice di incidenza nodo-bordo definita per componente come$$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. $$... Se il grafico è radiale (un albero), allora $\ker A = \emptyset$.
Ho difficoltà a visualizzare il motivo per cui l'ultima affermazione è vera: so che in modo equivalente dice che la matrice di incidenza del bordo del nodo di un albero è di rango pieno. Qualcuno potrebbe mostrarmi uno schizzo di prova per questo? Molte grazie!
EDIT : volevo dire$\ker A$ ha un kernel banale, non un kernel vuoto.
Risposte
Presumo che con un "grafo radiale" o "albero" ti riferisci a un albero diretto nel senso qui definito .
Detto questo, procediamo in modo induttivo. Il caso con$|V| = 2$è banale. Supporre che$|V| > 2$. Nota che ogni albero ha un nodo con grado$1$; permutare le righe di$A$ in modo che questo nodo (che etichettiamo come "$n$") corrisponde alla prima riga e permuta le colonne in modo che il bordo contenente questo nodo corrisponda alla prima colonna. Ne consegue che la matrice (permutata) $A$ può essere scritto nel modulo $$ A = \pmatrix{\pm1 & 0_{1\times (|E|-1)} \\ *& A'}, $$ dove $*$ denota alcuni $(|V|-1) \times 1$ vettore e $A'$ è la matrice di incidenza del grafico ottenuto cancellando $n$e il suo bordo associato. Perché$A$ è il blocco triangolare superiore, lo vediamo $A$ ha un banale kernel se e solo se $A'$ ha un kernel banale.
La conclusione segue.