Читать книгу Artificial Intelligence and Quantum Computing for Advanced Wireless Networks - Savo G. Glisic - Страница 90

(Properties of L) The matrix L satisfies the following properties:

1 For every vector f ∈ ℝn we have

2 L is symmetric and positive semidefinite.

3 The smallest eigenvalue of L is 0, and the corresponding eigenvector is the constant one vector 1.

4 L has n non‐negative, real‐valued eigenvalues 0 = λ1 ≤ λ2≤… ≤λn.

Proof:

Part (1): By the definition of d_i,

Part (2): The symmetry of L follows directly from the symmetry of W and D. The positive semidefiniteness is a direct consequence of Part (1), which shows that f ’ Lf ≥ 0 for all f ∈ ℝⁿ.

Part (3): Self‐evident.

Part (4) is a direct consequence of Parts (1)–(3).

The normalized graph Laplacians: There are two matrices that are called normalized graph Laplacians in the literature. Both matrices are closely related to each other and are defined as

We denote the first matrix by L_sym as it is a symmetric matrix, and the second one by L_rw as it is closely related to a random walk. In the following, we summarize several properties of L_sym and L_rw.