Students who do this activity will

1) understand how to numerically calculate the smallest and largest eigenvalues of an invertible matrix (if they exist) using the Power Method. They learn how to modify the existing code of the Power Method (Power_method.pdf (Acrobat (PDF) 1.9MB Oct29 24) for lecture notes, Power_method.mlx (MATLAB Live Script 168kB Oct29 24) for code) to replace a matrix with its inverse to find these eigenvalues.

These goals can be achieved through Assignment 1. The smallest eigenvalue (one having the smallest absolute value) and the corresponding eigenvector of an invertible matrix can be found by (a) finding the dominant eigenvalue/eigenvector of its inverse using the Power Method, and (b) taking the reciprocal of the dominant eigenvalue in Part (a) to get the smallest eigenvalue of the original matrix (the eigenvector stays the same).

2) explore how to improve the performance of the Google PageRank algorithm and modify the existing code (HW_PageRank.pdf (Acrobat (PDF) 294kB Oct29 24) for the homework instructions, Google_PageRank.mlx (MATLAB Live Script 147kB Oct29 24) for code solution) through Assignment 2. The Google PageRank algorithm uses the steady-state vector of the Google matrix to determine relative rankings of the importance of web pages. The steady-state vector is an eigenvector associated with the dominant eigenvalue of the Google matrix (which is 1). The Power Method can be utilized by iteratively multiplying the Google matrix with any initial vector to find the steady-state vector. This is much faster compared with finding the steady state vector by raising the Google matrix to some large power.

This activity can be used in Linear Algebra or Applied Linear Algebra courses for undergraduates after the theory behind the Power Method and the algorithm for Google PageRank have been explained and implemented. Since the activity requires coding, students can do this outside of class as a homework assignment, or instructors can set this up as a midterm test to check their students' coding skills. This activity can be challenging for those who don't understand the Power Method or Google PageRank algorithm.

Assignment 1: Finding the smallest eigenvalue of a square matrix.

The Power Method is used to find adominant eigenvalue (one having the largest absolute value), if one exists, and a corresponding eigenvector of a square matrix M.

Property: If M is an invertible matrix and λ is an eigenvalue of M, then λ^-1 is an eigenvalue of A = M^-1. Note that M and A have the same eigenvector x.

Use the above property to modify the Matlab function "power method" implemented in the previous lecture (Power_method.pdf (Acrobat (PDF) 1.9MB Oct29 24) for lecture notes, Power_method.mlx (MATLAB Live Script 168kB Oct29 24) for code) to compute the smallest eigenvalue of M (i.e., the one with the smallest absolute value) and the corresponding eigenvector.

Let's call the modified function as

function [Vn,Ln] = mod_power_method_for_smallest_eigval(M,N)

where M is an invertible matrix and N is the number of iterations. Ln is the smallest eigenvalue of M (one having the smallest absolute value) and Vn is the corresponding eigenvector.

----------------------------------------------------------------------------------

Assignment 2: Finding the steady-state vector for Google PageRank algorithm

One of the principal functions that Google does is is ranking web pages. A web page should be ranked by some sort of criteria. From your homework about the Google PageRank algorithm (HW_PageRank.pdf (Acrobat (PDF) 294kB Oct29 24) for the homework instructions, Google_PageRank.mlx (MATLAB Live Script 147kB Oct29 24) for code solution), you have understood how the Google Pagerank method works and how it connects to Markov Chains. The steady-state vector would correspond to where a web surfer would end up in the long term, and this seems like a reasonable way to assign value/ranking to web pages.

Note the term "PageRank" comes from the name of Larry Page, one of the founders of Google, not because it's related to web pages.

Part a: Based on the code solution (Google_PageRank.mlx (MATLAB Live Script 147kB Oct29 24)) where the steady-state vector is found by raising the Google matrix G to some large power, create a simple Google PageRank function in the following structure:

function [steady_state, highest_rank,index] = GooglePageRank(T,n)

• whose inputs are a transition matrix "T" and a number of iterations "n", and
• whose outputs are a "steady-state" vector, the highest rank, and the index of the website with the highest rank (for example, the website P3 has the highest value 0.54 in the steady-state vector. Then the output "highest_rank" is 0.54 and "index" is 3).

Test your function using the network example below where we assume that the internet consists of only six pages.

×

Provenance: Hoa Nguyen, Trinity University
Reuse: This item is in the public domain and maybe reused freely without restriction.

Part b: The steady-state vector of the Google matrix G is a corresponding eigenvector of the dominant eigenvalue "1" of the regular matrix G. Use the Power Method to find this eigenvector instead of raising G to some large power n as done in Part a (If G is a very large matrix, we won't be able to compute such an operation).

Implement a Google PageRank function by using the Power Method to find the "steady-state" vector

• whose inputs are a transition matrix "T" and a number of iterations "n", and
• whose outputs are a "steady-state" vector, the highest rank, and the index of the website with the highest rank (for example, the website P3 has the highest value 0.54 in the steady-state vector. Then the output "highest_rank" is 0.54 and "index" is 3).

The structure of your function is [steady_state, highest_rank, index] = GooglePageRank_PowerMethod(T,n).

Test your function with the same network used in Part a.

Compare the steady state vector in Part (b) with the output from Part a (where you raise G to some large power n).

The above assignments were created for my midterm test (the coding part) when I taught Applied Linear Algebra in Fall 2023. Matlab grader was used for automatic grading and embedded in Canvas. Most students had no problem with understanding my instructions and were able to implement their code with the setting I had in Matlab grader.

Student understanding can be assessed based on their ability to perform the following tasks (after they finish working on the two assignments):

1. Increase the size of an invertible matrix. Students should be able to explain how the computational time of the Power Method increases accordingly.

2. Compare the computational time of the Google PageRank algorithm before and after incorporating the Power Method to find the steady state vector. Students should realize that at some point, the original way of raising the Google matrix G to some large power n won't work when G is large.

To access students' ability and understanding of coding, an instructor can ask each student to record a 5-min video explaining some part of the code/assignment. A clear guide will be needed to help students know what you want them to do. An example is provided in the following file VideoPromptCriteria.docx (Microsoft Word 2007 (.docx) 19kB Oct29 24).

Also, since I use Matlab grader, students will need to pass all the assessments created for each assignment. Below is the description from Matlab grader: "When the learner submits their script for assessment, both the learner solution and the reference solution are run first. Your assessments then evaluate the learner solution."

Since there is not a way for me to directly link to my Matlab graders for these assignments, here is a list of the pdf files of my Matlab graders (MATLAB_Grader_Assignment_1.pdf (Acrobat (PDF) 461kB Oct29 24) for Assignment 1, MATLAB_Grader_Assignment_2_Part_a.pdf (Acrobat (PDF) 543kB Oct29 24) for Assignment 2 - Part a, and MATLAB_Grader_Assignment_2_Part_b.pdf (Acrobat (PDF) 517kB Oct29 24) for Assignment 2 - Part b). You can find all the assessment methods/codes that I set up for each assignment there. The solution codes are also posted: Assignment_1_sol.m (Matlab File 554bytes Oct29 24) for Assignment 1, Assignment_2_Part_a_sol.m (Matlab File 640bytes Oct29 24) for Assignment 2 - Part a, and Assignment_2_Part_b_sol.m (Matlab File 1010bytes Oct29 24) for Assignment 2 - Part b.

For lecture notes and homework assignments, I used an open-source book "Linear Algebra and Applications: An Inquiry-Based Approach" by Feryal Alayont and Steven Schlicker at Grand Valley State University (link)

For grading, I used Matlab grader: https://grader.mathworks.com/