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

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 $A : n \times n$ and real and let a vector $x$ exist with $(x^T A x) / (x^T x) = \alpha$. Does this imply:

a) $A$ is non-singular

b) All eigenvalues of $A$ are larger than or equal to $\alpha$

c) All eigenvalues of $A$ are smaller than or equal to $\alpha$

d) $A$ is positive definite

e) $A$ has an eigenvalue at least as large as $\alpha$

f) $A$ has an eigenvalue at most as large as $\alpha$

g) $A$ is symmetric

h) $x$ is an eigenvector of $A$ with eigenvalue $\alpha$

Briefly justify your answer.

 

 

 

---

Let $G=(V,E)$ be an undirected graph with a unit weight. Let $x$ be a vertex.

What is the relationship between the breadth first search distance from $x$ 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 $A$ and $B$ be real matrices.

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

a) $\| A \| = 0$ implies that $A = 0$

b) $\| A x \| \le \| A \| \|x \|$

c) $\| A + B \| \le \| A \| + \| B \|$

d) $\| \alpha A \| = | \alpha | \| A \|$

e) $\| A B \| \le \| A \| \| B ||$

Briefly justify your answer.

---

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

---

Let $A$ be a real-valued matrix, and let $x$ and $b$ be compatible vectors.
Suppose that $x$ where $Ax=b$ is uniquely defined for all $b$. What does this imply about $A$?

---

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

---

Let $A$ be an $n \times n$ real matrix.
Suppose that $PA = LU$ is an LU-factorization of $A$, where $L$ has a unit-diagonal. Does this help compute: $\det(A)$ ?

---

Challenge

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