Description
THEORY PROBLEMS
Problem 3.1 (Practice computing eigenvalues and eigenvectors)
In this problem you consider the eigenvalues and eigenvectors of each of the following four matrices:
(a) A =
”
3 1
2 2 #
, (b) A =
”
0 1
1 0 #
, (c) A =
”
0 1
−1 0 #
, (d) A =
1 0 0
1 1 1
0 0 1
.
For each of the matrices in parts (a)-(d) do the following:
(i) compute the eigenvalues of the matrix,
(ii) compute the eigenvectors of the matrix,
(iii) specify both the algebraic and geometric multiplicity of each distinct eigenvalue, and
(iv) if the matrix is diagonalizable express the matrix in its diagonalized form. In other words, if
A is diagonalizable express it as A = V ΛV
−1 where V is the matrix of eigenvectors and Λ is
a diagonal matrix of eigenvalues. Specify V and Λ for each matrix that is diagonalizable.
Problem 3.2 (Eigenvectors of a symmetric 2 × 2 matrix)
OptM Problem 4.1.
Problem 3.3 (Function approximation), from a previous exam
In this problem you consider the function f : R
2 → R defined pointwise as
f(x) = −
√
x1x2
where domf = {(x1, x2)|x1 > 0, x2 > 0} = R
2
++, i.e., the interior of the first quadrant. This
problem concerns first-order and second-order approximations of the function f.
(a) Denote by ˆf1 the first-order (affine) approximation of f when the approximation is centered
at some point x
(0) ∈ domf. Say you center the approximation at x
(0) = (4, 1) and you want
ˆf1((6, 3)), the first-order approximation at the point x = (6, 3). What is ˆf1((6, 3))? (Make
sure to show your work developing the approximation and then evaluate it for the specified
parameters.)
(b) Denote by ˆf2 the second-order approximation of f when the approximation is centered at
some point x
(0) ∈ domf. Say you center the approximation at x
(0) = (4, 1) and you want
ˆf2((6, 3)), the second-order approximation at the point x = (6, 3). What is ˆf2((6, 3))? (Make
sure to show your work developing the approximation and then evaluate it for the specified
parameters.)
(c) True or false: The Hessian ∇2f(x
(0)) is positive semi definite (PSD) at all points x
(0) ∈
domf.
Please note: If you answer “true” you must provide a proof. If you answer “false” you must
provide a counterexample. Providing a counterexample means you specific a point x
(0) ∈ R
2
and show that ∇2f(x
(0)) is not PSD. No credit is given for guessing. A “guess” is an answer
provided without justification.
Hint: In class we have seen multiple ways to test for positive definiteness. For this problem
some tests are easier to use than others.
Part (d) concerns lines. Recall the definition of a line. A line L ⊆ R
n
can be specified by a point
x
(0) ∈ R
n and a direction v ∈ R
n
, which we assume is normalized so kvk2 = 1. The line is the set
L = {x|x = x
(0) + tv, t ∈ R}. In this problem n = 2 so x
(0) ∈ R
2 and v ∈ R
2
.
(d) Find a point x
(0) ∈ domf and a direction v, kvk2 = 1, such that when both approximations,
ˆf1 and ˆf2, are centered at x
(0) the two approximations agree along the line L = {x|x =
x
(0) + tv, t ∈ R}. What is your pair (x
(0), v)?
Problem 3.4 (Symmetry across lines), from a previous exam
In this problem we consider the operation of finding the point symmetric to a given point in R
n
about some line L. Recall the definition of a line. A line L ⊆ R
n
can be specified by a point
x
(0) ∈ R
n and a direction v ∈ R
n
, which we assume is normalized so kvk2 = 1. The line is the set
L = {x|x = x
(0) + tv, t ∈ R}.
For any point x ∈ R
n
there is a point f(x) symmetric to x about the line. This point is defined as
f(x) = x + 2(p(x) − x) = 2p(x) − x where p(x) is the projection of x onto L, i.e.,
p(x) = arg min
p∈L
kp − xk2.
See Figure 1 for an illustration. Note almost all parts of this problem can be solved independently
of the other parts.
(a) Show that, for any x, f can be expressed as the map f(x) = Ax + b where A = 2P − I,
b = 2(I − P)x
(0), and P = vv
T
, where (x
(0)
, v) are given and define the line L.
(b) What is the geometric interpretation of the vector b?
(c) Show the mapping f is linear if and only if the line passes through the origin 0 ∈ R
n
.
(d) Show that f(f(x)) = x for every x ∈ R
n
. What is the geometric meaning of this?
(e) Show that A is symmetric and find its spectral decomposition. In particular, define {u
(2), u(3), . . . , u(n)}
to be an orthonormal basis for the subspace orthogonal to the v vector defined in part (a).
Show that the orthogonal matrix U = [v u
(2) . . . u(n)
] contains the eigenvectors of A where,
again, v is as per part (a). State your spectral decomposition in terms of U.
L
v
x
0
x
(0)
p(x)
f(x)
Figure 1: The point f(x) is symmetric to the point x about the line L defined by (x
(0)
, v).
(f) Consider the spectral decomposition of A you found in part (e). Explain the structure you
observe in the eigenvalue/vector pairs in terms of the geometry of the problem of finding
the point symmetric to a given point about the line L. Your explanation must connect
the structure to the problem. This is not a generic question about the interpretation of
eigenvalues/vectors.
Problem 3.5 (A lower bound on the rank)
OptM Problem 4.9 parts 1 and 2 only (not part 3).
Problem 3.6 (Ellipses, eigenvalues, eigenvectors, and volume)
Make neat and clearly-labelled sketches (i.e., draw by hand) of the ellipsoid E = {x|(x−xc)
TP
−1
(x−
xc) = 1} for the following sets of parameters:
(a) Center xc = [0 0]T and P = [1.5 − 0.5; −0.5 1.5].
(b) Center xc = [1 − 2]T and P = [3 0; 0 1].
(c) Center xc = [−2 1]T and P = [9 − 2; −2 6].
For each part (a)–(c) also compute each pair of eigenvalues and corresponding eigenvectors.
(d) Recall the geometrically meaningful property of the determinant of a square real matrix A:
its magnitude | det A| is equal to the volume of the parallelepiped P formed by applying A to
the unit cube C = {x| 0 ≤ xi ≤ 1, i ∈ [n]}. In other words, if P = {Ax|x ∈ C} then | det(A)|
is equal to the volume of P. Furthermore, recall that the determinant of a matrix is zero
if any of its eigenvalues are zero. Explain how to interpret this latter fact in terms of the
interpretation of | det(A)| as the volume of P. (This interpretation was mentioned in class so
this is just a “I want to make sure you understand that comment” type of question.)
APPLICATION PROBLEMS
Problem 3.7 (Second-order approximation of functions)
In this exercise you extend your code from the problem “First-order approximation of functions” to
second order. (As before you are welcome to use Matlab or Python or the software of your choice.)
The objective is, as before, to write code to plot approximations each of (the same) three functions
fi
: R
2 → R, i ∈ [3], but now the approximation is quadratic rather than linear. To recall, the
three functions are defined pointwise as
f1(x, y) = 2x + 3y + 1,
f2(x, y) = x
2 + y
2 − xy − 5,
f3(x, y) = (x − 5) cos(y − 5) − (y − 5) sin(x − 5).
For each of the above function, do the following.
(a) Write down the gradient and Hessian with respect to x and y in closed form. To recall the
gradient and Hessian are compactly denoted as ∇fi and ∇2fi for i ∈ [3] where
∇fi =
” ∂fi
∂x
∂fi
∂y #
∇2
fi =
∂
2fi
∂
2x
∂
2fi
∂x∂y
∂
2fi
∂y∂x
∂
2fi
∂
2y
.
(b) For each function produce do the following two things. First, produce a 2-D contour plot
indicating the level sets of each function in the range −2 ≤ x, y ≤ 3.5 and plot the direction of the gradient and tanget to the level set at the point (x,y) = 1,0). (Note, you have
already produced these plots in the previous problem, we are just reproducing them here to
help with visualization). Second, For the same point (x, y) = (1, 0) plot the 3-D quadratic
approximation of the function.
(c) Now, repeat the previous plot for point (x, y) = (−0.7, 2) and (x, y) = (2.5, −1).
(d) Comment on where your approximations are accurate and where they are not (if anywhere)
for the three functions. Discuss what the reason is behind your observations.
Note: We recommend you design these plotting scripts as Matlab functions so that you can reuse
them for to plot approximations for different non-linear functions (or for theses functions at different
points). In either case make sure to attach your code.
Problem 3.8 (Google’s PageRank algorithm)
In this problem you will implement and analyse approaches to the eigenvector computation that is
at the heart of Google’s PageRank algorithm (cf. discussion in Example 7.1 of OptM). Download
pagerank urls.txt and pagerank adj.mat files from the course website. The first is a plain text
file in which each line consists of a URL of a web page. We refer to the web pages by their
respective URL-line numbers starting from 1. For example, web page 9 is the page that the URL
in line 9 points to. The URLs are of the internal web pages of Hollins University in Roanoke,
Virginia. The provided data files consist of a modified version of web crawling data downloaded
from https://www.limfinity.com/ir. The original dataset has been created in January, 2004
therefore you might notice that some of the links are inactive.
Let N be the number of URLs (therefore the number of web pages) in the first file and i, j ∈ [N].
Execute the command load ‘pagerank adj.mat’ in MATLAB to load the content of the second
file into your MATLAB workspace. You will see that a new N × N variable J has been imported.
This variable represents an adjacency matrix J ∈ {0, 1}
N×N which describes the relationships
between the web pages. Specifically, the element in ith row and jth column Ji,j = 1 if there exists
a link from web page j to web page i, and Ji,j = 0 otherwise. Data have been carefully filtered so
that Jj,j = 0 and PN
i=1 Ji,j > 0 for all j ∈ [N]. In other words, we do not allow links from a web
page to itself, and we do not allow for dangling pages, that is pages with no outgoing links.
Use J to obtain the link matrix A where
Ai,j =
Ji,j
PN
k=1 Jk,j
.
Also, let x ∈ R
N be a vector with all entries equal to 1. Use the matrix A and the vector x the
same way as described in Example 7.1 to solve the following.
(a) Verify that each column in the provided matrix A sum to 1. What is the importance of this
property for the Google PageRank algorithm?
(b) In the following we are consistent with the notation used in OptM. Let x(k + 1) be the
approximation of the eigenvector in the k + 1th iteration. We define the approximation error
in the k + 1th iteration as e(k + 1) = kAx(k + 1) − x(k + 1)k2. Using MATLAB, implement
the power iteration algorithm described in Section 7.1.1 in OptM. Run the algorithm for 10
iterations and plot log(e(k + 1)) versus k.
(c) Implement the shift-invert power iteration and Rayleigh quotient iteration algorithms presented in Sections 7.1.2 and 7.1.3 of OptM. For the shift-invert power method use σ = 0.99.
In the Rayleigh quotient iteration method, use σ1 = σ2 = 0.99 for the first two iterations and
σk =
x
∗(k)Ax(k)
x∗(k)x(k)
for k > 2, in a similar manner as the discussion in Example 7.1. Repeat your
experiment of part (b) for these two algorithms. Plot log(e(k + 1)) for each of your three
algorithms on a single plot. Check whether your results are consistent with Example 7.1.
Include your MATLAB code with the answers.
(d) List the (page index, PageRank score) pairs of the top 5 and bottom 5 pages according to
your PageRank scores. Compare them with the provided web page links and briefly explain
whether the ranking seem intuitively correct.
(Note: While we write “MATLAB” in the above you are, as usual, welcome to use any software
you would like to, just not to use built-in functions that accomplish the objective.)
OPTIONAL PROBLEMS
Problem 3.9 (Eigenvectors and diagonalizing circulant matrices)
A square matrix A is “circulant” if
A =
a0 aN−1 aN−2 aN−3 . . . a1
a1 a0 aN−1 aN−2 . . . a2
a2 a1 a0 aN−1 . . . a3
a3 a2 a1 a0 . . . a4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
aN−1 aN−2 aN−3 aN−4 . . . a0
. (1)
In other words each column is a circularly-shifted version of the column to its left, where the shift
is downwards by one.
The (ij)th entry of the square N-dimensional Fourier matrix is defined as
[F]ij =
1
√
N
e
j
2π
N
(i−1)(j−1)
.
The relationship between a length-N vector x and its length-N discrete-time Fourier series (DTFS)
x˜ is given by
x˜ = F
Hx and x = Fx, ˜
where F
H is the Hermitian-transpose of F. That is, [F
H]ij = [F]
∗
ji where (·)
∗ denotes the complexconjugate of the scalar argument.
In this problem you prove that the Fourier matrix diagonalizes all circulant matrices.
(a) Denote the DTFS of the vector a = [a0 a1 . . . aN−1]
T as ˜a = [˜a0 a˜1 . . . a˜N−1]
T
. Define the
matrix A˜ as
A˜ = F
HA.
Write out the matrix A˜ in terms of {a˜0, a˜1, . . . a˜N−1} (or in terms of ˜a).
Hint: The first column of A˜ is simply given by ˜a = F
Ha. To find the second (and other)
column(s) it helps (though is not necessary) to recall some Fourier properties.
(b) Using the matrix A˜ from above, compute the matrix product B where
B = F
HAF = AF˜ .
(c) What are the eigenvalues of A? What are its eigenvectors?
