Recall the definition of the Laplacian L of a graph By its d

Recall the definition of the Laplacian L of a graph. By its definition L is a symmetric matrix. Prove L is positive semidefinite by showing that u^T Lu = 1/2 summation _(i.j) belongs to E (u_i - u_j)^2. For this first directly compute u^TLu and see what you get. Show that 0 is always an eigenvalue of L by exhibiting an associated eigenvector.

Solution

Ans-

In that case, sRb if and only if s has read b. Another, probably inequivalent, relation is: s S has checked b B out of the library. When used informally, relations may be ambiguous (did s read b if she only read the first page?), but in mathematical usage we always require that relations are definite, meaning that one and only one of the statements “these elements are related” or “these elements are not related” is true. The graph GR of a relation R on X and Y is the subset of X × Y defined by GR = {(x, y) X × Y : xRy} . This graph contains all of the information about which elements are related. Conversely, any subset G X ×Y defines a relation R by: xRy if and only if (x, y) G. Thus, a relation on X and Y may be (and often is) defined as subset of X × Y . As for sets, it doesn’t matter how a relation is defined, only what elements are related. A function f : X Y determines a relation F on X and Y by: xF y if and only if y = f(x). Thus, functions are a special case of relations. The graph GR of a general relation differs from the graph GF of a function in two ways: there may be elements x X such that (x, y) / GR for any y Y , and there may be x X such that (x, y) GR for many y Y . For example, in the case of the relation R in Example 1.31, there may be some students who haven’t read any books, and there may be other students who have 12 1. Sets and Functions read lots of books, in which case we don’t have a well-defined function from students to books. Two important types of relations are orders and equivalence relations, and we define them next. 1.5.1. Orders. A primary example of an order is the standard order on the natural (or real) numbers. This order is a linear or total order, meaning that two numbers are always comparable. Another example of an order is inclusion on the power set of some set; one set is “smaller” than another set if it is included in it. This order is a partial order (provided the original set has at least two elements), meaning that two subsets need not be comparable. Example 1.32. Let X = {1, 2}. The collection of subsets of X is P(X) = {, A, B, X} , A = {1}, B = {2}. We have A X and B X, but A 6 B and B 6 A, so A and B are not comparable under ordering by inclusion. The general definition of an order is as follows. Definition 1.33. An order on a set X is a binary relation on X such that for every x, y, z X: (a) x x (reflexivity); (b) if x y and y x then x = y (antisymmetry); (c) if x y and y z then x z (transitivity). An order is a linear, or total, order if for every x, y X either x y or y x, otherwise it is a partial order. If is an order, then we also write y x instead of x y, and we define a corresponding strict order by x y if x y and x 6= y. There are many ways to order a given set (with two or more elements). Example 1.34. Let X be a set. One way to partially order the subsets of X is by inclusion, as in Example 1.32. Another way is to say that A B for A, B X if and only if A B, meaning that A is “smaller” than B if A includes B. Then in an order on P(X), called ordering by reverse inclusion.