Eigenvectors and Eigenvalues of the Normalized Laplacian

For diagonal matrix D as the sum of the weights, adjacency matrix A with weighted degrees, and Laplacian matrix L (which is a positive semidefinite matrix), the normalized Laplacian is: D^(−1/2)*L*(D^−1/2)

Therefore I compute the following:

    % determine the Laplacian matrix L
    L = D - A;

   % determine the normalized Laplacian nL
    nL = (full(D)^(-.5))*L*(full(D)^(-.5));

    % list eigenvalues of nL, L
    [nv,nd] = eig(full(nL)); % seems incorrect?
    [v,d] = eig(full(L));

The first eigenvalue of both L and nL are zero, and the remaining eigenvalues are positive. However this is not true: nd = scalar*d.

Furthermore, the first eigenvector (v(:,1)) of L is constant, but not the case with the first eigenvector ((nv(:,1)) of nL.

This seems like it should be a straightforward computation; but it seems that either my normalized Laplacian is computed incorrectly or that the "eig" function on nL is incorrect.

I checked that L is computed correctly through the following known relationship: L*v(:,i) = d(i,i)*D*v(:,i) for all i

Any help would be greatly appreciated. Many Thanks -A

[Matt J]

Clarify what result you expect and why. I can't see any relationship that L and nL should have without knowing the contents of L and D. Also, clarify what M is supposed to represent in

 L*v(:,i) = d(i,i)*M*v(:,i)

since v are the eigenvectors of L and d its eigenvalues, it seems to me that M should equal 1.

[A C]

Sorry typo: L*v(:,i) = d(i,i)*D*v(:,i) where D is a non-singular diagonal matrix.

Since D is weighted, for the unnormalized Laplacian L, the diagonal along D is equal to the sum of the weights in the adjacency matrix A. In the case for the normalized Laplacian nL, you are right that the diagonal should be an identity matrix.

In evaluating nL, the first eigenvalue nd(1,1)=0. I would expect the first eigenvector for nL, which is nv(:,1), to be all constant.

For example, on a 6x6 matrix:

A =

   (2,1)       4.0000
   (4,1)       4.7059
   (5,1)       3.1120
   (1,2)       4.0000
   (3,2)       3.8462
   (4,2)       8.0000
   (5,2)       3.0000
   (6,2)       4.4543
   (2,3)       3.8462
   (5,3)       3.1707
   (6,3)       9.6154
   (1,4)       4.7059
   (2,4)       8.0000
   (5,4)       2.0000
   (1,5)       3.1120
   (2,5)       3.0000
   (3,5)       3.1707
   (4,5)       2.0000
   (6,5)       3.0000
   (2,6)       4.4543
   (3,6)       9.6154
   (5,6)       3.0000

D =

   (1,1)      11.8179
   (2,1)      23.3005
   (3,1)      16.6323
   (4,1)      14.7059
   (5,1)      14.2828
   (6,1)      17.0697

L =

   (1,1)      11.8179
   (2,1)      -4.0000
   (4,1)      -4.7059
   (5,1)      -3.1120
   (1,2)      -4.0000
   (2,2)      23.3005
   (3,2)      -3.8462
   (4,2)      -8.0000
   (5,2)      -3.0000
   (6,2)      -4.4543
   (2,3)      -3.8462
   (3,3)      16.6323
   (5,3)      -3.1707
   (6,3)      -9.6154
   (1,4)      -4.7059
   (2,4)      -8.0000
   (4,4)      14.7059
   (5,4)      -2.0000
   (1,5)      -3.1120
   (2,5)      -3.0000
   (3,5)      -3.1707
   (4,5)      -2.0000
   (5,5)      14.2828
   (6,5)      -3.0000
   (2,6)      -4.4543
   (3,6)      -9.6154
   (5,6)      -3.0000
   (6,6)      17.0697

nL =

   (1,1)       1.0000
   (2,1)      -0.2410
   (4,1)      -0.3570
   (5,1)      -0.2395
   (1,2)      -0.2410
   (2,2)       1.0000
   (3,2)      -0.1954
   (4,2)      -0.4322
   (5,2)      -0.1644
   (6,2)      -0.2234
   (2,3)      -0.1954
   (3,3)       1.0000
   (5,3)      -0.2057
   (6,3)      -0.5707
   (1,4)      -0.3570
   (2,4)      -0.4322
   (4,4)       1.0000
   (5,4)      -0.1380
   (1,5)      -0.2395
   (2,5)      -0.1644
   (3,5)      -0.2057
   (4,5)      -0.1380
   (5,5)       1.0000
   (6,5)      -0.1921
   (2,6)      -0.2234
   (3,6)      -0.5707
   (5,6)      -0.1921
   (6,6)       1.0000

v =

    0.4082   -0.5366    0.3882   -0.6241    0.0081    0.0714
    0.4082   -0.0841   -0.2729    0.0701   -0.1172   -0.8562
    0.4082    0.5127   -0.0853   -0.2110    0.7180    0.0559
    0.4082   -0.4382   -0.5743    0.3376    0.0777    0.4377
    0.4082    0.0482    0.6527    0.6354   -0.0050    0.0346
    0.4082    0.4978   -0.1085   -0.2080   -0.6816    0.2566

d =

   -0.0000         0         0         0         0         0
         0    7.6283         0         0         0         0
         0         0   16.3586         0         0         0
         0         0         0   17.9809         0         0
         0         0         0         0   26.4104         0
         0         0         0         0         0   29.4309

nv =

   -0.3476   -0.4380    0.3279    0.7288   -0.2199   -0.0196
   -0.4881   -0.1929   -0.4530   -0.3370   -0.6264   -0.1160
   -0.4124    0.5215   -0.0625    0.1951    0.2272   -0.6815
   -0.3878   -0.4820   -0.2922   -0.1258    0.7122    0.0940
   -0.3821    0.0067    0.7653   -0.5171    0.0160    0.0235
   -0.4178    0.5163   -0.1107    0.1845    0.0147    0.7158

nd =

    0.0000         0         0         0         0         0
         0    0.5046         0         0         0         0
         0         0    1.0920         0         0         0
         0         0         0    1.3430         0         0
         0         0         0         0    1.4871         0
         0         0         0         0         0    1.5732

Answer 1

[Antonio]

If you expect that nL shares the same eigenvectors and eigenvalues, that's not gonna happen.

Even if they share the \lambda_0=0 eigenvalue, the eigenvector does not need to be the same.

For that \lambda_0, why v(:,1) = [1,1,1,1,1]/sqrt(6) ? Simple: if you sum the values if the i-th row, by definition of A and D, you'll get 0: sum(L(:,i)) = sum(L(i,:)) = 0.

So v(:,1) = c_0 * [1,1,1,1,1,1] (for every nonzero c_0) will satisfy the equality.

That identity (the sum of the elements of a row) does not apply to nL.