| Previous Lecture | lect12 | Next Lecture |
lect12, Tue 02/18
Eigenvalues, eigenvectors, graphs, and matrices
Reading assignment
For next time, read the rest of “The $25,000,000,000 Eigenvector”.
Outline for this week’s lectures, with references
1) Eigenvalues and eigenvectors (NCM Sections 10.1, 10.2, 10.5; Gil Strang video lecture number 21).
2) Graphs and adjacency matrices (Lecture slides; Wolfram article “adjacency matrix”, but note that for a directed graph each edge (v,w) only makes A[w,v] == 1, and not A[v,w]).
3a) PageRank: The eigenvalue connection ($25B paper Sections 1, 2.1).
3b) PageRank: Modifying the matrix to make it work ($25B paper Sections 2.2, 3.1).
4a) Computing the eigenvector by the power method ($25B paper Section 4).
4b) The power method with a sparse matrix (Homework h06).
Outline of today’s lecture
- Eigenvalues and eigenvectors: definitions.
- Three theorems about an n-by-n real matrix A:
- A has at least one and at most n eigenvalues, and at most n linearly independent eigenvectors.
- The eigenvalues of A and A.T are the same, though the eigenvectors usually aren’t.
- If A is symmetric,
- All the eigenvalues of A are real.
- A has n linearly independent eigenvectors, which can be chosen to be orthogonal.
- Adjacency matrix of a graph
- In our adjacency matrices, edges go from columns to rows. (Some people do it the other way around.)
- indegree and outdegree of a vertex.
- The PageRank problem: which web pages are most important?
- important = lots of pages point to you? (ranking by indegree)
- important = lots of important pages point to you? (sounds like an eigenvector problem)
- numpy/scipy routines:
- np.random.randn()
- spla.eig()
- np.sum()
- np.sort()
- np.argsort()