Your name:

Please answer the following questions. You may not use any outside references or technology. Justify and explain all answers. This quiz is for my own evaluation of your background, so that I can provide better instruction in the course.

If you don’t recognize a term or idea, please circle it and explain your best guess.

Let and real and let a vector exist with . Does this imply:

a) is non-singular

b) All eigenvalues of are larger than or equal to

c) All eigenvalues of are smaller than or equal to

d) is positive definite

e) has an eigenvalue at least as large as

f) has an eigenvalue at most as large as

g) is symmetric

h) is an eigenvector of with eigenvalue

Briefly justify your answer.

Let be an undirected graph with a unit weight. Let be a vertex.

What is the relationship between the breadth first search distance from to all other nodes in the graph – computed with a BFS algorithm – and the set of shortest paths to all other nodes in the graph – computed via Dijkstra’s algorithm?

Let and be real matrices.

Which of the following is not a required property of a matrix norm (there can be more than one):

a) implies that

b)

c)

d)

e)

Briefly justify your answer.

What is the maximum number of connected components, strongly connected components, or weakly connected components in an graph with nodes?

Let be a real-valued matrix, and let and be compatible vectors.

Suppose that where is uniquely defined for all . What does this imply about ?

How many shortest paths are there between a pair of nodes in a tree?

Let be an real matrix.

Suppose that is an LU-factorization of , where has a unit-diagonal. Does this help compute: ?

**Challenge**

Let be a simple, undirected network. Provide the best bound you can on the largest eigenvalue of the adjacency matrix of .