木の接続行列のカーネルは $\emptyset$
私が読み込もうとしている論文で、次のことに出くわしました。
しましょう $G=(V,E)$ 有向グラフになり、 $A \in \mathbb{R}^{\vert V \vert \times \vert E \vert}$そのことノードエッジ入射マトリックスとして成分ごと定義$$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. $$...グラフが放射状（ツリー）の場合、 $\ker A = \emptyset$。
最後のステートメントが真である理由を視覚化するのに苦労しています。同等に、ツリーのノードエッジ接続行列がフルランクであると言っていることを知っています。誰かが私にこれの証明スケッチを見せてもらえますか？どうもありがとう！
編集：私は意味しました$\ker A$ 空のカーネルではなく、些細なカーネルがあります。
回答
「レーダーグラフ」または「ツリー」とは、ここで定義されている意味で有向ツリーを指していると思います。
そうは言っても、私たちは帰納的に進みます。の場合$|V| = 2$些細なことです。仮定$|V| > 2$。すべてのツリーには次数のノードがあることに注意してください$1$; の行を並べ替えます$A$ そのため、このノード（「$n$"）は最初の行に対応し、このノードを含むエッジが最初の列に対応するように列を並べ替えます。したがって、（置換された）行列が続きます。 $A$ 次の形式で書くことができます $$ A = \pmatrix{\pm1 & 0_{1\times (|E|-1)} \\ *& A'}, $$ どこ $*$ いくつかを示します $(|V|-1) \times 1$ ベクトルと $A'$ 削除して得られたグラフの接続行列です $n$およびそれに関連するエッジ。なぜなら$A$ ブロック上三角であることがわかります $A$ 些細なカーネルを持っているのは、 $A'$ 些細なカーネルがあります。
結論は次のとおりです。