Il nocciolo della matrice di incidenza di un albero è $\emptyset$

Aug 20 2020

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

2 BenGrossmann Aug 20 2020 at 14:10

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.