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)

$\newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

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.

Solution (there was a mistake in this question) condition g should have been in the assumptions, my apologies, i.e. Let $A : n \times n$ 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 $\alpha$ though.

Here’s a good counter example: $A = \bmat{1 & 0 \\ 0 & 2}$ and the vector $x = \bmat{1 \\ 1}$. The eigenvalues are $1$ and $2$, but $(x^T A x) / (x^T x) = 1.5$.

---

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?

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

---

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.

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 $n$ nodes?

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

---

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$?

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 $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)$ ?

Solution $\det(PA) = \det(LU) = \det(P) \det(A) = \det(L) \det(U)$ and $\det(P) = 1$ and $\det(L) = 1$, so $\det(A) = \det(U)$.

For an upper or lower triangular matrix, $\det(U)$ is just the product of the diagonal elements.

---

Challenge

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

Solution $\lambda_{\max}(A) \le$ maximum degree and $\sqrt{\text{maximum degree}} \le \lambda_{\max}(A)$.