Linear Algebra Stuff

Question 1

Sum of eigenvalues are equal to the sum of the diagonals

Question 2

Adj matrix is:

Answer 2

PxP matrix, where entry is 1 if i,j connected. So first row is v.0, with 1s in the columns where it is conn. to those vertices.

Question 3

permutation matrix:

Answer 3

is a matrix with single 1’s in each column and each row

Question 4

For 2 labellings giving A, A’ adj. matrices,

Answer 4

A = P^T A’ P (p permutes onto A, P unpermutes)

Question 5

Thm/ Let V(G) = {v.1,v.2,…v.p}. The (i, j)th entry of A^n is the number of v.i-v.j walks of length n

Question 6

Defn/ Diameter d(G) is

Answer 6

is a maximum value of d(v.i,v.j), i.e. the longest shortest-path

Question 7

Thm/ If G connected, K = # of distinct eigenvalues of A, K >=d(G)

Question 8

Defn/ the min. polynomial P of a matrix is smallist poly s.t. P(A) = 0

Question 9

Lemma/ Let A be adj. matrix. If d(v.i, v.j) = m for any i,j, then I, A, A^2,…A^m are linearly independent

Question 10

Thm/ L = D-A has the following properties (D is 1 along diagonals),

Answer 10

1. If G has components G,…,G.n then,
   entry u.j,^(k) is 1 if v.j in G.k
2. For u in Reals^P, Lu*u = (1/2)[v.iv.j]SUM(u.i-u.j)^2
3. Other eigenvalues of L are positive
4. [i=1,..p]SUM(lambda.i) = 2q

Question 11

Thm/ (Spanning Tree) The number of spanning trees in a graph is (lam.1lam.2…*lam.p-1)/p, where graph Laplacian has pos eigenvals

Question 12

What is the google pageRank weighting?

Answer 12

You get a matrix M where each row i is a vert, and each col entry is nonzero if that other vert v.j points into v.i, specifically it is 1/n.j, so 1 divided by the outdegree of v.j pointing into v.i.
Then, the largest eigenvalue’s eigenvec scaled to sum to 1 is the page ranking.

Question 13

If M positive, stochastic, then the dim(V.1) = 1, where V.1 is eigenspace spanned by eigenvectors with eigenval 1, aka there’s only 1 of them

Question 14

Defn/ a matrix is stochastic or substochastic IF,

Answer 14

stochastic - if entries are non-negative and col. sum to 1,
substoch. if non negative, col sums to less than 1

Question 15

How to find eigenvalues of a matrix:

Answer 15

Det|A-lambda*I|=0, solve for lambda.