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.

In [3]:
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);
In [4]:
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.

In [8]:
# generate a random 5×5 Markov matrix
M = rand(5,5)
M = M ./ sum(M,dims=1)
Out[8]:
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
In [10]:
using LinearAlgebra
v₀ = nullspace(M-I) # the λ=1 eigenvector of M
Out[10]:
5×1 Array{Float64,2}:
 0.48267995263276187
 0.5117085776853612
 0.2750657268231593
 0.5517619381863672
 0.35365520545544216
In [13]:
?nullspace; # Remove semicolon to read about nullspace
In [15]:
o = ones(size(v₀)) # the vector of 1's
Out[15]:
5×1 Array{Float64,2}:
 1.0
 1.0
 1.0
 1.0
 1.0
In [16]:
x₀ = randn(size(o)) # a random initial condition
Out[16]:
5×1 Array{Float64,2}:
  0.9961579656010291
  0.789326664976922
 -1.34761306245524
  0.35465418677796384
  0.14231581993833747
In [17]:
t = 100
x = exp((M-I) * t) * x₀  # the solution x(t)
Out[17]:
5×1 Array{Float64,2}:
 0.20747400830226442
 0.219951603782076
 0.11823360091774185
 0.23716804545070677
 0.15201431638621804
In [18]:
sum(x), sum(x₀)   # compare the sums of the components of x(t) and x(0)
Out[18]:
(0.9348415748390071, 0.9348415748390122)
In [ ]:
???? # 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.