Properties
For a graph G and its Laplacian matrix L with eigenvalues :
- L is always positive-semidefinite .
- The number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph.
- L is an M-matrix.
- is always 0 because every Laplacian matrix has an eigenvector that, for each row, adds the corresponding node's degree (from the diagonal) to a "-1" for each neighbor so that
- The smallest non-zero eigenvalue of L is called the spectral gap.
- If we define an oriented incidence matrix M with element Mev for edge e (connecting vertex i and j, with i < j) and vertex v given by
then the Laplacian matrix L satisfies
where is the matrix transpose of M.
- The second smallest eigenvalue of L is the algebraic connectivity (or Fiedler value) of G.
Read more about this topic: Laplacian Matrix
Famous quotes containing the word properties:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)