image of a large network

Network & Matrix Computations

David Gleich

Purdue University

Fall 2011

Course number CS 59000-NMC

Tuesdays and Thursday, 10:30am-11:45am

CIVL 2123


In class background quiz (solutions)

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.

Solution (there was a mistake in this question) condition g should have been in the assumptions, my apologies, i.e. Let be real, symmetric. In which case, the Rayleigh-Ritz characterization of largest eigenvalue is:

\lambda_{\max} = \max_{x} \frac{x^T A x}{x^T x}

so that the correct answer is (given g), then (e).

We cannot conclude that there was an eigenvalue equal to though.

Here’s a good counter example: and the vector . The eigenvalues are and , but .


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?

Solution These are the same. BFS is actually more efficient in this case.


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.

Solution As mentioned in class, c) and e) are not required.


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

Solution An empty graph can have connected components of any type.


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 ?

Solution This implies that it’s non-singular, as mentioned in class


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

Solution There is only 1 shortest path.


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

Solution and and , so .

For an upper or lower triangular matrix, is just the product of the diagonal elements.


Challenge

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

Solution maximum degree and .