Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    Lecture 8

    Uploaded by

    snehalparab183

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Lecture 8

    Uploaded by

    snehalparab183
    6 views3 pages

    Original Title

    lecture8

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    6 views3 pages

    Lecture 8

    Uploaded by

    snehalparab183

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    REU 2013: Apprentice Program Summer 2013

    Lecture 8: July 9, 2013


    Madhur Tulsiani Scribe: David Kim, Young Kun Ko

    1 Eigenvalues and eigenvectors of adjacency matrices


    Recall given an adjacency matrix for an undirected graph G = (V, E), A is real and symmetric,
    and hence diagonalizable (A = U DU ∗ , D is diagonalizable with real entries). We can decompose
    A as follows:
    Xn
    A= µi ui uTi
    i=1
    where we order the eigenvalues so that µ1 ≥ µ2 ≥ ... ≥ µn .

    Exercise 1.1 Given an adjacency matrix A, (Al )ij = # of paths of length l between i and j.

    Definition 1.2 (Trace) Given an n × n matrix A, T r(A) is the sum of its diagonal entries.

    Exercise 1.3 Suppose G is a graph with n vertices, m edges, and no self-loops. Then show that
    Pn
    1. i=1 µi = 0 (Hint: sum of the roots of the characteristic polynomial).
    Pn 2 2
    2. i=1 µi = 2m (Hint: what are the eigenvalues of A ?)

    Exercise 1.4 If B ∼ A, then T r(B) = T r(A).

    Definition 1.5 (Clique) Kn ≡complete graph on n vertices.


    (
    1 if i 6= j
    Aij =
    0 if i = j

    Exercise 1.6 Find the eigenvalues and eigenvectors of the complete graph on n vertices, denoted
    as Kn . In Kn , we have an edge between any two vertices i and j such that i 6= j.
    Hint: AKn = J − I where J denotes the n × n matrix with all entries equal to 1. Look at the
    dimension of the null space of J.

    Exercise 1.7 Let Cn ≡ cycle of length n. What is its adjacency matrix? Find the eigenvalues and
    eigenvectors.

    Hint: Consider v = (1, ω, ω 2 , ..., ω n−1 )T , where ω is a root of the unity.

    Definition 1.8 A graph G is said to be d-regular if ∀i ∈ V, deg(i) = d.

    Note that for any d-regular graph G, the vector (1, . . . , 1)T is an eigenvector of AG with eigenvalue
    d. The graphs Kn and Cn are respectively (n − 1)-regular and 2-regular.

    1
    2 Rayleigh Quotients
    Definition 2.1 (Rayleigh Quotient) For a real matrix A, the Rayleigh quotient of A, denoted
    as RA (·) is a function from Rn \ {0} to R, defined as follows

    xT Ax
    RA (x) = .
    xT x

    We know that A = ni=1 µi Ui UiT where µ1 ≥ µ2 ≥ · · · ≥ µn . The eigenvalues of a real-symmetric


    P
    matrix A can also be characterized in terms of the Rayleigh quotients. For example, we can show
    that

    µ1 = max RA (x)
    x∈Rn \{0}

    µn = min RA (x)
    x∈Rn \{0}

    First note that if vi is the eigenvector corresponding to the eigenvalue µi , then RA (vi ) = µi . Thus,
    we have that
    maxn RA (x) ≥ RA (v1 ) = µ1 .
    x∈R

    Also, for any x ∈ Rn \ {0}, we P can express it in the orthonormal basis given by the eigenvectors
    v1 , . . . , vn of A. Writing x = i αi vi gives

    n
    !T n
    ! n
    X X X X
    T
    x x = αi vi αi vi = αi αj viT vj = αi2 .
    i=1 i=1 i,j i=1

    Similarly, we get

    n
    !T n
    ! n
    !T n
    ! n
    X X X X X
    xT Ax = αi vi αi Avi = αi vi αi µi vi = αi2 · µi .
    i=1 i=1 i=1 i=1 i=1

    Now we can express RA (x) as


    Pn
    xT Ax αi2 · µi
    RA (x) = = Pi=1
    n 2
    xT x i=1 αi µi

    Using the fact that µi ≤ µ1 for all i, we get that RA (x) ≤ µ1 for all x. Combining it with RA (v1 ) =
    µ1 , we get that µ1 = maxx∈Rn \{0} RA (x). Similarly, we can prove that µn = minx∈Rn \{0} RA (x)
    Similarly, we can observe that

    xT Ax
    µ2 = max
    x∈Span(v2 ,...,vn )\{0} xT x

    Note that saying that x ∈ Span(v2 , . . . , vn ) is equivalent to saying that hx, v1 i = xT v1 = 0.

    2
    Exercise 2.2 If v1 , . . . , vn are orthogonal vectors in Cn (or in Rn ), then for any k ≤ n

    {x | hx, v1 i = · · · = hx, vk i = 0} = Span(vk+1 , . . . , vn ) .

    The Courant-Fischer theorem charactertizes all the eigenvalues in terms of the Rayleigh quotients.

    Theorem 2.3 (Courant-Fischer) Let A be an n × n real symmetric matrix. Let the eigenvalues
    of A be λ1 ≥ λ2 ≥ · · · ≥ λn . Then

    xT Ax xT Ax
    λk = maxn min = minn max
    S⊆R x∈S\{0} xT x T ⊆R x∈T \{0} xT x
    dim(S)=k dim(S)=n−k+1

    Try proving the theorem by extending the proof for the characterization of µ1 .

    Exercise 2.4 For a graph G, prove the following


    n
    1X
    deg(i) ≤ µ1 ≤ max deg(i)
    n i∈V
    i=1

    Exercise 2.5 Show that if G is an undirected graph with eigenvalues µ1 ≥ · · · ≥ µn , then G can
    be colored with bµ1 c + 1 colors.

    Exercise 2.6 (Interlacing theorem) Use the Courant-Fischer to show the following: if G has
    eigenvals µ1 ≥ . . . ≥ µn and G0 is a graph obtained by removing a vertex from G with eigenvalues
    ν1 ≥ . . . ≥ νn−1 then
    µ1 ≥ ν1 ≥ µ2 ≥ . . . ≥ νn−1 ≥ µn .

    You might also like