Numpy Exercise 4

Imports



In [1]:

    
import numpy as np
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns

Complete graph Laplacian

In discrete mathematics a Graph is a set of vertices or nodes that are connected to each other by edges or lines. If those edges don't have directionality, the graph is said to be undirected. Graphs are used to model social and communications networks (Twitter, Facebook, Internet) as well as natural systems such as molecules.

A Complete Graph, $K_n$ on $n$ nodes has an edge that connects each node to every other node.

Here is $K_5$:



In [2]:

    
import networkx as nx
K_5=nx.complete_graph(5)
nx.draw(K_5)

The Laplacian Matrix is a matrix that is extremely important in graph theory and numerical analysis. It is defined as $L=D-A$. Where $D$ is the degree matrix and $A$ is the adjecency matrix. For the purpose of this problem you don't need to understand the details of these matrices, although their definitions are relatively simple.

The degree matrix for $K_n$ is an $n \times n$ diagonal matrix with the value $n-1$ along the diagonal and zeros everywhere else. Write a function to compute the degree matrix for $K_n$ using NumPy.



In [3]:

    
def complete_deg(n):
    return np.identity(n,dtype=np.int)*(n-1)



In [4]:

    
D = complete_deg(5)
assert D.shape==(5,5)
assert D.dtype==np.dtype(int)
assert np.all(D.diagonal()==4*np.ones(5))
assert np.all(D-np.diag(D.diagonal())==np.zeros((5,5),dtype=int))

The adjacency matrix for $K_n$ is an $n \times n$ matrix with zeros along the diagonal and ones everywhere else. Write a function to compute the adjacency matrix for $K_n$ using NumPy.



In [5]:

    
def complete_adj(n):
    #I used diagflat to create an identity matrix of size n. I also could have just used np.identity
    return np.ones((n,n),np.dtype(int)) - np.diagflat([1]*n)



In [6]:

    
A = complete_adj(5)
assert A.shape==(5,5)
assert A.dtype==np.dtype(int)
assert np.all(A+np.eye(5,dtype=int)==np.ones((5,5),dtype=int))

Use NumPy to explore the eigenvalues or spectrum of the Laplacian L of $K_n$. What patterns do you notice as $n$ changes? Create a conjecture about the general Laplace spectrum of $K_n$.



In [7]:

    
def Laplace_n(n):
    return complete_deg(n) - complete_adj(n)
def eigenvalue(Laplacian):
     return np.linalg.eigvalsh(Laplacian)
for i in range(1,10):
    print eigenvalue(Laplace_n(i))









    



[ 0.]
[ 0.  2.]
[ -1.11022302e-16   3.00000000e+00   3.00000000e+00]
[ -1.66533454e-16   4.00000000e+00   4.00000000e+00   4.00000000e+00]
[ -1.11022302e-15   5.00000000e+00   5.00000000e+00   5.00000000e+00
   5.00000000e+00]
[  1.44328993e-15   6.00000000e+00   6.00000000e+00   6.00000000e+00
   6.00000000e+00   6.00000000e+00]
[ -8.04911693e-16   7.00000000e+00   7.00000000e+00   7.00000000e+00
   7.00000000e+00   7.00000000e+00   7.00000000e+00]
[ -1.66533454e-15   8.00000000e+00   8.00000000e+00   8.00000000e+00
   8.00000000e+00   8.00000000e+00   8.00000000e+00   8.00000000e+00]
[ -1.77635684e-15   9.00000000e+00   9.00000000e+00   9.00000000e+00
   9.00000000e+00   9.00000000e+00   9.00000000e+00   9.00000000e+00
   9.00000000e+00]

The first eigenvalue is always 0, the following eigenvalues are all equal to n, and those nonzero eigenvalues have multiplicty n-1



In [ ]:

    
print