圖的鄰接矩陣/關聯矩陣的秩有什麼直觀的幾何意義嗎？

12-31

或者說有什麼意義？或者說樹或二分圖或其他特殊的圖的意義

我不確定題主是不是希望在graph和linear algebra之間構建一些聯繫，如果是的話，那麼 Spectral graph theory 恰好是這麼一個試圖使用linear algebra的工具來解決graph中的一些問題的領域。

In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix. -from Wikipedia

--------------------------------------------------------------------

回到原問題，通常我們不會直接考慮graph的鄰接矩陣，通常是考慮其Laplacian matrix.

為方便理解以及形式的優美，在這裡我們給出關於 $d- ext{regular}$ graph的結論，但實際上對於每個頂點度數不同的圖，仍有類似的結論成立.

記一個 $d- ext{regular}$ 的無向圖為 $G(V,E)$ , 則其(Normalized) Laplacian matrix可以定義為 $L:= I-frac{1}{d}A$ , 其中 $A$ 是其鄰接矩陣(Adjacent matrix).

記 $L$ 的實值特徵值為 $lambda_1 leq lambda_2 leq cdots leq lambda_n$ , 則有下面的結論成立：

$1. lambda_1=0 ext{ and } lambda_n leq 2.$ . $2. lambda_k=0 ext{ if and only if } G ext{ has at least } k ext{ connected components.}$

注意到，上述性質告訴我們

Laplacian矩陣的特徵值中0的代數重數恰好是 $m{G}$ 中連通分量的個數。

--------------------------------------------------------------------

上述結論的證明相對比較困難，需要一點關於 Rayleigh quotient的內容，將graph的性質和一個矩陣的代數結構進行聯繫，非常漂亮。這裡就不給出了，感興趣可以參考最後的參考文獻，只給一個例子作為直觀上的感受：

考慮如下的具有兩個連通分量的無向圖 $G(V,E)$

容易寫出其Adjacent matrix和Laplacian matrix分別為

對應的特徵值為 $[0, 0, 1, 1, 1.5, 1.5, 2]$

--------------------------------------------------------------------

Reference:

CS294: Graph Partitioning, Expanders and Spectral Methods

考慮一個圖，找一個頂點V0。新加一個頂點V1，只與V0相連。此後每次新加一個頂點Vk，只與Vk-1相連。那麼鄰接矩陣的秩在第一步後每次加一。

再考慮一個圖，其他如上，只是每次新加的頂點Vk只與V0相連。那麼鄰接矩陣的秩再第一步後每次不變。

上述兩個操作都很平凡，也很相似，但秩的變化不同。所以我覺得秩和行數減秩這兩個量都沒什麼幾何意義。

——————————————————————————

考慮一個連通圖，對邊任意給定定向，考慮其incidence matrix，每一行代表一條邊，每一列代表一個頂點。如果某頂點是某邊的起點，則對應位置的矩陣元素為1，如果是終點，為-1，如果頂點不在邊上，為0. 注意由incidence matrix可還原出鄰接矩陣。事實上，記incidence matrix為M，則-M"M把對角線變為0就是鄰接矩陣。

比如一個三角形，順時針定向，對應的incidence matrix是

1 0 -1

-1 1 0

0 -1 1

這個矩陣的秩是列數減一，而行數減秩是圖的Betti數，也就是獨立的圈的個數，比如『日』是2，『田』是4.

『行數減秩是獨立的圈的個數』直觀如下：矩陣的行線性不獨立，意味著某些邊放在一起後，其邊界點消失，這意味著成了環。每個獨立的環對應一組線性不獨立的邊。獨立的圈的個數就是左null space的維數，而左null space的維數加上秩就是行數。

由上還可以知道，如果把鄰接矩陣的每個對角元改為對應頂點的度數取負，新得到的矩陣就是-M"M，其秩就是M的秩，幾何意義之類的同上。剛發現這就是圖的鄰接矩陣的秩有什麼直觀的幾何意義嗎？ - 知乎用戶的回答提到的Laplacian matrix，當然這個矩陣不限制於d-regular. （我說怎麼覺得這個矩陣的性質還不錯...）

以上說的都是連通圖，不連通的時候有類似結論。

具體的性質看wiki吧 Laplacian matrix

另外，incidence matrix提供了用代數方法研究圖上的圈的方法，參見

Polettini, Matteo. "Cycle/cocycle oblique projections

on oriented graphs." Letters in Mathematical Physics 105.1 (2015): 89-107.

統計出圖的特徵，用於分類。

樹的鄰接矩陣的秩等於其匹配數的二倍。圖譜理論的經典結果之一。