Degree matrix

Degree matrixMain

Community hub

Degree matrix

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Degree matrix

View on Wikipedia

from Wikipedia

In the mathematical field of algebraic graph theory, the degree matrix of an undirected graph is a diagonal matrix which contains information about the degree of each vertex—that is, the number of edges attached to each vertex.^[1] It is used together with the adjacency matrix to construct the Laplacian matrix of a graph: the Laplacian matrix is the difference of the degree matrix and the adjacency matrix.^[2]

Definition

[edit]

Given a graph $G=(V,E)$ with $|V|=n$ , the degree matrix $D$ for $G$ is a $n\times n$ diagonal matrix defined as^[1]

D_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.

where the degree $\deg(v_{i})$ of a vertex counts the number of times an edge terminates at that vertex. In an undirected graph, this means that each loop increases the degree of a vertex by two. In a directed graph, the term degree may refer either to indegree (the number of incoming edges at each vertex) or outdegree (the number of outgoing edges at each vertex).

Example

[edit]

The following undirected graph has a 6x6 degree matrix with values:

Vertex labeled graph	Degree matrix
	${\begin{pmatrix}4&0&0&0&0&0\\0&3&0&0&0&0\\0&0&2&0&0&0\\0&0&0&3&0&0\\0&0&0&0&3&0\\0&0&0&0&0&1\\\end{pmatrix}}$

Note that in the case of undirected graphs, an edge that starts and ends in the same node increases the corresponding degree value by 2 (i.e. it is counted twice).

Properties

[edit]

The degree matrix of a k-regular graph has a constant diagonal of $k$ .

According to the degree sum formula, the trace of the degree matrix is twice the number of edges of the considered graph.

References

[edit]

^ ^a ^b Chung, Fan; Lu, Linyuan; Vu, Van (2003), "Spectra of random graphs with given expected degrees", Proceedings of the National Academy of Sciences of the United States of America, 100 (11): 6313–6318, Bibcode:2003PNAS..100.6313C, doi:10.1073/pnas.0937490100, MR 1982145, PMC 164443, PMID 12743375.
^ Mohar, Bojan (2004), "Graph Laplacians", in Beineke, Lowell W.; Wilson, Robin J. (eds.), Topics in algebraic graph theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, Cambridge, pp. 113–136, ISBN 0-521-80197-4, MR 2125091.

v t e Matrix classes
Explicitly constrained entries	Alternant Anti-diagonal Anti-Hermitian Anti-symmetric Arrowhead Band Bidiagonal Bisymmetric Block-diagonal Block Block tridiagonal Boolean Cauchy Centrosymmetric Conference Complex Hadamard Copositive Diagonally dominant Diagonal Discrete Fourier Transform Elementary Equivalent Frobenius Generalized permutation Hadamard Hankel Hermitian Hessenberg Hollow Integer Logical Matrix unit Metzler Moore Nonnegative Pentadiagonal Permutation Persymmetric Polynomial Quaternionic Signature Skew-Hermitian Skew-symmetric Skyline Sparse Sylvester Symmetric Toeplitz Triangular Tridiagonal Vandermonde Walsh Z
Constant	Exchange Hilbert Identity Lehmer Of ones Pascal Pauli Redheffer Shift Zero
Conditions on eigenvalues or eigenvectors	Companion Convergent Defective Definite Diagonalizable Hurwitz-stable Positive-definite Stieltjes
Satisfying conditions on products or inverses	Congruent Idempotent or Projection Invertible Involutory Nilpotent Normal Orthogonal Unimodular Unipotent Unitary Totally unimodular Weighing
With specific applications	Adjugate Alternating sign Augmented Bézout Jabotinsky Cartan Circulant Cofactor Commutation Confusion Coxeter Distance Duplication and elimination Euclidean distance Fundamental (linear differential equation) Generator Gram Hessian Householder Jacobian Moment Payoff Pick Random Rotation Routh-Hurwitz Seifert Shear Similarity Symplectic Totally positive Transformation
Used in statistics	Centering Correlation Covariance Design Doubly stochastic Fisher information Hat Precision Stochastic Transition
Used in graph theory	Adjacency Biadjacency Degree Edmonds Incidence Laplacian Seidel adjacency Tutte
Used in science and engineering	Cabibbo–Kobayashi–Maskawa Density Fundamental (computer vision) Fuzzy associative Gamma Gell-Mann Hamiltonian Irregular Overlap S State transition Substitution Z (chemistry)
Related terms	Jordan normal form Linear independence Matrix exponential Matrix representation of conic sections Perfect matrix Pseudoinverse Row echelon form Wronskian
Mathematics portal List of matrices Category:Matrices (mathematics)

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

In graph theory, the degree matrix (also known as the valency matrix) of a graph

G = (V, E)

with vertex set

V = \{v_1, \dots, v_n\}

is a diagonal matrix

D \in \mathbb{R}^{n \times n}

where the diagonal entry

D_{ii}

equals the degree

d(v_i)

of vertex

v_i

, and all off-diagonal entries are zero.^[1] For an undirected simple graph, the degree

d(v_i)

is the number of edges incident to

v_i

; in weighted graphs, it is the sum of the weights of edges adjacent to

v_i

.^[2] For directed graphs, variants use either in-degrees or out-degrees on the diagonal, depending on the context. The degree matrix plays a central role in spectral graph theory and matrix representations of graphs, particularly in the construction of the graph Laplacian matrix

L = D - A

, where

A

is the adjacency matrix of

G

.^[2] This Laplacian is symmetric and positive semi-definite for undirected graphs, with eigenvalues that are real and non-negative, providing insights into graph connectivity, clustering, and spectral properties.^[2] In weighted graphs, the formulation extends to

L = D - W

, where

W

is the weight matrix, and the quadratic form

x^T L x = \frac{1}{2} \sum_{i,j} w_{ij} (x_i - x_j)^2

underscores its semi-definiteness.^[2] Key properties of the degree matrix include its diagonal structure, which simplifies computations in graph algorithms, and its dependence on vertex ordering, typically aligned with the rows and columns of the adjacency matrix.^[1] It is also integral to the incidence matrix formulation of the Laplacian, where

L = B B^T

for the unoriented incidence matrix

B

, linking combinatorial and algebraic graph properties.^[2]

Fundamentals

Definition

In graph theory, an undirected graph

G = (V, E)

consists of a finite set

V

of vertices and a set

E

of unordered pairs

\{i, j\}

with

i, j \in V

(possibly

i = j

) representing edges between vertices. The degree of a vertex

i \in V

, denoted

d_i

, is the number of edges incident to it. In simple graphs without loops or multiple edges, this equals the number of distinct neighbors of

i

. In general undirected graphs allowing loops and multiple edges, the degree is given by

d_i = \sum_{j \neq i} m_{ij} + 2 m_{ii}

, where

m_{ij}

is the multiplicity (number) of edges between distinct vertices

i

and

j

, and

m_{ii}

is the number of loops at

i

; each loop contributes 2 to the degree, while each multiple edge contributes once to each endpoint. In weighted graphs, the degree

d_i

is the sum of the weights of edges incident to

v_i

, with a loop's weight contributing twice.^[3] The degree matrix

D

G

with

|V| = n

is the

n \times n

diagonal matrix where the diagonal entry

D_{ii} = d_i

for each

i = 1, \dots, n

, and all off-diagonal entries are zero.^[4] Formally,

D = \operatorname{diag}(d_1, d_2, \dots, d_n),

where the

d_i

are defined as above. This matrix encodes the degrees in a compact form, distinct from the adjacency matrix which captures direct connections between vertices.

Notation and prerequisites

In graph theory, the degree matrix is commonly introduced using undirected simple graphs, which consist of a finite nonempty set of vertices

V = \{v_1, v_2, \dots, v_n\}

and a set of edges

E \subseteq \binom{V}{2}

, where each edge connects exactly two distinct vertices without direction. These graphs assume no self-loops (edges from a vertex to itself) or multiple edges between the same pair of vertices, ensuring a straightforward counting of connections per vertex. However, the concept extends to multigraphs with loops and multiple edges, as well as weighted and directed graphs.^[5] While the degree matrix is primarily defined for undirected graphs, directed graphs introduce asymmetries via in-degrees and out-degrees, typically requiring separate matrices rather than a single degree matrix.^[5] Standard notation denotes the degree matrix of a graph

G

D(G)

or simply

D

, represented in boldface as D to indicate its matrix form, with diagonal entries given by lowercase

d_i

, the degree of vertex

v_i

.^[1] Formally, D is the

n \times n

diagonal matrix

\diag(d_1, d_2, \dots, d_n)

, where each

d_i

counts the number of edges incident to

v_i

.^[1] In the context of weighted graphs, degrees are computed as the sum of weights on incident edges, extending the diagonal entries accordingly while maintaining the diagonal structure.^[6] The concept of the degree matrix originated in early 20th-century graph theory as part of efforts to represent graph properties via matrices, with formalization in spectral graph theory during the 1950s and 1960s through analyses of adjacency and Laplacian matrices.^[7]

Construction

From graph degrees

The degree matrix

D

of an undirected graph

G = (V, E)

with vertex set

V = \{1, 2, \dots, n\}

is constructed by first determining the degree

d_i

of each vertex

i \in V

, defined as the number of edges in

E

incident to

i

. The matrix

D

is then the

n \times n

diagonal matrix

D = \operatorname{diag}(d_1, d_2, \dots, d_n)

, where all off-diagonal entries are zero.^[8] The construction proceeds in the following steps: (1) For each vertex

i

, compute

d_i

by counting the edges connected to

i

; (2) assign

d_i

to the

(i,i)

-th entry of

D

; (3) set all off-diagonal entries to 0. This direct method ensures

D

captures the local connectivity of each vertex without relying on other matrix representations.^[9] A pseudocode implementation for building

D

from the edge set

E

(assuming 1-based indexing and an undirected simple graph) is:

Initialize degrees array of size n to 0 For each edge {u, v} in E: degrees[u] ← degrees[u] + 1 degrees[v] ← degrees[v] + 1 Initialize n × n matrix D to the [zero matrix](/page/Zero_matrix) For i = 1 to n: D[i, i] ← degrees[i]

Equivalently, the diagonal entries can be expressed as

D_{i,i} = \sum_{j \neq i} \mathbf{1}_{\{i,j\} \in E}

for

i = 1

n

, where

\mathbf{1}

is the indicator function.^[8] Isolated vertices, which have no incident edges, yield

d_i = 0

and thus a zero entry on the corresponding diagonal position in

D

, preserving the matrix's diagonal structure and indicating no contribution to the graph's connectivity from that vertex.^[10] For sparse graph representations (e.g., adjacency lists or edge lists), computing the degrees requires scanning all edges once, incrementing counts for each endpoint, which takes

O(|E|)

time overall since

\sum_i d_i = 2|E|

; constructing the diagonal matrix then adds

O(n)

time.^[9]

Relation to adjacency matrix

The degree matrix

D

of an undirected graph can be constructed directly from its adjacency matrix

A

by taking the diagonal matrix whose entries are the row sums of

A

.^[11] Specifically, for a graph with

n

vertices, the

i

-th diagonal entry

D_{ii}

equals the degree

d_i

of vertex

i

, given by

d_i = \sum_{j=1}^n A_{ij}

.^[12] This relation holds because the adjacency matrix

A

has entries

A_{ij} = 1

if vertices

i

and

j

are adjacent and

0

otherwise, so the row sum counts the number of neighbors of vertex

i

. In matrix form, this is expressed as

D = \operatorname{diag}(A \mathbf{1})

, where

\mathbf{1}

is the

n \times 1

all-ones vector.^[12] For weighted undirected graphs, the adjacency matrix

A

contains the weights

w_{ij}

of edges between vertices

i

and

j

(with

A_{ij} = 0

if no edge exists), and the degree

d_i

is defined as the sum of the weights of all edges incident to vertex

i

, so

d_i = \sum_{j=1}^n A_{ij}

.^[13] Thus, the degree matrix

D

is again the diagonal matrix with these weighted degrees on the diagonal,

D = \operatorname{diag}(A \mathbf{1})

.^[14] This generalization preserves the structural connection between the adjacency matrix and vertex degrees while accounting for edge weights.

Examples

Path graph

A path graph

P_n

consists of

n

vertices labeled

1

through

n

, connected by edges between consecutive vertices, specifically the edge set

E = \{\{i, i+1\} \mid 1 \leq i < n\}

.^[15] In

P_n

, the two endpoint vertices (1 and

n

) each have degree 1, while the

n-2

internal vertices (2 through

n-1

) each have degree 2.^[4] The degree matrix

D

P_n

is the

n \times n

diagonal matrix whose diagonal entries

d_{ii}

equal the degree of vertex

i

, with all off-diagonal entries zero.^[16] For the small path graph

P_3

, with vertices 1--2--3, the degrees are 1, 2, and 1, yielding

D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix}.

100020001

. This structure reveals a clear diagonal pattern: 1's at the ends corresponding to the low-degree endpoints, and 2's in the middle for the higher-degree internal vertices.^[16]

Cycle graph

A cycle graph

C_n

is an undirected graph consisting of

n

vertices labeled 1 through

n

, connected by edges between consecutive vertices

\{i, i+1\}

for

i = 1

n-1

, and an additional edge between vertices

n

and 1, forming a closed loop.^[4]^[15] In

C_n

, every vertex has exactly two incident edges, resulting in a degree of 2 for all vertices; thus,

C_n

is a 2-regular graph.^[4] The degree matrix

D

for

C_n

is therefore the

n \times n

diagonal matrix with 2 on each diagonal entry, which can be expressed as

D = 2I_n

, where

I_n

is the

n \times n

identity matrix.^[4]^[15] This uniform structure contrasts with the degree matrix of a path graph, where endpoint degrees are 1 and interior degrees are 2; closing the path into a cycle equalizes all degrees to 2, yielding a simple scalar multiple of the identity matrix.^[4]

Properties

Basic characteristics

The degree matrix

D

of an undirected graph

G = (V, E)

with vertex set

V = \{v_1, \dots, v_n\}

is defined as the

n \times n

diagonal matrix

D = \operatorname{diag}(d(v_1), \dots, d(v_n))

, where

d(v_i)

denotes the degree of vertex

v_i

.^[12] As a diagonal matrix,

D

is inherently symmetric, since all off-diagonal entries are zero.^[12] Moreover, with non-negative diagonal entries (as degrees are non-negative integers),

D

is positive semi-definite, meaning the quadratic form

\mathbf{x}^T D \mathbf{x} \geq 0

for all real vectors

\mathbf{x} \in \mathbb{R}^n

.^[17] The trace of

D

, given by

\operatorname{tr}(D) = \sum_{i=1}^n d(v_i)

, equals twice the number of edges in

G

, i.e.,

\operatorname{tr}(D) = 2 |E|

, by the handshaking lemma.^[12]^[18] This relation underscores the matrix's connection to global graph structure. Due to its diagonal form,

D

has exactly

n

nonzero entries in an

n \times n

matrix, making it highly sparse and computationally efficient for storage and operations in sparse matrix representations.^[12] For a disconnected graph with multiple connected components, if the vertices are reordered to group those within each component,

D

takes a block-diagonal form, where each block corresponds to the degree matrix of an individual component. This structure reflects the independence of degree computations across components.^[19]

Eigenvalues and trace

The degree matrix

D

of a graph is a diagonal matrix, and thus its eigenvalues are precisely the diagonal entries, which are the vertex degrees

d_1, d_2, \dots, d_n

. Each eigenvalue

d_i

has algebraic multiplicity one, assuming all degrees are distinct, though multiplicities increase if degrees repeat. The corresponding eigenvectors are the standard basis vectors

e_i

\mathbb{R}^n

, where the

i

-th basis vector satisfies

D e_i = d_i e_i

, reflecting the matrix's diagonal structure. This simplicity arises directly from the properties of diagonal matrices in linear algebra, applied within the graph-theoretic context. The trace of

D

, denoted

\operatorname{tr}(D)

, equals the sum of its eigenvalues, which is

\sum_{i=1}^n d_i

. For an undirected graph, this sum is twice the number of edges,

2|E|

, by the handshaking lemma.^[18] The determinant of

D

is the product of its eigenvalues, given by

\det(D) = \prod_{i=1}^n d_i

. Thus,

D

is singular if and only if the graph has at least one isolated vertex, where some

d_i = 0

Applications

Spectral graph theory

In spectral graph theory, the degree matrix

D

plays a crucial role in normalizing graph operators to account for varying vertex degrees, enabling the analysis of eigenvalues that reveal structural properties such as connectivity and expansion. One key application is in the construction of the normalized Laplacian

\mathcal{L} = I - D^{-1/2} A D^{-1/2}

, where

A

is the adjacency matrix and

D^{-1/2}

scales the rows and columns by the inverse square roots of the degrees; this normalization ensures that the eigenvalues of

\mathcal{L}

lie between 0 and 2, providing bounds on graph cuts and mixing times independent of degree irregularities.^[7] This formulation, introduced by Fan Chung, facilitates the study of expander graphs and Cheeger's inequality, linking the second smallest eigenvalue to the graph's conductance.^[7] The degree matrix also features prominently in the spectral analysis of random walks on graphs, where the transition matrix

P = D^{-1} A

defines the probabilities of moving from one vertex to its neighbors, with

D

normalizing for the fact that higher-degree vertices have more outgoing edges and thus lower per-edge transition probabilities. The eigenvalues of

P

determine the walk's convergence rate to the stationary distribution, which is proportional to the degrees (i.e., the entries of

D

); this spectral gap, influenced by

D

's diagonal values, quantifies how quickly the walk mixes, with applications to sampling and approximation algorithms.^[7] In irregular graphs,

D

's role ensures that the random walk behaves equitably across vertices of different degrees, avoiding bias toward high-degree nodes in the spectral decomposition. In spectral partitioning and graph clustering, the degree matrix influences the eigenvectors used to identify balanced cuts, as seen in methods that leverage the normalized Laplacian to embed vertices into a lower-dimensional space where clustering algorithms like k-means can be applied. The degrees in

D

affect the weighting of edges in the cut objective, promoting partitions that minimize the normalized cut value, which balances the number of edges crossing the partition against the volumes (sum of degrees) of the clusters.^[20] This approach, building on earlier work, ensures robustness to degree heterogeneity by scaling the similarity matrix appropriately. Chung's work further expands the normalized Laplacian framework with variants such as the random-walk normalized Laplacian

\mathcal{L}_{rw} = I - D^{-1} A

and the signless version, both incorporating

D

to adapt spectral properties for directed or weighted graphs; these allow finer control over eigenvalue interpretations, particularly for directed walks where

D

's out-degrees normalize asymmetries.^[7] For instance, the eigenvalues of

\mathcal{L}_{rw}

directly relate to the relaxation times of Markov chains, highlighting

D

's essential role in bridging combinatorial graph properties with probabilistic behaviors.^[7]

Graph Laplacians

The graph Laplacian matrix is a fundamental operator in spectral graph theory, constructed using the degree matrix

D

and the adjacency matrix

A

. The unnormalized Laplacian is defined as

L = D - A

, where

D

is the diagonal matrix with the vertex degrees on its main diagonal, providing the necessary degree-based subtraction that ensures

L

captures the graph's connectivity structure.^[7] This formulation highlights

D

's central role in balancing the adjacency contributions, transforming the simple edge connections in

A

into a differential operator analogous to the continuous Laplacian.^[21] A key property arising from

D

's construction is that the rows of

L

sum to zero, as each row

i

D - A

has

d_i

on the diagonal minus the sum of the

i

-th row of

A

, which equals

d_i

, yielding zero overall; this makes

L

singular with a kernel including the all-ones vector.^[7] The eigenvalues of

L

are real and non-negative, with the smallest eigenvalue being zero (with multiplicity equal to the number of connected components), and the largest eigenvalue bounded above by twice the maximum degree

\Delta = \max d_i

, reflecting

D

's influence in scaling the spectrum relative to vertex degrees.^[7] These spectral bounds underscore

D

's contribution to confining the operator's action within degree-dependent limits. The quadratic form associated with

L

further illustrates

D

's enabling role: for a vector

x \in \mathbb{R}^n

x^T L x = \sum_{(i,j) \in E} (x_i - x_j)^2,

where the sum is over all edges, and this equality derives from expanding

x^T (D - A) x = \sum_i d_i x_i^2 - 2 \sum_{(i,j) \in E} x_i x_j

, which simplifies to the edge-difference sum; here,

D

weights the self-terms to match the degree-incidence structure.^[7] This form measures the smoothness of

x

over the graph, with

D

's diagonal entries ensuring the quadratic penalizes variations proportionally to local connectivity. In addition to the unnormalized form, normalized Laplacians incorporate

D

more explicitly to handle irregular degree distributions. The symmetric normalized Laplacian is

\mathcal{L} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}

, where

D^{-1/2}

scales rows and columns by the inverse square roots of degrees, making

\mathcal{L}

suitable for non-regular graphs by degree-normalizing the operator.^[7] The combinatorial Laplacian

L

emphasizes raw edge counts via

D - A

, while the normalized variant

\mathcal{L}

or the random-walk form

D^{-1} L

adjusts for degree heterogeneity, with

D

's inverse highlighting its pivotal diagonal role in achieving scale-invariance across vertices.^[7] Both forms leverage

D

to derive positive semidefiniteness and bounded spectra (0 to 2 for

\mathcal{L}

), facilitating applications in partitioning and diffusion processes.^[7]

Info Pages

Talk Pages

Special Pages

Degree matrix

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Degree matrix

Definition

Example

Properties

References

Degree matrix

Fundamentals

Definition

Notation and prerequisites

Construction

From graph degrees

Relation to adjacency matrix

Examples

Path graph

Cycle graph

Properties

Basic characteristics

Eigenvalues and trace

Applications

Spectral graph theory

Graph Laplacians

References

Add your contribution

Related Hubs

Contribute something

History

Degree matrix

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Degree matrix

Definition

Example

Properties

References

Degree matrix

Fundamentals

Definition

Notation and prerequisites

Construction

From graph degrees

Relation to adjacency matrix

Examples

Path graph

Add your contribution

Related Hubs

Contribute something