Pset 8: Due Thursday April 30
(1.) (a) Find the eigenvalues and eigenvectors of$$ A = \begin{pmatrix} 1 & 4 \\ 2 & 3 \end{pmatrix}, \qquad A + 2I = \begin{pmatrix} 3 & 4 \\ 2 & 5 \end{pmatrix} $$
(b) If $Ax=\lambda x$, then what is $(A+\alpha I)x$? Therefore, how are the eigenvalues and eigenvectors of $A+\alpha I$ related to those of $A$? Is this consistent with your answer from (a)?
(2) (From Strang, section 6.1, problem 11.)
Here is a strange fact about 2×2 matrices with eigenvalues $\lambda_1 \ne \lambda_2$: the columns of $A - \lambda_1 I$ are multiples of the eigenvector $x_2$. Why?
(Hint: think about the column and null spaces of $A - \lambda_1 I$.)
(3) (Based on Strang, section 6.2, problem 9.)
Suppose we form the sequence
$$ g_0,g_1,g_2,g_3,\ldots = 0, 1, \frac{1}{2}, \frac{3}{4}, \frac{5}{8}, \frac{11}{16}, \frac{21}{32}, \frac{43}{64}, \frac{85}{128}, \frac{171}{256}, \frac{341}{512}, \frac{683}{1024}, \frac{1365}{2048}, \frac{2731}{4096}, \frac{5461}{8192}, \frac{10923}{16384}, \frac{21845}{32768}, \ldots $$by the rule that $g_{k+2} = \frac{g_{k+1} + g_k}{2}$: each number is the average of the previous two.
(a) If we define $x_k = \begin{pmatrix} g_{k+1} \\ g_k \end{pmatrix}$, then write the rule for the sequence in matrix form: $x_{k+1} = A x_k$. What is $A$?
(b) Find the eigenvalues and eigenvectors of A.
(c) The eigenvalues immediately tell which of these three possibilities: the sequence blows up, decays, or goes to a constant as $n\to\infty$? Does this behavior depend on the starting vector $x_0$?
(d) Find the limit as $n\to\infty$ of $A^n$ from the diagonalization of $A$.
(e) If $g_0 = 0$ and $g_1 = 1$, i.e. $x_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$, then show that the sequence approaches 2/3.
(f) With $g_0 = 0$ and $g_1 = 1$ as in the previous part, how fast does $g_n - 2/3$ go to zero? In particular, what should $\frac{g_{n+1} - 2/3}{g_n - 2/3}$ approach for large $n$? Optionally heck your answer by the using the following Julia code, which numerically computes the sequence.
function gsequence(n)
g = [0.0, 1.0]
for i = 3:n
push!(g, (g[end]+g[end-1])/2)
end
return g
end
gsequence(25);
gsequence(25) .- 2/3;
(4) If $M$ is an $m\times m$ Markov matrix with positive entries, consider the system of ODEs$$\frac{dx}{dt} = (M-I)x$$.
(a) Explain why the sum of the components of $x(t)$ is "conserved": that is, $o^T x(t)$ is the same number for all $t$, where $o$ is the vector of $m$ 1's.
(b) What do the eigenvalues of $M$ (positive Markov: one λ=1 eigenvalue and the remainder have $|\lambda|\lt 1$) tell you about the solution $x(t)$ for large $t$? Does it blow up, oscillate, decay to zero, or … ?
(c) Given the initial condition $x(0)$, give a formula for the solution $x(\infty) = \lim_{t\to\infty} x(t)$ in terms of $x(0)$, $o$, and the "steady-state" eigenvector $v_0$ ($M v_0 = v_0$) of $M$.
(d) Optionally Check your answers to (a) and (c) by using the following Julia code to generate a random 5×5 positive Markov matrix, a random initial condition, and evaluating $x(t)=e^{(M-I)t} x(0)$ via exp((M-I)t)x₀ for one or more values of t in Julia.
# generate a random 5×5 Markov matrix
M = rand(5,5)
M = M ./ sum(M,dims=1)
5×5 Array{Float64,2}: 0.312681 0.106057 0.310267 0.31472 0.0522849 0.219626 0.228889 0.223043 0.16869 0.379316 0.194814 0.188103 0.048816 0.090204 0.0610204 0.0699395 0.164298 0.282433 0.393264 0.39376 0.20294 0.312653 0.135441 0.0331224 0.113618
using LinearAlgebra
v₀ = nullspace(M-I) # the λ=1 eigenvector of M
5×1 Array{Float64,2}: 0.48267995263276187 0.5117085776853612 0.2750657268231593 0.5517619381863672 0.35365520545544216
?nullspace; # Remove semicolon to read about nullspace
o = ones(size(v₀)) # the vector of 1's
5×1 Array{Float64,2}: 1.0 1.0 1.0 1.0 1.0
x₀ = randn(size(o)) # a random initial condition
5×1 Array{Float64,2}: 0.9961579656010291 0.789326664976922 -1.34761306245524 0.35465418677796384 0.14231581993833747
t = 100
x = exp((M-I) * t) * x₀ # the solution x(t)
5×1 Array{Float64,2}: 0.20747400830226442 0.219951603782076 0.11823360091774185 0.23716804545070677 0.15201431638621804
sum(x), sum(x₀) # compare the sums of the components of x(t) and x(0)
(0.9348415748390071, 0.9348415748390122)
???? # enter your formula from (c) and compare it to x
(5) Construct for every n=2,3,... a non-zero matrix A that has all eigenvalues 0, but has (n-1) singular values 1. Is A diagonalizible? (Possible Hint: Permuting the rows or columns of a matrix does not influence the singular values.)
(6) Find two matrices (or argue that is impossible) for which $AB-BA=I$.
(7) Use the full svd to derive the so called "polar factorization" of a matrix: Every square matrix $A$ can be factored into $QS$ where $Q$ is orthogonal and $S$ is positive semi-definite. If $A$ is invertible further show $S$ is positive definite. (Hint: if $A=U\Sigma V^T$, the orthogonal matrix $Q$ will be $UV^T$. What do we need to complete the story.) (Hint: if you don't yet see the answer, the polar decomposition is on page 394 of Strang.)
(8) Suppose $x\in R^n$ is constant and $A$ is nxn variable. Find the gradient $\nabla_A$ of sum( sin.(Ax) ). The answer can be expressed as an nxn matrix or a linear transformation.