Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

30.3: The Power of a Matrix

( \newcommand{\kernel}{\mathrm{null}\,}\)

  • For a diagonalizable matrix A, we have C1AC=D. Then we have A=CDC1
  • We have A2=CDC1CDC1=CD2C1An=CDC1CDC1=CDnC1.
  • Because the columns of C are eigenvectors, so we can say that the eigenvectors for A and An are the same if A is diagonalizable.
  • If x is an eigenvector of A with the corresponding eigenvalue λ, then x is also an eigenvector of An with the corresponding eigenvalue λn.

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

# Here are some libraries you may need to use
%matplotlib inline
import numpy as np
import sympy as sym
import networkx as nx
import matplotlib.pyplot as plt
from urllib.request import urlretrieve

sym.init_printing(use_unicode=True)
urlretrieve('https://raw.githubusercontent.com/colbrydi/jupytercheck/master/answercheck.py', 
            'answercheck.py');
# Here are some libraries you may need to use
%matplotlib inline
import numpy as np
import sympy as sym
import networkx as nx
import matplotlib.pyplot as plt
from urllib.request import urlretrieve

sym.init_printing(use_unicode=True)
urlretrieve('https://raw.githubusercontent.com/colbrydi/jupytercheck/master/answercheck.py', 
            'answercheck.py');

Graph Random Walk

  • Define the following matrices:
    • I is the identity matrix
    • A is the adjacency matrix
    • D is diagonal matrix of degrees (number of edges connected to each node)

W=12(I+AD1)

  • The lazy random walk matrix, W, takes a distribution vector of stuff, pt, and diffuses it to its neighbors:

pt+1=Wpt

  • For some initial distribution of stuff, p0, we can compute how much of it would be at each node at time, t, by powering W as follows:

pt=Wtp0

  • Plugging in the above expression yields:

pt=(12(I+AD1))tp0

Do This

Using matrix algebra, show that 12(I+AD1) is similar to I12N, where N=D12(DA)D12 is the normalized graph Laplacian.

Random Walk on Barbell Graph

To generate the barbell graph, run the following cell.

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

n = 60 # number of nodes
B = nx.Graph() # initialize graph

## initialize empty edge lists
edge_list_complete_1 = [] 
edge_list_complete_2 = []
edge_list_path = []

## generate node lists
node_list_complete_1 = np.arange(int(n/3))
node_list_complete_2 = np.arange(int(2*n/3),n)
node_list_path = np.arange(int(n/3)-1,int(2*n/3))

## generate edge sets for barbell graph
for u in node_list_complete_1:
    for v in np.arange(u+1,int(n/3)):
        edge_list_complete_1.append((u,v))
        
for u in node_list_complete_2:
    for v in np.arange(u+1,n):
        edge_list_complete_2.append((u,v))

for u in node_list_path:
    edge_list_path.append((u,u+1))

# G.remove_edges_from([(3,0),(5,7),(0,7),(3,5)])

## add edges
B.add_edges_from(edge_list_complete_1)
B.add_edges_from(edge_list_complete_2)
B.add_edges_from(edge_list_path)


## draw graph
pos=nx.spring_layout(B) # positions for all nodes

### nodes
nx.draw_networkx_nodes(B,pos,
                       nodelist=list(node_list_complete_1),
                       node_color='c',
                       node_size=400,
                       alpha=0.8)
nx.draw_networkx_nodes(B,pos,
                       nodelist=list(node_list_path),
                       node_color='g',
                       node_size=200,
                       alpha=0.8)
nx.draw_networkx_nodes(B,pos,
                       nodelist=list(node_list_complete_2),
                       node_color='b',
                       node_size=400,
                       alpha=0.8)


### edges
nx.draw_networkx_edges(B,pos,
                       edgelist=edge_list_complete_1,
                       width=2,alpha=0.5,edge_color='c')
nx.draw_networkx_edges(B,pos,
                       edgelist=edge_list_path,
                       width=3,alpha=0.5,edge_color='g')
nx.draw_networkx_edges(B,pos,
                       edgelist=edge_list_complete_2,
                       width=2,alpha=0.5,edge_color='b')


plt.axis('off')
plt.show() # display
n = 60 # number of nodes
B = nx.Graph() # initialize graph

## initialize empty edge lists
edge_list_complete_1 = [] 
edge_list_complete_2 = []
edge_list_path = []

## generate node lists
node_list_complete_1 = np.arange(int(n/3))
node_list_complete_2 = np.arange(int(2*n/3),n)
node_list_path = np.arange(int(n/3)-1,int(2*n/3))

## generate edge sets for barbell graph
for u in node_list_complete_1:
    for v in np.arange(u+1,int(n/3)):
        edge_list_complete_1.append((u,v))
        
for u in node_list_complete_2:
    for v in np.arange(u+1,n):
        edge_list_complete_2.append((u,v))

for u in node_list_path:
    edge_list_path.append((u,u+1))

# G.remove_edges_from([(3,0),(5,7),(0,7),(3,5)])

## add edges
B.add_edges_from(edge_list_complete_1)
B.add_edges_from(edge_list_complete_2)
B.add_edges_from(edge_list_path)


## draw graph
pos=nx.spring_layout(B) # positions for all nodes

### nodes
nx.draw_networkx_nodes(B,pos,
                       nodelist=list(node_list_complete_1),
                       node_color='c',
                       node_size=400,
                       alpha=0.8)
nx.draw_networkx_nodes(B,pos,
                       nodelist=list(node_list_path),
                       node_color='g',
                       node_size=200,
                       alpha=0.8)
nx.draw_networkx_nodes(B,pos,
                       nodelist=list(node_list_complete_2),
                       node_color='b',
                       node_size=400,
                       alpha=0.8)


### edges
nx.draw_networkx_edges(B,pos,
                       edgelist=edge_list_complete_1,
                       width=2,alpha=0.5,edge_color='c')
nx.draw_networkx_edges(B,pos,
                       edgelist=edge_list_path,
                       width=3,alpha=0.5,edge_color='g')
nx.draw_networkx_edges(B,pos,
                       edgelist=edge_list_complete_2,
                       width=2,alpha=0.5,edge_color='b')


plt.axis('off')
plt.show() # display
Do This

Generate the lazy random walk matrix, W, for the above graph.

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

A = nx.adjacency_matrix(B)
A = A.todense()

d = np.sum(A,0) # Make a vector of the sums.
D = np.diag(np.asarray(d)[0])
A = nx.adjacency_matrix(B)
A = A.todense()

d = np.sum(A,0) # Make a vector of the sums.
D = np.diag(np.asarray(d)[0])

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

#Put your answer to the above question here.
#Put your answer to the above question here.

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

from answercheck import checkanswer
checkanswer.matrix(W, "7af4a5b11892da6e1a605c8239b62093")
from answercheck import checkanswer
checkanswer.matrix(W, "7af4a5b11892da6e1a605c8239b62093")
Do This

Compute the eigenvalues and eigenvectors of W. Make a diagonal matrix J with the eigenvalues on the diagonal. Name the matrix of eigenvectors V (each column is an eigenvector).

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

#Put your answer to the above question here. 
#Put your answer to the above question here. 

Now we make sure we constructed V and A correctly by double checking that W=VJV1

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

np.allclose(W, V*J*np.linalg.inv(V))
np.allclose(W, V*J*np.linalg.inv(V))
Do This

Let your p0=[1,0,0,,0]. Compute pt for t=1,2,,100, and plot ||v1pt||1 versus t, where v1 is the eigenvector associated with the largest eigenvalue λ1=1 and whose sum equals 1. (Note: ||||1 may be computed using np.linalg.norm(v_1-p_t, 1).)

Login with LibreOne to run this code cell interactively.

If you have already signed in, please refresh the page.

#Put your answer to the above question here. 
#Put your answer to the above question here. 

Compare to Complete Graph

If you complete the above, do the same for a complete graph on the same number of nodes.

Question

What do you notice about the graph that is different from that above?


This page titled 30.3: The Power of a Matrix is shared under a CC BY-NC 4.0 license and was authored, remixed, and/or curated by Dirk Colbry via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?