Rank (graph theory)

<h2 id="examples">Examples</h2>
<p>A sample graph and matrix:
</p>

<p>(corresponding to the four edges, e1–e4):
</p>
<table><tbody><tr><td><table><tbody><tr><th></th><th>1</th><th>2</th><th>3</th><th>4</th></tr><tr><th>1</th><td>0</td><td>1</td><td>1</td><td>1</td></tr><tr><th>2</th><td>1</td><td>0</td><td>0</td><td>0</td></tr><tr><th>3</th><td>1</td><td>0</td><td>0</td><td>1</td></tr><tr><th>4</th><td>1</td><td>0</td><td>1</td><td>0</td></tr></tbody></table></td><td>=</td><td><p>                                          (                                                            0                                                  1                                                  1                                                  1                                                                              1                                                  0                                                  0                                                  0                                                                              1                                                  0                                                  0                                                  1                                                                              1                                                  0                                                  1                                                  0                                                      )                          .              {\displaystyle {\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&1\\1&0&1&0\\\end{pmatrix}}.}  </p></td></tr></tbody></table>
<p>In this example, the matrix theory rank of the matrix is 4, because its column vectors are linearly independent.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Circuit_rank/RqbfVDR6">Circuit rank</a></li>
<li><a href="/facts/Cycle_rank/KKGbLcKo">Cycle rank</a></li>
<li><a href="/facts/Nullity_(graph_theory)/gIq3qssp">Nullity (graph theory)</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Chen, Wai-Kai (1976), <i>Applied Graph Theory</i>, North Holland Publishing Company, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-7204-2371-6.</li>
<li>Hedetniemi, S. T., Jacobs, D. P., Laskar, R. (1989), Inequalities involving the rank of a graph. <i>Journal of Combinatorial Mathematics and Combinatorial Computing</i>, vol. 6, pp. 173–176.</li>
<li>Bevis, Jean H., Blount, Kevin K., Davis, George J., Domke, Gayla S., Miller, Valerie A. (1997), <a href="https://www.sciencedirect.com/science/article/pii/S0024379596005137/pdf?md5=d4fb4bfce95f03fecb3e51f0c4d3af0d&isDTMRedir=Y&pid=1-s2.0-S0024379596005137-main.pdf&_valck=1">The rank of a graph after vertex addition</a>. <i>Linear Algebra and its Applications</i>, vol. 265, pp. 55–69.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Grossman, Jerrold W.; Kulkarni, Devadatta M.; Schochetman, Irwin E. (1995), "On the minors of an incidence matrix and its Smith normal form", Linear Algebra and Its Applications, 218: 213–224, doi:10.1016/0024-3795(93)00173-W, MR 1324059. See in particular the discussion on p. 218. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Rank (graph theory) open-in-new

Rank (graph theory)