Eigenranking by power method
in Assignments
(5 pts)
This problem is only 5 points since it's pretty easy but it does bring us rather full circle a bit. Your mission is simple: Reproduce the computation of your eigenvector for the Eigenranking problem using the power method. You can find some simple code implementing the power method for a $2\times2$ matrix in this SageCell linked from our presentation on the power method.
Comments
My matrix from the eigenranking problem is
$
M=
\begin{bmatrix}
0 & 94 & 58 & 77 \\
17 & 0 & 30 & 51 \\
24 & 17 & 0 & 71 \\
35 & 27 & 41 & 0
\end{bmatrix}.$
After importing my data, I used the power method by starting the vector $\langle1,1,1,1\rangle$ and transforming it by the multiplication of $M$ and normalizing the result.
20 iterations was enough to make all the components of $(Mv)\frac{1}{v}$ equal to one another to 6 decimal places, so $v$ has converged to be an eigenvector of $M$.
I also used
numpy.linagl.eig
to compare these results to the original.My matrix was,
$$
\begin{pmatrix}
0 & 54 & 56 & 72 \\
33 & 0 & 27 & 43 \\
55 & 34 & 0 & 50 \\
30 & 13 & 52 & 0
\end{pmatrix}
$$
Once I imported the libraries and defined my matrix, I decided to use a randomly generated vector as the seed;
I arbitrarily chose 100 iterations for the calculation,
Next, I computed the eigenvectors/eigenvalues using the eig() function and extracted the dominate eigenvector/eigenvalue in order to determine the difference between them and my results;
I found the difference by subtracting my results from these values,
As you can see, both methods produce almost identical results.
My matrix was
$M = \left[\begin{matrix}
0 & 46 & 66 & 95 & 60 \\
21 & 0 & 31 & 61 & 65 \\
24 & 34 & 0 & 72 & 35 \\
45 & 17 & 17 & 0 & 34 \\
58 & 13 & 31 & 13 & 0 \\
\end{matrix}\right]$
I imported the following libraries
and input my matrices M and v
To find the vectors and values
which gave
and to compare the values I simply used the code from last time:
which gave
It is easy to see there is significant decimal approximation accuracy utilizing this method, since the outputs of both method share very similar answers.
I used the matrix from my original eigenranking post,
$$M=\begin{pmatrix}
0&39&68&24\\
33&0&54&54\\
48&14&0&45\\
51&23&40&0\end{pmatrix}.$$
using the same index (New York Giants, Philadelphia Eagles, Dallas Cowboys, and Washington Redskins). I reevaluated the teams ranking by using the power method, iterating
$$\mathbf{v_{(k)}}=\frac{M\mathbf{v_{(k-1)}}}{\left|\left|M\mathbf{v_{(k-1)}}\right|\right|}$$
fifty times with a randomly generated $\mathbf{v_{(0)}}$. After ranking the teams with the new eigenvector, I got the same results* as my original post,
*Note: The untrimmed values from both methods are the same within at least 15 decimal places.
I used the same data from the original Eigenranking problem, defined below:
I generated a random vector and multiplied it to $M$ fifty times, normalizing the vector after each iteration.
Finally, I took the absolute value of the eigenvector entries and sorted them to achieve my ranking:
The matrix I had was the following:
$$
A = \left(
\begin{array}{cccc}
0 & 33 & 30 & 14 \\
0 & 0 & 28 & 28 \\
20 & 10 & 0 & 281 \\
5 & 30 & 36 & 0 \\
\end{array}
\right).
$$
I then used the following section of code the determine the normalized eigenvectors and eigenvalue of the system:
This resulted in the following output:
This results were then put into the following section of code to rank the results:
Which gave the following:
Referring to my previous work on this matrix using eig() to determine the eigenvectors, I can see that this results match what I had gotten then:
The ranking ends up identical through both approaches and the primary difference is seeming the number of decimal places generated.
We are given the following matrix:
$$ A =\begin{pmatrix}
0 & 51 & 68 & 75 \\
20 & 0 & 38 & 39 \\
60 & 51 & 0 & 43 \\
33 & 46 & 43 & 0
\end{pmatrix}.$$
Implementing the power method, we find our dominant eigenvalue and eigenvector:
Next we can use similar code that was used to originally rank the division:
Checking the original rankings we calculated, we see that these answers are identical.
My matrix was
$M=
\begin{bmatrix}
0 & 34 & 55 & 68 \\
33 & 0 & 34 & 38 \\
13 & 20 & 0 & 45 \\
51 & 44 & 19 & 0
\end{bmatrix}$
The power method is to take $<1,1,1,1>$ and multiply it by M, than normalizing, than iterating that process x, amount of times till all entries of are new ket vector are the samish. That result is are dominant eigenvalue and the dominant eigenvalue can be found by taking that by its norm. The cut and dry code and comparing the power method to the "standard" method can be found below:
My matrix from the eigenranking problem was
$$
M =
\begin{bmatrix}
0 & 47 & 44 & 38\\
52 & 0 & 20 & 23\\
38 & 61 & 0 & 28\\
65 & 73 & 56 & 0
\end{bmatrix}.
$$
Using python to implement the power method, I noticed that the dominant eigenvector converged surprisingly early on.
After only 1 iteration the power method yielded a vector with the same ranking order
and after 10 iterations the vector was accurate to 4 digits, even 5 for the larger elements.
Since the vector found using the power method is so close to the true eigenvector, it must yield the same team ranking. Just to be sure, here are the results after a total of 50 iterations
@dan I think you've got a little error in your code where you tried to do your loop. In short, whitespace is significant in Python.
This is an effective loop
This is not an effective loop